Re: Fwd: [computer-go] Zobrist hashing with easy transformation comparison
On Wed, 2007-02-14 at 10:45 +0100, Erik van der Werf wrote:
From: Nic Schraudolph [EMAIL PROTECTED]
Date: 12 February 2007 10:45:50 GMT+11:00
To: computer-go computer-go@computer-go.org
Subject: Re: [computer-go] Zobrist hashing with easy transformation
comparison
did you read Anti Huima's paper? The idea looks similar, but
unfortunately it does not work. I provided a proof of the defect
on this list (end of 2002 if I remember well). It's not that easy
to get a working scheme. In fact there is only one combination
with 8 chunks of data. In 2002 I exchanged a lot of email with
Nici Schraudolph, and we found the right scheme. We wanted to
write a paper, but we did not (it takes time, and I had not that
much time - mathematic and computer go is just a hobby for me).
The bad news: a colleague here has proven that no standard
segmented Zobrist hash can work in less than 8 chunks - and that's
without color symmetry. That makes 16 chunks with color, not very
attractive!
The good news: I've developed a defect-free scheme including color
symmetry that works in only 6 chunks, and has a very efficient way
to compute a canonical hash (that is: without having to compute all
8/16 candidates). No contradiction to the above proof as it's not a
standard Zobrist hash. This is provably the minimal scheme.
Do sit on me - I really need to finish writing this up! In the
meantime, as long as you don't need color, the 8-chunk scheme Erik
posted works fine. Nick's (if I understood it correctly - I took
r_x, r_y, r_xy to mean reflection about vertical, horizontal, and
diagonal axis, respectively) has a problem though: for all
positions p, r_x(r_xy(r_x(r_xy(p == p. Huima's scheme can't
work because it's really a 4-chunk scheme doubled up for color
symmetry.
Me too:
#define T_X(h) \
( (((h) 0x) 1 ) \
| (((h) 0x) 1 ) \
)
/* { 2,3,0,1,6,7,4,3} */
#define T_Y(h) \
( ( ((h) 0x) 2 ) \
| ( ((h) 0x) 2 ) \
)
/* { 3,1,2,0,7,5,6,4} */
#define T_P(h) \
( ( ((h) 0x) ) \
| ( ((h) 0x) 3 ) \
| ( ((h) 0x) 3 ) \
)
/* { 0,2,1,3,4,6,5,7} */
#define T_Q(h) \
( ( ((h) 0x) ) \
| ( ((h) 0x) 1 ) \
| ( ((h) 0x) 1 ) \
)
#include stdio.h
#include stdlib.h
int main()
{
unsigned long val0, val1, val2, val3;
unsigned aa,bb,cc;
unsigned at,bt;
char * legend[4] = { (X) ,(Y) ,(P) , (Q) };
val0 = 0x12345678;
at = bt = 4;
for (aa=0; aa 4; aa++ ) {
switch(aa) {
case 0:val1 = T_X(val0); break;
case 1:val1 = T_Y(val0); break;
case 2:val1 = T_P(val0); break;
case 3:val1 = T_Q(val0); break;
}
for (bb=0; bb 4; bb++ ) {
if (bb==aa) continue;
if (bb bt) at =4;
switch(bb) {
case 0:val2 = T_X(val1); break;
case 1:val2 = T_Y(val1); break;
case 2:val2 = T_P(val1); break;
case 3:val2 = T_Q(val1); break;
}
for (cc=0; cc 4; cc++ ) {
if (cc==bb) continue;
switch(cc) {
case 0:val3 = T_X(val2); break;
case 1:val3 = T_Y(val2); break;
case 2:val3 = T_P(val2); break;
case 3:val3 = T_Q(val2); break;
}
if (aa!=at) fprintf(stdout,%8lx -%s- %8lx
,val0,legend[aa],val1);
else fprintf(stdout, -%s-
,legend[aa], val1);
if (bb!=bt) fprintf(stdout, -%s- %8lx
, legend[bb],val2);
else fprintf(stdout, -%s-
, legend[bb]);
fprintf(stdout, -%s- %8lx\n,legend[cc],val3);
at = aa; bt = bb; ;
}
}
}
exit(0);
}
/**
Legend: T_X() and T_Y() transform the hash value, when flipping the X
and Y coordinates; T_P() and T_Q()
flipping over the diagonals. The rest is trivial.
HTH,
AvK
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Zobrist hashing with easy transformation comparison
Hi Erik And what distinguishes database look up from things like transposition table look up? Why wouldn't one use database look up during tree search? The interest in rotation/mirror. In database search, what is good for a position is good for the mirror/rotation. In tree search, rotation of the full board does not happen, and if it does (in a very simple position) its pointless to detect because it is not the same position. 4. The analysis based on uniform distributions are fundamentally flawed because the move sequences are not random in go, particularly, the BWBWBW sequence can only be avoided by pass moves which do not occur in real games globally before the end of the game. So? Of course. The most important superko that really happens in strong games is triple ko. Detecting triple ko with probability=1 and a 32 bit hash is not a trivial question. And it requires B keys to have some difference with W keys. Note that to be _sure_ that a move is legal, you only have to check 6x32 bit keys. That would be impossible if the hashes were pure random. You simply cannot control any combination of 19x19x2=722 hashes of length 6, but you can control BWBWBW even of length 7. Since the test is faster than any another and is also, unlike the others, with error probability=0 it is simply the best. Of course, it does not consider board repetitions of longer cycles. I have searched for (the possibility of) such cycles in my 50K games database and did not find any. I would love to see a game where both players are at least shodan, in which a superko other than triple ko limits the legal options. If someone has such a game, please post it. I'm speculating here because I seem to be missing some context, but AFAICS almost any Go-specific application will have more legal moves hash keys than bits for the hash. Of course. That's because full global search is intractable. But local search with 16 empty cells (which can be either B or W, and therefore you only have 32 keys) is not. That's what I mean when I say when it makes sense. Again, I do use 64 bit hashes. And my favorite: if the hash calculation is a major factor in the performance of your program, you should seriously consider adding some knowledge. We have seen this when talking about programming language. Each time someone cares about details and builds programs that are optimized from the day of their birth, they are: a. Dirty and hard to maintain. (IMO only patched programs are hard to maintain and they are patched because important issues were thought too late.) b. Caring about stupid issues == ignoring Big Algorithmic Improvements. (IMO If you don't really care about details you don't really control the big picture. And more important, you only have to do it once, if you do it well. That will give you a lot of time for thinking about algorithms.) Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Zobrist hashing with easy transformation comparison
Erik van der Werf wrote: And then we get another small questions with a dangerous answer... 1. What makes a question big or small is not a personal preference, but the number of millions times it happens during a game. 1a. Database lookup. Happens very few times (Unfortunately, I must say, because I like the knowledge integration part and I think it is one of my strong points.) 2a. Local search + legal moves identification (see superko) This happens billions of times per hour of go computing. Therefore, finding optimal solutions for 1a is a small question and for 1b its is not a small question at all. Of course, if your program is hyper-knowledge driven or does not search, this may be different. 2. Using an unnecessarily big hash key slows down the program. On a 32 bit platform, for using a 64 bit key you have to choose between bad (2x32) and worse (FPU 64 bit integers). Due to this slow down, you will fail to complete searches you could have done with a smaller hash. Therefore, the program may suffer more from code obesity than from collisions. Don't take this as if I didn't use 64 bit keys. I do. But only when it is a good idea. 3. In the cases where a 32 key is enough, a local search with 32 stones or detecting superko, it works with error=0 and therefore, it is better than any hash size. 0 is smaller than 2^-64. 4. The analysis based on uniform distributions are fundamentally flawed because the move sequences are not random in go, particularly, the BWBWBW sequence can only be avoided by pass moves which do not occur in real games globally before the end of the game. And finally a question: Why do you admit that having two identical hashes is a flaw (which is obvious) and do not admit that having 32 hashes not forming a base is not? When you have 31 independent hashes, the probability that a new key forms a base is 1/2. If it does, you can use this set with error probability = 0, if it doesn't you will get collisions because the new key is not independent. It's the same as having two identical keys. If the key is dependent, reject it and get another random key. That does not change any other statistical properties. It could have been a random set, many sets pass as they are others get some correction. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Zobrist hashing with easy transformation comparison
On 2/12/07, Jacques Basaldúa [EMAIL PROTECTED] wrote: Erik van der Werf wrote: And then we get another small questions with a dangerous answer... 1. What makes a question big or small is not a personal preference, but the number of millions times it happens during a game. Can't take a joke? IMO informed hash key generation is interesting from an academic viewpoint, and a fun exercise. However, in my experience anything to do with this subject tends to lead only to relatively small over-all improvements (unless you have a crappy implementation to start with), and when not used with great care and a good understanding of the consequences of the domain-specific optimizations then it easily weakens the performance. To give an example, if you optimize your keys for global tree-search (using, e.g., the BCH construction), I would not be surprised if they perform sub-par on things like opening book construction, or shape hashing. 1a. Database lookup. Happens very few times (Unfortunately, I must say, because I like the knowledge integration part and I think it is one of my strong points.) And what distinguishes database look up from things like transposition table look up? Why wouldn't one use database look up during tree search? 2a. Local search + legal moves identification (see superko) This happens billions of times per hour of go computing. Forget about using hashes for superko/legal move detection, it's a non-issue. For this you should only use hashes as a last resort. Therefore, finding optimal solutions for 1a is a small question and for 1b its is not a small question at all. Of course, if your program is hyper-knowledge driven or does not search, this may be different. 2. Using an unnecessarily big hash key slows down the program. Hardly. IMO, if the hash calculation is a major factor in the performance of your program, you should seriously consider adding some knowledge. In Migos I had 96-bit hashes and the update time was never an important factor in the performance. Moreover, I could recompute all relevant symmetrical hashes from scratch whenever needed without severely hurting the performance. On a 32 bit platform, for using a 64 bit key you have to choose between bad (2x32) and worse (FPU 64 bit integers). Due to this slow down, you will fail to complete searches you could have done with a smaller hash. Therefore, the program may suffer more from code obesity than from collisions. Don't take this as if I didn't use 64 bit keys. I do. But only when it is a good idea. And what fraction of your searches is affected by your new superior-strength hash keys? snip 0 is smaller than 2^-64. Thanks for sharing that :-) 4. The analysis based on uniform distributions are fundamentally flawed because the move sequences are not random in go, particularly, the BWBWBW sequence can only be avoided by pass moves which do not occur in real games globally before the end of the game. So? And finally a question: Why do you admit that having two identical hashes is a flaw (which is obvious) and do not admit that having 32 hashes not forming a base is not? I have no idea what you're talking about here. When you have 31 independent hashes, the probability that a new key forms a base is 1/2. If it does, you can use this set with error probability = 0, if it doesn't you will get collisions because the new key is not independent. It's the same as having two identical keys. If the key is dependent, reject it and get another random key. That does not change any other statistical properties. It could have been a random set, many sets pass as they are others get some correction. I'm speculating here because I seem to be missing some context, but AFAICS almost any Go-specific application will have more legal moves / hash keys than bits for the hash. Consequently for all practical purposes you will never be able to set up a complete independent set of hash keys, and in the rare case where you could do it (e.g., on a small board) you might just as well store the complete state as a hash. E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Zobrist hashing with easy transformation comparison
Please do. I will put it on a web page. But I need some time. My job keeps me very busy right now. But I'm not sure I will post the statistical analysis (it was almost ten hand writen pages, and I'm not sure I still have them). Have You performed an empirical test for collisions? No, analysis was analytic. I've used the scheme in different ways, and since I knew were was the defect I put extra code to protect from the defect. This proved to be usefull... I was able to catch collisions at low rate in practice, but this rate would have been unacceptable if I had not been able to detect them. The defect is as follow: if you have 2 different board configurations, the probability that they have the same hash key can be as low as 1/256 (for a 64-bit key) if the difference between the 2 configurations has self symmetries. Anti Huima's scheme had the same defect, except the probability was 1. That's why I've been able to isolate it: I always had collisions between the same positions, and it didn't depend on the way random bits were generated. Antoine ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Zobrist hashing with easy transformation comparison
On 2/10/07, Łukasz Lew [EMAIL PROTECTED] wrote: On 2/10/07, Antoine de Maricourt [EMAIL PROTECTED] wrote: If there is strong interest, I can post the scheme. Please do. Since Antoine claims there is only on solution I might as well post mine ;-) mirroring: [abcdefgh] - [hgfedcba] rotation: [abcdefgh] - [cdefghab] This scheme follows trivially from dividing the square in 8 triangular regions, and assigning each a letter. If you want to include color symmetry you need to change the operators (xor doesn't work any more) or increase the number of segments. Erik This is one out of the 3 possibilities that were left once we eliminated obvious defects (the ones the original proposal by Anti Huima suffered). However, if my analysis was right, this scheme was the one that introduces the biggest weakness in the key. That's why I didn't keep it. Antoine. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Zobrist hashing with easy transformation comparison
On 2/10/07, Łukasz Lew [EMAIL PROTECTED] wrote: On 2/10/07, Antoine de Maricourt [EMAIL PROTECTED] wrote: If there is strong interest, I can post the scheme. Please do. Since Antoine claims there is only on solution I might as well post mine ;-) mirroring: [abcdefgh] - [hgfedcba] rotation: [abcdefgh] - [cdefghab] This scheme follows trivially from dividing the square in 8 triangular regions, and assigning each a letter. If you want to include color symmetry you need to change the operators (xor doesn't work any more) or increase the number of segments. Erik ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Zobrist hashing with easy transformation comparison
As Antoine de Maricourt says, this weakens the key. I think it is a serious problem and it is a dangerous answer to a small question. I compute hashes and patterns for database lookup eight at a time, which is faster (much more optimizable) than one after the other. Then I also use the smallest as the canonical and simply discard the others. Since database lookup is so fast that's not a problem at all. Other situations where hashes are needed do not require verifying rotations, so the advantage of Nick's idea is very small (IMO). But the question is: Does someone do the opposite, i.e. playing with the hash values to make then *stronger*? Even with 32 bit hashes, triple ko can be detected with probability = 1 for any sequence of alternating BWBW or WBWB of length less than 8. (Tripe Ko is a sequence of length 6) I don't know if that is published. In fact, unless you have a computer allowing to store a 2^64 bit table, strong collision analysis can only be done for 32 bit hashes (With my hardware where I can manage a 4 gigabit table decently. Checking that all 4x4x2(colors) squares in a 19x19 array form a base and replacing the invalid hashes as needed takes about 15 hours on a P4D at 3.4GHz) Of course, once you have a strong 32 bit hash set you can fill the higher 32 bits with random bits to have a 64 bit set. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Zobrist hashing with easy transformation comparison
On 2/10/07, Jacques Basaldúa [EMAIL PROTECTED] wrote: snip But the question is: Does someone do the opposite, i.e. playing with the hash values to make then *stronger*? And then we get another small questions with a dangerous answer... Just search the archive for BCH construction. E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Zobrist hashing with easy transformation comparison
On 2/10/07, Antoine de Maricourt [EMAIL PROTECTED] wrote: Hi, did you read Anti Huima's paper? The idea looks similar, but unfortunately it does not work. I provided a proof of the defect on this list (end of 2002 if I remember well). It's not that easy to get a working scheme. In fact there is only one combination with 8 chunks of data. In 2002 I exchanged a lot of email with Nici Schraudolph, and we found the right scheme. We wanted to write a paper, but we did not (it takes time, and I had not that much time - mathematic and computer go is just a hobby for me). After having the right scheme, the tricky part is to perform a statistical analysis: unfortunately introducing constraints to deal with symetries weakens the hash key. The probability of collision becomes non uniform and depends on the board configuration. In short: if you take two different random board configurations, then the probability that they have the same key becomes higher if one of the configuration has self symetries. If there is strong interest, I can post the scheme. Please do. But I'm not sure I will post the statistical analysis (it was almost ten hand writen pages, and I'm not sure I still have them). Have You performed an empirical test for collisions? Best, Łukasz Lew Antoine. ___ 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] Zobrist hashing with easy transformation comparison
Sorry for posting then, I didn't realize that it had been tried. I may work through the problem and try to get it to work in order to fully understand why it in fact does not work. If by some miracle I manage to get something working with a collision rate of 1/(2^61) I'll certainly post it. Thanks for the info. - Nick On 2/9/07, Erik van der Werf [EMAIL PROTECTED] wrote: Nick, The basic idea of what you're describing is well known. It was first published by Antti Huima several years ago. Unfortunately though, his implementation was flawed. I didn't check your code but likely it suffers from a similar defect. It is possible to fix the defects in Huima's scheme. If you ignore colour symmetry it's relatively easy to find a defect-free xor-based scheme that works with 8 segments. The more interesting part is in finding the minimal number of segments, and then proving correctness. Nic Schraudolph has done some interesting work on this, but as far as I know he still hasn't published it. Maybe if we all sit on him we can finally get him to finish it :-) Erik On 2/9/07, Nick Apperson [EMAIL PROTECTED] wrote: Hey all, I was thinking about our conversation and i decided to design a zobrist class that allows for easy comparison to check and see if 2 different zobrist values are equivalent after a rotation etc... It updates the zobrist in such a way that it can transform them and after trying 8 possiblilities, it can determine if they are equal. There are actually quite a few optimizations that could be performed on it, but I just wanted to post the basic idea. See the following source code for the basic idea: http://www.nicholasapperson.com/computergo/zobrist.h Essentially it works so that it hashes the played stone as each of the rotated forms and stores that in each of the 8 bytes used. The bytes are arranged in an order such that flipping the 2 DWORDs results in the zobrist value for if there was a rotation in the x axis, flipping WORDs results in a reflection across the y axis and swapping bytes results in a reflection across the y=x line. Order obviously matters in the case of xy so the transformation is assumed to take place after the other reflections. For example: if we have 0x1234567890ABCDEF as a zobrist value, 0x90ABCDEF12345678 would be the zobrist of the position with a reflection across the x-axis Anyway, I'm sure there is a bug or two, but I wanted to get your alls thoughts. - Nick ___ 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/
