Computer Chess Club Archives


Search

Terms

Messages

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

Author: Ricardo Gibert

Date: 07:43:08 07/31/04

Go up one level in this thread


On July 31, 2004 at 09:52:37, Christophe Theron wrote:

>On July 31, 2004 at 06:04:34, Ricardo Gibert wrote:
>
>>On July 30, 2004 at 23:14:42, Christophe Theron wrote:
>>
>>>On July 30, 2004 at 23:05:05, Christophe Theron wrote:
>>>
>>>>On July 30, 2004 at 20:26:19, Uri Blass wrote:
>>>>
>>>>>On July 30, 2004 at 20:03:55, Christophe Theron wrote:
>>>>>
>>>>>>On July 30, 2004 at 06:47:39, Gerd Isenberg wrote:
>>>>>>
>>>>>>>On July 29, 2004 at 23:18:53, Walter Faxon 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.
>>>>>>>>>
>>>>>>>>>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.
>>>>>>>>>
>>>>>>>>>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. :)
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>    Christophe
>>>>>>>>
>>>>>>>>
>>>>>>>>Will this detect when two like pieces have "traded places" in the repeated
>>>>>>>>position?
>>>>>>>
>>>>>>>Good point.
>>>>>>>
>>>>>>>I don't see how the "New Approach" handles "traded places" as well, because the
>>>>>>>list_of_moves doesn't contain piece information but only from/to squares.
>>>>>>>
>>>>>>>So occasionally the "New Appoach" may miss some repetitions, where rooks or
>>>>>>>knights have traded places. Whether this is practically relevant is another
>>>>>>>question.
>>>>>>>
>>>>>>>Gerd
>>>>>>
>>>>>>
>>>>>>
>>>>>>It will also catch the cases where pieces have just traded squares.
>>>>>>
>>>>>>Each piece is tracked individually by a vector summing up all of its moves. When
>>>>>>all vectors are 0, all pieces have been moved back to their "original" square.
>>>>>>
>>>>>>The "master vector" is just a way to tell quickly if it is possible that there
>>>>>>is a repetition, and in this case all the individual vectors must be checked.
>>>>>>
>>>>>>It is a "perfect" detector in the sense that it will not make any mistake.
>>>>>>
>>>>>>
>>>>>>
>>>>>>    Christophe
>>>>>If I understand correctly
>>>>>it can miss some repetitions when 2 white rooks traded squares because in that
>>>>>case not all vectors are 0 and vector of one rook is positive when vector of
>>>>>second rook is negative.
>>>>>
>>>>>Uri
>>>>
>>>>
>>>>
>>>>Mmh... You are right.
>>>>
>>>>So it is not perfect in that sense.
>>>>
>>>>Someone has a solution for this?
>>>>
>>>>Actually I think the detector mentionned in the paper would have exactly the
>>>>same problem.
>>>>
>>>>
>>>>
>>>>    Christophe
>>>
>>>
>>>
>>>OK I have the solution.
>>>
>>>The master vector trick still works.
>>>
>>>When the master vector is 0 (nul vector), check the array.
>>>
>>>Instead of looking for 0 everywhere, the following conditions are accepted for
>>>each individual piece vector:
>>>* if it is 0: OK
>>>* if it is not 0 and the content of (square_of_the_piece + vector) is the piece
>>>itself on the current board (or a similar piece from the same side): OK
>>>
>>>(note that the first condition is just an optimization and can be removed)
>>>
>>>If all the vectors are "OK" then a repetition is detected.
>>>
>>>So the algorithm still works, but it is a little bit less elegant now. :)
>>
>>
>>A lot less elegant when you incorporate ep status and castling rights.
>
>
>
>You do not have to take these into account. A move that would change the
>ep/castling status data is an irreversible move that stops the repetition
>detection.

You're right about that of course. Never mind.

>
>What you need is to have a flag in your move stack (or list) to mark
>irreversible moves. You stop the draw detection algorithm (by 3-rep or
>50-moves-rule) as soon as you find an irreversible move.
>
>You also need to maintain this flag if you are using a draw detection method
>based on Zobrist hash keys anyway.
>
>
>
>    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.