Re: computer-go: unmake move?

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

38 nodes is really good.  I wrote my reply because it
sounded like your point was that heuristic search would take
50 times more nodes than abstract proof search.  I wanted
to point out that there is a heristic, liberty-count based
search that uses very few nodes. :)

For tactical search, Many Faces stops at the first move
that works.  For any full board reading, it looks for all
moves that work.

David

At 03:07 PM 6/15/00 +0200, Tristan Cazenave wrote:
>Darren Cook wrote:
>
>> >>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.
>> >
>> >By the way, I do not understand how you get 27 nodes,
>>
>> I was waiting for Tristans reply to this. The reply I was expecting was
>> that Tristans program searches for all possible moves that work, while Many
>> Faces stops as soon as it finds one move that works. Is that not the case
>> here?
>
>That's also true, and I forgot to mention it in my reply. I search
>
>3 plies deeper than the shortest solution depth so as to find
>
>other moves that may work. The result I gave (38 nodes) is with this option
>
>switched off, and the ordering of moves in the quiescence search is done
>
>with playing the move that would give the string to capture the most
>
>liberties.
>
>--
>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/
>
>
>
>