Overlapped Zobrist keys array

[hgm]

That Hamming distance of key pairs is completely meaningless is trivially proven:

XORing two keys K1 and K2 with the same constant C (so you get C^K1 and C^K2) preserves their Hamming distance. But take three keys from the set, and K1^K2^K3, and (C^K1) ^ (C^K2) ^ (C^K3) = C ^(K1^K2^K3). Now if you pick C = K1^K2^K3, the latter is zero. So the tranformed keys, which have just the same Hamming distance as the original keys, have K1^K2^K3 = 0, a dependency of the worst kind (part from two keys being equal).

[bob]

I guess I always use + in stead of ^ because it is more general. XORing only works if you never have more than one piece on the same square. Adding the Zobrist keys would work for any number of pieces per square. In games where pieces can be stacked (e.g. in the Crazyhouse holdings) ^ would not work at all, as two identical pieces on the same square would be indistinguishable from an empty square. Of course there are work-arounds for that, by assigning separate keys to each (copyNumber, pieceType, square) combination, but these bloat the key table even more, for apparently no reason at all. With + I can treat the holdings like they are just a single extra square.

I must be missing something? I play crazyhouse all the time and _never_ have two pieces on the same square. What am I overlooking in this discussion???

[rjgibert]

There are 2 additional locations for the pieces that are still in play. They are held in your hand and in your opponents hand. If you don't hash these pieces, you will have undesirable collisions, since there are multiple distributions of the pieces held in hand and they are not equivalent.

[bob]

There are 2 additional locations for the pieces that are still in play. They are held in your hand and in your opponents hand. If you don't hash these pieces, you will have undesirable collisions, since there are multiple distributions of the pieces held in hand and they are not equivalent.

Sure. But you can have a set of zobrist random numbers for each type of piece, and for each one, you just hash in the appropriate key. I'm still missing the point about multiple pieces on the same square where two knights would cancel each other out by xor'ing the same random number twice.

[rjgibert]

There are 2 additional locations for the pieces that are still in play. They are held in your hand and in your opponents hand. If you don't hash these pieces, you will have undesirable collisions, since there are multiple distributions of the pieces held in hand and they are not equivalent.

Sure. But you can have a set of zobrist random numbers for each type of piece, and for each one, you just hash in the appropriate key. I'm still missing the point about multiple pieces on the same square where two knights would cancel each other out by xor'ing the same random number twice.

Let Z = the Zobrist hash signature for the position
Let a = the Zobrist hash for a knight in hand
Now if you have 2 knights in hand, then (Z^a)^a = Z^(a^a) = Z^0 = Z. The 2 knights in hand cancel each other out. In other words, those 2 knights in hand could be in your possession or your opponents possession to be played with each case generating the same hash signature even though the 2 positions are significantly different.

What you would need to do to avoid this problem is to hash the number of knights held in hand with its own unique hash value. You can hold up to 10 knights in hand, so that would be 10 distinct hash values. Actually, that's 20 depending on whether those knights are in possession of you or your opponent. Likewise for the other 4 piece types possible.

[bob]

There are 2 additional locations for the pieces that are still in play. They are held in your hand and in your opponents hand. If you don't hash these pieces, you will have undesirable collisions, since there are multiple distributions of the pieces held in hand and they are not equivalent.

Sure. But you can have a set of zobrist random numbers for each type of piece, and for each one, you just hash in the appropriate key. I'm still missing the point about multiple pieces on the same square where two knights would cancel each other out by xor'ing the same random number twice.

Let Z = the Zobrist hash signature for the position
Let a = the Zobrist hash for a knight in hand
Now if you have 2 knights in hand, then (Z^a)^a = Z^(a^a) = Z^0 = Z. The 2 knights in hand cancel each other out. In other words, those 2 knights in hand could be in your possession or your opponents possession to be played with each case generating the same hash signature even though the 2 positions are significantly different.

What you would need to do to avoid this problem is to hash the number of knights held in hand with its own unique hash value. You can hold up to 10 knights in hand, so that would be 10 distinct hash values. Actually, that's 20 depending on whether those knights are in possession of you or your opponent. Likewise for the other 4 piece types possible.

No. I explicitly said I would use a _list_ of zobrist random numbers for each piece type. Since I can have 10 knights in total from my pieces, plus my partner can hand me two from his game, I need an array of numbers knights(12). Now I don't use the same zobrist key for each knight. And when I choose to drop a piece on the board, I would xor the last number in the active list, and then xor in the square I dropped to and away we'd go.

[TonyJH]

Note that a player can only hold (in hand) a maximum of 4 knights in crazyhouse, since promoted pieces turn back into pawns when captured.
In bughouse, for a minute I was thinking it would be a maximum of 8 knights, but it's still 4 because of piece colors. Of course you could hold up to 16 pawns.

[bob]

Note that a player can only hold (in hand) a maximum of 4 knights in crazyhouse, since promoted pieces turn back into pawns when captured.
In bughouse, for a minute I was thinking it would be a maximum of 8 knights, but it's still 4 because of piece colors. Of course you could hold up to 16 pawns.

Right. I was mixing on the board pieces with held pieces. You could actually have 20 knights on the board, since you could promote 16 pawns to knights, plus your original 2, plus 2 from your partner. That would be a knightmare to play for the other side of course.

[rjgibert]

Note that a player can only hold (in hand) a maximum of 4 knights in crazyhouse, since promoted pieces turn back into pawns when captured.
In bughouse, for a minute I was thinking it would be a maximum of 8 knights, but it's still 4 because of piece colors. Of course you could hold up to 16 pawns.

I don't play crazy house, so I don't know the details, but how do you tell whether a given piece will turn back into a pawn when captured? Do you just have to remember? Seems like an ugly rule to me.

[TonyJH]

Note that a player can only hold (in hand) a maximum of 4 knights in crazyhouse, since promoted pieces turn back into pawns when captured.
In bughouse, for a minute I was thinking it would be a maximum of 8 knights, but it's still 4 because of piece colors. Of course you could hold up to 16 pawns.

I don't play crazy house, so I don't know the details, but how do you tell whether a given piece will turn back into a pawn when captured? Do you just have to remember? Seems like an ugly rule to me.

With most GUIs I think you just have to remember. However, I think H.G. has added support into newer versions of WinBoard for showing promoted pieces a little bit differently.