Hey all. My engine doesn't have a notion of colours, it only has 'us' and 'them' also known as 'friendly' and 'enemy'. When a move is played, all friendly pieces are made into enemy pieces and all enemy pieces are made into friendly pieces. Additionally, their square is mirrored on the rank axis. For example, a friendly rook on E2 would become an enemy rook on E7. Castling rights are also updated accordingly.
After the move is made, everything is as usual but now you are operating as if you are looking from the black side in a real board. The only know to know who's side is it for I/O purposes is the ply counter, which is odd when the side to move is white.
I've wrote perft() tests to test for positions and I am 100% sure it works perfectly (I tested hundreds of billions of nodes).
I then decided to add zobrist hashing and I can't get it to work. In my implementation, I have a side key, 8 en-passant keys, 16 castling keys, and 64 * 6 piece keys. When I need to hash an enemy piece, I do hash(piece, sq, enemy) = hash(piece, sq ^ 56, friendly) (a rankwise mirror). Reasoning is that when a move will be made, a friendly piece on C2 will be made into an enemy piece on C7, so their hashes have to be the same if I want to be incremental.
The issue is that, any symmetrical position will have the same hash key. For example, startpos will have the same zobrist key as an empty position with white and black kings on A1 and A8 respectively.
I have looked everywhere I can and all I saw was Gerd Isenberg with something like mine, instead of using the formula `hash(piece, sq, enemy) = hash(piece, sq ^ 56, friendly)`, he used `hash(piece, sq, enemy) = byteswap(hash, sq ^ 56, friendly)`, a.k.a also byte-swapping the key. My issue with that is when flipping the position in the end of `make_move`, the hash key will be invalid because it has a combination of the previous byteswapped keys.
Anyone had this problem and has a solution? Anything?
Zobrist hashing in monochrome board representation
Moderator: Ras
-
- Posts: 29
- Joined: Thu Sep 15, 2022 4:51 pm
- Full name: Elad Yosef Cohen
-
- Posts: 28353
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Zobrist hashing in monochrome board representation
It is not just the piece you move that switches color and location, right? It is all the pieces. So all the pieces would need different keys. In general that would mean that you have to recalculate the hash key from scratch, using the color-and-rank reversed base keys.
If all color-reversed base keys are the byte-swapped version of the original ones, the XOR of a number of byte-swapped base keys would be the byte-swapped XOR of the original keys, though. So recalculating the board for the color-reversed position (without applying a move to it) would just be a matter of byte-swapping the old key. You can then apply the move using the white keys for the moved piece, and the black keys for the captured piece.
But this only works because of the very special relation between color-reversed base keys: the transformation between those keys must commute with the XOR operation.
If all color-reversed base keys are the byte-swapped version of the original ones, the XOR of a number of byte-swapped base keys would be the byte-swapped XOR of the original keys, though. So recalculating the board for the color-reversed position (without applying a move to it) would just be a matter of byte-swapping the old key. You can then apply the move using the white keys for the moved piece, and the black keys for the captured piece.
But this only works because of the very special relation between color-reversed base keys: the transformation between those keys must commute with the XOR operation.
-
- Posts: 290
- Joined: Mon Mar 13, 2006 5:23 pm
- Location: Québec
- Full name: Mathieu Pagé
Re: Zobrist hashing in monochrome board representation
This is true. If you want to "flip" the sides and have the zobrist hash value unchanged and valid you do indeed need this kind of symetry. However as you noticed this will not works correctly, because lots of position (symetrical positions) will collides because your zobrists keys are not independant and cancel each others out when you xor two indentical key into your hash.Reasoning is that when a move will be made, a friendly piece on C2 will be made into an enemy piece on C7, so their hashes have to be the same if I want to be incremental.
You need a way to still have some symetry regardings rank and color, but never use the same key twice to compute the hash.
Here is an idea. I have not tested this and I'm not sure it would work. When you create your hash keys, instead of using the same key for both side try to interchange the lower 32 bits and upper 32 bits of the key. like this
Code: Select all
hash(piece, sq, enemy) = InterchangeUpperAndLowerBits(hash(piece, sq ^ 56, friendly))
Code: Select all
zobHash = InterchangeUpperAndLowerBits(zobHash)
You will need to do something similar with the hash values that are not piece-based (en-passant, castling, etc.) to make then dependant on the enemy/friendly side too.
Let me know if it works.
Mathieu Pagé
mathieu@mathieupage.com
mathieu@mathieupage.com
-
- Posts: 28353
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Zobrist hashing in monochrome board representation
Swapping words, bytes or bits should all be OK. The important thing is that the transformation T you use to derive the color-reversed base key (!color, type, sqr^56) from (color, type, sqr) is such that
T(A) ^ T(B) = T(A ^ B).
Then you only have to apply T to the incrementally updated key to get the key for the entire color-reversed board.
It helps if T(T(X)) = X, like you would have when you swap pairs of bits: then you don't have to worry in which direction you have to transform, as T would be its own inverse. If you would (for instance) have rotated the key by one bit position on the white moves, you would have to rotate in the opposit direction each time black moves. That is just needlessly complex.
T(A) ^ T(B) = T(A ^ B).
Then you only have to apply T to the incrementally updated key to get the key for the entire color-reversed board.
It helps if T(T(X)) = X, like you would have when you swap pairs of bits: then you don't have to worry in which direction you have to transform, as T would be its own inverse. If you would (for instance) have rotated the key by one bit position on the white moves, you would have to rotate in the opposit direction each time black moves. That is just needlessly complex.
-
- Posts: 29
- Joined: Thu Sep 15, 2022 4:51 pm
- Full name: Elad Yosef Cohen
Re: Zobrist hashing in monochrome board representation
About the en passant: I did something I am not really proud of.hgm wrote: ↑Tue Dec 12, 2023 7:18 pm It is not just the piece you move that switches color and location, right? It is all the pieces. So all the pieces would need different keys. In general that would mean that you have to recalculate the hash key from scratch, using the color-and-rank reversed base keys.
If all color-reversed base keys are the byte-swapped version of the original ones, the XOR of a number of byte-swapped base keys would be the byte-swapped XOR of the original keys, though. So recalculating the board for the color-reversed position (without applying a move to it) would just be a matter of byte-swapping the old key. You can then apply the move using the white keys for the moved piece, and the black keys for the captured piece.
But this only works because of the very special relation between color-reversed base keys: the transformation between those keys must commute with the XOR operation.
I remove the en passant at the start of the move and changed it (if there was a double push) *after* the key flip because the en-passant shouldn't be flipped because it doesn't have a notion of colour or rank.
Now no assertions fail.
Am I correct or do the assertions not fail by luck ?
-
- Posts: 1062
- Joined: Tue Apr 28, 2020 10:03 pm
- Full name: Daniel Infuehr
Re: Zobrist hashing in monochrome board representation
Zobrist generally can only live in L1 since you have lookup tables bigger than available register space.
There are cool alternatives that are underutilized imo that do not need to lookup anything. Namely any hardware instruction with cryptography or fast hashing that is reasonably fast.
Depending if your board structure supports it you can use this:
https://godbolt.org/z/WfWo3T1bE
Disassembly looks like a lot but all of that happens inside the CPU core with register renaming etc.. its really fast. Many billions of boards / second / thread.
In my tests same speed as zobrist (insofar as other parts of the code like eval() are much slower anyways) with the advantage of much simpler code.
There are cool alternatives that are underutilized imo that do not need to lookup anything. Namely any hardware instruction with cryptography or fast hashing that is reasonably fast.
Depending if your board structure supports it you can use this:
https://godbolt.org/z/WfWo3T1bE
Disassembly looks like a lot but all of that happens inside the CPU core with register renaming etc.. its really fast. Many billions of boards / second / thread.
In my tests same speed as zobrist (insofar as other parts of the code like eval() are much slower anyways) with the advantage of much simpler code.
Worlds-fastest-Bitboard-Chess-Movegenerator
Daniel Inführ - Software Developer
Daniel Inführ - Software Developer
-
- Posts: 29
- Joined: Thu Sep 15, 2022 4:51 pm
- Full name: Elad Yosef Cohen
Re: Zobrist hashing in monochrome board representation
I saw your idea in one post with AES intrinsics.. Was really excited until I realized I lack the hardware.
About this instruction: Are you sure? Doesn't it only use 32-bit of entropy (because the instruction is `_mm_crc32_u64`)? Did you have no hash key quality issues whatsoever? I'd love to try it
About this instruction: Are you sure? Doesn't it only use 32-bit of entropy (because the instruction is `_mm_crc32_u64`)? Did you have no hash key quality issues whatsoever? I'd love to try it
-
- Posts: 893
- Joined: Sun Nov 19, 2006 9:16 pm
- Location: Russia
Re: Zobrist hashing in monochrome board representation
I was bothered with both mentioned problems. My solution is to use only several magic keys.
Byteswap used to change color. Bit rotate to get different key for each square.
Pawns that can be captured en passant and rooks with castling rights is special 7th piece "extra" type. As they can appear only on disjoint set of squares no collision is possible.
Any de Bruijn number is maximally contrast to bit rotation operation by its definition. The only problem is to create a set of numbers not correlated to each other in any permutation. I do not know any science how to do it ideally.
I tested this numbers in various combinations of 2 and 3 to avoid easy collisions and picked one of the most contrast set.
I have not found any problems with collisions so far. I believe that this set is not worse then any set of random numbers because of birthdays paradox.
For more information you may look in my working code https://github.com/o5e2e2/petrel (not finished to participate in any tournament, but it works as a perft engine).
Byteswap used to change color. Bit rotate to get different key for each square.
Pawns that can be captured en passant and rooks with castling rights is special 7th piece "extra" type. As they can appear only on disjoint set of squares no collision is possible.
Any de Bruijn number is maximally contrast to bit rotation operation by its definition. The only problem is to create a set of numbers not correlated to each other in any permutation. I do not know any science how to do it ideally.
I tested this numbers in various combinations of 2 and 3 to avoid easy collisions and picked one of the most contrast set.
I have not found any problems with collisions so far. I believe that this set is not worse then any set of random numbers because of birthdays paradox.
For more information you may look in my working code https://github.com/o5e2e2/petrel (not finished to participate in any tournament, but it works as a perft engine).
Code: Select all
class ZobristKey {
//hand picked set of de Bruijn numbers
enum : u64_t {
_Queen = 0x0218a392cd5d3dbfull,
_Rook = 0x024530decb9f8eadull,
_Bishop = 0x02b91efc4b53a1b3ull,
_Knight = 0x02dc61d5ecfc9a51ull,
_Pawn = 0x031faf09dcda2ca9ull,
_King = 0x0352138afdd1e65bull,
_Extra = 0x03ac4dfb48546797ull,
_Castling = _Extra ^ _Rook,
_EnPassant = _Extra ^ _Pawn,
};
const std::array<u64_t, 8> key = {{
_Queen, _Rook, _Bishop, _Knight, _Pawn, _King, _Castling, _EnPassant
}};
static constexpr u64_t rol(u64_t n, Square sq) { return n << sq | n >> (64-sq); }
public:
constexpr u64_t operator() (PieceType ty, Square sq) const { return rol(key[ty], sq); }
};