Author: Uri Blass
Date: 17:26:19 07/30/04
Go up one level in this thread
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
This page took 0.01 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.