Gian-Carlo Pascutto <[EMAIL PROTECTED]> said:
> I wrote my program to track psuedoliberties because this is very fast
> and I thought I could take a lot of shortcuts and early exits when I had
> to know the real amount of liberties. Unfortunately the interesting
> cases seem to be the ones that don't allow for the shortcuts. I am now
> convinced designing the program with psuedoliberties was a mistake.
My friends and I have just finished an alpha version of a code
generator that compares go board implementations in a wholistic
manner. The results are complicated, but pseudo-liberties work
reasonably well, too. See below.
Michael Wing
www.swcp.com/~wing/cgbg
-----------
The Critters Go Board Generator
Michael Wing
January 15, 2008
Ive wanted to develop a fast go board for many years, and have spent
the last few months helping write a go board generator to figure out what
fast means. The current code was inspired in part by discussions on the
computer-go email.
CGBG generates many go board implementations: 4 methods of tracking
liberties, 3 methods of tracking adjacent groups, 2 methods for mapping a
location to a chain. It also can generate code with and without borders, and
for many board sizes. It generates ptest, which runs 2 performance tests:
filling the board to 90% full (which resembles Monte Carlo readouts) and
ladder reading (which resembles local board analysis). It generates ftest,
which runs many functional unit tests.
Caveats. CGBG was intended to create apples-to-apples comparisons,
but does not strictly do so. First, the current implementations are solid,
but not necessarily optimal. For example, union-find uses classic 2-pass
path compression, rather than the 1-pass version in libego. Also, Many other
optimizations (loop unrolling) are not implemented. This is alpha code. Many
ideas are just sketches. There is a lot of cruft.
Main conclusions:
* GnuGo data structures are pretty darn good, even for Monte Carlo
simulation. I had hoped to find a linked-list data structure, but didnt.
* Behavior at 9*9 can be very different than behavior at 19*19.
* The complex nature of cache and processor architecture makes it
very hard to predict the effect of any data structure decision. Trying it
out empirically is the only way.
* Many reasonable implementations run within a factor or 33% or so
of the best.
Main conclusions for 19*19:
* Using union-find is slower than changing the smaller chain, by a
tiny amount.
* Using arrays to track liberties is best for board analysis.
* Using pseudo-liberties only is best for pure simulation.
* Using arrays to track adjacent groups is best for board analysis.
* Using search-only to track adjacent groups is best for pure
simulation.
* For a program that does both Monte Carlo and local board analysis,
I would use arrays to track both liberties and adjacencies.
* For a program that does no local analysis, I would use pseudo
liberties only.
Other Notes
* CGBG precomputes board and hash data, so they can be stored in
read-only memory and do not need to be initialized. This can be used as an
example, or cut and paste into other implementations.
* This implements positional superko checking (though not tested),
which GnuGo and libego do not. Situational superko checking is sketched, but
not complete.
* The play() routine uses gotos. The conventional technique of
deciding the status of a move and then using a switch statement is about 1
percent slower.
The code is written in Ruby, and currently generates C code for gcc under
cygwin. It also needs to link in SFMT. It is available at
www.swcp.com/~wing/cgbg
To Use
* ./cgbg <config_file>
* make
* ./ftest
* ./ptest
I would appreciate any feedback.
Michael Wing
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
