Devlogs - Dots and Boxes
Dots and Boxes is a fun and challenging board game. Creating an algorithm to find the best move is a rewarding exercise. While the Minimax algorithm is commonly used for such games, it’s too slow on mobile devices for boards larger than 2x2 or when there are more than 12 possible moves.
To solve this, we built heuristics similar to how expert players think — by creating strategies for different game stages, recognizing patterns, and finding the best move quickly, all within a fraction of a second. In this blog, I'll share the key ideas behind these heuristics and the technical challenges we faced in building them.
Stages
The game of Dots and Boxes can be divided into two stages, based on the type of moves available. These stages are identified by checking if there are any moves that don't give away boxes.
Stage 1
The game is in Stage 1 when there are moves that don’t give away boxes. In this stage, players focus on avoiding giveaways and often build long chains in the process.
Example of Stage 1 - The game position has moves that don't give away boxes.
Stage 2
The game enters Stage 2 when every move gives away boxes. Here, players focus on choosing which chains to open, aiming to give away as few boxes as possible.
Example of Stage 2 - Any move in this game position gives away boxes.
Heuristics for Stage 1
If there are boxes that can be taken, take them.
When no boxes can be taken, score each move based on how well it follows or breaks the long chain rule — both immediately and over the next "k" moves. Choose the move with the highest score. Breaking the rule gives a negative score, with more weight given to the move's immediate impact than to its future effects.
Long chain: A chain consisting of 3 or more boxes.
Long chain rule: If the number of dots on the board is even, the first player should create an even number of long chains, and the second player should aim for an odd number. If the number of dots is odd, the first player should aim for an odd number of long chains, and the second player should aim for an even number. To find out the math behind this rule, check out the book "The Dots and Boxes Game: Sophisticated Child's Play" by Elwyn Berlekamp.
In this example, move 1 has the highest score for the first player(blue) as it creates odd long chains in more scenarios than other moves.
Heurisitics for Stage 2
If a chain of boxes is offered, first check if it can be double-crossed. If it can't be (usually short chains), take all the boxes. If it can be, decide whether to double-cross or not by comparing both options. Evaluate all possible outcomes for the current and remaining chains to see which choice results in the most boxes.
Double-Cross: A move where a player intentionally leaves the last two boxes of a chain (or four in a loop) for the opponent, forcing them to open the next chain.
Short chain: A chain consisting of 2 or fewer boxes.
In this example, the purple player can double-cross chain 1, 2, 3 and take all boxes in chain 4 to win the game 10 to 6.
If a chain must be offered, first check for short chains. If any exist, offer the shortest one in a way that prevents a double-cross. If only long chains are available, offer the one that leads to the highest total box gain. To decide this, evaluate different orders of offering chains, with and without using the double-cross strategy.
In this example, the purple player can draw the game by offering chain 2 first. Offering chain 1 or 3 first would lead to a loss.
Technical Challenges
The following are the interesting technical challenges in implementing the heuristics.
Trace chains on the board
The chains on the board are traced to determine the long chain count or the chain to offer. We implemented this using breadth first search (bfs) on open edges. Each open edge has one or two open boxes. If the open box has one or two open edges, it's part of the chain. If it has a second open edge, then that is used to trace the chain further. The chain ends when we reach a box with more than two open edges or no further open edge to follow.
Double-cross or not
The decision to double-cross or not is made by exploring all possible orders of offering chains, both with and without using the double-cross strategy. We implemented this using a recursive function that generates all such combinations, accounting for turn changes and assuming both players make optimal moves. This helps determine the option that yields the maximum number of boxes.
Loop with a tail
A loop with a tail is a special type of chain that exhibits asymmetry. If opened from the loop side, all boxes can be taken. But if opened from the tail, only the tail is captured, and the loop closes off. Sometimes, two loops can even share a tail.
To decide the best way to open such chains and maximize box gain, we treat the tail as a separate chain. When generating different chain offering orders:
If the whole chain is offered first, the tail is removed from the list.
If the tail is offered first, the whole chain is replaced by just the loop.
Example of a loop with a tail.
Junction boxes and chain merges
Junction box is an anomaly with three or more open edges but taking any of them will give away boxes. When the third open edge is taken, the remaining two chains terminating on the junction box merge. If there are multiple junction boxes on the board, this could create cascading chain merges. This introduces greater complexity and needs additional handling when doing long chain count and determining to double-cross or not.
Example of junction box and chain merge in dots and boxes.