Re: [computer-go] A superko paradox

[Erik van der Werf <E.vanderWerf@xxxxxxxxxxxxx>]

Heikki Levanto wrote:

> On Fri, Feb 11, 2005 at 09:25:31AM -0800, Peter Drake 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?
> >    
> Hashing has already been discussed, so I ignore that.
>
> You can at least sort the previous positions in 361 buckets by the
> number of stones on board, and check only against the right bucket. Most
> buckets will contain only one position.
>
> Doesn't speed up the storing of them, but if you need to check for
> repetition, it will be faster.
>
> -H
>  
No need to use the number of stones. You can simply use the lowest n 
bits of your hash to identify a 'bucket' which contains a counter for 
the number of times this (small) part of the hash has occurred on the path.

E.


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