Optimal play for 2 by 2 dots and boxes

Question

Consider the classic pencil and paper game Dots and Boxes . You can assume the 2 by 2 version (that is with 9 dots).

Starting with an empty grid of dots, players take turns, adding a single horizontal or vertical line between two unjoined adjacent dots. A player who completes the fourth side of a 1×1 box earns one point and takes another turn. (The points are typically recorded by placing in the box an identifying mark of the player, such as an initial). The game ends when no more lines can be placed. The winner of the game is the player with the most points.

Note that there are at most 12 moves in the entire game and I think there will be between 9 and 11 turns.

The puzzle is to determine if the game is a win, lose or draw for the first player assuming optimal play by both sides.

Clearly you could brute force it by computer, which is fine and perfectly interesting, but not as interesting as a human understandable proof.

Answer 1

Going first, you should be able to force a win.

Using @kaine's terminology:

• box - an area on the board that can be made into a square
• square - a box of 4 lines
• three - a box of three lines which can be made into a square on the next turn
• safe - a move that doesn't result in a three

Moves are enumerated as follows:

* 1 * 2 *
3   4   5
* 6 * 7 *
8   9  10
*11 * 12*

Winning Boards

Split Board

After 5 moves, the board is split down the middle into 2 1x2 half boards. One half contains 2 connected boxes with no threes and no safe moves, and the other contains 2 separate boxes with no threes and no safe moves. For example, the following boards are split down the middle into left and right half boards. Any move on either board will concede a square or two:

o   o---o      o   o---o      o   o   o      o   o   o
    |              |              |   |          |   |
o---o   o      o---o   o      o---o   o      o---o   o
    |   |          |              |   |          |   
o   o   o      o   o---o      o   o   o      o   o---o

If you can make any of these boards, or rotations/flips of them, you will win.

Note that there are three sections, one with 2 boxes (on the right in these examples), and 2 with 1 box (on the left). Your opponent goes first, and must concede two of these sections to you. Since you will have a choice of which to concede, you never have to concede the right half (with 2 squares). Thus, you will win 3-1 every time.

Corner Board

If a board can be divided in such a way after 6 turns that you are forced to concede a single square, but the other 3 squares are connected and will be conceded to you, then you will win.

Below are some examples of such boards.

o   o   o      o---o---o      o---o---o
|   | c            | c              c |    
o   o---o      o   o   o      o   o   o
|              |              |        
o---o---o      o---o---o      o---o---o

For all three boards, concede the box 'c' in the upper right, and your opponent will be forced to concede the other 3 to you.

Corner Boards have the following properties:

• the corner box has two out of four sides completed
• there are no threes
• the corner box is isolated so that making a square in it does not make a three elsewhere, but results in all boxes having 2 out of three sides completed

General Strategy

The general strategy to be used is as follows:

• If presented with a three, take the square and play again
• If no squares can be taken, play safe
• If you can't play safe, concede a single square

This strategy is used in a number of situations and is referenced simply as "General Strategy" for the following scenarios.

Strategy

On your first move, you must take an outside edge.

Note: If you don't and take one of the lines touching the middle dot, then your opponent can force a draw simply by splitting the board with their first move and then mirroring every move you make on the other half of the board. When you are forced to make a three, he will take the square and make the same three on the other half board. Repeat until the end of the game for a tie.

So, here is an example of taking an outside edge:

o   o---o

o   o   o

o   o   o

Your goal will be to create the split board, but failing that, work towards the corner board. Your opponent can now either take an interior line, or an edge.

Interior line

If your opponent takes an interior line (4/6/7/9), then you can take another interior line 90 degrees to it without setting up a three. Here are the moves you would make based on his move:

4 --> 6
6 --> 4
7 --> 9
9 --> 7

Thus, there are two possible boards (since either 4/6 and 7/9 result in the same board):

 Board 1        Board 2
o   o---o      o   o---o
    |                                  
o---o   o      o   o---o
                   |    
o   o   o      o   o   o

Board 1

Your opponent has a few choices.

• Moves 1/3/5/7: All concede a square, which you take on your first turn, and then make move 11. Proceed with the General Strategy for the win.
• Moves 9/10/12: In one move, you can create a Split Board for a win.
• Move 8/11: Play safe with 10, and he will be forced to either concede a square, or make a Corner Board with move 12. If he concedes, play the General Strategy for the win.

