Author: Uri Blass
Date: 20:38:50 07/30/03
Go up one level in this thread
On July 30, 2003 at 17:34:55, Gerd Isenberg wrote: >On July 30, 2003 at 16:39:57, Bas Hamstra wrote: > >>On July 30, 2003 at 12:17:36, Gerd Isenberg wrote: >> >>>On July 29, 2003 at 14:34:41, Bas Hamstra wrote: >>> >>>>On July 29, 2003 at 00:16:53, macaroni wrote: >>>> >>>>>I have been having great trouble finding an efficient routine for Repetition >>>>>checks, I can get the zobrist keys of the current line being searched, but what >>>>>is the best (if there is a best) method of comparing them to check for 3 the >>>>>same? it seems crazy to loop through all of them for each one, looking for like >>>>>positions. Is there something really simple and nice i'm completely missing? or >>>>>is that the only way, >>>>>Thanks all :) >>>> >>>>How about this: char RepCheck[64000]. Now you in each position you take the last >>>>16 bits of the hashkey. If RepCheck[Last16] is nonzero, it *might* be a >>>>repetition and you do the extensive check of comparing hashkeys all to the root. >>>>For this to work, you increment RepCheck[Last16]++ in your Make(Move) code. >>>>Decrement it at Unmake(). So now you have 1/64000 th of the cost... >>>> >>>>Bas. >>> >>>Hi Bas, >>> >>>The "Ronald de Man" trick works well, >>>except Last16 becomes a bit larger than 64000 in your sample ;-) >>>May be last13 or last14 with smaller tables is even enough. >> >>Maybe. But as the game proceeds the probability of a "hit" becomes higher and >>higher, even if there was no real repetition at all. Suppose you are at move 30 >>in a game and there is no real repetition. What's the probability of NOT getting >>a hit in this case? Probably smaller than you would think, says my gut feeling. >>Like throwing a 16bit dice 60 times in a row, not getting ONCE that number ;-) >>Therefore I prefer to have a not too small table. >> >>Bas. > >I see, i checked my code and only use 2^^12 entries, 4 KByte. >May be the reason IsiChess lost to Tao ;-) > >First of all i use gameMoveCount50 + 4 <= gameMoveCount of course. >I guess the collision rate is so low, that the table pays clearly off. There are >N entries set in 4K, where N is the number of all reversable (half) moves played >in the game and in current search backward from the current search position, <= >100. How much speed can you get from faster repetition detection? Do you use more than 1% of your time for repetition detection? > >There are still a lot of blanks inside the table. Ok 64K is not so huge today, >but 16 4K pages instead of one, hopefully at least in second level chache - if >you have more of these tables it becomes narrow in cache. Remember the thread >about TLB misses ;-) I do not understand all the cache considerations. I only know that if you use arrays often then it is better to do it with small arrays and not with big tables. I do not understand the comparison between 16 4K and 64K. Where do you have 16 4K in this thread? Uri
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.