Author: Gerd Isenberg
Date: 02:51:10 07/31/04
Go up one level in this thread
On July 31, 2004 at 05:03:13, Gerd Isenberg 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. :) >> >> >> >> Christophe > > >Yes, one has to consider each slot != 0 to look whether it is ok. > >Lets try two white knights on f3,d4 and the following sequence: >d4b3,b3d2,f3d4,d2f3 or >d4b3,f3d4,b3d2,d2f3 or... > >d4b3,b3d2,d2f3->d4f3 >and f3d4 > >One idea, if vector != 0, might be to look for pairs of slots with swapped >from/to coordinates. And if found whether both slots are associated with the >same piece. We concat d4f3,f3d4 to get zero here. > >Another idea, which require at least two bit piece information inside the moves, >is to use 8 bitboards as chain vector. The bitboards are indexed by w/b >knight/rook/queen/king and are xored by 2**from|2**to. oups, too early in the morning ;-) Forgot the bishops of course! > >But that looks not cheaper than the ususal zobrist key approach, where all keys >of reversible move pairs (w/b or b/w) are xored inside one 64-bit register, >looking for zero. > >Gerd
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.