Re: [computer-go] A superko paradox

[Peter Drake <drake@xxxxxxxxxx>]

Don -- thank, that's the sort of thing I was looking for.  Judging by 
other comments, though, it sounds like most people simply ignore the 
risk of false positives.  I think I'll do that for now, then add the 
special-case code you describe after I lose my first tournament to a ko 
error.  :-)

Fascinating!

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


On Friday, February 11, 2005, at 10:05  AM, Don Dailey wrote:

>    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

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