Author: Gerd Isenberg
Date: 02:03:13 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. :) > > > > 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. 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.