Re: [computer-go] Kinds of Zobrist hashes
Hi! Thanks to all for replies. On Tue, Dec 08, 2009 at 09:30:47PM -0500, Eric Boesch wrote: You can mathematically prove the two systems are almost the same, so there's no need to test. Yes, this was my line of thought, but I wasn't sure if I'm not missing anything... Petr Pasky Baudis ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Kinds of Zobrist hashes
On Tue, Dec 08, 2009 at 09:30:47PM -0500, Eric Boesch wrote: You can mathematically prove the two systems are almost the same, so there's no need to test. Yes, this was my line of thought, but I wasn't sure if I'm not missing anything... If you ever decide to test which is faster, please post the results, I'm curious about how expensive the branch prediction miss is when using two values :-) Christian ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Kinds of Zobrist hashes
2009/12/9 Christian Nentwich christ...@modeltwozero.com: On Tue, Dec 08, 2009 at 09:30:47PM -0500, Eric Boesch wrote: You can mathematically prove the two systems are almost the same, so there's no need to test. Yes, this was my line of thought, but I wasn't sure if I'm not missing anything... If you ever decide to test which is faster, please post the results, I'm curious about how expensive the branch prediction miss is when using two values :-) I don't think there is any branching involved. When you place a stone, you add zobrist_table[point][color]. When you remove it, you subtract it. That's all you need to do. If you had a value for empty, you would have to add and subtract zobrist_table[point][color]-zobrist_table[point][empty]. Nothing else changes. Álvaro. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Kinds of Zobrist hashes
On Tue, Dec 8, 2009 at 8:37 PM, David Fotland fotl...@smart-games.com wrote: I use two values. I never even occurred to me to use three. I use one, it never occurred to me to use two :) At the time I'd never heard of Zobrist, but I used to use a single value for each point to look up Joseki. By using white-value = -black-value I could recognise the same joseki with colors inverted simply by using -value. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Kinds of Zobrist hashes
1. The 3 hashes: As Eric Boesch and Álvaro said, you can get the same codes as in the Black[], White[], Empty[] scenario using only 2 BlackXorEmpty[] and WhiteXorEmpty[] 2. What does make sense is making a difference between a POSITIONAL hash and a SITUATIONAL hash. The positional hash is the typical Zobrist hash of just the stones. The situational hash is the XOR of the positional hash and all moves forbidden by ko or superko (if any). I use another table of 361 64 bit codes for each forbidden move. At least, the tree search must have this in consideration, because the same stones but different legal moves, it is not the same position. I guess most programs do this one way or another. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Kinds of Zobrist hashes
On Wed, Dec 9, 2009 at 1:19 PM, Jacques Basaldúa jacq...@dybot.com wrote: 1. The 3 hashes: As Eric Boesch and Álvaro said, you can get the same codes as in the Black[], White[], Empty[] scenario using only 2 BlackXorEmpty[] and WhiteXorEmpty[] 2. What does make sense is making a difference between a POSITIONAL hash and a SITUATIONAL hash. The positional hash is the typical Zobrist hash of just the stones. The situational hash is the XOR of the positional hash and all moves forbidden by ko or superko (if any). I use another table of 361 64 bit codes for each forbidden move. At least, the tree search must have this in consideration, because the same stones but different legal moves, it is not the same position. You can take this further and say that if it's the same stone configuration, the same legal moves but a different set of visited stone configurations, it is not the same position. The legal moves might be the same now, but they might be different after I perform a particular move. I usually understand that the Zobrist key just hashes the stone configuration, and I have to mess with it if I want to add more information (side to move, ko...). Álvaro. I guess most programs do this one way or another. 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/
[computer-go] Kinds of Zobrist hashes
Álvaro Begué wrote: The legal moves might be the same now, but they might be different after I perform a particular move. You are right. Looks like my solution is not perfect, but it works good enough. I have seen trouble, before I implemented it, because the transposition table identified the same position in different situations. My solution worked, but, as you say it may not be perfect. Anyway, it is good enough for ko and my version of superko is a simplification restricted to the last 8 moves. Basically, triple ko and double ko of a group with one eye are the only superko sequences I have seen in serious games. I though it was good, now I have added a remark to the source code just in case some weird behavior appears. Thanks. Jacques. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Kinds of Zobrist hashes
Hi! In most papers I've read, three-valued Zobrist hashes are used - per intersection, values for empty, black and white coloring [1]. I'm not clear on why is the empty value needed, however, shouldn't only black, white values work just fine? Is the hash behaving better with extra values for empty intersections? Has anyone measured it? [1] In pattern-matching, it is desirable to also use edge coloring. Thanks, Petr Pasky Baudis ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Kinds of Zobrist hashes
The empty value is not needed. In some games it's easier to have it because it can be a simplification - everything handled uniformly for instance and it can avoid a conditional branch but I don't think that is an issue with Go. - Don On Tue, Dec 8, 2009 at 5:49 PM, Petr Baudis pa...@ucw.cz wrote: Hi! In most papers I've read, three-valued Zobrist hashes are used - per intersection, values for empty, black and white coloring [1]. I'm not clear on why is the empty value needed, however, shouldn't only black, white values work just fine? Is the hash behaving better with extra values for empty intersections? Has anyone measured it? [1] In pattern-matching, it is desirable to also use edge coloring. Thanks, Petr Pasky Baudis ___ 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] Kinds of Zobrist hashes
On Tue, Dec 8, 2009 at 5:49 PM, Petr Baudis pa...@ucw.cz wrote: Hi! In most papers I've read, three-valued Zobrist hashes are used - per intersection, values for empty, black and white coloring [1]. I'm not clear on why is the empty value needed, however, shouldn't only black, white values work just fine? Is the hash behaving better with extra values for empty intersections? Has anyone measured it? You can mathematically prove the two systems are almost the same, so there's no need to test. For simplicity, suppose you're doing a 3-color hash of just hashing two intersections, and your Zobrist values are b1, w1, e1, b2, w2, and e2 (where e.g. e1 means the first intersection is empty and b2 means the second intersection is black). This is equiavlent to using the Zobrist values b1' = (b1 xor e1), w1' = (w1 xor e1), e1' = 0, b2' = (b2 xor e2), w2' = (w2 xor e2), e2' = 0, and then when you're finished, xoring the result with (e1 xor e2). So a 3-color Zobrist with one set of constants is equivalent to a 2-color Zobrist (and zero for empty) with a different set of constants, plus a constant. Assuming your Zobrist values are random, the random 3-color Zobrist is equivalent to a random 2-color Zobrist (failing to hash the empty squares) plus a random constant. [1] In pattern-matching, it is desirable to also use edge coloring. Thanks, Petr Pasky Baudis ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Kinds of Zobrist hashes
I use two values. I never even occurred to me to use three. David -Original Message- From: computer-go-boun...@computer-go.org [mailto:computer-go- boun...@computer-go.org] On Behalf Of Petr Baudis Sent: Tuesday, December 08, 2009 2:50 PM To: computer-go@computer-go.org Subject: [computer-go] Kinds of Zobrist hashes Hi! In most papers I've read, three-valued Zobrist hashes are used - per intersection, values for empty, black and white coloring [1]. I'm not clear on why is the empty value needed, however, shouldn't only black, white values work just fine? Is the hash behaving better with extra values for empty intersections? Has anyone measured it? [1] In pattern-matching, it is desirable to also use edge coloring. Thanks, Petr Pasky Baudis ___ 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/
