Re: computer-go: unmake move?

["Mark Boon" <tesuji@xxxxxxxxx>]

I think the mistake in thinking is to use the same make/unmake move routine
as for the other tactical search(es). Goliath spends more than half its time
making and unmaking moves as well, but it has specialised routines for 2
liberty search that are an order of magnitude faster than for regular
making/unmaking moves.

I spent a lot of time optimising 2 liberty search, partly because it was
necessary at the time, partly because it was fun. It also gave me good ideas
how to optimise the rest of the program. I must have spent at least 50% of
development time on optimising existing algorithms and a significant amount
on time on optimising ladders. It got to the point where reading a ladder
across the board would take 5 milliseconds. With todays high-end PCs that
should be microseconds.

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

No, for ladders I don't keep liberties. In fact, you hardly need to keep any
information at all. I only have an array that marks which stones are to be
captured (which needs updating ever other move) and a list of adjacent
chains in atari. And a move stack of course. The only luxury I permitted
myself was recursion, which is probably the only area in which it can still
be improved upon significantly.

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

Well, the reason was historical as well. :-) But somehow it also seems the
logical thing to do. Does it mean yours uses the same routines when it
starts a long diagonal ladder across the board? (Ouch!)

> 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 don't understand this. How can it not find some moves? All the attacker
can do is fill one of the liberties and all that the escaper can do is
either play at the remaining liberty or capture an adjacent chain. Any other
move cannot be for 2 liberty search and should be 3 or more liberty search.

I never bothered with more than 3 because it would get even more expensive
and I thought it wasn't worth it. In my opinion it's rare to find
interesting 4 liberty tactics while they're quite expensive to calculate.
Most of the time the same information can be obtained more cheaply by doing
global analysis of chains and groups.

    Mark