Transposition table random numbers

[jdm64]

Didn't think about needing a key for pieces I'm holding. Would the following work:

index 0-768 has piece-type * square combinations
index 769 has side to move
index 770-801 has piece holding state

and still use XOR? So the initial key would be XOR of index 770-801. Then a piece placement would XOR that piece's key along with XOR the piece-type/square key. What happens to captured pieces? Would it just be XOR the piece-type/square key?

[hgm]

The scheme you propose makes pieces of equal type in the holdings distinguishable. E.g. Rook A and Rook B have different keys. So dropping Rook A would produce a different hash key from dropping Rook B on the same square, while logically the positions that result are equivalent. If you enforce a prescribed order of dropping, (within the same piece type), this is no problem, though. You just need a little more keys.

[hgm]

Yes, its been discussed here more than once. Maximum hamming distance between pairs of your 769 keys doesn't mean squat, because real board positions will have lots of those keys XORed together -- usually a dozen or more of them.

A very simple way to prove that Hamming distance "doesn't mean squat" is this:

- Take a set of 768 (or whatever) keys,, and make the Hamming distance as good as you can. Call the first 3 keys from the set A, B and C.
- Caluclate D = A^B^C
- Now XOR _every_ key in the set of 768 with D
- That will not change the Hamming distance between any pair of the keys; the hamming distance between A and B is just the number of one bits in A^B, and A'^B' = (A^D) ^ (B^D) = A^B ^ (D^D) = A^B. So the Hamming distance of the new set {A', B', C', ... } is still good.
- But the first three keys now satisfy A'^B'^C' = (A^D)^(B^D)^(C^D) = (A^B^C) ^(D^D^D) = D^D = 0.

So the new set will have a dependency between three keys, wich will lead to a disastrously high collision rate. E.g. if these were the keys for Pawns on e3, e4 and d4, you could not see the difference anymore between a single Pawn on e4, or two Pawns on e3 and d4.

[jdm64]

The scheme you propose makes pieces of equal type in the holdings distinguishable. E.g. Rook A and Rook B have different keys. So dropping Rook A would produce a different hash key from dropping Rook B on the same square, while logically the positions that result are equivalent. If you enforce a prescribed order of dropping, (within the same piece type), this is no problem, though. You just need a little more keys.

Well, how my piece placements currently go I always place the first piece of a type down because of how I search for a piece.

But back to your original idea. So use XOR for piece-type/square and then '+' for placing pieces. And to undo piece placement and get the original hash back I'd '-' the key -- right?

[bob]

And as I bolded in the quote above, there is no castling in my chess variant.

Don't worry about Bob. He never reads what you write, so repeating it a few more times will not help either...

And when there would be e.p. capture, like in orthodox Chess, one would need 8 keys (one for each file) to indicate it, not one, of course.

Why 8? You can only have one EP capture possibility in any single position...

[jdm64]

Yes, its been discussed here more than once. Maximum hamming distance between pairs of your 769 keys doesn't mean squat, because real board positions will have lots of those keys XORed together -- usually a dozen or more of them.

A very simple way to prove that Hamming distance "doesn't mean squat" is this:

- Take a set of 768 (or whatever) keys,, and make the Hamming distance as good as you can. Call the first 3 keys from the set A, B and C.
- Caluclate D = A^B^C
- Now XOR _every_ key in the set of 768 with D
- That will not change the Hamming distance between any pair of the keys; the hamming distance between A and B is just the number of one bits in A^B, and A'^B' = (A^D) ^ (B^D) = A^B ^ (D^D) = A^B. So the Hamming distance of the new set {A', B', C', ... } is still good.
- But the first three keys now satisfy A'^B'^C' = (A^D)^(B^D)^(C^D) = (A^B^C) ^(D^D^D) = D^D = 0.

So the new set will have a dependency between three keys, wich will lead to a disastrously high collision rate. E.g. if these were the keys for Pawns on e3, e4 and d4, you could not see the difference anymore between a single Pawn on e4, or two Pawns on e3 and d4.

Does this mean that my Genesis Chess will have high collision rates because pieces can be placed almost anywhere/anytime. Would it make the transposition table useless?

Besides the two rules below, every board combination should be legal (at least I think).

1) If number of pieces on the board is less than 3, then the pieces must be kings.
2) Both kings cannot be in check.

[hgm]

So use XOR for piece-type/square and then '+' for placing pieces. And to undo piece placement and get the original hash back I'd '-' the key -- right?

That would break the possibility to incrementally update the hash key, as +/- and XOR do not commute. The hash key would have to be the sum of all elementary keys, both for the on-board pieces and the holdings.

In that case the incremental update can be done by adding the keys for all pieces you place (i.e. the key for the to-Square of both drops and normal moves), and subtracting the key for the locations where you remove a piece (i.e. the holdings or from-square, and the captured piece):

hashKey += key[piece][to] - key[victim][to] - key[piece][from]

(where 'from' is the 65th square in case of drop moves).

For restoring the hash key you could subtract the same stuff, but it is of course more efficient to simply make a copy of the old one, and put it back.

[hgm]

Why 8? You can only have one EP capture possibility in any single position...

Nope. You can have an e.p. capture for any Pawn on the 4th/5th rank that is standing next to an enemy Pawn. That could be up to 5 (e.g. Black: a5, c5, d5, f5, g5).

The path leading to a position is not encoded in the hash key. That includes the double push through which the position was reached.

[bob]

Why 8? You can only have one EP capture possibility in any single position...

Nope. You can have an e.p. capture for any Pawn on the 4th/5th rank that is standing next to an enemy Pawn. That could be up to 5 (e.g. Black: a5, c5, d5, f5, g5).

The path leading to a position is not encoded in the hash key. That includes the double push through which the position was reached.

While I agree it is possible to have ambiguities, how often would you find the _exact_ same position, but with ep captures possible on different squares? I'd bet this can be ignored quite safely although I don't do it myself. But clearly for one position, there can only be one ep target possible, since the previous move must have been a single pawn push.

[AlvaroBegue]

While I agree it is possible to have ambiguities, how often would you find the _exact_ same position, but with ep captures possible on different squares?

1. e4, d5 2. e5, f5

1. e4, f5 2. e5, d5

That wasn't so hard to imagine...