Ben Lambrechts wrote:
What is the Zobrist Hash of the following board?
You have to create a table of *random* numbers (typically unsigned 64 bit) lets
call the type int64.
Your table is:
CONST BlackH : array [0..19*19 - 1] of int 64 = ($badf00dcafebabe1, .. //
361 entries
WhiteH : array [0..19*19 - 1] of int 64 = ( // a different set of
361 entries
The Zobrist hash of a board is the xor of all the moves
Example (a board with 3 stones):
black (3, 4) // assume coordinates are zero-based 19x19
white (5, 7)
black (3, 2)
Hash = BlackH[19*3 + 4] XOR WhiteH[19*5 + 7] XOR BlackH[19*3 + 2];
Of course, it represents the position and is independent of the order. If you
ignore
the move history, you can just compute the stones in any order.
The hash of the transformed black move transformed by (y, inv X) where (x=3, y=4)
is BlackH[4, (19-1) - 3]
The hash of a transformed board is the hash computed transforming all the moves.
The idea is that any of the board the can be transformed by mirror rot from a
given
board will produce the same set 8 hashes, just in a different order. Because the
hashes are (with high probability) unique, one hash represents a board and the
canonical hash represents the class of 8 boards produced by mirror/rot.
It is true: Another board in the class -> same set of 8 hashes -> same
canonical hash.
It is almost certain (prob = 1/2^64 per check): A different board -> a
different set
of 8 hashes -> different canonical hash.
Jacques.
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
