Author: Christophe Theron
Date: 20:05:05 07/30/04
Go up one level in this thread
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
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.