I wrote a simple Bloom filter and I tried feeding it a sequence of random numbers (which is what Zobrist keys would look like if there are no repetitions), to see how many false positives I would get, with different values for k. I tried using 128 bytes, 256 bytes and 512 bytes. In every case. It looks like k=2 is certainly better than k=1, and overall I think 512 bytes with k=2 is probably what I would use (probability of a false positive is about .01 after 200 moves, and about .04 after 400 moves).
If you are interested in the details, I have some code and some graphs. Álvaro. On Thu, Oct 9, 2008 at 9:51 AM, Don Dailey <[EMAIL PROTECTED]> wrote: > Álvaro, > > I never tried it, but I once considered doing it. It's an intriguing > idea. Since speed is all important here I would probably try just a > single probe version (bloom filter with k = 1 where k is the number of > hash functions.) > > You have to clear the filter before each playout of course, but the > filter could be quite tiny, perhaps 256 - 1024 bytes for 9x9. One > would of course measure the trade-offs and also test k=2, etc. My > intuition is that k=1 is best for speed but it should be tested. > > There is a cost involved in just maintaining a Zobrist hash key and I > wonder if this is the greatest cost anyway? Even with the bloom filter > you have a lot of logic on top of an extremely simple move maker so I > never got motivated enough to try this. Plus, I didn't feel that it > would actually make the program stronger. > > In my programs, I don't maintain a key or do PSK in the playouts. I > have 2 versions of everything involving move generation. One make() > function tests for superko and builds a key, the other tries to be fast > and cheats. > > - Don > > > > On Thu, 2008-10-09 at 09:36 -0400, Álvaro Begué wrote: >> On Thu, Oct 9, 2008 at 9:26 AM, Don Dailey <[EMAIL PROTECTED]> wrote: >> > If you use zobrist hashing, it is probably not ridiculously slow to do >> > this. And if your play-outs are pretty heavy anyway, the cost will be >> > negligible as you say. >> >> Has anyone tried to use a Bloom filter ( >> http://en.wikipedia.org/wiki/Bloom_filter ) for this? It would very >> quickly tell you that most positions are not repetitions, and leave >> only a tiny fraction of positions to test in a deterministic way. >> >> Álvaro. >> _______________________________________________ >> 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/
