Re: [computer-go] A superko paradox

["Arend Bayer" <arend.bayer@xxxxxx>]

computer-go <computer-go@xxxxxxxxxxxxxxxxx> schrieb am 11.02.05 19:11:32:

>>>  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.

This is underoptimistic, by a huge factor. :)

Your number is only correct if you always compare with _all_ previous positions ever generated.
In Peter's situation, he will only be comparing with all previous board positions of one single game.
So he will be comparing with 100 positions on average. So you get one hash collision for
2^64/100 positions, which is s.thl like 2e17. So one hash collision per 1e15 games.

I think he can safely offer every user who encounters a hash collision a nice bottle of wine.

Arend




_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/