1
$\begingroup$

I am implementing an AI based on the MiniMax algorithm that plays the game Dots and Boxes. I would like to reduce the branching factor of the search tree, by introducing a heuristic rule that limits the number of successor states. However, I am not sure whether there exist any situations, where this rule would exclude the optimal move and make the AI play worse.

In the game 2 players take turns, until one of them captures a box, after which they have to make another move, possibly capturing another box etc. For this purpose, I define successor states of $S$ to be all states, where the opponent gets the move, or the terminal state. If a player made a capture and still has to make another move, then the current state is not yet a successor state of $S$ - the player has to continue making moves until they're unable to.

My rule is as follows:
Assume a player makes a series of captures from a starting state $S$ and ends it with a move $m$, after which the turn goes to the opponent. Then it's always better or at least not worse for the player to have made as many captures as possible before finishing the sequence with $m$.

This means that any state $S$ always has less successors, then there are legal moves. All successors where the player captures $n$ boxes and finishes with move $m$ are discarded, unless $n$ is the maximum number of boxes that can be captured such that $m$ can still be a finishing move. For example, in the following state:
example state
immediately capturing the 4 boxes leads to a loss, while dividing them into 2 small chains, 2 boxes each, with the move (2,2)-(2,3) leads to a victory. The optimal strategy is consistent with the rule, as it would not be possible to finish with the move (2,2)-(2,3), if any of the boxes were captured. The rule excludes all successors, where the player captures 1 or 2 boxes, from being considered.

$\endgroup$
  • $\begingroup$ This seems like a question of pure mathematics to me. (Is Sprague-Grundy theory helpful?) $\endgroup$ – D.W. Jan 23 at 21:57
  • $\begingroup$ @D.W. unfortunately not, since in Dots and Boxes the player who makes the last legal move doesn't necessarily win - instead the player with the most captured boxes wins. $\endgroup$ – ZyTelevan Jan 23 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.