Computer Chess Club Archives


Search

Terms

Messages

Subject: Draw Detection by Move Repetition Procedure -- Comments

Author: Djordje Vidanovic

Date: 09:40:26 08/01/04


Hi,

we (Vladan Vuckovic and Djordje Vidanovic) are sorry not to have taken part in
the long thread started by Gian Carlo Pascutto that dealt with a paper we wrote
some time ago that is now being processed by a journal.  We are on holiday, and
while Vladan is busy with some extracurricular activities, Djordje is trying to
rest his eyes as much as he can and drops in at CCC only once in a couple of
days...

Anyway, our paper (A New Approach to Draw Detection by Move Repetition in
Computer Chess Programming) can be found at the ACM Computing Research
Repository as we wished to make it available to people who might help us improve
our ideas regarding draw detection.  Therefore the opinions of  top chess
programmers are very important for us.

We have already benefitted much from reading the thread that dealt with some
aspects of our paper.   We would also like to thank primarily Christophe Theron
who grasped our ideas very well and already addressed most of the issues and
answered most of the questions that appeared in the thread.

Some very brief comments are in order.  First of all, we'd like to say that the
paper presents the theoretical framework of a novel alogrithm written in
assembly that is part of the kernel of our chess program.  This project is
predominantly academic, but the program  plays _real chess_ :-) well and will
probably be competitive even against some strong chess engines in the near
future.  The draw detection algorithm has been tried out both in games against
human chess masters and against other engines, and it has shown to be very
efficient and fast, practically proving the functionality and usefulness of our
new procedure.

The idea for the draw detection procedure as described in the paper has evolved
from the structure of the Axon chess engine, a machine-assembly searcher, doing
over 2 million k/ns on an Athlon XP 2200.  To optimise the search we have
decided to throw out the propagation of positions along the search tree, so that
all the operations are performed over one nucleus.  The procedures in search
actually have access to only the _last_ position, while the previous positions
are not accessible as they are _not_ memorised.

On the other hand, we should emphasize that we _do not_ use the 64-bit Zobrist
hash key, but a different type of hash (best move hash with a 24-bit key) which
cannot be used for draw detection as many different positions can generate the
same key.  Our experiments have shown that using Zobrist hash in the extender is
rather inefficient.  To speed up the search, the extender must be «cleansed» as
much as possible.

We did not specifically mention the Zobrist hash key method in our paper, but on
page 4 we did talk generally  about the comparison speed-up by way of using hash
keys (thus covering the Zobrist method as well).  It shouldn't be much of a
problem to refer to the Zobrist method specifically, of course.

An excerpt fromt the paper (bottom of page 4):

"In order to speed up the search a positional checksum (16-bit) can be
introduced so that the control checksum should be verified before any comparison
of positions.  In case the sums do not check out correctly there is no need to
investigate complete matrices:  they simply have to differ.  As a checksum a
part of the hash key variable can be used, of course  if the program has viable
hash support."

One more thing.  In some cases the slow computation of hash key does not pay off
in extended search.  It is, of course, well known that the optimisation of the
extender is crucial for the efficiency of an engine.

Thus, at least in our opinion, the only source of information that can serve as
a basis for detecting draws  (in all cases) are variant strings.  The detection
procedure _must_ be implemented in the extender as well because if a repetition
has been detected the search needn't evaluate the position further and it
needn't expand the tree.

The procedure that we described runs correctly in _all_ cases. The castling, ep
and promotion questions are not relevant as the draw detector applies _only_ to
_reversible_ moves.  As it has been shown, the move generator sets a flag in the
variant list only if non-reversible moves are in question, so that if in the
inverse analysis a move that is not reversible has been found, the procedure is
terminated.

The procedure has two stages:

1.  Deletion of the concatenation list (asm:  mov cx,24; xor ax,ax; rep stosw
NB.: this is VERY fast!)

2.  A single-pass processing of the concatenating list that has 24 integers.
While it is being processed the machine register AX stores dynamically the
number of the vectors that are not 0,  while as soon as AX gets the value of 0 a
repetition of moves has been detected.

The advantage of this method can be seen especially in positions with a small
number of pieces and long checking sequences where the bulk of the processing is
done in the first few elements of the concatenating list.  The generation and
processing of 64-bit Zobrist keys takes a bit of time so we think that our draw
detector is better suited for Axon than the classical methods employing the
Zobrist keys.

So we hope that the algorithm described in the paper will find its place in fast
chess programs, especially in cases where the access to draw detection is
possible only via variant strings (or similar strings) due to absence of
positional keys.

BTW, Djordje has already replied to some questions regarding the structure of
the 6-byte hash as used in Axon in one of the posts in the Winboard Forum, as a
reply to Tord Romstad's (Gothmog) and Rahman Paidar's (Ktulu) questions.

Regards,

Vladan and Djordje



This page took 0.09 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

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