[computer-go] Another beginner question: string management

[Peter Drake]

On May 16, 2008, at 5:41 PM, Carter Cheng wrote:

> Thanks for pointing to the existence of this document. It clarifies  
> some things about a conventional light playout UCT design(It also  
> answered a question about pseudo-liberties I guess they are  
> equivalent to what I term |multi set liberty|). From the code I  
> gather Orego (thus libEgo) does update all the pointers to the  
> chain record.

When two chains are merged, the chainIds for the stones in only one  
of them (ideally, the smaller one) have to be changed. This takes  
time proportional to the size of the smaller chain. Also the two  
circular linked lists have to be appended, which takes constant time.

See orego.core.Board.mergeChains().

> There are still a few design tradeoffs I dont quite understand such  
> as caching adjacent vertex properties in the vertex. How much and  
> why does this result in a speedup?

Do you mean neighborCounts? This has a number of uses. It allows you  
to immediately:

1) Eliminate most points from being "eyelike". See isEyelike().

2) Determine the initial pseudoliberty count of a newly-placed stone  
(before merging with neighboring chains). See placeStone().

3) Tell whether you need to check for single-stone suicide or simple  
ko violation. See playNonPassUnoccupied().

4) Tell whether a point is surrounded when counting the score at the  
end of a playout. See playoutScore().

Lukasz could say more -- he spent a lot of time optimizing the heck  
out of this stuff.

Peter Drake
http://www.lclark.edu/~drake/