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 >> 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 >>>> >>> >>> _______________________________________________ >>> 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 >> > > > _______________________________________________ > Computer-go mailing list > Computer-go@computer-go.org > http://computer-go.org/mailman/listinfo/computer-go > -- Peter Drake https://sites.google.com/a/lclark.edu/drake/
_______________________________________________ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
