Upcoming repetition detection

[Gerd Isenberg]

Hmm, I would have expected 3668 instead of 1834 dictionary entries since hash(piece,a,b) != hash(piece,b,a)

The paper indicates that for ZobristXOR hashing we do have equality of these hash() calls.

In chess there are 7,336 reversible move hashes or half that number if we equal (piece, a, b) to
(piece, b, a) as is the case with XOR­based Zobrist hashing.

We have that HASH[PIECE][TO] ^ HASH[PIECE][FROM] has XOR commute with TO/FROM, so that
HASH_DIFF[PIECE][TO][FROM]==HASH_DIFF[PIECE][FROM][TO], as desired.
I gain another 2x by only considering one colour in my implementation (again following the lead of the paper).
...

Yes of course! As already mentioned in 3.3. Legality of a reverting move

4. The hash, which represents the two moves (piece, a, b) and (piece, b, a), but neither of which is a legal move due to a hashing collision with a combination of other moves

So beside squares along the path are free, shouldn't is_legal_move need following pre-conditions, which also covers the color problem?

Code: Select all

if ( board[a] == piece && board[b] == EMPTY ) { from a to b }
if ( board[b] == piece && board[a] == EMPTY ) { from b to a }

[BB+]

Also, more importantly, is there an expected effect, either positive or negative, on type-1 errors / key collisions?

If I understand correctly, you are asking whether determining the 13 lower bits for ZOBRIST[piece][sq] as with the method above might tend to induce more/less 64-bit hash collisions overall. I don't really see why it would have an effect either way. One could presumably test this: take a list of Zobrist keys and a bunch of positions (say a million), and see whether the resulting bunch of keys are well-distributed in the bottom 13 bits. [In fact, one can make a general testing method for Zobrist randomness in a similar manner].

[marcelk]

So beside squares along the path are free, shouldn't is_legal_move need following pre-conditions, which also covers the color problem?

Code: Select all

if ( board[a] == piece && board[b] == EMPTY ) { from a to b }
if ( board[b] == piece && board[a] == EMPTY ) { from b to a }

This additional check is not needed as it can be safely inferred from finding 'diff' already: After that we know that either move is there and we don't care for the purpose of draw detection which one we have. (And the path to check for clearance is the same).

Also, more importantly, is there an expected effect, either positive or negative, on type-1 errors / key collisions?

If I understand correctly, you are asking whether determining the 13 lower bits for ZOBRIST[piece][sq] as with the method above might tend to induce more/less 64-bit hash collisions overall. I don't really see why it would have an effect either way. One could presumably test this: take a list of Zobrist keys and a bunch of positions (say a million), and see whether the resulting bunch of keys are well-distributed in the bottom 13 bits. [In fact, one can make a general testing method for Zobrist randomness in a similar manner].

It can indeed best be tested. In essence the programmer has two choices for optimization: a single probe using your perfect hashing scheme and 48kB of data. Alternatively go for a ternary cuckoo scheme as with that the density of the table can go to over 90% which is enough to fit our 3668 items in 4096 slots or 24 kB. (Or just keep the binary cuckoo scheme of the paper if he doesn't want to tweak the Zobrist hashes, for example to remain compatible with some outside standard).

[marcelk]

So beside squares along the path are free, shouldn't is_legal_move need following pre-conditions, which also covers the color problem?

Code: Select all

if ( board[a] == piece && board[b] == EMPTY ) { from a to b }
if ( board[b] == piece && board[a] == EMPTY ) { from b to a }

This additional check is not needed as it can be safely inferred from finding 'diff' already: After that we know that either move is there and we don't care for the purpose of draw detection which one we have. (And the path to check for clearance is the same).

I forgot to add: the test always passes and (therefore) doesn't resolve the color problem: After 1. move(a,b) move(c,d) 2. move(b,a) move(d,e) we might find 'diff == hash(move(e,c))' but the wrong side is to move.

[BB+]

Another thing you could aim for (with the 1834 entries in 2048 slots) is a k-ary Cuckoo, but cache-friendly. That is, all relevant entries would be in the same 16-entry cache line (assuming 4 bytes per entry). Maybe you could get this to work with k=4 (I can't even ensure that each 16-entry bucket has only 16 data items yet). You could also make this branchless, by simply testing all the possibles each time. Then again, maybe the whole table is so small that cache overhead is not that problematic.

[marcelk]

I wrote down some notes regarding upcoming repetition detection I've been working on recently.
http://marcelk.net/2013-04-06/paper/upcoming-rep-v2.pdf

I just received news that this now got implemented in Stockfish and apparently passed "fishtesting".
http://tests.stockfishchess.org/tests/v ... 26dba90ddc
Thanks Tom Truscott for doing the real work on this fantastic validation!