Re: [computer-go] rotate board
With 8 hashes per position, the chance of two different boards producing a different set of hashes but the same canonical hash is greater than 1/2^64, because there will be a bias in the choice of canonical hashes - toward numerically lower numbers, for instance. I think. Arthur On Dec 20, 2007, at 10:49 AM, Jacques Basaldúa wrote: snip 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. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
On Dec 20, 2007 10:15 AM, Arthur Cater [EMAIL PROTECTED] wrote: With 8 hashes per position, the chance of two different boards producing a different set of hashes but the same canonical hash is greater than 1/2^64, because there will be a bias in the choice of canonical hashes - toward numerically lower numbers, for instance. I think. More importantly, how does it differ from 8/2^64 = 1/2^61? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
On Dec 20, 2007 10:19 AM, Jason House [EMAIL PROTECTED] wrote: On Dec 20, 2007 10:15 AM, Arthur Cater [EMAIL PROTECTED] wrote: With 8 hashes per position, the chance of two different boards producing a different set of hashes but the same canonical hash is greater than 1/2^64, because there will be a bias in the choice of canonical hashes - toward numerically lower numbers, for instance. I think. More importantly, how does it differ from 8/2^64 = 1/2^61? If you are going to compute all 8 hash keys, you can just add them up at the end instead of picking the minimum. Wouldn't that be better? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
That was my first thought too - actually my 2nd, my 1st was (8*8/2)/(2^64) - but I reason, one particular choice of position A's 8 must match one particular choice of position B's, rather than any one of A's matching the particular one of B's. But since the choosing is biased, the chance of collision is somewhat increased. Arthur - Original Message - From: Jason House [EMAIL PROTECTED] Date: Thursday, December 20, 2007 3:20 pm Subject: Re: [computer-go] rotate board To: computer-go computer-go@computer-go.org On Dec 20, 2007 10:15 AM, Arthur Cater [EMAIL PROTECTED] wrote: With 8 hashes per position, the chance of two different boards producing a different set of hashes but the same canonical hash is greater than 1/2^64, because there will be a bias in the choice of canonical hashes - toward numerically lower numbers, for instance. I think. More importantly, how does it differ from 8/2^64 = 1/2^61? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
With 8 hashes per position, the chance of two different boards producing a different set of hashes but the same canonical hash is greater than 1/2^64, because there will be a bias in the choice of canonical hashes - toward numerically lower numbers, for instance. I think. More importantly, how does it differ from 8/2^64 = 1/2^61? If hash collisions are worrisome, you can always use 96-bit or 128-bit hashes. Modern x86s can do 8 parallel loads, adds, subtracts, or stores of 16-bit numbers in one step using SIMD, just like Antti Huima suggests in http://fragrieu.free.fr/zobrist.pdf. Michael Wing ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
I think that would be worse. There are lots of sets of 8 numbers that sum the same, far more than there are sets of 8 with the same minimum element. Arthur - Original Message - From: Álvaro Begué [EMAIL PROTECTED] Date: Thursday, December 20, 2007 4:08 pm Subject: Re: [computer-go] rotate board To: computer-go computer-go@computer-go.org On Dec 20, 2007 10:19 AM, Jason House [EMAIL PROTECTED] wrote: On Dec 20, 2007 10:15 AM, Arthur Cater [EMAIL PROTECTED] wrote: With 8 hashes per position, the chance of two different boards producing a different set of hashes but the same canonical hash is greater than 1/2^64, because there will be a bias in the choice of canonical hashes - toward numerically lower numbers, for instance. I think. More importantly, how does it differ from 8/2^64 = 1/2^61? If you are going to compute all 8 hash keys, you can just add them up at the end instead of picking the minimum. Wouldn't that be better? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
As Gunnar pointed out, you may not need the canonical hash at all. I think you only need to compute the canonical hash if you are matching to some game-external hash, such as a fuseki or pattern library. If you are just using it for transposition and super-ko checking, no board rotation will have occurred. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
On Dec 20, 2007 11:23 AM, Arthur W Cater [EMAIL PROTECTED] wrote:
I think that would be worse. There are lots of sets of 8 numbers that sum
the same,
far more than there are sets of 8 with the same minimum element.
Arthur
- Original Message -
From: Álvaro Begué [EMAIL PROTECTED]
Date: Thursday, December 20, 2007 4:08 pm
Subject: Re: [computer-go] rotate board
To: computer-go computer-go@computer-go.org
On Dec 20, 2007 10:19 AM, Jason House [EMAIL PROTECTED]
wrote:
On Dec 20, 2007 10:15 AM, Arthur Cater [EMAIL PROTECTED] wrote:
With 8 hashes per position, the chance of two different boards
producing a different set of hashes but
the same canonical hash is greater than 1/2^64, because there
will be
a bias in the choice of canonical
hashes - toward numerically lower numbers, for instance.
I think.
More importantly, how does it differ from 8/2^64 = 1/2^61?
If you are going to compute all 8 hash keys, you can just add them
up at the
end instead of picking the minimum. Wouldn't that be better?
That can't possibly be true... Think about it. Sums of random numbers are
uniformly distributed (remember we are working in the ring of integers
modulo 2^64), while the minimum is very biased towards small numbers.
These two Unix commands show the number of different sums and the number of
different minimums among 10,000 sets of 8 random integers. I did it with 16
bits instead of 64:
alvaro-begue-aguados-computer:~ alvaro$ perl -e 'for $x (1..1){$s=0;for
$y (1..8){$s+=int(rand(65536));}print .($s%65536).\n;}' | sort -u | wc
-l
9294
alvaro-begue-aguados-computer:~ alvaro$ perl -e 'for $x
(1..1){$s=999;for $y (1..8){$t=int(rand(65536)); $s=$t if
$t$s;}print $s\n;}' | sort -u | wc -l
7476
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
Álvaro Begué wrote: On Dec 20, 2007 10:19 AM, Jason House [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: On Dec 20, 2007 10:15 AM, Arthur Cater [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: With 8 hashes per position, the chance of two different boards producing a different set of hashes but the same canonical hash is greater than 1/2^64, because there will be a bias in the choice of canonical hashes - toward numerically lower numbers, for instance. I think. More importantly, how does it differ from 8/2^64 = 1/2^61? If you are going to compute all 8 hash keys, you can just add them up at the end instead of picking the minimum. Wouldn't that be better? I think that's pretty workable.XOR is definitely wrong here. If you use xor, then the empty board would hash to the same value as the position after a stone (of either color) is placed on e5 as well as any other symmetry like this.I also think symetries like putting a black stone on 2 points across from each other (such as in diagonal corners) would create a zero hash because you have 2 sets of 4 hashes that cancel each other.I think addition as Álvaro suggests fixes this. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
The only way this might help is in the opening or in very nearly symmetrical positions and this is really rare. The possible slight benefit would be canceled by even a very small slowdown. It would be useful on small boards as an opening book however where exact positions (or hashes) are stored. - Don Chris Fant wrote: As Gunnar pointed out, you may not need the canonical hash at all. I think you only need to compute the canonical hash if you are matching to some game-external hash, such as a fuseki or pattern library. If you are just using it for transposition and super-ko checking, no board rotation will have occurred. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
Don Dailey wrote: You can use Zobrist hashing for maintaining all 8 keys incrementally, but you probably need a fairly good reason to do so. Incrementally updating of 1 key is almost free, but 8 might be noticeable if you are doing it inside a tree search or play-outs. Yes. Don is right. Of course that is not part of the real program, but of a program that searches the book. In my case (19x19 only) I play a maximum of 20 moves (10 per player) from the book and then switch to the real program. I never shared the naif idea that some openings (played by high dan) are better than others and that finding a correlation between a given move and the result of the game was meaningful. I consider all popular openings equally balanced and playable. Finding a move in the book just saves you the time of 4-5 moves (10 if you are really lucky), gives you a straightforward way to randomize the opening (drawing between all moves in the book uniformly) and makes the board contain some information when the real thing starts. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
Jacques Basaldúa wrote: Don Dailey wrote: You can use Zobrist hashing for maintaining all 8 keys incrementally, but you probably need a fairly good reason to do so. Incrementally updating of 1 key is almost free, but 8 might be noticeable if you are doing it inside a tree search or play-outs. Yes. Don is right. Of course that is not part of the real program, but of a program that searches the book. In my case (19x19 only) I play a maximum of 20 moves (10 per player) from the book and then switch to the real program. I never shared the naif idea that some openings (played by high dan) are better than others and that finding a correlation between a given move and the result of the game was meaningful. I consider all popular openings equally balanced and playable. Finding a move in the book just saves you the time of 4-5 moves (10 if you are really lucky), gives you a straightforward way to randomize the opening (drawing between all moves in the book uniformly) and makes the board contain some information when the real thing starts. Indeed, my book scheme for Lazarus is very simple. I track the first move out of book for Lazarus and deep search it N times (for variety.)The next time Lazarus encounters that same position, there is a book response and Lazarus saves search time. Lazarus plays moves in same proportion they are selected in the deep search process. In the opening position, if e5 was selected 5 times and d5 1 times, Lazarus would play e5 5/6th of the time. In all games, Lazarus writes to a file the first move out of book and it is placed in a queue of moves to be deep-searched. In practice, the book search is slower than on-line play but this could be adjusted. I'm building up moves to be searched quicker than I am searching them. I could solve this by setting N smaller and/or searching faster but I prefer nice deep searches with reasonable variety. I think N is 4 right now. This doesn't guarantee that the book moves are high quality, but it does have the desirable features that the search is better than during a real game and it saves time.I suspect saving time for future searches is more important than the improved quality of the opening moves. Unfortunately, if Lazarus improves I have to rebuild from scratch (unless the improvement was very minor.) Also, the book would not be useful for games at higher time-controls than the book was searched at. - Don Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
I stand corrected.
Arthur
- Original Message -
From: Álvaro Begué [EMAIL PROTECTED]
Date: Thursday, December 20, 2007 4:37 pm
Subject: Re: [computer-go] rotate board
To: computer-go computer-go@computer-go.org
On Dec 20, 2007 11:23 AM, Arthur W Cater [EMAIL PROTECTED] wrote:
I think that would be worse. There are lots of sets of 8 numbers
that sum
the same,
far more than there are sets of 8 with the same minimum element.
Arthur
- Original Message -
From: Álvaro Begué [EMAIL PROTECTED]
Date: Thursday, December 20, 2007 4:08 pm
Subject: Re: [computer-go] rotate board
To: computer-go computer-go@computer-go.org
On Dec 20, 2007 10:19 AM, Jason House
[EMAIL PROTECTED] wrote:
On Dec 20, 2007 10:15 AM, Arthur Cater [EMAIL PROTECTED]
wrote:
With 8 hashes per position, the chance of two different boards
producing a different set of hashes but
the same canonical hash is greater than 1/2^64, because there
will be
a bias in the choice of canonical
hashes - toward numerically lower numbers, for instance.
I think.
More importantly, how does it differ from 8/2^64 = 1/2^61?
If you are going to compute all 8 hash keys, you can just add them
up at the
end instead of picking the minimum. Wouldn't that be better?
That can't possibly be true... Think about it. Sums of random
numbers are
uniformly distributed (remember we are working in the ring of integers
modulo 2^64), while the minimum is very biased towards small numbers.
These two Unix commands show the number of different sums and the
number of
different minimums among 10,000 sets of 8 random integers. I did it
with 16
bits instead of 64:
alvaro-begue-aguados-computer:~ alvaro$ perl -e 'for $x
(1..1){$s=0;for$y (1..8){$s+=int(rand(65536));}print
.($s%65536).\n;}' | sort -u | wc
-l
9294
alvaro-begue-aguados-computer:~ alvaro$ perl -e 'for $x
(1..1){$s=999;for $y (1..8){$t=int(rand(65536)); $s=$t if
$t$s;}print $s\n;}' | sort -u | wc -l
7476
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
Taking the min of the 8 rotated and reflected values is safe enough.
Yes, the probability density will be eight times higher at the low
end, so you're left with 61 bits and change worth of collision
protection instead of 64. If that's not enough, then you can use a
bigger hash size, as has been mentioned. And since all practical hash
table sizes are far less than 2^61, let alone 2^64, I think that
(minimum hash % hash_table_size) should work fine as a key to your
hash table, while -- and this may be different from what Jason had in
mind -- the formula ((bit-reverse of mininum hash) % hash_table_size))
will, if hash_table_size is a multiple of 8, needlessly favor hash
values that are even or multiples of 4 or 8.
On Dec 20, 2007 1:33 PM, Don Dailey [EMAIL PROTECTED] wrote:
If you are going to compute all 8 hash keys, you can just add them up
at the end instead of picking the minimum. Wouldn't that be better?
I think that's pretty workable.XOR is definitely wrong here. If
you use xor, then the empty board would hash to the same value as the
position after a stone (of either color) is placed on e5 as well as any
other symmetry like this.I also think symetries like putting a black
stone on 2 points across from each other (such as in diagonal corners)
would create a zero hash because you have 2 sets of 4 hashes that cancel
each other.I think addition as Álvaro suggests fixes this.
No, the problem you identified applies to addition too. There is no
100% certainty of collision, but there is a very elevated probability
of it. The eight symmetries include reflections and 180 degree
rotations, all of which have the property that s(s(p)) = p. Suppose
your symmetry transformation exchanges points a and c, and points b
and d. How does the sum of the Zobrist hashes compare for the set
{a,b} versus the set {a,d}? They will collide if
(a XOR b) + (c XOR d) = (a XOR d) + (c XOR b)
If (but not only if) ((a XOR c) AND (b XOR d)) == 0 then a collision
is guaranteed. The probability of this is closer to 2^-32 than to
2^-64.
I suggest that those who are interested follow Erik's link
(http://computer-go.org/pipermail/computer-go/2007-February/thread.html#8653),
as this is not the first or second (or probably even third) time this
issue has come up, and as people have warned several times before, it
is easy to get wrong. I vaguely remember that somebody found a safe
set of Zobrist values that allows reflections to be detected without
recomputation and without greatly increasing the collision probability
was found, but I don't remember the details. I also vaguely remember
hearing that the random values with rotated nybbles approach is
broken too.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
I wrote: If (but not only if) ((a XOR c) AND (b XOR d)) == 0 then a collision is guaranteed. The probability of this is closer to 2^-32 than to 2^-64. Before anybody else feels the need to correct me here -- to be more precise, the probability of collision is at least E(0.5**binomial_variable(64, 0.5)) ~= 1/100,000,000. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
Pseudo random number and hashing. Two ways to get into trouble quickly.
The idea of combining all 8 transformations is appealing on modern
processors because you can eliminate all conditional branching.But
maybe this is not practical after all.
If speed is not a concern, you could simple hash the 64x8 bit value
itself with a good mixing hash function, such as md4 or md5.But even
this doesn't work unless you establish some kind of ordering first,
such as sorting them before hashing them.
- Don
Eric Boesch wrote:
Taking the min of the 8 rotated and reflected values is safe enough.
Yes, the probability density will be eight times higher at the low
end, so you're left with 61 bits and change worth of collision
protection instead of 64. If that's not enough, then you can use a
bigger hash size, as has been mentioned. And since all practical hash
table sizes are far less than 2^61, let alone 2^64, I think that
(minimum hash % hash_table_size) should work fine as a key to your
hash table, while -- and this may be different from what Jason had in
mind -- the formula ((bit-reverse of mininum hash) % hash_table_size))
will, if hash_table_size is a multiple of 8, needlessly favor hash
values that are even or multiples of 4 or 8.
On Dec 20, 2007 1:33 PM, Don Dailey [EMAIL PROTECTED] wrote:
If you are going to compute all 8 hash keys, you can just add them up
at the end instead of picking the minimum. Wouldn't that be better?
I think that's pretty workable.XOR is definitely wrong here. If
you use xor, then the empty board would hash to the same value as the
position after a stone (of either color) is placed on e5 as well as any
other symmetry like this.I also think symetries like putting a black
stone on 2 points across from each other (such as in diagonal corners)
would create a zero hash because you have 2 sets of 4 hashes that cancel
each other.I think addition as Álvaro suggests fixes this.
No, the problem you identified applies to addition too. There is no
100% certainty of collision, but there is a very elevated probability
of it. The eight symmetries include reflections and 180 degree
rotations, all of which have the property that s(s(p)) = p. Suppose
your symmetry transformation exchanges points a and c, and points b
and d. How does the sum of the Zobrist hashes compare for the set
{a,b} versus the set {a,d}? They will collide if
(a XOR b) + (c XOR d) = (a XOR d) + (c XOR b)
If (but not only if) ((a XOR c) AND (b XOR d)) == 0 then a collision
is guaranteed. The probability of this is closer to 2^-32 than to
2^-64.
I suggest that those who are interested follow Erik's link
(http://computer-go.org/pipermail/computer-go/2007-February/thread.html#8653),
as this is not the first or second (or probably even third) time this
issue has come up, and as people have warned several times before, it
is easy to get wrong. I vaguely remember that somebody found a safe
set of Zobrist values that allows reflections to be detected without
recomputation and without greatly increasing the collision probability
was found, but I don't remember the details. I also vaguely remember
hearing that the random values with rotated nybbles approach is
broken too.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] rotate board
Hi all, I am planning a fuseki database. Now I got the following problem: how to rotate/mirror the board for a unique representation. $$c $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . 5 . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ $$c $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . 5 . . . . . . . . . . | $$ | . . X , . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . O . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ Both are the same board, but has anyone made an algorithm that rotates the board or an area of the board in a unique way? I don't need the move order, just the snapshot of the board. Ben ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
On Dec 19, 2007 3:08 AM, Ben Lambrechts [EMAIL PROTECTED] wrote: Hi all, I am planning a fuseki database. Now I got the following problem: how to rotate/mirror the board for a unique representation. $$c $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . 5 . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ $$c $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . 5 . . . . . . . . . . | $$ | . . X , . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . O . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ Both are the same board, but has anyone made an algorithm that rotates the board or an area of the board in a unique way? I don't need the move order, just the snapshot of the board. You can compute all rotated versions of the board (8 of them) and pick the minimum, in some sense. For instance, you can compare boards lexicographically, or you can compute a zobrist key and pick the minimum of that. Does that help? Álvaro. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
Ben Lambrechts wrote: Now I got the following problem: how to rotate/mirror the board for a unique representation. Both are the same board, but has anyone made an algorithm that rotates the board or an area of the board in a unique way? I don't need the move order, just the snapshot of the board. Compute the the min(8 Zobrist hashes for all mirror/rot combinations) (x, y), (inv Y, x), (inv X, inv Y), (y, inv X), (inv X, y), (inv Y, inv X), (x, inv Y), (y, x). Call the smallest of the 8 hashes the canonical hash. Make a database of canonical hashes. Since Zobrist hashes can be updated incrementally, checking over the legal moves is just xoring the 8 hashes of the each legal move (with a given mirror/rot) to the hashes of the current position in that same mirror/rot. You store 8 hashes for the current position (=without the move) and compute the 8 hashes of the next position. The smallest of these is the canonical of the next position. This is repeated for each legal move. Its simple, but perhaps my explanation makes it sound more complicated than it is ;-) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
Now I got the following problem: how to rotate/mirror the board for a unique representation.Both are the same board, but has anyone made an algorithm that rotates the board or an area of the board in a unique way? I don't need the move order, just the snapshot of the board. Compute the the min(8 Zobrist hashes for all mirror/rot combinations) (x, y), (inv Y, x), (inv X, inv Y), (y, inv X), (inv X, y), (inv Y, inv X), (x, inv Y), (y, x). Call the smallest of the 8 hashes the canonical hash. Make a database of canonical hashes. Since Zobrist hashes can be updated incrementally, checking over the legal moves is just xoring the 8 hashes of the each legal move (with a given mirror/rot) to the hashes of the current position in that same mirror/rot. You store 8 hashes for the current position (=without the move) and compute the 8 hashes of the next position. The smallest of these is the canonical of the next position. This is repeated for each legal move. Its simple, but perhaps my explanation makes it sound more complicated than it is ;-) This is going to sound really stupid. How do I compute the Zobrist Hash? What is the Zobrist Hash of the following board? $$c $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . X X O . . . . . . . . . . . . . . | $$ | . . X O O X . O . . O . . . . . . . . | $$ | . . X O . . . . . , . . . . . X . . . | $$ | . . . O . . . . . . . . . . . X X . . | $$ | . . X . . . . . . . . . . . O X O . . | $$ | . . . . . . . . . . . . . . . O . . . | $$ | . . O . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . X . . | $$ | . . . , . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . O O O . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . X . . . | $$ | . . O . . . . . . . . . . . O O O . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . O O . . . . . X . . X . . , X . . | $$ | . . O X . X . . . . . . . . . X . . . | $$ | . . X . X . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ Ben ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
Say you represent the content of each point with 0 for empty, 1 for black
and 2 for white. Start by creating a table of 19x19x3 random 64-bit numbers.
unsigned long long zobrist_table[19][19][3];
...
unsigned long long zobrist_key=0;
for(int row=0;row19;++row){
for(int col=0;col19;++col){
int point_content = board[row][col];
zobrist_key ^= zobrist_table[row][col][point_content];
}
}
The result is the zobrist key. In practice, you would make the zobrist key
part of your representation of the board, and when you modify the board, you
just incrementally update the zobrist key. Just remember that when you
change the content of a point,
new_zobrist_key = old_zobrist_key ^
zobrist_table[row][col][old_point_content] ^
zobrist_table[row][col][new_point_content];
Get that working first and then reread Jacques's post.
Álvaro.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] rotate board
I only use 2 random numbers per point, one for black and one for white. I
xor another random number indicating the side to move.
David
_
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] On Behalf Of Álvaro Begué
Sent: Wednesday, December 19, 2007 4:15 AM
To: computer-go
Subject: Re: [computer-go] rotate board
Say you represent the content of each point with 0 for empty, 1 for black
and 2 for white. Start by creating a table of 19x19x3 random 64-bit numbers.
unsigned long long zobrist_table[19][19][3];
...
unsigned long long zobrist_key=0;
for(int row=0;row19;++row){
for(int col=0;col19;++col){
int point_content = board[row][col];
zobrist_key ^= zobrist_table[row][col][point_content];
}
}
The result is the zobrist key. In practice, you would make the zobrist key
part of your representation of the board, and when you modify the board, you
just incrementally update the zobrist key. Just remember that when you
change the content of a point,
new_zobrist_key = old_zobrist_key ^
zobrist_table[row][col][old_point_content] ^
zobrist_table[row][col][new_point_content];
Get that working first and then reread Jacques's post.
Álvaro.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
On Dec 19, 2007 9:27 AM, David Fotland [EMAIL PROTECTED] wrote: I only use 2 random numbers per point, one for black and one for white. I xor another random number indicating the side to move. What about ko? I use another number for points that are illegal due to ko. I think I define a hash key indicating illegal for black and another as illegal for white, but that's not needed ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
Yes, you can set all the values in the table that correspond to empty points to 0 or, equivalently, only have 2 numbers per point. Actually, that's what our code does too. But that's a very minor optimization, and I think the concept is easier to understand without it. On Dec 19, 2007 9:33 AM, Jason House [EMAIL PROTECTED] wrote: On Dec 19, 2007 9:27 AM, David Fotland [EMAIL PROTECTED] wrote: I only use 2 random numbers per point, one for black and one for white. I xor another random number indicating the side to move. What about ko? I use another number for points that are illegal due to ko. I think I define a hash key indicating illegal for black and another as illegal for white, but that's not needed ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
I actually have a routine in Lazarus that rotates a full board. It's called transformBoard() and it takes 2 arguments - a board to rotate and a transformation (0 through 7) and returns a new rotated board. I don't use it much except for debugging or stuff done at the root, because there are faster ways to do things. I also have a routine called canHash() which returns a canonical hash of the board by trying all 8 transformations and returning the lowest valued one. It is more efficient (but not efficient) because it doesn't actually produce a new board - it just builds 8 hashes of the board from scratch without touching anything.This routine is only used at the root for storing opening book moves. You can use zobrist hashing for maintaining all 8 keys incrementally, but you probably need a fairly good reason to do so. Incrementally updating of 1 key is almost free, but 8 might be noticeable if you are doing it inside a tree search or play-outs. It depends on how fat or lean your program is. Even 8 keys may not be noticeable if your program does a lot of work at each move (or an end nodes.)If you are not, then it doesn't really matter how you do it. I typically have 2 routines for everything - I have a slow_make() and a fast_make() and the fast_make() doesn't care about superko (although it checks for simple-ko) or anything that fast play-outs doesn't care about. So the fast make doesn't even try to update zobrist keys. - Don Ben Lambrechts wrote: Hi all, I am planning a fuseki database. Now I got the following problem: how to rotate/mirror the board for a unique representation. $$c $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . 5 . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ $$c $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . 5 . . . . . . . . . . | $$ | . . X , . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . O . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ Both are the same board, but has anyone made an algorithm that rotates the board or an area of the board in a unique way? I don't need the move order, just the snapshot of the board. Ben ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
Another thing about Zobrist hashes... after you select the canonical hash, you will end up with a non-uniform distribution. If this value is going to be used in binary tree, you may wish to swap the low-order bits with the high-order bits to keep the tree more balanced. On Dec 19, 2007 10:44 AM, Don Dailey [EMAIL PROTECTED] wrote: I actually have a routine in Lazarus that rotates a full board. It's called transformBoard() and it takes 2 arguments - a board to rotate and a transformation (0 through 7) and returns a new rotated board. I don't use it much except for debugging or stuff done at the root, because there are faster ways to do things. I also have a routine called canHash() which returns a canonical hash of the board by trying all 8 transformations and returning the lowest valued one. It is more efficient (but not efficient) because it doesn't actually produce a new board - it just builds 8 hashes of the board from scratch without touching anything.This routine is only used at the root for storing opening book moves. You can use zobrist hashing for maintaining all 8 keys incrementally, but you probably need a fairly good reason to do so. Incrementally updating of 1 key is almost free, but 8 might be noticeable if you are doing it inside a tree search or play-outs. It depends on how fat or lean your program is. Even 8 keys may not be noticeable if your program does a lot of work at each move (or an end nodes.)If you are not, then it doesn't really matter how you do it. I typically have 2 routines for everything - I have a slow_make() and a fast_make() and the fast_make() doesn't care about superko (although it checks for simple-ko) or anything that fast play-outs doesn't care about. So the fast make doesn't even try to update zobrist keys. - Don Ben Lambrechts wrote: Hi all, I am planning a fuseki database. Now I got the following problem: how to rotate/mirror the board for a unique representation. $$c $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . 5 . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ $$c $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . 5 . . . . . . . . . . | $$ | . . X , . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . O . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ Both are the same board, but has anyone made an algorithm that rotates the board or an area of the board in a unique way? I don't need the move order, just the snapshot of the board. Ben ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
Excellent idea Chris! Of course you could also hash the hash! But then we are talking about using even more CPU time. - Don Chris Fant wrote: Another thing about Zobrist hashes... after you select the canonical hash, you will end up with a non-uniform distribution. If this value is going to be used in binary tree, you may wish to swap the low-order bits with the high-order bits to keep the tree more balanced. On Dec 19, 2007 10:44 AM, Don Dailey [EMAIL PROTECTED] wrote: I actually have a routine in Lazarus that rotates a full board. It's called transformBoard() and it takes 2 arguments - a board to rotate and a transformation (0 through 7) and returns a new rotated board. I don't use it much except for debugging or stuff done at the root, because there are faster ways to do things. I also have a routine called canHash() which returns a canonical hash of the board by trying all 8 transformations and returning the lowest valued one. It is more efficient (but not efficient) because it doesn't actually produce a new board - it just builds 8 hashes of the board from scratch without touching anything.This routine is only used at the root for storing opening book moves. You can use zobrist hashing for maintaining all 8 keys incrementally, but you probably need a fairly good reason to do so. Incrementally updating of 1 key is almost free, but 8 might be noticeable if you are doing it inside a tree search or play-outs. It depends on how fat or lean your program is. Even 8 keys may not be noticeable if your program does a lot of work at each move (or an end nodes.)If you are not, then it doesn't really matter how you do it. I typically have 2 routines for everything - I have a slow_make() and a fast_make() and the fast_make() doesn't care about superko (although it checks for simple-ko) or anything that fast play-outs doesn't care about. So the fast make doesn't even try to update zobrist keys. - Don Ben Lambrechts wrote: Hi all, I am planning a fuseki database. Now I got the following problem: how to rotate/mirror the board for a unique representation. $$c $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . 5 . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ $$c $$ +---+ $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . 5 . . . . . . . . . . | $$ | . . X , . . . . . , . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . , . . . . . , . . . . . , . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . O . . . . . , . . . . . O . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ +---+ Both are the same board, but has anyone made an algorithm that rotates the board or an area of the board in a unique way? I don't need the move order, just the snapshot of the board. Ben ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
It's also possible to select hash keys such that transformations of the board's key is the same as recomputing the key for a symmetrical board position. This will be *much* faster. I came up with a scheme to do this and documented it on my website, but haven't actually implemented it yet. I can't find your website. Can you give me a link? - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
The basic idea is this: 90 degree rotation (to the right) is represented as a circular shift (to the right) by 1/4 of the key length. mirroring the board (swap left and right) is done as reversing the order of the bits in the key. Distinct hash values around the board would have to share the same rules. Picking a somewhat arbitrary example (on 19x19), here's some candidate keys (kept simple for manual typing) A2 = 0x 01 02 03 04 B19 = 0x 04 01 02 03 T18 = 0x 03 04 01 02 U1 = 0x 02 03 04 01 T2 = 0x 20 c0 40 80 B1 = 0x 80 20 c0 40 A18 = 0x 40 80 20 c0 U19 = 0x c0 40 80 20 Points on lines of symmetry (such as C3 with 4 equivalent points or the unique tengen) need more care with how they're selected). That's the same system I used in my first Go program, and it appears to also be the same as what is in the paper that Remi linked. I didn't use it for full-board hashes, I used it for patterns. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
Hi, I have not had time to study it in details, but I found this: http://fragrieu.free.fr/zobrist.pdf A Group-Theoretic Zobrist Hash Function Antti Huima September 19, 2000 Abstract Zobrist hash functions are hash functions that hash go positions to fixed-length bit strings. They work so that every intersection i on a go board is associated with two values Bi and Wi. To hash a position, all those values of Bi are XORed together that correspond to an intersec- tion with black stone on it. Similarly, all Wi’s are XORed together for those intersections that have a white stone. Then the results are XORed together. We present a Zobrist hash function with the extra property that if z is the hash value of a position p, then the values z′ for the positions p′ that are obtained from p by exchanging the colors, by rotating the position and my mirroring can be efficiently calculated from z alone. Still, z and z′ are different. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] rotate board
This should help: http://computer-go.org/pipermail/computer-go/2007-February/thread.html#8653 Erik On Dec 19, 2007 5:58 PM, Rémi Coulom [EMAIL PROTECTED] wrote: Hi, I have not had time to study it in details, but I found this: http://fragrieu.free.fr/zobrist.pdf A Group-Theoretic Zobrist Hash Function Antti Huima September 19, 2000 Abstract Zobrist hash functions are hash functions that hash go positions to fixed-length bit strings. They work so that every intersection i on a go board is associated with two values Bi and Wi. To hash a position, all those values of Bi are XORed together that correspond to an intersec- tion with black stone on it. Similarly, all Wi's are XORed together for those intersections that have a white stone. Then the results are XORed together. We present a Zobrist hash function with the extra property that if z is the hash value of a position p, then the values z′ for the positions p′ that are obtained from p by exchanging the colors, by rotating the position and my mirroring can be efficiently calculated from z alone. Still, z and z′ are different. Rémi ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
