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.
Hash table bug
Moderators: hgm, Rebel, chrisw
-
- Posts: 2204
- Joined: Sat Jan 18, 2014 10:24 am
- Location: Andorra
Re: Hash table bug
Daniel José - http://www.andscacs.com
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: Hash table bug
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.zenpawn wrote:Mine's done incrementally in make/undo, so this is always a good assert.Sven Schüle wrote: #2 is often solved automatically by pushing the hash key on a stack - provided you restore it correctly.
-
- Posts: 27869
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Hash table bug
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.
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Hash table bug
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:hgm wrote: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.
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);
}
-
- Posts: 349
- Joined: Sat Aug 06, 2016 8:31 pm
- Location: United States
Re: Hash table bug
Likewise, although my hash key is simply zobrist % hah table size.AlvaroBegue wrote: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:hgm wrote: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.
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); }
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Hash table bug
But do you encode castling rights and en-passant availability in your key somehow?zenpawn wrote: Likewise, although my hash key is simply zobrist % hah table size.
-
- Posts: 349
- Joined: Sat Aug 06, 2016 8:31 pm
- Location: United States
Re: Hash table bug
Yes, Zobrist keys have these in them.AlvaroBegue wrote:But do you encode castling rights and en-passant availability in your key somehow?zenpawn wrote: Likewise, although my hash key is simply zobrist % hah table size.
-
- Posts: 349
- Joined: Sat Aug 06, 2016 8:31 pm
- Location: United States
Re: Hash table bug
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.jwes wrote: Do you have killer moves? Qc1 refutes most moves.
-
- Posts: 2498
- Joined: Tue Aug 30, 2016 8:19 pm
- Full name: Rasmus Althoff
Re: Hash table bug
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?zenpawn wrote:Likewise, although my hash key is simply zobrist % hah table size.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Hash table bug
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".zenpawn wrote:Likewise, although my hash key is simply zobrist % hah table size.AlvaroBegue wrote: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:hgm wrote: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.
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); }
Just a wording issue, of course.