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
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
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
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
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
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
]
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
Á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
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
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
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
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
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
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
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
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
$$ +---+
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . . . . . . . . . . . . . |
$$ | . . . . . . . .
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
$$ +---+
$$ | . . . . . . . . . . . . . . . . . .
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
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
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){
: 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
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
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,
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
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
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
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
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
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
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
31 matches
Mail list logo
