computer-go: Go4++: Passing in tsume searches.

["Michael Reiss" <mick@xxxxxxxxxxxxxxxxx>]

Passing in tsume searches.
==========================

In go4++ I have an (alpha-beta-minimax) tsume searching module which 
searches local life and death situations. The search mechanism explores 
the tree of possible moves in neatly bound regions. The object of the 
search is to determine the status of a given group of stones. The group 
on the inside of the bound region is called the "defender" and the group 
around the outside is called the "attacker". All moves in the search must 
be inside the bound region or pass. The possible answers to the search 
are:

Alive.
Ko.
Seki.
Dead.
Unknown.

During the search there is effectively no ko rule. What I do instead is 
to repeat the search twice, once with the option "white wins all ko's" 
and once with "black wins all ko's". When "black wins all ko's" is set 
then white is simply not allowed to make a ko move in the first place, it 
becomes an illegal move that won't even be tried. If the search result is 
different depending on who wins ko's then the final result is said to be 
ko.

A node in the tree search can be considered "terminal" for several 
different reasons:

1. Part or all of the original defending group is captured in which case 
a value of "DEAD" is passed back up the tree.

2. A function determines that the defending group has 2 eyes in which 
case a value of "ALIVE" is passed back up the tree.

3. the previous two nodes were both passes in which case a value of 
"SEKI" is passed back up the tree.

4. the tree is deemed too deep or bushy in this variation in which case a 
value of "UNKNOWN" is passed back up the tree.

At each non-terminal node in the tree I have to generate a list of 
possible moves for the next turn. This often includes a pass move. There 
are clearly situations where the defender *must* pass. For example when 
the defender has exactly 2 liberties both of which are eyes. It should be 
noted that if the defender has 3 liberties, two of which are eyes then it 
could play a move on that third liberty instead of passing - that 
wouldn't affect the final outcome.

I now have two questions:

Are there any tsume problems where the defender *must* pass *more than 
once* (not necessarily consecutively) in order to prove it's alive or 
seki?

Are there any tsume problems where the defender *must* pass but the pass 
move is not the defenders last move before the search terminates?

My suspicion is that the answer to both these questions is "no", but I'm 
not sure. I would like to know the answer because then I could ban a 
whole load of pass moves and make the search tree much smaller.

Mick.