Author: Robert Hyatt
Date: 15:30:58 06/25/98
Go up one level in this thread
On June 25, 1998 at 17:46:56, John Stanback wrote: >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. > I (actually Harry Nelson) found the same thing. In Crafty, I just generate 'em in that order, knights, bishops, rooks, queens, king and then pawns... You can (I don't because bitmaps makes it not so convenient) also emit moves toward the center of the board first (CB did this). >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.