I could pack all of the information into a single array. Here is one
possible scheme which fits in 32 bits and accommodates all board sizes:
3 bits to identify white/black/empty/off-board
9 bits for the hash key (the reference stone)
9 bits for pseudo liberty count
9 bits for stone count
That's quite close to the data structure I've been working on. So far I have:
2 bits to identify black/white/empty (no off-board, I'm not really a
"mailboxer")
2 bit to identify liberties for both sides
1 bit for parity, used with floodfills to track which squares have been updated
9 bit for string reference: I was thinking of using this as a sort of
linked list. Now I'm not so sure, it might be better to have each
element link to a root element. It is possible however to keep a
doubly linked list and a base reference...
For the rest, I'm not so sure what to put in; this is my first Go
program. The pseudo liberty count might be useful, or maybe the real
liberty count. I was thinking of having a linked list of liberties for
a string. However a liberty can belong to more than one string/color.
Also a topic that I've thought about a lot is bitboards (I come from
the chess world). It seems the most natural representation for Go as
there is only one piece type and floodfills are used all the time.
However the use of them seems to be quite esoteric, the only
implementation I have seen is 1 word = 1 row. I would rather use more
data in each word and have each word represent a region more
rectangular in shape, but this makes things much more complicated,
especially if you support multiple board sizes.
Zach
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
