Computer Chess Club Archives




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

Author: vladan

Date: 14:35:16 08/01/04

Go up one level in this thread

On August 01, 2004 at 14:23:26, Uri Blass wrote:

>On August 01, 2004 at 12:40:26, Djordje Vidanovic wrote:
>>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
>>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
>I think that the most important thing to be competitive against strong engines
>is not speed tricks but algorithm tricks.
>Shredder8 could be competitive against strong engines even in case that it was
>twice slower than what it is today.
>  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.
>What it can be used for?
>If it is too dangerous to use them for draw detection then it seem to me also
>too dangerous to use them at all unless you use hash only for order of moves and
>not for pruning.
>Another question is how much speed improvement do you think that you get from
>not using 64 bit zobrist keys.
>Note that I consider all the small linear improvement as not important(after all
>being 20% faster means less than 20 elo improvement).
>I do not say that I do not care about speed but I am not interested in speed
>tricks that will give me less than 20% speed improvement unless the
>implementation can be done in a short time.

Hi Uri,

We try to find optimal solutions for our program. In my opinion the right
combination is:

1. Zobrist 64-bit in normal search where all techniques (direct hash pruning of
course) will be used. Draw detection in that case will be performed using
standard approaches.

2. Our approach using variant strings could be performed in Qsearch, in the
nodes where Zobrist key is not calculated.

A new version of Axon will have the both techniques implemented.

For me everything is important. If the opponent program has the same techniques
and the knowledge as mine, I will be in advantage if my program is faster.



(Axon programmer)

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.