Board 2

There are the following options for your opponent:

• Moves 1/3/6: You can make a Split Board on your next move.
• Moves 4/5/10/12: Take the square and make move 8. General Strategy results in a win.
• Move 8/11: Play safe with move 3. He will be force to make a Corner Board with move 1 or concede a square. General Strategy results in a win either way.

Exterior Line

If your opponent takes an exterior line, then you can try to aim for a Split Board or Corner Board, if available.

Split Board Candidates

The following boards should be attempted to be made into a Split Board.

 Board 1        Board 2        Board 3
o   o   o      o   o---o      o   o---o
        |                               
o   o   o      o   o   o      o   o   o
        |              |               
o   o   o      o   o   o      o   o---o

If the flipping/rotating the board matches any of these, then you can try for a Split Board by attempting to split the board vertically. So, make move 4. To complete the Split Board, your opponent must make either 6 or 9, and when they do, you make the other for the guaranteed victory.

If they make a different move, then your goal is now to make a Corner Board. Here are the break downs for each board above after you make move 4:

Boards 1 and 2

o   o   o      o   o---o
    |   |          |    
o   o   o      o   o   o
        |              | 
o   o   o      o   o   o

The only safe moves (other than 6/9 which can be made into a Split Board) are 1/3/8/11/12.

• Move 2/7: He is conceding the upper right square early. Take it and then play safe with move 11. General Strategy wins the day.
• Move 8/11/12: If you make move 6 (the bottom of the top left corner square) the only remaining safe move is 12 or 11, which makes a Corner Board. If your opponent instead concedes a square, General Strategy wins.
• Move 1/3: Make move 11. Your opponent can now complete the Corner Board by making move 12, or make the only other safe move - move 8. By making move 12 your self, the next move by your opponent will concede all 4 squares to you.

Board 3

o   o---o
    |   
o   o   o

o   o---o

The only safe moves are 1/3/8/10/11.

1. Move 5/7: Similar to the previous case, you can take the square and then force a victory by making move 11 and using the General Strategy.
2. Move 8/11/10: If you make move 6, the only remaining safe move is 10 or 11 which makes a Corner Board. Anything else, and General Strategy will win for you.
3. Move 1/3: Concede the upper right square immediately by making move 7! If your opponent takes the square, they will only have 2 possible safe moves for their second move - 8 or 11. You take the other, and they will be forced to concede the other three squares. Alternatively, your opponent may concede the one of the other squares, so take it, and then make move 11. They will then be forced to concede the other two squares.

Corner Board Candidates

After eliminating the Split Board candidates, and any rotations/flips, the following three boards remain:

o   o---o      o   o---o      o   o---o
        |                              
o   o   o      o   o   o      o   o   o
                              |        
o   o   o      o---o   o      o   o   o

None of these are split board candidates. So, you will aim for a Corner Board instead.

On your move, for the first and second boards, make move 8. For the third, make move 11. All three boards are now rotations/flips of one another, so they are all the same scenario. Thus, without loss of generality, we can use the following board for your opponents move:

o   o---o
        |
o   o   o

o---o   o

Your opponent can either play safe or concede the square.

• Move 4/7: Take the square on your first move of the turn and then make move 8. General Strategy takes over from here.
• Moves 3/8/12: Try to make a Corner Board with the top right corner as the corner box. Thus, you can play move 8 (or 3/12 is 8 is already taken), leaving your opponent move 12 or 3 as the only safe move, which results in a Corner Board. If instead, they concede a square earlier, General Strategy can be used to win.
• Moves 1/10: Make move 8 and the board is now a rotation/flip of the previous case except the corner is the lower left. Flip the board and use the same strategy.
• Move 6/9: Make move 10. The only safe move left is 1 or 3, and if they take it, you have a Corner Board. If they don't use General Strategy to win.

Answer 2

Not as interesting as a manual analysis, but here is a brute-force solver, written in Python. (Warning, CPU intensive for about two minutes)

from collections import defaultdict

VERTICAL, HORIZONTAL = 0, 1

