Á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/
signature.asc
Description: This is a digitally signed message part
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/