[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [computer-go] A superko paradox

Don wrote:
> The solution is based on the fact that these collisions are very rare
> if you are using a reasonable hash key size.  Since this is a very
> rare situation, you only have to recreate the positions you have
> already encountered.  Presumably you have stored the list of moves
> that get to the current position.  Initialize the board to the
> starting position and play back the move list, comparing each new
> position encountered with the current position.   
> 
> This is very expensive when it happens, but it should be a truly rare
> situation and amortized over the computing time of your program it
> should be unnoticeable.    And there will not be the overhead of storing
> every position encountered.  

There are two things I don't understand here.

1. This code can be triggered either by a genuine repetition or a hash
   collision. You don't know beforehand which it is so you have to do
   the full check in both situations. While repetitions may be
   infrequent (I take for granted that length 2 cycles are detected by
   a cheap simple ko test) I doubt that they count as "truly rare" in
   contrast to hash collisions.

2. Why compare each new position encountered and not only the ones
   where the hashes match?

But it's not really important. Like everybody else I recommend using
64-bit Zobrist hashes and forget about collisions. They won't happen.

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