Hash table bug

[cdani]

To detect why an strange line of play happens in Andscacs, I use many times the Visual Studio debugger helped with an "is_line("e2e4 e7e5 g1f3");" function where I put a breakpoint if is the line.
If I have to go farther, I take the move number, I put a breakpoint in a node number verification condition, and I change the "is_line" argument as needed. This has helped so many times that I can recommend it.

[Evert]

#2 is often solved automatically by pushing the hash key on a stack - provided you restore it correctly.

Mine's done incrementally in make/undo, so this is always a good assert.

You cannot reconstruct the hashkey by undo in general. Even if you take care to put the captured piece back, there is no way to restore castling rights or en-passant capture if you didn't back those up. In which case you might as well do the same for the hash key.

[hgm]

I think it is a mistake to treat rights incrementally, in the key. Adding the rights keys to the (incrementally updated) board key whenever you need the hash key is faster. Doing it incrementally requires to remove the old key, in addition to adding the new key. That just doubles the work, for no benefit.

[AlvaroBegue]

I think it is a mistake to treat rights incrementally, in the key. Adding the rights keys to the (incrementally updated) board key whenever you need the hash key is faster. Doing it incrementally requires to remove the old key, in addition to adding the new key. That just doubles the work, for no benefit.

I agree. I incrementally maintain a Zobrist key that encodes the position on the board, and then the hash key for a board is computed in a member function, like this:

Code: Select all

u64 Board::get_hash_key() const {
  return zobrist_key
    ^ en_passant_zobrist_table[en_passant]
    ^ castling_availability_zobrist_table[castling_availability]
    ^ (active == White ? 0ull : 0x8000000000000001ull);
}

[zenpawn]

I think it is a mistake to treat rights incrementally, in the key. Adding the rights keys to the (incrementally updated) board key whenever you need the hash key is faster. Doing it incrementally requires to remove the old key, in addition to adding the new key. That just doubles the work, for no benefit.

I agree. I incrementally maintain a Zobrist key that encodes the position on the board, and then the hash key for a board is computed in a member function, like this:

Code: Select all

u64 Board::get_hash_key() const {
  return zobrist_key
    ^ en_passant_zobrist_table[en_passant]
    ^ castling_availability_zobrist_table[castling_availability]
    ^ (active == White ? 0ull : 0x8000000000000001ull);
}

Likewise, although my hash key is simply zobrist % hah table size.

[AlvaroBegue]

Likewise, although my hash key is simply zobrist % hah table size.

But do you encode castling rights and en-passant availability in your key somehow?

[zenpawn]

Likewise, although my hash key is simply zobrist % hah table size.

But do you encode castling rights and en-passant availability in your key somehow?

Yes, Zobrist keys have these in them.

[zenpawn]

Do you have killer moves? Qc1 refutes most moves.

Yes, with the caveat that I don't put captures or checks there, since they're sorted to the front of the move list anyway.

[Ras]

Likewise, although my hash key is simply zobrist % hah table size.

Do you use some sort of cluster system? Like, if the entry is occupied, then try the next entry? If so, does the hash table have enough additional space at the end to prevent out-of-bounds operations?

[Sven]

I think it is a mistake to treat rights incrementally, in the key. Adding the rights keys to the (incrementally updated) board key whenever you need the hash key is faster. Doing it incrementally requires to remove the old key, in addition to adding the new key. That just doubles the work, for no benefit.

I agree. I incrementally maintain a Zobrist key that encodes the position on the board, and then the hash key for a board is computed in a member function, like this:

Code: Select all

u64 Board::get_hash_key() const {
  return zobrist_key
    ^ en_passant_zobrist_table[en_passant]
    ^ castling_availability_zobrist_table[castling_availability]
    ^ (active == White ? 0ull : 0x8000000000000001ull);
}

Likewise, although my hash key is simply zobrist % hah table size.

That is not the hash key but the hash table index - which is also what you wanted me to elaborate on. You use the lower N bits of the hash key as table index (array index) and your hash table has 2^N entries, so the index is in the range [0 .. 2^N-1]. The hash key is what you call "zobrist".

Just a wording issue, of course.