Author: Don Dailey
Date: 16:44:35 06/24/98
Go up one level in this thread
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
This page took 0.01 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.