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?
Transposition table random numbers
Moderators: hgm, Rebel, chrisw
-
- Posts: 27869
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Transposition table random numbers
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.
-
- Posts: 27869
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Transposition table random numbers
A very simple way to prove that Hamming distance "doesn't mean squat" is this:wgarvin wrote: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.
- 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.
-
- Posts: 41
- Joined: Thu May 27, 2010 11:32 pm
Re: Transposition table random numbers
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.hgm wrote: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.
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?
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Transposition table random numbers
Why 8? You can only have one EP capture possibility in any single position...hgm wrote:Don't worry about Bob. He never reads what you write, so repeating it a few more times will not help either...jdm64 wrote:And as I bolded in the quote above, there is no castling in my chess variant.
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.
-
- Posts: 41
- Joined: Thu May 27, 2010 11:32 pm
Re: Transposition table random numbers
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?hgm wrote:A very simple way to prove that Hamming distance "doesn't mean squat" is this:wgarvin wrote: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.
- 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.
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.
-
- Posts: 27869
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Transposition table random numbers
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.jdm64 wrote: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?
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.
-
- Posts: 27869
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Transposition table random numbers
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).bob wrote:Why 8? You can only have one EP capture possibility in any single position...
The path leading to a position is not encoded in the hash key. That includes the double push through which the position was reached.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Transposition table random numbers
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.hgm wrote: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).bob wrote:Why 8? You can only have one EP capture possibility in any single position...
The path leading to a position is not encoded in the hash key. That includes the double push through which the position was reached.
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Transposition table random numbers
1. e4, d5 2. e5, f5bob wrote: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, f5 2. e5, d5
That wasn't so hard to imagine...