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.