[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: computer-go: Languages for programming go are?
I'd be interested in hearing about how others maintain incremental
structures, and what type of knowledge is incremented.
My Go program, written in C++, implements the following objects:
Each board object (ie., for each move) maintains 1) a list of black and
white strings, 2) a cell for each position on the board, 3) bitmap of black
and white stones, 4) the Simple Ko Point, 5) who's turn it is, 6) the number
of captured black and white stones, and 7) the move number. I'll eventually,
add Hash value (Zobrost)
Each string maintains 1) a bitmap of positions occopied, 2) a bitmap of all
liberties, 3) the number of stones in string, 4) the liberty count, 4)
"AbsolutelyAlive" flag by Benson's Algorithm, and 5)
"AbsolutelyAliveByAlternatingPlays" by Muller's Algorithm. (I haven't
implemented the last two yet - anyone want to help?).
Each cell contains 1) the enumerated string number, and 2) which player, if
any, occupies that position.
Using smart pointers, objects are copied-when-modified. So it's inexpensive
to copy objects since it's just a copy of a pointer. The trade-off is an
addition pointer de-reference when first accessing an object. In addition,
when an object is actually modified, than is the cost of copy operation is
paid. Note, this isn't a deep copy, as that wouldn't be necessary.
The most complex algorithm, so far, is actually doing a move: 1) Captured
strings need to be removed when their atari point is filled, and liberties
re-adjusted for all neighboring strings, 2) Strings need to be merged when
joined, each cell possibly needs a new string enumerator assigned. Both of
which are comparatively slower than anything else.
Just for some sporty fun, my Go program on PIII-500 can execute about one
million random moves in under 5 seconds:
Board::TimingTests()
---> Playing Random Game
***> 1000000 Turns
***> 4.625 seconds.
***> 216216 turns per second.
Anyway, I'm curious about what other knowledge is incrementally updated by
my fellow Go programmers, and how, if you don't mind.