This series of posts demonstrates how to decrease the branching factor in game-tree search for many connection games. The ideas are presented in the framework of Havannah although they apply to a wider class of two-player zero-sum games. This class includes games with the following properties:
the evaluation of every position is an integer number,
after every Augmenter's move the evaluation at most decreases by one,
there is no Zugzwang, that is no situations where a player would benefit from skipping his move.
Let us start with a few definitions.
Definition 1
For the sake of simplicity, let us initially consider subgames of Havannah. Let a subgame mean a simple goal, such as “Connect the White stone at c3 to the west edge; White to move” or “Close any White ring; White to move”. The subgames we will consider below are actually alternatives of a connection goal and of closing any ring.
Definition 2
In Havannah, let the evaluation of a terminal position in a subgame mean the difference between the number of moves that Minimizer and Augmenter [note] have made in the subgame. The twist is that in every Augmenter's turn, he can either make a move or pass. Passes do not count as Augmenter's moves in computing the evaluation.
Let the evaluation of a non-terminal position in a subgame mean the min-max propagation of evaluation up the game tree. Minimizer strives to minimize the evaluation; Augmenter strives to maximize it. Note that the evaluation of a position can be infinite if Augmenter can prevent a successful completion of a subgame.
The subgame is “Connect the White stones at *b3* and *d2*; Black (Augmenter) to move”. The diagram below shows the evaluation of positions in this subgame. Nodes that point upwards represent positions with Augmenter to move; nodes that point downwards represent positions with Minimizer to move. Edges labeled with ε stand for pass; edges labeled with Σ stand for the set of worse moves than their siblings. The diagram has been simplified by observing that:
\* Augmenter's ε move always pays off better to him than any of his Σ moves.
\* The ε-Σ move sequence forms loops in the graph of moves and increases the score so playing Σ after ε never pays off to the Minimizer.
\* The Σ-ε move sequence also forms futile loops in the graph of moves so we can omit it for clarity.
The evaluation of the starting position in the subgame “Connect the White stones at *b3* and *d2*; White (Minimizer) to move” is 1. The evaluation of the starting position in the subgame “Connect the White stones at *b3* and *d2*; Black (Augmenter) to move” is +∞.
The subgame, known in the Hex world as the Ziggurat or the 2-3-4 template, is “Connect the White stone at *d1* to the SE edge; Black (Augmenter) to move”. The evaluation of its starting position is 2. Below are the evaluations of positions that emerge after an initial pass, without Σ moves. The full tree of play, including also *c3* as Black's initial move, is several times bigger so it would be unreadable.
"This series of posts demonstrates how to decrease the branching factor in game-tree search for many connection games. The ideas are presented in the framework of Havannah although they apply to a wider class of two-player zero-sum games."
Including games that have positions with problems that can be broken down in sub-problems, like some territory games too, I presume?
"In Havannah, let the evaluation of a terminal position in a subgame mean the difference between the number of moves that Minimizer and Augmenter have made in the subgame. The twist is that in every Augmenterâs turn, he can either make a move or pass. Passes do not count as Augmenterâs moves in computing the evaluation."
Breaking a position down to locally defined sub-games in which passes are (inherently) allowed is a conceivable approach. Eventually Augmenter cannot pass in every subgame without worsening his position.
The sub-games are defined as 'goals'. I cannot quite understand (being a layman) how one would go about handling the evaluations of a number of sub-games in the context of a final evaluation and an actual move, nor which goals to choose in the first place (though 'close any white ring - white to move' will be among them of course).
So I can't really tell if you're on to something yet, but I hope you are :)
This was just an introduction. The main result is an algorithm to determine which cells are important for a subgame. Thanks to it, the branching factor decreases, as promised in the first post. Stay tuned!
We have no practical method yet to automatically divide a game into subgames. But the algorithm prunes unimportant moves when it is given any goal, even a holistic one: "win the game by any means".
Little Golem
