search

nkarve / surge

A fast bitboard-based chess move generator in C++
MIT License
63 stars 15 forks source link

Hash key collisions on castling, En passant, and side to move #15

Open osvitashev opened 3 years ago

osvitashev commented 3 years ago

Consider the following code snippet:

int main() {
    initialise_all_databases();
    zobrist::initialise_zobrist_keys();
    Position p;
    Position::set("r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -", p);
    std::cout << p;
    Position p2;
    Position::set("r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R b - -", p2);
    std::cout << p2;
    return 0;
  }

The two positions end up having the same hash key. The two positions share placement of pieces on the board, but they do not represent the same game state: the side-to-move is different, so is castling availability. Some key collisions are inevitable, but ideally they would happen between entirely different board positions, rather than the ones that are superficially similar.

I believe the classic solution to this is to have an extra number of Zobrist keys to represent game state parameters such as 'white to move', 'black can castle on queen side', 'en passant available on c-file', and so on.

... Thoughts?

nkarve commented 2 years ago

@osvitashev Thanks for spotting this (and sorry for the long delay, I've returned after quite a while). You are absolutely correct regarding the special state zobrist keys, I had put those off until the Position::set function worked completely correctly (it currently doesn't, see https://github.com/nkarve/surge/issues/17). I will try and implement this soon, exactly as you suggest (4 keys for castling, 1 for side to play and 8 for EP file).