> Btw does anyone have a good initialization vector for the Zobrist table?
The obvious thing to try is random numbers. Another idea is turning your
Zobrist key into CRC64, which I think is what you get if you generate your
numbers like this:
#include <cstdio>
int main() {
unsigned long long const P = 0x42F0E1EBA9EA3693ull;
unsigned long long h = P;
for (int i = 0; i < 1000; ++i) { // Or as many as you need
std::printf("%016llx\n", h);
h = (h & 0x8000000000000000ull) ? (h << 1) ^ P : (h << 1);
}
}
Álvaro.
On Fri, Oct 16, 2015 at 9:36 AM, Gonçalo Mendes Ferreira <go...@sapo.pt>
wrote:
> Hmmm, that's interesting but for random playouts seems a bit overkill. In
> a random playout kos will only consistently happen if they are the last
> legal positions in the board, at which point it might be better just
> waiting for a few more plays, reaching the max depth and calling the score
> as it is. Testing simple kos should be faster too. Did you benchmark the
> difference between your method and just prohibiting play at the last eaten
> position (if one stone only)? What max depth (if any) did you use to limit
> the playouts?
>
> For hashing I use 64 bit Zobrist hashes of the board contents without
> last played/eaten information, so it is not changed by passing. On
> collision I memcmp the whole board; if I didn't play legality would be off
> in false eyes, kos, suicides, etc and I store that in the node statistics.
> Btw does anyone have a good initialization vector for the Zobrist table?
>
> Gonçalo
>
> On 16/10/2015 13:50, Ben Ellis wrote:
>
>> My go playing program mostly just does random play outs so I don't claim
>> to
>> be an expert, but I check for super KO in my go program and it doesn't
>> seem
>> to slow it down too much. I use the same algorithm for checking for simple
>> KO as well.
>>
>> *This doesn't catch 100% of super KO but it is good enough to prevent
>> looping in your play-outs.*
>>
>>
>> From memory, the high-level algorithm,
>>
>> At the start of the play out, start with
>> - HashSet of board hashes
>> - HashSet of board intersections (pre-populated with all board
>> intersections)
>>
>> After each move has been played and captured stones removed,
>>
>> 1. If the played intersection has not been played on before,
>> - empty the board hashes set. O(1)
>>
>> 2. If any stones were captured and the intersection has not been played
>> before,
>> - Generate hash O(1)
>> - Insert hash into set of board hashes. O(1)
>>
>> 3. If the intersection has been played on before,
>> - Generate hash O(1)
>> - Insert hash into set of board hashes and check for duplicate O(1)
>> - If duplicate, KO or super KO detected O(1)
>>
>> 4. Remove intersection from set of intersections not yet played. O(1)
>>
>> Conditions at 2 and 3 are infrequent and tend to only happen in the end
>> game.
>>
>> Zobrist hash is common I'm not sure of any alternatives.
>>
>> If you want to check for all moves that would result in a KO or super KO,
>> you can iterate through all the empty intersections that have already been
>> played (there usually aren't many unless a big dragon is captured), and
>> see
>> if they would cause a duplicate hash.
>>
>> I'm sure someone more academic than me on this list will be able to pick
>> plenty of holes out of this :)
>>
>>
>> On 31 August 2015 at 09:18, <valky...@phmp.se> wrote:
>>
>> I once tried to use 32bit hashes only. It might work for super ko
>>> detection, but if you use it for transposition detection storing a lot of
>>> poisitions you will get collisions now and then. So my reasoning is: if
>>> 32
>>> bits almost works then using another 32 bits will work.
>>>
>>> Best
>>> Magnus
>>>
>>>
>>> On 2015-08-31 06:26, Minjae Kim wrote:
>>>
>>> Is 64 bits really enough?
>>>>
>>>> I may be wrong but there are 3^361 possible board positions in 19x19.
>>>> log2(3^361) gives me 572.171..., which means I need at least 573 bits
>>>> to record all possible board positions. This still doesn't mean that a
>>>> 2048 bit Zobrist hash for example will never collide for a 19x19
>>>> board, but the odds will be significantly lesser.
>>>>
>>>> Do you have some source about the probability of Zobrist hash
>>>> collision on a go board for different bit string sizes?
>>>>
>>>> On Mon, Aug 31, 2015 at 12:37 PM, Peter Drake <dr...@lclark.edu>
>>>> wrote:
>>>>
>>>> 64 bits seems to be enough. As I understand it, the convention is to
>>>>
>>>>> simply _ignore_ the possibility of collisions; you're more likely to
>>>>> have a hardware error.
>>>>>
>>>>> On Sun, Aug 30, 2015 at 8:27 PM, Minjae Kim <xive...@gmail.com>
>>>>> wrote:
>>>>>
>>>>> To my understanding, you need a sufficiently large bitstring to
>>>>> minimize possible hash collisions when using Zobrist hashing. When a
>>>>> hash collision does occur, it can possibly generate an illegal move.
>>>>> What is an acceptable size of the hash bitstring for a 19x19 board?
>>>>>
>>>>> On Mon, Aug 31, 2015 at 10:52 AM, Jason House
>>>>> <jason.james.ho...@gmail.com> wrote:
>>>>>
>>>>> There are longer cycles that can occur but I have never encountered
>>>>> any that didn't naturally resolve themselves in the playout.
>>>>>
>>>>> Zobrist having is cheap to compute (one xor if no stones were
>>>>> captured). Comparing the resulting number against the others is also
>>>>> cheap. The hash is also helpful for handling transpositions in the
>>>>> search tree.
>>>>>
>>>>> https://en.m.wikipedia.org/wiki/Zobrist_hashing [1]
>>>>>
>>>>> On Aug 30, 2015 9:17 PM, "Minjae Kim" <xive...@gmail.com> wrote:
>>>>>
>>>>> Yes, but to 'remember' the prior board state, doesn't the program
>>>>> have to store the whole board position per every turn by whatever
>>>>> means including Zobrist hashing that you suggested?
>>>>>
>>>>> After that, the program has to search whether the current position
>>>>> matches any of the previous ones. You said 3 is enough for triple
>>>>> kos, but as far as I know aren't there some rare repeating positions
>>>>> with a cycle longer than 3?
>>>>>
>>>>> But anyway solving the problem this way seems too expensive to me.
>>>>> 2015. 8. 31. 오전 9:59에 "Jason House"
>>>>> <jason.james.ho...@gmail.com>님이 작성:
>>>>>
>>>>> Triple ko can be detected by remembering the prior three board
>>>>> states. A zorbist hash value should be good enough to detect a
>>>>> repeat.
>>>>> On Aug 30, 2015 8:46 PM, "Minjae Kim" <xive...@gmail.com> wrote:
>>>>>
>>>>> I finally managed to build a program that can produce a sequence of
>>>>> random legal go moves. One problem I found recently is that it
>>>>> rarely never ends a game because of triple ko, especially on small
>>>>> boards.
>>>>>
>>>>> One possible solution would be saving every board position that has
>>>>> occurred and searching for a match before generating a move. But
>>>>> this doesn't sound like an efficient solution at all.
>>>>>
>>>>> How do you handle this problem?
>>>>>
>>>>> Also as a side question, white constantly seems to have a better
>>>>> winning rate in any board size larger than 9x9 with komi greater
>>>>> than 6 under area scoring in completely random games; is this
>>>>> natural?
>>>>>
>>>>
> _______________________________________________
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
_______________________________________________
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go
