Re: computer-go: unmake move?

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

I don't do anything fancy.  I just count liberties.  There
are a few shortcuts.  If it is the opponent's move
and the string has one liberty, you can stop, so there
is no need to get to zero liberties.  And I look at
approach moves and second order liberties, so often I
can prove early that a string must be able to get 5 liberties.
That lets me avoid search for single stone groups with 4
liberties and lots of space around.  I also look at the liberty
count of neighboring enemy groups, and stop if there are
a lot of enemy neibors with 1 or 2 liberties.  I also recognize
small eyes and seki.

The main thing for me is to do good move generation and sorting.
Only try moves that have high probability of working.  You can
get pretty good move sorting just by looking at second order
liberties (liberties of liberties).  I have about 3500 lines of
move generation code, but it's been tuned for 15 years :)

David


At 01:33 AM 6/9/00 -0400, you 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.
>I also test  for trasnpositions.   I  call the routine  twice for each
>string.  I believe what  I'm doing is fairly  standard, but I know  my
>implementation is  broken in  the sense that   I'm including too  many
>moves.
>
>Is there a good description of how this might be done somewhere?  I am
>sure I don't have it right.
>
>I had  always thought that programs  do some static evaluation  in the
>tactical search to  avoid the blowup  and that  that is  what is wrong
>with my routine.   I can imagine that  there might be  ways, with some
>kind of simple (or not  so simple) analysis,  to find out that further
>searching is  futile for this  tactical string search.  I just haven't
>figured it out.
>
>Don
>
>