#represents a single line segment that can be drawn on the board.
class Line:
    def __init__(self, x, y, orientation):
        self.x = x
        self.y = y
        self.orientation = orientation
    def __hash__(self):
        return hash((self.x, self.y, self.orientation))
    def __eq__(self, other):
        if not isinstance(other, Line): return False
        return self.x == other.x and self.y == other.y and self.orientation == other.orientation
    def __repr__(self):
        return "Line({}, {}, {})".format(self.x, self.y, "HORIZONTAL" if self.orientation == HORIZONTAL else "VERTICAL")

class State:
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.whose_turn = 0
        self.scores = {0:0, 1:0}
        self.lines = set()
    def copy(self):
        ret = State(self.width, self.height)
        ret.whose_turn = self.whose_turn
        ret.scores = self.scores.copy()
        ret.lines = self.lines.copy()
        return ret
    #iterate through all lines that can be placed on a blank board.
    def iter_all_lines(self):
        #horizontal lines
        for x in range(self.width):
            for y in range(self.height+1):
                yield Line(x, y, HORIZONTAL)
        #vertical lines
        for x in range(self.width+1):
            for y in range(self.height):
                yield Line(x, y, VERTICAL)
    #iterate through all lines that can be placed on this board, 
    #that haven't already been placed.
    def iter_available_lines(self):
        for line in self.iter_all_lines():
            if line not in self.lines:
                yield line

    #returns the number of points that would be earned by a player placing the line.
    def value(self, line):
        assert line not in self.lines
        all_placed = lambda seq: all(l in self.lines for l in seq)
        if line.orientation == HORIZONTAL:
            #lines composing the box above the line
            lines_above = [
                Line(line.x,   line.y+1, HORIZONTAL), #top
                Line(line.x,   line.y,   VERTICAL),   #left
                Line(line.x+1, line.y,   VERTICAL),   #right
            ]
            #lines composing the box below the line
            lines_below = [
                Line(line.x,   line.y-1, HORIZONTAL), #bottom
                Line(line.x,   line.y-1, VERTICAL),   #left
                Line(line.x+1, line.y-1, VERTICAL),   #right
            ]
            return all_placed(lines_above) + all_placed(lines_below)
        else:
            #lines composing the box to the left of the line
            lines_left = [
                Line(line.x-1, line.y+1, HORIZONTAL), #top
                Line(line.x-1, line.y,   HORIZONTAL), #bottom
                Line(line.x-1, line.y,   VERTICAL),   #left
            ]
            #lines composing the box to the right of the line
            lines_right = [
                Line(line.x,   line.y+1, HORIZONTAL), #top
                Line(line.x,   line.y,   HORIZONTAL), #bottom
                Line(line.x+1, line.y,   VERTICAL),   #right
            ]
            return all_placed(lines_left) + all_placed(lines_right)

    def is_game_over(self):
        #the game is over when no more moves can be made.
        return len(list(self.iter_available_lines())) == 0

    #iterates through all possible moves the current player could make.
    #Because scoring a point lets a player go again, a move can consist of a collection of multiple lines.
    def possible_moves(self):
        for line in self.iter_available_lines():
            if self.value(line) > 0:
                #this line would give us an extra turn.
                #so we create a hypothetical future state with this line already placed, and see what other moves can be made.
                future = self.copy()
                future.lines.add(line)
                if future.is_game_over(): 
                    yield [line]
                else:
                    for future_move in future.possible_moves():
                        yield [line] + future_move
            else:
                yield [line]

    def make_move(self, move):
        for line in move:
            self.scores[self.whose_turn] += self.value(line)
            self.lines.add(line)
        self.whose_turn = 1 - self.whose_turn

    def tuple(self):
        return (tuple(self.lines), tuple(self.scores.items()), self.whose_turn)
    def __hash__(self):
        return hash(self.tuple())
    def __eq__(self, other):
        if not isinstance(other, State): return False
        return self.tuple() == other.tuple()

#function decorator which memorizes previously calculated values.
def memoized(fn):
    answers = {}
    def mem_fn(*args):
        if args not in answers:
            answers[args] = fn(*args)
        return answers[args]
    return mem_fn

#finds the best possible move for the current player.
#returns a (move, value) tuple.
@memoized
def get_best_move(state):
    cur_player = state.whose_turn
    next_player = 1 - state.whose_turn
    if state.is_game_over():
        return (None, state.scores[cur_player] - state.scores[next_player])
    best_move = None
    best_score = float("inf")
    #choose the move that gives our opponent the lowest score
    for move in state.possible_moves():
        future = state.copy()
        future.make_move(move)
        _, score = get_best_move(future)
        if score < best_score:
            best_move = move
            best_score = score
    return [best_move, -best_score]

