Re: [computer-go] Ko and transposition tables

[Evan Daniel <evanbd@xxxxxxxxx>]

On 5/11/05, Chris Fant <chrisfant@xxxxxxxxxxxxxxxxx> wrote:
> > > Using your notation, notice that the value F (which presumably
> > > represents a stone at some location) is no longer a factor in the
> > > final cumulative hash.  This means that the cumulative hash will be
> > > the same no matter where move 3 is played.  Isn't this a problem?
> >
> > Yes, that is a problem.  Thanks for pointing out that it was me who
> > was mistaken.  So a simple modification would be the following:
> >
> > NewCumHash = (OldCumHash<<1) ^ BoardHash
> 
> Unfortunately that has the undesirable effect of making move sequence
> a,b,c,d result in a different hash than c,b,a,d.  Hmm, back to the
> drawing board...

I'm confused as to what the goal here is.  Are we trying to construct
something that is different for each set of previous positions?  If
so, the above is desirable.  (Ie repeating the position with with just
a and b played is a superko violation in one case but not the other.)

If not, then what is the goal?

The above scheme also has the problem that old enough moves get
shifted off the end and thrown out, so only the 64 most recent moves
are relevant in a 64 bit hash, etc.  (And old moves impact fewer bits,
so they have less collision resistance).

On a related note, you might consider adding the zobrist numbers to
get a position hash and xoring positions together:

(A) ^ (A + B) ^ (A + B + C) ^ (A + B + C + D)

but that has the same playing order dependence.

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