[computer-go] Fast Board implementation

[Łukasz Lew]

On 12/11/06, dhillismail at netscape.net <dhillismail at netscape.net> wrote:
>
>  Hello all.
> I've been lurking on the list for a few years now. In amongst the usual
> musings on the meaning of AI and social justice, etc., there's been a sharp
> increase in the amount of useful information posted here of late. I'll try
> to contribute.
>
> My engine is AntIgo. It's been a speed bump on CGOS and in several KGS
> tournaments so I've turned to MC UCT.
>
> I have a Pentium 1.86 GHz laptop.
> From an empty board, without using the "mercy rule", I get about 22,000 pps
> (1 pps: playout per second including scoring, if needed, and restoring the
> board). I use the rules discussed on the list and get an average of 107
> moves/game not counting passes. With the mercy rule, I get about 29,000 pps
> and the average game length is around 99.
>
> Here are a few speedup tricks that have helped me.
>
> 1. The mercy rule. Since I'm incrementally keeping track of a list of empty
> points, it's no real extra pain to keep track of the number of black and
> white stones on the board. If the difference between them exceeds a
> threshold, the game is over. Ending early has an added bonus that I know the
> outcome without needing to score the board. (You can shoot yourself in the
> foot here. Best to pick a more conservative threshold the closer you are to
> interior nodes of the tree.) For exterior nodes far from any interior nodes,
> I use a threshold of 25 stones.

Thanks for that, I implemented this in libgoboard

> 2. Pseudo liberties (I think that this wheel has been reinvented many times
> with many different names; "Pseudo liberties" is a good name). Checking
> whether a potential move would be suicide, fill an eye, etc. is complex
> enough to entail a function call inside a tight loop. If an empty space on
> the board has one or more pseudo liberties, it is an acceptable move. It
> can't be suicide or Ko or fill any kind of single point eye. So I make that
> test first and usually skip the function call.

Isn't adding an integer faster than memory access?

Best Regards and thanks,
Lukasz

> 3. For every space on the board, I pre-calculate the addresses of all its
> neighbors. I treat the off-edge as one super-safe third-color group, so a
> space next to the edge doesn't need to be treated as any kind of special
> case.
> 4. At every move, I update the pseudo liberties, group membership, stone
> counts, and empty spaces list. When a stone is removed due to capture, I
> place that position at the end of the empty spaces list. When a stone is
> added, the space it's about to occupy is already at the end of the list, so
> I just decrement the counter. I never need to regenerate the empty spaces
> list.
>
> Dave Hillis
>  ________________________________
>  Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading
> spam and email virus protection.
>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
>