Computer Chess Club Archives


Search

Terms

Messages

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

Author: José Carlos

Date: 07:22:25 07/31/04

Go up one level in this thread


On July 31, 2004 at 09:44:30, Christophe Theron wrote:

>On July 31, 2004 at 05:03:13, Gerd Isenberg 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. :)
>>>
>>>
>>>
>>>    Christophe
>>
>>
>>Yes, one has to consider each slot != 0 to look whether it is ok.
>>
>>Lets try two white knights on f3,d4 and the following sequence:
>>d4b3,b3d2,f3d4,d2f3 or
>>d4b3,f3d4,b3d2,d2f3 or...
>>
>>d4b3,b3d2,d2f3->d4f3
>>and             f3d4
>>
>>One idea, if vector != 0, might be to look for pairs of slots with swapped
>>from/to coordinates. And if found whether both slots are associated with the
>>same piece. We concat d4f3,f3d4 to get zero here.
>>
>>Another idea, which require at least two bit piece information inside the moves,
>>is to use 8 bitboards as chain vector. The bitboards are indexed by w/b
>>knight/rook/queen/king and are xored by 2**from|2**to.
>>
>>But that looks not cheaper than the ususal zobrist key approach, where all keys
>>of reversible move pairs (w/b or b/w) are xored inside one 64-bit register,
>>looking for zero.
>>
>>Gerd
>
>
>
>I think it could be cheaper than Zobrist hash keys.
>
>If you want to avoid computing hash keys in QSearch for example, for performance
>reasons, and depending how you QSearch works, you might have to find a way to
>detect draws.
>
>If your program generates some checks in the QSearch and also generates some
>escapes to check in QSearch, you need a draw detector.
>
>But the repetition detection is not going to be called at every node. Just at
>the nodes where the move played is not irreversible (i.e. it's not a capture).
>In QSearch most moves are captures, so the repetition detection is going to be
>called seldomly. And in most cases it is going to return "not a draw" very
>quickly (because the previous move was a capture for example).


  You could even keep a counter of non-capture moves (you can use the 50 moves
counter for this) in qsearch. Then, only if that counter is at least 4, you need
to look for repetitions. This would restrict the tests even more, making it
faster.

  José C.


>On the other hand, if you use a hash key you have to compute it at every node.
>And it is not free at all when you consider that it moves 64 bits integers
>around, and that it has to be added in several branches of the make move code
>(one case for simple moves, one case for captures, one case for castling, one
>case when you capture a rook that could have been part of a castle move, and so
>on...).
>
>So it is possible that a repetition detection not based on Zobrist hash keys
>will be faster for programs that have a very fast and optimized QSearch.
>
>
>
>    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.