Repetiion rules and 50 moves without hash table

[NaltaP312]

Hello great team,

I continue to try to develop my engine and debug it
and i have a little question resume in the subject.

Is it possible to not use has table to found 3 repeat position and 50 moves.
I have an idea to use fen and store all fen position for each move played, but it seems than the art of development is to use hashtable.

thanks for feedback.
Best Regards
NaltaP

[Dann Corbit]

You can find 50 move with the half move clock alone, but hash is better.
You can find three position repeats by scanning the history if you store the whole FEN or EPD but hash is better.

There is always more than one way to solve a problem. But when you see everyone using hash, there's probably a reason for it.

[Gerd Isenberg]

Maybe more common is an array of zobrist hashkeys, and to compare hashkey[currentply] with hashkey[currentply-4], hashkey[currentply-6]... as long as the half move clock indicates. In case of equality with one of the previous keys, a (at least) two-fold repetition is detected. One can distinguish cases where the found index is inside or outside the search tree. If the first occurrence applies inside the search tree, one usually returns draw score immediately. Otherwise one may continue to look for a threefold repetition.

[Dann Corbit]

Maybe more common is an array of zobrist hashkeys, and to compare hashkey[currentply] with hashkey[currentply-4], hashkey[currentply-6]... as long as the half move clock indicates. In case of equality with one of the previous keys, a (at least) two-fold repetition is detected. One can distinguish cases where the found index is inside or outside the search tree. If the first occurrence applies inside the search tree, one usually returns draw score immediately. Otherwise one may continue to look for a threefold repetition.

But doesn't this method also use a hash (the Zobrist keys)?

[Gerd Isenberg]

OK, with hashing I associated a dedicated small hashtable alá Gerbil or Rookie (http://alexandria.tue.nl/extra2/afstver ... ck2002.pdf page 39, Courtesy to Ronald de Man), where hashkeys (part of it) are used to index a small table to "lock" nodes.

So we both refer the game-record approach to compare zobrist-keys rather than fen-strings

[NaltaP312]

Hello Dan and Gerd,

thanks for you reply.
I have understand my future work, may in one month : how to use hash table.
I will read this article and work with it.
http://chessprogramming.wikispaces.com/Repetitions

Thanks again.
Best Regards
NaltaP

[H.G.Muller]

To be any good inthe end-game a prorgam will need a hash table anyway, and once the hash key is available, it is convenient to also use it for repetition detection. Even when you do't have a hash table yet, and want to do repetition detection, you could develop a Zobrist key just for that. (And easily upgrade to areal transposition table later...) Calculating Zobrist keys is not anymore difficult than calculating other compact unique representations of the position. In fact, because it can be updated differentially, it is much easier than most other forms of signature (like FENs or Hufmann coding). Only the board itself (if you use a mailbox board with piece types on it) is as easy to update as the Zobrist key, but it is very bulkey in comparison.