Dots and boxes solving algorithm

Question

I'm currently working on a "dots and boxes" program where the input is automatically generated by a computer, and our output is what move we'll make. I'll be competing against another player (their algorithm).

I'm representing the dots and boxes board as a matrix in Python. Winning the game is top priority: algorithm efficiency is not that important.

Is there a best, not complex algorithm for automatically figuring out what move we should make, given a board?

P.S. - You don't need to give me anything in code if you want...English algorithms are perfectly acceptable.

Answer 1

I think that minimax is not the best choice of algorithm for dots-and-boxes. For the full story about this game you really need to read the book The Dots and Boxes Game: Sophisticated Child's Play by Elwyn R. Berlekamp, but I'll give you a brief summary here.

Berlekamp makes a number of powerful observations. The first is the double-cross strategy, which I assume you know about (it's described in the Wikipedia page on the game).

The second is the parity rule for long chains. This follows from three facts about the majority of well-played games:

1. The long chains will be played out at the very end of the game.
2. There will be a double cross in every chain except the last one.
3. The player who first has to play in any long chain loses the game.

plus the constraint that the number of dots you start with, plus the number of double-crosses, equals the number of turns in the game. So if there are sixteen dots to start with, and there is one double-cross, there will be seventeen turns. (And in the majority of games, this means that the first player will win.)

This simplifies the analysis of mid-game positions enormously. For example, consider this position with 16 dots and 11 moves played (problem 3.3 from Berlekamp's book). What's the best move here?

Well, if there are two long chains, there will be one double cross, the game will end after another six moves (16 + 1 = 11 + 6), and the player to move will lose. But if there is only one long chain, there will be no double cross and the game will end after another five moves (16 + 0 = 11 + 5) and the player to move will win. So how can the player to move ensure that there is only one long chain? The only winning move sacrifices two boxes:

Minimax would have found this move but with a lot more work.

The third and most powerful observation is that dots and boxes is an impartial game: the available moves are the same regardless of whose turn it is to play, and in typical positions that arise in the course of play (that is, ones containing long chains of boxes) it's also a normal game: the last player to move wins. The combination of these properties means that positions can be analyzed statically using Sprague–Grundy theory.

Here's an example of how powerful this approach is, using figure 25 from Berlekamp's book.

There are 33 possible moves in this position, and a well-played game lasts for around 20 more moves, so I'd be surprised if it were feasible for minimax to complete its analysis in a reasonable time. But the position has a long chain (the chain of six squares in the top half) so it can be analyzed statically. The position divides into three pieces whose values are nimbers:

These nimbers can be computed by dynamic programming in time O(2ⁿ) for a position with n moves remaining, and you will probably want to cache the results for many common small positions anyway.

Nimbers add using exclusive or: *1 + *4 + *2 = *7. So the only winning move (a move that reduces the nim-sum to *0) is to change *4 to *3 (so that the positions sum is *1 + *3 + *2 = *0). Any of the three dotted red moves is winning:

---

Edited to add: I'm aware that this summary doesn't really constitute an algorithm as such, and leaves lots of questions unanswered. For some of the answers you can read Berlekamp's book. But there's a bit of a gap when it comes to the opening: chain counting and Sprague–Grundy theory are really only practical in the mid- and endgame. For the opening you'll need to try something new: if it were me I'd be tempted to try Monte Carlo tree search up to the point where the chains can be counted. This technique worked wonders for the game of Go and might be productive here too.

Answer 2

I think Gareth's answer above is excellent but just to add (I don't have any reputation to add comments) that Dots and boxes has been shown (at least with a sketch) to be np-hard according to this: arxiv.org/pdf/cs/0106019v2.pdf

I wrote a javascript version of dots and boxes that tries to incorporate the strategies mentioned above dotsandboxes.org. It's not the best one available (doesn't yet incorporate all techniques that Gareth mentions) but the graphics are nice and it beats most humans and other implementations :) Feel free to have a look at the code and there are some other links to other people's version of the game you can train yours on.