Author: Don Dailey
Date: 14:24:38 06/24/98
Go up one level in this thread
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
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.