Re: [computer-go] A superko paradox

[David Weiss <dweiss51@xxxxxxxxx>]

--- Francois Grieu <fgrieu@xxxxxxxxxxxxxxxxx> wrote:

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

There are two different questions being addressed
here.

1.  For a given board position how many other board 
positions can be hashed before there is a false
match?

2. How many board positions can be hashed before
the same hash occurs for two different boards?

I haven't done the math, but I am guessing that the
10^18 number is for question 1, and the 10^9
number is for question 2.  I believe that Dr. Drake
was concerned with question 1 and so the chances of
a false positive are very low.  For other
applications,
such as joseki libraries, question 2 is more relevant.


		
__________________________________ 
Do you Yahoo!? 
The all-new My Yahoo! - Get yours free! 
http://my.yahoo.com 
 

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