Algorithm for solving points and boxes

Question

I am currently working on the dots and boxes program, where input is automatically generated by the computer, and our output is what we will do. I will compete with another player (their algorithm).

I represent dots and boxes as a matrix in Python. Winning the game is a top priority: the effectiveness of the algorithm is not so important.

Is there a better and not complicated algorithm for automatically determining what we should do, given the board?

PS - You do not need to give me anything in the code if you want ... English algorithms are quite acceptable.

Answer 1

This game is a zero-sum game , so I would suggest using the min-max algorithm . This algorithm was used by dark blue to win Kasparov in chess.

Create your heuristic function that evaluates each state of the game and uses it as a function to evaluate the min-max algorithm.

You can also improve min-max by using the alpha-beta addiction .

The idea of ​​min-max is to exhaustively search for all possible moves [to a certain depth usually, since the states that you need to go through exponentially in terms of the number of depths] and choose the best step, assuming that your supporter will also do everything possible.

ps

Winning the game is a top priority: the effectiveness of the algorithm is not that important.

They are strongly related to each other, since the more efficient your algorithm, you can check the possible solutions to the best depth, and the greater the chances of winning. Please note that with unlimited time you can explore the entire tree of the game and come up with a winning strategy from each state of the game. However, learning the entire game tree is probably unrealistic.

Answer 2

I think minimax is not the best choice of algorithm for points and boxes. For the full story of this game, you really need to read the book The Points and Boxes Game: Elwyn R. Berlekamp , a complex children's game , but I here You will find a brief description.

Berlekamp makes a series of powerful observations. The first is a double-intersection strategy, which I assume you know about (described on page

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

Minimax would have found this move, but with much more work.

The third and most powerful observation is that the dots and boxes are an impartial game : the available moves are the same no matter what the turn is to play, but in typical positions that arise during the game (i.e. those that contain long chains of boxes ), this is also a normal game : the last player to move wins. The combination of these properties means that positions can be analyzed statically using the Sprague-Grundy theory .

Here is an example of how strong this approach is using Figure 25 from Berlekamp's book.

There are 33 possible steps in this position, and a well-played game lasts about 20 more moves, so I would be surprised if minimax could complete its analysis in a reasonable amount of time. But the position has a long chain (a chain of six squares in the upper half), so it can be analyzed statically. The position is divided into three parts, the values ​​of which are nimbers :

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

Nimmers are added using exclusive or: * 1 + * 4 + * 2 = * 7. Thus, the only winning move (a step that reduces the amount of nim-sum to * 0) is to change * 4 to * 3 (so the sum of the positions is * 1 + * 3 + * 2 = * 0). Any of the three dotted red moves wins:

---

Edited to add: I know that this resume is not really an algorithm as such and leaves many questions unanswered. For some answers, you can read Berlekamp's book. But there is a bit of a gap when it comes to discovery: chain counting and Sprague-Grundy theory are really practical only in the middle and endgame. To discover, you need to try something new: if it were me, I would have a desire to try searching the Monte Carlo tree to the point where the chains can be counted. This technique worked wonders for Go and could also be productive here.

Answer 3

I think Gareth's answer is above, but just add (I don't have a reputation for adding comments) that points and fields were shown (at least with a thumbnail) for np-hard according to this: arxiv.org/pdf/cs /0106019v2.pdf

I wrote a javascript version of points and boxes that try to incorporate the strategies mentioned above by dotsandboxes.org . This is not the best available (it does not yet include all the methods that Gareth mentions), but the graphics are good, and it surpasses most people and other implementations :) Feel free to look at the code, and there are other links to other people versions of the game you can train yours.