OpenChess

Abstract
An algorithm is presented that detects cycles one ply before they appear in the search of a game tree. The algorithm is suitable for use in the leaf nodes of a chess program and can there shift the detection of repetition draws to an earlier iteration. The algorithm is fast because it doesn’t generate or iterate over candidate moves during search. Instead, the Zobrist hashes of potential reversible moves are precalculated and stored in a cuckoo table. Further speed is gained by employing a light­weight measure for the displacement of opponent pieces that is based on the exclusive OR of an even number of hash history items. Measurements are given for tree size, node speed and improved playing strength when applied to a chess program.

marcelk wrote:If the search employs the null move heuristic[2] such move will be considered an irreversible move that resets hm to zero when it is made on the internal board.

marcelk wrote:More importantly, in the nodes of interest presumably a complete move generation has been done already because another reversible move is already being searched from there and many move generators produce all such moves at once. (3.1, page 5)

marcelk wrote:The problem of a regular hash table is that it either needs a lot of space to prevent collisions, or it needs an arbitrary number of probes.

Gerd Isenberg wrote:I once proposed the cheapo trick with direct move repetition applied two plies before the repetition might be occur, to prune "unmake" of a previous reversible move of the stronger side (alpha > 0), which would allow a refutation of the weaker side in "unmaking" its previous reversible move as well to repeat the position:

http://www.talkchess.com/forum/viewtopic.php?t=13791
and below.

 if ( beta < 0 && move50 >= 3 && ply >= 3
     && move[ply-3].from == move[ply-1].to
     && move[ply-3].to == move[ply-1].from
     && move[ply-1].to isNotElement (inbetween(move[ply-2].from, move[ply-2].to) )
        return 0; 

 if ( ... &&
     S[0] ^ S[1] ^ S[2] ^ S[3] == 0
     && ... )
        return 0; 

BB+ wrote:

marcelk wrote:If the search employs the null move heuristic[2] such move will be considered an irreversible move that resets hm to zero when it is made on the internal board.

You might want to stress that one can still have a "repetition" (null Nf6 null Ng8), but that these shall be ignored for the purposes here.

BB+ wrote:[For that matter, you might mention castling/rights, as it is "reversible" for the 50-move rule, but not for 3-rep (see this thread].

BB+ wrote:

marcelk wrote:More importantly, in the nodes of interest presumably a complete move generation has been done already because another reversible move is already being searched from there and many move generators produce all such moves at once. (3.1, page 5)

I don't know about this, as hash moves and killers are often reversible, but usually are processed before "ordinary" moves w/o the full move generation?

BB+ wrote:

marcelk wrote:The problem of a regular hash table is that it either needs a lot of space to prevent collisions, or it needs an arbitrary number of probes.

I've often had hash tables in programming that I do, and have never found the cuckoo solution all that useful. Is ensuring the worst case is small that important? Otherwise something simply like a "rolling" hash [linear probing with step 1, I guess] has good average performance (if X is filled, use X+1, average case takes 1/(1-density) probes). Admittedly, capping the probe limit probably has some branch prediction benefits.

BB+ wrote:Also, what is the genesis of Figure 1 [correlation of 15s versus 300s searches]? I have been wondering about such data for some time but could find nothing too recent (my recollection is that an old ICCA article gave a predictive model, but I can't find it).

BB+ wrote:You might also mention that the idea shares some (vague) similarity to enhanced transposition cutoffs, though it seems the technical details of your repetition scheme are not available there.

marcelk wrote:A perfect hashing scheme with a small footprint seems unobtainable

BB+ wrote:I attach code that generates a 4096 entry collision-less table for the 1834 dictionary entries, in the manner indicated above. It seems to hang on Qh8 for 2048 entries, maybe the linear algebra over F2 demands collisions (other random seeds get as far as Re7 or so, but I've never reached completion).

BB+ wrote:I attach code that generates a 4096 entry collision-less table for the 1834 dictionary entries, in the manner indicated above. It seems to hang on Qh8 for 2048 entries, maybe the linear algebra over F2 demands collisions (other random seeds get as far as Re7 or so, but I've never reached completion).

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

marcelk wrote: 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.

marcelk wrote:Is there something fundamental that prohibits this method from squeezing all of White's and Black's moves into a single table? Also, more importantly, is there an expected effect, either positive or negative, on type-1 errors / key collisions?

marcelk wrote:Or I might remove the null move reference all together as it doesn't matter for the algorithm and there is always somebody ready to claim that repetitions should be allowed to span the null move.

marcelk wrote:I can squeeze in an "unlike ETC [ref]" somewhere when I talk about not generating moves and application in leaf nodes.