Computer Chess Club Archives




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

Author: José Carlos

Date: 15:48:16 07/29/04

Go up one level in this thread

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.

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