Author: Robert Hyatt
Date: 14:56:20 06/24/98
Go up one level in this thread
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??
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.