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: 16:49:26 07/30/04

Go up one level in this thread


On July 29, 2004 at 18:00:00, Robert Hyatt wrote:

>On July 29, 2004 at 17:34:11, Christophe Theron wrote:
>
>>On July 29, 2004 at 14:07:10, Robert Hyatt 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.
>>>>
>>>>They also have a paper about hashing out which I can't
>>>>download.
>>>>
>>>>--
>>>>GCP
>>>
>>>
>>>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.
>
>I've tried that.  Hurts in endgames where there is little q-search and the extra
>cache traffic hurt performance.  Helped in the middlegame.
>
>>
>>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?
>
>
>I don't in the q-search as I don't do checks or anything other than captures.
>That's why I originally decided to try this idea...  has some merit to try again
>however.



I do generate some checks and some escapes from check in the QSearch, and
sometimes very deep.

Actually I also sometimes generate non-capture moves which are neither checks
nor escapes from check in the QSearch...

So I definitely need to detect repetitions there.


    Christophe




>>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.
>
>Right...
>
>
>>
>>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. :)
>>
>>
>
>Always. :)
>
>
>>
>>    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.