> While most ko detections are easy (if this point has never beencaptured, playing here can't violate ko), I occasionally have to check if the current configuration has occurred before. While most of these checks are quick Zobrist hash comparisons, occasionally two positions will hash to the same value. Thus, I have to store the entire board configuration with each move. This is a frequent, expensive operation to deal with a situation that is very rare, but can happen. Is there any way out of this?Use 64-bit hashes with optimal distribution. On average you would have to generate 1x10E18 positions before you encounter a collision.
This is overoptimistic, by a huge factor. A general purpose 64 bit hash (e.g. truncated SHA-1) is expected to generate a collision after about 2^32 = 4e9, not 1e18 hashes. AFAIK, the best that Zobrist hashing achieves is that it is about as good as a general purpose hash in a Go context, while costing litle to compute, especially for incremental board changes. I'd say that a 128 bit Zobrist hashing with random values has entirely negligible odds of generating a false collision; At 64 bits the odds are sizable, but probably negligible compared to some other concerns, like DRAM errors on a PC without ECC, or plain software bugs. François Grieu _______________________________________________ computer-go mailing list computer-go@xxxxxxxxxxxxxxxxx http://www.computer-go.org/mailman/listinfo/computer-go/