Author: John Stanback
Date: 20:36:36 06/24/98
Go up one level in this thread
On June 24, 1998 at 19:44:35, Don Dailey wrote: >On June 24, 1998 at 17:56:20, Robert Hyatt wrote: > >>On June 24, 1998 at 17:24:38, Don Dailey wrote: >> >>>On June 22, 1998 at 14:24:01, Bruce Moreland wrote: >>> >>>> >>>>On June 22, 1998 at 13:56:57, Don Dailey wrote: >>>> >>>>>I have never used the counter idea. I thought about it and assumed >>>>>it would not be very effective. But I would like to give a try >>>>>to satisfy my curiousity. The reason I didn't try it is because >>>>>once a move got put in the "winner" slot, even if it was not >>>>>a very popular move, it might never get bumped since it is possible >>>>>for other moves to constantly "knock each other out." >>>>> >>>>>Move A count = 10 >>>>>MOVE B count = 1 >>>>> >>>>>Move B comes along, replace move C new count 1 >>>>>Move C comes along, replace move B new count 1 >>>>>Move B comes along, replace move C new count 1 >>>>>Move C comes along, replace move B new count 1 >>>> >>>>When you open a node, clear the killers at the next ply. >>>> >>>>So at the top of search, you zap these, and the first time you try a candidate >>>>move, the killers at that candidate's depth are fresh. >>>> >>>>This seems insane but maybe it isn't. >>>> >>>>I've been doing this for so long (I didn't invent it), that I haven't >>>>questioned, but now that I think about it I can think of some other experiments. >>>> >>>>bruce >>> >>>Ok, I did a lot of expermentation and now after a lot of effort have >>>a version that is 1/2 percent fewer nodes than what I had. A few >>>positions are slower, a few faster. I doubt this has any statistical >>>signficance. >>> >>>So, I am either doing something wrong, or the way I have been doing >>>it is about the same (but much simpler.) >>> >>>Here is what I do, please tell me if I'm missing an implementation >>>detail you guy's may have discovered: >>> >>>For each level of the search I have a 2 killer list with a counter. >>>Every time a killer is found, I do one of 2 things, increment the >>>counter if it is one of the 2 killers I am currently saving, or >>>replace it with the least used killer according to the counter. >>>The new killer gets a count of 1. >>> >>>During the search I try the most popular killer (by counter) first >>>and the other killer second (after the hash table move and captures.) >>> >>>This whole counter thing is actually slower than what I was doing if >>>I don't use Bruce's suggestion of clearing the next level, except it >>>seems to work best to clear two levels up the tree (the grandchildren >>>level.) Since I'm using extra memory and extra memory references and >>>slightly more complex logic, the half percent reduction in nodes makes >>>the program slightly slower. I'm still trying to make the idea work >>>however... >>> >>>I'm also wondering if anyone has done it the way I do. I've never >>>seen the algorithm described the way I do it and it's always the >>>counter idea. Maybe the way I do it is just as good? Sometimes >>>each program responds differently to different algorithms. >>> >>>I'm actually surprised the counter method is at least as competitive, >>>because I can see how an unpopular move can stick as I described >>>before. Probably why Bruces's clear counter thing is good. >>> >>>Someone said my method will throw away the best killer but this is >>>not true. It will just migrate to the 2nd place slot and only >>>be lost if a 3rd move comes along while it is in the 2nd place >>>slot. Most of the time the most popular move will be in the killer >>>list and if it is the most popular it will spend most of it's time >>>in the first slot. >>> >>>- Don >> >> >>I'm lost. What you describe is exactly what I do, and have done for years. >>Two killers, two counters, clearing the counters at ply+1, and so forth. I >>think this is what Bruce does too... so I don't understand your question at >>all because it seems like you are doing exactly the same thing?? > >So people have posted telling me I'm not doing it the fastest way >which is using the counters like you and Bruce do. > >The way I do it NOW is simpler than using counters, and appears to be >slightly faster but for all practical purposes the same speed over a >20 position sample. > >So my question is where is my speedup? > > >Here is the way I do it now: > >I keep killerA and killerB for each level. When a new killer comes >along it always get placed in the killerA slot. But if there is >a different move in killerA slot I move it to killerB first. > >I always use killerA first and then KillerB when ordering my moves. > >- Don I have always used this method too, except that I keep a 3rd killer which is for the best move at nodes where alpha < score < beta (this only helps a little). I've never tried keeping a counter for killers. John
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.