Re: [computer-go] A superko paradox

[Don Dailey <drd@xxxxxxx>]

   While most ko detections are easy (if this point has never been 
   captured, 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?

Peter,

Yes, there is a simple way to deal with this.   I assume that you have
a single global board and do not want to store intermediate boards.

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.  

- Don







   Peter Drake
   Assistant Professor of Computer Science
   Lewis & Clark College
   http://www.lclark.edu/~drake/

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

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