Problem 617464 · hard · Level 06 Heuristics & Optimization

Dots and Boxes: Solve the Endgame

minimax · negamax · memoisation · bitmasks · game theory

In dots and boxes, a grid of rows by cols boxes is drawn with dots at the corners. Two players take turns drawing one of the unit lines between neighbouring dots. A player who draws the fourth side of a box claims it (one line can close two boxes at once) and must move again; a move that closes no box passes the turn. The game ends when every line is drawn.

Lines are named by tuples. ("h", r, c) is the horizontal line from dot (r, c) to dot (r, c + 1), for 0 <= r <= rows and 0 <= c < cols. ("v", r, c) is the vertical line from dot (r, c) to dot (r + 1, c), for 0 <= r < rows and 0 <= c <= cols. Box (r, c) has the sides ("h", r, c), ("h", r + 1, c), ("v", r, c) and ("v", r, c + 1).

You are given the lines drawn so far. Boxes that are already complete belong to someone and no longer matter. From now on both players play perfectly, each maximising (their boxes minus the other's boxes) over the boxes still open. Return a tuple (margin, moves): the margin the player to move can force, and the sorted list of all lines whose drawing achieves it. If every line is already drawn, return (0, []).

The helper opening(rows, cols, free, seed) is available: it returns the lines drawn by two careful but short-sighted players, stopping when free lines are left.

Examples

Input:  rows = 1, cols = 1, drawn = []
Output: (-1, [('h', 0, 0), ('h', 1, 0), ('v', 0, 0), ('v', 0, 1)])
Explanation: whoever draws the fourth line wins the box, and that is the second player.

Input:  rows = 1, cols = 2, drawn = [('h', 0, 0), ('h', 1, 0), ('v', 0, 0)]
Output: (2, [('v', 0, 1)])
Explanation: close the left box, then draw one of the three lines left. The opponent must
draw the second, and you close the right box with the third.

Input:  rows = 2, cols = 2, drawn = []
Output: (2, [('h', 0, 0), ('h', 0, 1), ('h', 2, 0), ('h', 2, 1), ('v', 0, 0), ('v', 0, 2), ('v', 1, 0), ('v', 1, 2)])

Constraints

  • 1 <= rows, cols <= 4
  • At most 14 lines are not yet drawn; drawn has no repeats.

Goals

  • Solve a game in which a move can earn the same player another turn
  • Encode a position as a bitmask and memoise on it
  • Report every optimal move, not just the value
Starting Python…