Re: computer-go: unmake move?

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

Hi Tristan,

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.

My heuristics are primarily based on the number of liberties 
a group can get for each possible move, modified by information
on the liberty counts of nearby groups.  In this problem it
finds the correct first move because it also gains liberties
for the white stone.

Your approach is interesting since it gives pretty
good results without years of tuning a move selection
heuristic.

David Fotland
 

At 12:29 PM 6/9/00 +0200, Tristan Cazenave wrote:
>Don Dailey wrote:
>
>> > String tactics is fast since the evaluation is just the
>> > number of liberties.  Stable is 5 liberties, and captured is
>> > zero.
>>
>> I do this too, but I don't do it very well.  I'm  not sure which moves
>> to cover.  I consider all moves to the  liberties of the target string
>> and have some simple stopping rules to  try to control  the search.  I
>> include some  moves that attack the  opponent if it's  relevant to the
>> target string.  I can  find ladders and the  thing does work, sort of.
>
>> Is there a good description of how this might be done somewhere?  I am
>> sure I don't have it right.
>
>You may find this paper interesting:
>
>http://www.ai.univ-paris8.fr/~cazenave/APS.ps
>
>During a dinner at 99'Ing cup in London, we had a discussion
>about that, I remember people believing that the number of
>liberties is a good indicator of the 'capturability' of a string.
>I did not think so, but could not find good arguments.
>Here they are. Any comments welcome.
>
>--
>Tristan Cazenave
>Universite Paris 8, Departement Informatique, Labo IA
>2, rue de la Liberte 93526 Saint-Denis Cedex - France
>http://www.ai.univ-paris8.fr/~cazenave/
>
>
>
>