Moved bits and Zobrist hashing

[leanchess]

Speaking of illegal ranks, here's a crazy idea: use rank 1 of WP0 for MovedWK, rank 1 of WP1 for MovedWR, etc.

I'm wondering if indirection could be avoided through some clever bit manipulation...

[dangi12012]

With this encoding you can encode the whole FEN information (except movecount) into 4 bits per square.
Which is faster yet again:

Code: Select all

Hash ^= Zobrist[(sq << 4) | piece]

How about this?

Code: Select all

Zobrist[(piece << 6) | sq]

I am asking because I am hiding the keys for the e.p. file in the pawns' illegal ranks, and I want them to nicely overflow from WPawn's Rank 8 to BPawn's Rank 1 (an illegal e.p. file can be anything between 0x8 and 0xF). That should also allow my branchless make to remove one LUT access by placing an extra pawn in rank 8 outside the board (0x88, remember?) during a double push.

If piece enum contains Special_W and Special_B then you have the double pushed pawns too.
A special piece on the first rank is a rook that can be used to castle.
A special piece on any other rank is a double pushed pawn.
Then your piece encodes the type and the hash calculation becomes very cheap.

I dont know if in 0x88 the outside squares are also part of the hash calculation - but i think not since they are "guard pieces"?
Yours is also possible:

Code: Select all

Hash ^= Zobrist[(sq << 4) | piece]

This is equivalent to the code you posted in the beginning. But branchless and you see that when implementing good ideas whole code tree collapse into a single lookup.
Thats what i find so interesting in chessprogramming.

Merry christmas!

[leanchess]

Well, thanks to our discussion, I think I finally cracked it:

Code: Select all

hash_keys[(type && !moved ? Type_Pawn : type) + (black << 3) + (file << 4) + (rank << 7)]

If unmoved (and non-empty), this is either a pawn (so nothing changes), or a piece in its initial rank.

Keys in rank 1 of WP are initialised as follows:

1. Random
2. Copied from WN/b1
3. Copied from WB/c1
4. Copied from WQ/d1
5. XOR between WK/e1, WR/a1, WP/a1, WR/h1, and WP/h1 (this must be initialised last)
6. Copied from WB/f1
7. Copied from WN/g1
8. Random

The same goes for Rank 8 of BP.

Now this looks like true Christmas to me

However, I see a branch in the lookup code. Any ideas as to how to remove it?

[leanchess]

Well, thanks to our discussion, I think I finally cracked it:

Code: Select all

hash_keys[(type && !moved ? Type_Pawn : type) + (black << 3) + (file << 4) + (rank << 7)]

If unmoved (and non-empty), this is either a pawn (so nothing changes), or a piece in its initial rank.

That part seems to work. The key derivation, on the other hand, doesn't, since all moved RKR cancel each other out.

I'll have to think of a working formula (or just use 6 random keys and accept the false negatives).

Meanwhile, the e.p. keys fit nicely in the BEmpty space, so the (nearly branchless) calculation has become:

Code: Select all

key ^= key_get(from) ^ key_get(to) ^ key_get(from2) ^ key_get(to2) ^ key_get_ep(ep_square) ^ key_get_color();

[hgm]

I think it is a mistake to try handling the castling rights (or side to move, e.p. rights) in the hash key incrementally. For castling rights this just complicates things, as there are too many events that can change them. And you don't want to know what rights exist just in the key; the move generator needs to know it too. So the simplest way is just keep track of the existence of rights independent of the key, and then unconditionally XOR the key for the existing combination of rights to the board key in every node, and only treat the board key incrementally. That is faster than the overhead you suffer from determining whether the move that led to the node changed the castling rights (which the samemove sometimes does, and sometimes doesn't).

The standard way is to have a mailbox board char spoilerMasks[64], and do newRights = rights & spoilerMask[fromSqr] & spoilerMask[toSqr] in MakeMove.

[leanchess]

I think it is a mistake to try handling the castling rights (or side to move, e.p. rights) in the hash key incrementally. For castling rights this just complicates things, as there are too many events that can change them. And you don't want to know what rights exist just in the key; the move generator needs to know it too. So the simplest way is just keep track of the existence of rights independent of the key, and then unconditionally XOR the key for the existing combination of rights to the board key in every node, and only treat the board key incrementally. That is faster than the overhead you suffer from determining whether the move that led to the node changed the castling rights (which the samemove sometimes does, and sometimes doesn't).

I see only three events that can change a castling right:

• The king moves
• A rook moves
• A rook is captured

My current implementation is almost entirely branchless (and I'm still hoping to replace the ternary with bit manipulation), so I don't think there is much overhead. The only problem I see is the false negatives resulting from the six independent keys.

The simple branchless make/unmake perform 5 writes each (as seen in my previous post), and if we add a piece list to the equation, those will become 8 for make (thanks to the e.p. optimisation) and 9 for unmake. That seems quite wasteful, considering all we need is a hash key.

However, it might be worth splitting both make and unmake into two steps. That way, we may write to the piece list first, derive the castling key deltas, query the hash, then, depending on the result, perform either the 2nd-step make (write to the board) or the 1st-step unmake (write the old values to the piece list). Since K and Rs are all in known locations in the piece list, a castling key delta for each player would be trivially derived from the three moved bits, requiring two reads from the castling key table. That's four more XORs in the incremental key calculation (or three if we keep the current result). I'm still unsure if the few false negatives justify all that complexity.

[leanchess]

A couple more optimisations later:

Code: Select all

key ^= key_get_ep_color(ep_square) ^ key_get(from) ^ key_get_to(to) ^ key_get(from2) ^ key_get_to(to2);

key_get_to() doesn't check if the piece is moved (it always is).
key_get_ep() and key_get_ep_color() take advantage of BEmpty's ranks 1, 2, 3, 4, 6 and 7, with the e.p. file value being allowed to overflow to the next rank.

Edit: Since rank 2 is filled with the colour key, it is now simply taken from a2.