Author: Robert Hyatt
Date: 07:01:58 05/04/00
Go up one level in this thread
On May 04, 2000 at 02:28:02, Dan Newman wrote: >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. That is the front half of the problem. After a search is done, and the move actually move, I take all the counts as history_w[i]>>=8; This trims them all back, and lets the really useful ones climb back up.
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.