Re: computer-go: unmake move?

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

Hi Mark,

I knew that Goliath tried 2 liberty laddders first with a very fast
routine, and then more general reading.  But I never did that.  I
had special fast move generators for attacking 2 liberties and defending
one liberty for a long time, to make the ladder case faster.
But I removed the 2 liberty attack generator a few years ago, since 
it wasn't finding some of the moves that the general generator could 
find.

I guess you could think of doing a 2 liberty search first as similar
to doing iterative deepening in chess... :)  Doesn't take much extra time
for complex searches, and finds the simple solutions quickly. 

I don't think I could make a specialized 2 ladder searcher that was 10 times 
faster than my tactical search.  My current search spends about half
its time making and unmaking moves, so a faster move generator can
only speed it up by a factor of two.  My tactical make/unmake only
changes the data structures that are needed for tactics (liberty count,
string combine and split, adjacent enemy strings, etc.), and I think it would
have to be the same for 2 liberty searches.

I always thought that the reason Goliath had two searchers was historical.
You started out with just a 2 liberty search and highly optimized it.
Then when you added searching for higher liberty counts, it was easier
and to write a second searcher, than to extend the first one (since the 2 
ladder search had already been highly optimized).

Does anyone else do this kind of two stage tactical search (iterative
deepening on liberty count rather than on search depth)?

The move generator looks at features of each plausible move and assigns
values 
to them, and adds them up, then selects the top few cantidates.  So yuo
could say that every move choice is due to some heuristic :)

David


At 11:35 AM 6/16/00 +0200, Mark Boon wrote:
>It is a ladder indeed. Davids approach surprises me a little. I had assumed
>all programs would start off with a 'ladder' search. Only when it turns out
>it can't be captured by the 'ladder' routine would it need to do a more
>extensive tactical search, which in its turn calls the 'ladder' routine to
>do the last two liberties.
>
>Of course there are advantages doing it the way David does. Most of the
>times it's better to play a geta instead of a long ladder. On the other
>hand, often it's also better to play the solution that minimises the number
>of liberties a chain can get, instead of minimising the search-depth. For
>example, if there had been a 'O' stone at 'i', connecting at 'b' in the
>third sequence would have worked. But in this case it's clearly an inferior
>solution because the '@' move above 'i' would become sente. (This is maybe
>not a good example, but in general minimising the number of liberties also
>minimises the number of forcing moves of the opponent.)
>
>In my experience, a two-liberty search (or 'ladder' search) can be highly
>optimised, way beyond what's possible with more general tactical searches.
>So the main reason I'm surprised is that I find it hard to see how Davids
>method can compete in terms of performance. A simple 'ladder' routine would
>have 50% chance of starting with 'a' and 50% with 'c'. Starting with 'a'
>would take 22 nodes while starting with 'c' would take 39 nodes (Average of
>30.5, if I counted right). With a specialised 'ladder' routine that can
>search ten times faster than a more general tactical routine, it would
>finish in 15% of the time or less.
>
>    Mark
>
>P.S. David, your program doesn't try 'k' after 'j' failed in the third
>sequence because of some heuristic?
>
>
>----- Original Message -----
>From: Martin Mueller <mueller@xxxxxxxxxxxxxxxxx>
>To: <computer-go@xxxxxxxxxxxxxxxxx>
>Sent: Friday, June 16, 2000 8:04 AM
>Subject: Re: computer-go: unmake move?
>
>
>>
>>     + + @ @ @ @ @ + |
>>     + + + O O O @ i |
>>     + @ + O @ @ O O k
>>     + @ O b O @ @ c h
>>     + @ + d @ O a g j
>>     _ _ _ f e _ _ _ _
>>
>> I may be missing something, but: isn't this simply a ladder problem?
>>
>> Martin
>>
>
>