Author: Ricardo Gibert
Date: 03:04:34 07/31/04
Go up one level in this thread
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. > > > > 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.