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