Computer Chess Club Archives


Search

Terms

Messages

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

Author: Christophe Theron

Date: 08:20:29 07/29/04

Go up one level in this thread


On July 29, 2004 at 07:46:08, Paul Clarke wrote:

>On July 29, 2004 at 06:26:52, Gian-Carlo Pascutto wrote:
>
>>http://arxiv.org/ftp/cs/papers/0406/0406038.pdf
>>
>>I stumbled onto this when doing a search for Axon.
>>Not seen it mentioned here yet.
>
>Cute algorithm, though I'd like to have seen them test it against a more
>conventional approach instead of testing it against a version of Axon with no
>repetition detection. A couple of other thoughts:
>
>1) Do any engines really do full board comparisons to detect repetition? I'd
>have thought comparing Zorbrist signatures would be reliable enough.


It is.

So from a practical point of view, if your program generates a hash key for each
position you do not need anything else to test for repetitions.

If your program does not generate the hash key at every node, then you
definitely need something else and their solution is quite elegant.




>2) Their code seems to analyse the complete move list (since the last
>irreversible move) each time. I can't see any problem with building the
>concatenation list incrementally, you just need to undo the effect of the
>current move when returning from the search.


Their algorithm allows you to answer the question "is the current position the
same as the one at the beginning of the tested string?". It would work forward
or backwards, so the "start" of the tested string can as well be the end of the
list if you wish (that's how they use it).

So you need to start from the current position (the one you reach at the end of
your search) and move backwards until you either find an irreversible move or a
repetition.

If you always start at the last reversible move and move forward, building the
concatenation list incrementally for exemple, you are only going to answer the
question "is the current position the same as the position before the last
reversible move". You will not notice a repetition that has happened in between.



    Christophe



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.