Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Draw Detection by Move Repetition Procedure -- Comments

Author: Gerd Isenberg

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

Go up one level in this thread


On August 01, 2004 at 12:40:26, Djordje Vidanovic wrote:

>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.


Hi Vladan and Djordje,

it seems that your really smart and ressource friendly algorithm detects move
repetitions but not necessarily position repetitions if pieces of one kind
change place:

E.g. two white knights on f3,d4 and the following sequence:

d4b3,b3d2,f3d4,d2f3 or
d4b3,f3d4,b3d2,d2f3 or...
concat
d4b3,b3d2,d2f3->d4f3
and             f3d4

How do you intend to handle such repetitions?


>
>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.


So as soon the unequal counter becomes two (or more general even), it might be a
idea to look for swapped from to coordinates of same piece kinds.


>
>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.


Seems there is some potential for improvement.
Avoiding traversing the list twice.

Btw. see the notes about "loop" instruction in AMD64 (as well as Athlons)
optimization manual:

6.8 The LOOP Instruction

Optimization
Avoid using the LOOP instruction.
...
Rationale
The LOOP instruction has a latency of at least 8 cycles.

Avoid code like this, which uses the LOOP instruction:
loop label

Instead, replace the loop instruction with a DEC and a JNZ:
dec rcx
jnz label

See also 2.23 32-Bit Integral Data Types.


>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.


Yes, thank you very much for sharing your ideas.

Cheers,
Gerd


>
>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 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.