Zobrist hashing in monochrome board representation

Discussion of chess software programming and technical issues.

Moderator: Ras

gxchess1
Posts: 29
Joined: Thu Sep 15, 2022 4:51 pm
Full name: Elad Yosef Cohen

Zobrist hashing in monochrome board representation

Post by gxchess1 »

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?
User avatar
hgm
Posts: 28353
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Zobrist hashing in monochrome board representation

Post by hgm »

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.
mathmoi
Posts: 290
Joined: Mon Mar 13, 2006 5:23 pm
Location: Québec
Full name: Mathieu Pagé

Re: Zobrist hashing in monochrome board representation

Post by mathmoi »

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.
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.

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))
At the end of your make_move function, Interchange the upper and lower bits of the hash value:

Code: Select all

zobHash = InterchangeUpperAndLowerBits(zobHash)
This way you keep the symetry, but the keys for mirror pairs are still the same.

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.
User avatar
hgm
Posts: 28353
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Zobrist hashing in monochrome board representation

Post by hgm »

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.
gxchess1
Posts: 29
Joined: Thu Sep 15, 2022 4:51 pm
Full name: Elad Yosef Cohen

Re: Zobrist hashing in monochrome board representation

Post by gxchess1 »

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.
About the en passant: I did something I am not really proud of.

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 ?
dangi12012
Posts: 1062
Joined: Tue Apr 28, 2020 10:03 pm
Full name: Daniel Infuehr

Re: Zobrist hashing in monochrome board representation

Post by dangi12012 »

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.
Worlds-fastest-Bitboard-Chess-Movegenerator
Daniel Inführ - Software Developer
gxchess1
Posts: 29
Joined: Thu Sep 15, 2022 4:51 pm
Full name: Elad Yosef Cohen

Re: Zobrist hashing in monochrome board representation

Post by gxchess1 »

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
Aleks Peshkov
Posts: 893
Joined: Sun Nov 19, 2006 9:16 pm
Location: Russia

Re: Zobrist hashing in monochrome board representation

Post by Aleks Peshkov »

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).

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); }

};