dots and boxes game in c#

Question

dots and boxes game in c# with ai algorithm

Rajendra Tripathy · Answer

** Last Weekend I was trying to do similar kind of thing and took reference from stackoverflow So publishing the same answer... Hope it helps you. 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: The long chains will be played out at the very end of the game. There will be a double cross in every chain except the last one. 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 n ) 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: