Author: John Stanback
Date: 14:46:56 06/25/98
Go up one level in this thread
On June 25, 1998 at 01:04:57, Don Dailey wrote: > >>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 > > >I have been experimenting with the counter idea and so far it has >not proven to be of any value. My best implementation of the counter >method saves about 1/2 percent of the nodes over the method you and me >are using but using more memory and involves more bookeeping so their >is a slight slowdown. > >I'm amazed that it works at all and yet the counter method seems >completely broken to me and illogical. I can easily construct an >example where 1 move is a killer a very tiny percentage of the time >and yet will always be tried first. It's sort of like a race, but >where one guy gets a head start and the coach at random intervals >makes one of the other runners start at the beginning again! > >In several positions the counter method had much greater node >counts and and in several others it was better. I tried 20 >positions. I think the reason it does not do as badly as one >would expect is that it is probably not too common to have >more than 2 moves compete for killer status. This method would >be quite sound if there were never more than 2 moves competing >to be the cutoff king. > >I have always seen the counter method described in the >literature and always wondered what the hell they were talking >about. I never ever implemented it for the reasons I have >stated above. > >The strange thing about this, is that the only way to make it >work is to constantly reset the counters, an idea Bruce >passed on to me. I think this cures it of the "unfair race" >behavior by making everyone start at the beginning every once >in a while! It also solves the "locality" problem, where the >position changes fundamentally due to an ancestor node and the >number one killer may not work for an entire subtree. > >Potentially there must be a big improvement we can make, because >almost any move ordering experiment will drastically help at >least SOME positions. That means, for at least those positions, >that there is something much better than what you are doing! >Maybe there is a way to consistantly get something very close >to the best and bypass most of the noise? > >- Don I agree that a good way to estimate the potential improvement available is to do a bunch of strange things with move ordering and use the lowest node count for each position as a "reference". I'm guessing that improvements of 20% or more on average might be possible... One other thing I do for move ordering that seems to help a little is to give a slight preference to knight and bishop moves and a slight penalty to pawn and king moves. As for history heuristic, I'm still using a variant of this idea that I came up with to save a little memory under DOS. I have a table like this: Bonus[side][piece][square] which gets incremented when a cutoff occurs. For the best move, the piece and destination square form the indexes to the array. As I recall this was slightly worse (< 1 percent?) than the standard 64 x 64 history table. 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.