One-sided minimizing-set search: Draft of an approach

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.

*Example 1*

!http://i39.tinypic.com/55l2fp.png!

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.

!http://i39.tinypic.com/9r6n4n.png!

*Example 2*

!http://i40.tinypic.com/2qu0uok.png!

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 +∞.

*Example 3*

!http://i41.tinypic.com/978i74.png!

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.

!http://i42.tinypic.com/x0r8tl.png!

"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".