UsingAIToWinDotsAndBoxes

The game known as Dots and Boxes (Also known as Connect the Dots) is a popular children's game. It is normally played on a 10 x 10 grid of dots (Figure 1), although the number of dots can be changed to allow for a longer or shorter game. Players alternate drawing horizontal and vertical lines between two adjacent dots (Figure 2). If a player completes a box, they get a bonus turn and get to draw an additional line. The player at the end of the game with the most boxes wins. In a game with a 10 x 10 grid, there are 81 possible boxes. The game is clearly adversarial since it is played against an opponent. Since the game map is always available, it is fully observable. There is no randomness making every move deterministic. There are only fixed moves, making it a discrete game.


Figure 1: Grid of 10 x 10 Dots	Figure 2: Two players drawing lines

The game is separated into three main stages. The first stage is 'Free Stage'. There is no real strategy. Players are just trying to fill in lines and are not trying to complete boxes (Figure 3). The second stage is filling in the few remaining lines without letting your opponent score. In this stage there are scoring opportunities (Figure 4). In the third and final stage, every move will result in a score. Since players keep drawing lines until there are no more available boxes to complete, you always have to give your opponent scoring move. This stage is where using artificial intelligence comes into play. By using a minmax search tree, the agent can pick the best move each turn (Figure 5).


Figure 3: Stage I - Lots of Free Moves	Figure 4: Stage II - Only a Few Free Moves

Figure 5: Stage III - Only Scoring Moves

In order to come up with an applicable AI, we must first analyze the map. There are two main methods of analysis. The first is named the Box Score and the second is named Line Score.

The Box Score is determined number of lines touching each box, ranging 0 to 4. If a particular box has a Box Score of 3, a player can draw a line on that particular box and get an additional turn. A player can always draw a free line (a line that will not give their opponent a scoring move) if they can draw a line that is not next to a box with a Box Score of 2. Figure 6 and 7 show games with their Box Score displayed.


Figure 6: Example of Box Score in Stage II	Figure 7: Example of Box Score in Stage III

The Line Score is a method developed for stage III. It determines for each line, how many boxes can the opponent get on the following turn. For example, in Figure 7, if you played the left most vertical line, your opponent would get 18 boxes. Figure 8 and 9 show examples of Line Score. Numbers highlighted in red have a box score of 0. These are free moves.


Figure 8: Example of Line Score in Stage II	Figure 9: Example of Line Score in Stage III

Final Paper: Attach:AlanRosenthal.pdf