Dec 30, 2006

[Plan] A crude repetition detection

Not being able to detect draw by repetition is a huge problem. The most obvious reason is of course the fact that even in the most obvious winning situations it can start repeating moves and the opponent gladly accepts the draw.

But the reason I am picking this up (before implementing transposition tables as I said I should) is because trying to play the engine against itself simply does not work with no repetition detection. In 90% of the matches somewhere in the middle game the engine started repeating and the game was drawn. So I could never see the games played to the end.

What I will do is a very crude repetition detection that probably slows down the engine a tad (not enough to make a difference though).

I will keep a history consisting of FEN-strings (instead of Zobrist keys which will be used in the transposition and history later) and in the alpha-beta search I will go through the history and compare the moves just made and see if a three-fold repetition occurs. If it does the engine will evaluate it to draw.

This takes care of the most pressing repetition detection.

What it will not handle is repetitions that occur in the search tree. So it will miss forced repetitions while searching. This is a minor problem though since they are not too common.

This solution will do for now.


Anonymous said...

1. Is there an advantage in using FEN strings instead of the Zobrist keys? Zobrist keys can be compared quickly.
2. Draw detection prunes the search tree and speeds up the search; so I find it useful to internally declare any (not only the 2nd) repetition a draw. This could theoretically be abused by an opponent who knows the engine (if he blunders in a won position but still retains a positive score, he could reverse his move, and the engine would reverse its own move in hope for a draw), but I never saw that happen.

Jonatan Pettersson said...

There is no advantage of using FEN-strings instead of Zobrist keys, except for easy implementation at this point since I already had them available..

Not only can zobrist keys be compared quickly, and used in hash tables easily. They are very easy to maintain in the Board-class so a key is always available and you don't have to generate it every time.

I only use FEN-strings temporarily at this point for development purposes. I will be implementing zobrist keys in the near future.

About declaring any repetition a draw I am not sure yet. Most likely I will do as you say, I am not too worried about the repeats.