Re: computer-go: unmake move?

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

At 10:17 AM 6/15/00 +0200, Tristan Cazenave wrote:
>Hi David,
>>Many Faces's heuristic search only looks at 27 nodes
>>to solve this one.  So you still have lots of room for
>>improvement :)  The heuristic tactical move generator
>>only selects one non-optimal move in this search for
>>white, and gets the correct move on the second try.
>>
>
>By the way, I do not understand how you get 27 nodes,
>Don't you use iterative deepening ?

I do not do iterative deepening.  Since so many searches are
very deep, it didn't seem like a good idea for go tactics.
And my move generator is pretty good at finding the best
first move.  Since my tactical evaluation is just
captured/escaped/unknown, the early iterations would have
most moves evaluate to unknown, and the early iterations
wouldn't help the move ordering much.

Without iterative deepening, I have to be careful that a
bad early move choice doesn't waste lots of nodes in a
bushy part of the tree when there is a simple answer
with a different move.  I do this by rationing nodes to
subtrees based on the relative heuristic values for the
first and second move choices.  I also generate more
moves near the root of the tree.

I limit the size of each individual search to 100 nodes,
not counting forced moves.  A forced move is when the
move generator only generates one move.  In a simple
ladder, after the first few ply, all moves are forced.

The 27 nodes counts every make-move/evaluate pair.


    + + @ @ @ @ @ + |
    + + + O O O @ i |
    + @ + O @ @ O O k
    + @ O b O @ @ c h
    + @ + d @ O a g j
    _ _ _ f e _ _ _ _

The 27 moves searched are:

a-b-c-connect-d-e-f  (captured since can't get more than one liberty)
 -c-g-b-h-connect-d-e-f (captured)
     -h-b-i-j-k (escapes) the move generator put the wrong move first here (b)
       -k-b-j-connect-d-e-f (captured)

It looks like 23 nodes is the minimum possible for Many Faces for this 
problem.  This is an easy problem for Many Faces.  Its liberty counting
heuristics work well.

This search has about 8 forced moves, so it would count as 19 nodes
toward the 100 node search limit.

On average, over a game, when the program finds a way to capture a 
group, it tries the best move first about 90% of the time.  The
attacking side does better than that here, finding the best
first move 12 out of 13 times.

>Do you stop at a node when you see that a move does
>not work without playing it, therefore not counting the following node ?

For example, I stop when a group has one liberty and it is the
opponent's move.  I don't make the move to take the stones off the
board.  I stop if a group has one liberty and has the move and can't
get more than one liberty.

>Do you use your probability stuff for deciding that it is not worth
>coutinuing searching for capture problems too ?

I use the probability stuff only for full board life and death
reading.  The full board group evaluation is so slow that it only
does about 10 nps, so I wanted to use a best-first algorithm.
For full board reading, making/unmaking moves is hundreds of times
faster than evaluation, so the overhead of expanding nodes in
different parts of the tree is very low.

>
>It would be quite useful to have a non-copyrighted database of
>problems for capturing strings and connecting them. So as to
>enable a comparison of our respective algorithms, and to
>provide a standard benchmark for other programmers and
>researchers. I think it could be possible by automatically
>selecting 'interesting' problems froms the games the programs
>plays, and making them review by humans...

Agreed.  Since everyone has the graded go problem books, we
can still use them as a standard, referring to them by
number.

David

>Tristan.