Re: computer-go: unmake move?

["Tristan Cazenave" <cazenave@xxxxxxxxxxxxxxxxx>]

Hi David,

>In your paper you give an example of reading to catch
>a 4 stone group in figure 4.  You say that it takes
>787 nodes with abstract proof search and 44K nodes
>with heuristic search.  I assume the tactical
>problem is White to move and capture 4 stones.
>
>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.
>


If I include in the quiescence search the forced moves on
adjacent atari strings of a string in atari, I get 1 node for
the main search and 38 nodes for the quiescence
search. The example in the paper uses a very simple
quiescence search. However my point is not on move
ordering using liberties or other quite Go specific
knowledge to speed up the search, it is rather to prove
theorems about games, which is surprisingly faster than
doing an heuristic search using standard techniques.

You can still use other heuristics with abstract proof search,
that may improve it, but there is good chances that you
will still have better results using my theorem proving
functions than without them. Moreover the idea is quite
general and applicable to connections for example or
to other similar games.

By the way, I do not understand how you get 27 nodes,
Don't you use iterative deepening ?
Do you stop at a node when you see that a move does
not work without playing it, therefore not counting the following node ?
Do you use your probability stuff for deciding that it is not worth
coutinuing searching for capture problems too ?

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

Tristan.