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:56:27 07/30/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:
>>>
>>>>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.
>>
>>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
>speed.
>
>>
>>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. It has 32 integers, one per piece. Actually you only need one per non-pawn
(because pawn moves are always irreversible, so you do not need to take pawn
moves into account). So you could do it with 16 integers if you assume that the
total of pieces (non-pawns) including promoted ones will never exceed 8 per
side.




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



In my case it would have helped, because my rewritten QSearch was very fast and
computing the hash key started to represent a significant percentage of the time
spent in the QSearch (maybe 20% of it).



    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.