Author: Don Dailey
Date: 21:00:15 06/24/98
Go up one level in this thread
On June 24, 1998 at 21:09:40, Robert Hyatt wrote: >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 > > >OK.. here's where that fails: start in a position where white has a knight >on b5, black has a rook on a8 and a king on e8. after searching some >meaningless move for black, you eventually discover at ply=2 that Nc7+ >wins at least an exchange, plus maybe wrecks his pawn structure as the knight >tries to get out. > >For the next several black moves that you try at ply=1, each falls to Nc7+. >Finally, you try (say) O-O, and after Nc7 Rc8 there is no problem for black, >so you find something better for white. That "something better" becomes your >primary killer. Back to ply=1, you try another meaningless move, and now >rather than trying the killer Nc7, you try the best move from the last search >here, and *then* discover that Nc7 is better (again). > >That's where you lose nodes. If you keep the count, you will always try >Nc7+ first, because it will have the higher count, and won't get displaced >when you occasionally stumble across a move that refutes it. What if Nc7+ suddenly becomes a loser because some parent node changes the context of the search? If the counter is built up pretty high then you will ALWAYS try Nc7+ even though it is wrong. My method will quickly switch to the new move and quickly switch back when Nc7+ becomes the right move again. With my method Nc7+ does not become displaced, it will still remain the 2nd killer and will immediately become the primary killer as soon as it creates a cutoff. So I see some serious weaknesses with the counter approach too. I still don't think it's logical because I can show you how a move that's rarely played can remain the top killer with counters. The fact that they can get reset makes them unreliable counters, what are they counting? And how can you compare them fairly when each counter could have been reset at different times? >How big a savings this is I don't know, however, when you factor in the history >moves which are a sort of global killer approach...
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.