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 >>> 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 >
_______________________________________________ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
