Re: [computer-go] Ko and transposition tables

[Chris Fant <chrisfant@xxxxxxxxx>]

> > One option is to XOR all previous-board Zobrist hashes and store that
> > value in the table as well.  This would take care of #1 and #2 below.
> 
> I may have some misconceptions about Zobrist hashes, but this doesn't
> seem like it would work.  Suppose I play the move sequence A, B, C,
> D.  This produces the following sequence of Zobrist hashes:
> 
> A
> A xor B
> A xor B xor C
> A xor B xor C xor D
> 
> If I xor these four bit patterns together, I'll get B xor D.  In
> other words, only the stones that are on the board for an odd number
> of moves in the sequence will be taken into account.  Thus, an
> alternate sequence like E, B, F, D will look exactly the same.
> 
> I also don't see how this would take depth into account.

Yes, you have misconceptions.   

In a 128 bit Zobrist hash scheme, each point on the board has a random
128 bit number for each possible state that it could be in.  XOR all
the states together for each board position to get your hash value. 
Changing the state of a single point on the board completely changes
the hash (on average, half the bits will change).  So hashes A, B, C,
and D are unrelated to each other.  XOR-ing them together is not the
same as XORing only B and D together.  Once you understand this, it
should be clear that the depth is implicitly handled as well (except I
just realized that a pass is an exception to this since it does not
change the board).
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/