s = State(2,2)
best_move, relative_value = get_best_move(s)
print("The best first move is {}, with {} more points than the second player.".format(best_move, relative_value))

Result:

The best first move is [Line(0, 0, HORIZONTAL)], with 2 more points than the second player.

In English, this means the first player should place his first line horizontally in the lower left corner, and the final score will be 3-1 in his favor.

Interesting Observations

Some trivia I found while writing the above program.

• A full transcription of one possible optimal play:

  Player 0 makes move [Line(0, 0, HORIZONTAL)].
  Player 1 makes move [Line(0, 1, HORIZONTAL)].
  Player 0 makes move [Line(1, 0, HORIZONTAL)].
  Player 1 makes move [Line(1, 1, HORIZONTAL)].
  Player 0 makes move [Line(1, 1, VERTICAL)].
  Player 1 makes move [Line(0, 2, HORIZONTAL)].
  Player 0 makes move [Line(0, 1, VERTICAL), Line(1, 2, HORIZONTAL)].
  Player 1 makes move [Line(2, 1, VERTICAL), Line(0, 0, VERTICAL)].
  Player 0 makes move [Line(1, 0, VERTICAL), Line(2, 0, VERTICAL)].
  

• If the first player chooses an interior line as his first move (a sub-optimal play), the second player can force a tie if he chooses the opposite interior line, and loses 1-3 if he chooses anything else.

Answer 3

The key to perfect play in this game seems to be the number of lines in the center cross at the end of turn 6! Warnig I"ve not taken the time to put my 39 drawings into the computer so this is a map of the complex (largely brute force) proof. This was all done by hand but I figured out which of the 3 out of 4 possible 7 line patterns with no squares or threes forced player 2 to give all the squares to player 1. This made the problem much simpler

squares - the things that earn points Threes - one line is left to make a square

Turn seven study with no Threes or Squares

Turn seven means there are 6 lines on the board and it is player 1's turn. I also assumed no squares or threes.

Case 1: Turn seven starts and there is one or fewer lines in the center cross and no squares or threes. Player 1 can force a win in any circumstance. I proved this with brute force. There are only 15 such truely unique cases due to symetry.

Case 2: Turn seven starts and the two center lines are at right angles to each other but there are no squares or threes. Player 1 can force a win in any circumstance. I proved this with brute force. There are only 3 such truely unique cases due to symetry.

Case 3: Turn seven starts and there are two center lines in the same direction with no squares or threes. Only a draw can be forced. AVOID There are only 7 such unique cases.

It is impossible for there to be three in the center and no threes or squares.

Player 2 playing optimumly, therefore, needs to make a square or three on turn 6 or before! I also need to look for the possible force draw option for Player 2.

Early square study

Player 1 does not want any squares or threes before turn seven so he will not make one on turn three. The earliest possible Three will therefore be on turn four. This will go to Player 1 on turn five. This does not appear to give Player 2 an advantage and can only seem to force the same scenereos as him leaving one Three for turn seven.

Turn seven revisited with Threes or one square

Assume that a Three is a Three and it's orientation does not matter and it is equivalent to a square already owned by that player (leaving an extra line on the board).

If there are more than two threes, they all go to player 1 and, therefore, He will win or draw. If Player 2 wants a win, he can leave at most one three at the end of turn 6. There are 10 such possibilities.

If Player 1 can manage (after receiving his square on turn 7) to not create a three he wins. This is because there will be 8 lines on the board after this turn and there is no way to place 9 such that only one square and no three's are formed.

This is impossible if there are three lines in the center after he makes his square. He can, however, chose in all cases to create the three in such a way that the other player can only get one square.

Conclusion

I've walked through how to show by hand that Player 2 cannot force a win. I have not, however, shown that he cannot force a tie. I've also neglected to include the 39 drawings I made on paper to come to this conclusion. I will include them if I find time to draw them on the computer on another date.

If Player 2 can force a tie this requires him to either give the other player two squares or threes by turn seven or place exactly two parellel lines (and no perpendicular lines) in the center by turn seven. Player 1 should be able to avoid this by placing more lines in the center that don't form three but I've not shown this yet for any series of moves.