Computer Chess Club Archives




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

Author: Christophe Theron

Date: 16:51:37 07/30/04

Go up one level in this thread

On July 29, 2004 at 18:48:16, José Carlos wrote:

>On July 29, 2004 at 18:01:34, Uri Blass 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:
>>>>>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
>>>>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.
>>>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.
>>I think that the interesting improvements are not small linear improvement in
>>>The problem then is how do you check for repetitions?
>>>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.
>>>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.
>>I do not understand
>>Does the array has 64 integers?
>  No, this array is a piece list array, if I understand correctly. You have an
>integer for each piece. When you move a rook from square 1 to square 2, you add
>2-1=1. Then, if you move back the rook to square 1, you add 1-2=-1 and get a
>zero there.
>  He also adds a "master vector", a single integer where you add the 1 and the
>-1 and all the other moves. Only if this master vector is zero, you need to
>check the full list.
>  Sounds like a good idea and it is not only a linear speed improvement, because
>if you do this at every node (and this is faster than the hash key trick, which
>is the key), then you have an exponential improvement (every node is faster).
>  José C.

You've got it José.

But Uri is right, it is only a linear improvement over the method of detecting
repetitions with hash keys.


>>>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.
>>I do not understand but I remember something that sound similiar that was used
>>in the past in tscp.
>>The idea is to detect repetition if the empty squares are the same.
>>Of course the empty squares can be the same without repetition and it caused
>>bugs in  tscp but the idea can still be used by detecting no repetition if the
>>empty squares are not the same and only if the empty squares are the same(not
>>something that happens often) to do more expensive check for repetition.
>>I do not think that all these ideas can help because calculating the hash key
>>after every move is cheap and I think that the only case when something
>>different than hash can help is if you want to have a function to detect if
>>repetition in the next move is possible(you can often use the history to find
>>that it is impossible).

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.