Computer Chess Club Archives




Subject: Re: A New Approach to Draw Detection by Move Repetition in Computer Ches

Author: Christophe Theron

Date: 14:34:11 07/29/04

Go up one level in this thread

On July 29, 2004 at 14:07:10, Robert Hyatt wrote:

>On July 29, 2004 at 06:26:52, Gian-Carlo Pascutto wrote:
>>I stumbled onto this when doing a search for Axon.
>>Not seen it mentioned here yet.
>>They also have a paper about hashing out which I can't
>Doesn't strike me as particularly interesting.  IE it almost seems that they
>don't realize that most programs store positions in a repetition list as 64 bit
>Zobrist integers...

Actually I think it might be interesting.

Recently, when I was rewriting the core of the Chess Tiger engine, I realized
that I could get even more speed by not computing the hash keys during the
quiescence search for example.

In my case, it would have meant some more changes in the engine and the way I do
QSearch. But for some programs, it could be interesting.

The problem then is how do you check for repetitions?

If you allow checks and escape from checks in your QSearch, and if you actually
extend them in some way, you have to detect repetitions.

So a lightweight, hash key free, repetitions detector is a must in this case.

It could also be interesting for people who want to write a very small chess
program for portable units.

But I think there is a better method than the one given in the paper. I would
use an array of integers, one per piece on the board. The array starts filled
with 0. Every time a piece is moved I would add the move vector to the integer
in the array.

A repetition is detected when all the array is filled with 0 (nul vectors). It
is possible to use a "master vector" that receives all the individual vectors
after every move. One has to check the whole array only when the master vector
is nul, otherwise there cannot be a repetition.

This method also works backwards (from the current move back to the last
irreversible move), but avoids any search in the concatenation list.

It should be significantly faster than their method.

Now I should write a paper. :)


This page took 0.02 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.