Author: Dan Newman
Date: 23:28:02 05/03/00
Go up one level in this thread
On May 03, 2000 at 23:28:51, Robert Hyatt wrote: >On May 03, 2000 at 22:16:12, William Bryant wrote: > >>On May 03, 2000 at 18:20:36, Robert Hyatt wrote: >> >>>On May 03, 2000 at 14:31:19, Dan Newman wrote: >>> >>>>On May 02, 2000 at 21:29:46, Robert Hyatt wrote: >>>> >>>>>On May 02, 2000 at 20:35:09, William Bryant wrote: >>>>> >>>>>>In my program my killer table is simply an array of [ply][2] with two killers >>>>>>allowed per ply. When updating the killer table, I replace the first killer >>>>>>with the new one (assuming it is not the same move), and move the old first >>>>>>killer to the second killer position, dropping what ever move is in the second >>>>>>killer position. >>>>>> >>>>>>In the introductory paragraphs of Ernst's book, he describes using counters >>>>>>to order the killer moves (page 23) >>>>>>"The killer moves carry "hit" counters with them which specify their priorities >>>>>>for sorting and replacement." >>>>>> >>>>>>This would, of course, require a larger table, and more time spent updating >>>>>>and sorting the killer table. >>>>>> >>>>>>Is this more efficient or effective than a standard replace table? Other >>>>>>thoughts or comments about organizing the killer moves? >>>>>> >>>>>>Thanks. >>>>>> >>>>>>William >>>>>>wbryant@ix.netcom.com >>>>> >>>>> >>>>>I use counters... I think this is the right way to do this... >>>> >>>>Bob, >>>> >>>>I just looked at Crafty v17.10 (to see if and where you zero the counters) >>>>and didn't see them. I suspect you got rid of the counters when you went >>>>SMP (otherwise you'd have to do some locking to keep the counters and moves >>>>coherent, I suppose). [I've been zeroing the counters in my program in the >>>>wrong spot I think...] >>>> >>>>-Dan. >>> >>> >>>you are right. I don't know when I did that. I now just always add a new >>>killer by bumping #1 to #2, and #2 out. Unless the move is already in the >>>list in the #1 spot. Then I leave it alone. >>> >>>I'm not sure when I did this. But for your question of zeroing the counts, >>>I did it in search... when I entered search, I would clear killer_count[ply+1] >>>(the next ply's counters). >> >>I appreciate the responses, but I think you all (yall) just lost me. >> >>I assume the killer table is zeroed at the start of each search. >>Also I assume the killer table only holds two moves for each ply, and the move >>with the lowest counts is replaced when a new one is added. >> >>So are you zeroing the counts and/or the entire list as you move through the >>tree? >> >>William >>wbryant@ix.netcom.com > > >If you leave the counts alone (and I see no reason to _ever_ clear the killer >moves themselves, just the counts) you run into a possible problem. You find >a good killer and it is used often so that its count gets quite high. However, >this position is 'odd' and hardly any other branches will be refuted by this >killer. But its count is high, and unless another killer somehow gets an >equally high counter, this one sticks in slot 1, and the others just displace >each other in slot 2. > >The easy solution is to clear ply N+1's counter when you first reach ply N. > >There are other approaches... but you must do something. IE if you look at >my code, I don't clear the history counts during the search, but after I make >a move, I do 'shrink' them, to avoid this problem... When I first tried the history heuristic I had trouble with count o'flow: I used "count += 1 << depth" as sugested in Schaeffer's paper. The trouble is that you can easily search to near and beyond depth=32 on an endgame, all within a single search. I've been using "count += depth * depth" ever since I saw it in Crafty... [IIRC, I first tried something like "count += 1 << (depth >> 1)" which didn't work nearly as well.] -Dan.
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.