Author: Robert Hyatt
Date: 11:28:06 06/22/98
Go up one level in this thread
On June 22, 1998 at 13:56:57, Don Dailey wrote: >On June 22, 1998 at 13:24:58, Peter Fendrich wrote: > >>On June 22, 1998 at 11:33:50, JW de Kort wrote: >> >>>Hi, >>> >>>Here are two simple questions; >>> >>>1. can anybody give me a hint on how to implement the killer heuristic? >>> >>>2. Can anybody point me to a source taht explains the history heuristic? The >>>only reference i found is to some work by mr. Schaefer, but these books are not >>>available to me. >>> >>> >>> >>>Any help appriaciated!! >>> >>>Jan Willem >> >>Hi Jan, >>they are both technically quite easy to implement. >>What you must know, however, is that hash-tables, move ordering and these two >>heuristics are very closely interacting with each other so the way you implement >>one of them affects the optimal implementation for the others. Testing and more >>testin is the only way to find out in detail which combination is best. >> >>1) Killer heuristic. >>The idea is that the same move often is a "killer move" on the same plydepth >>regardless of what the previous move was. This is true very often during the >>tree search. >>The implementation is as a table. >>The classical killer table has one entry for each possible plydepth. The entry >>is a move. In every node, during the tree search, you just store the move that >>turned out to be the best one in that node. You store it in the entry for that >>plydepth. Whenever you are going to generate moves you grab the killer move for >>that plydepth and generate it as one of the first moves (after hash-move and >>captures). Now, to get it more effective you can do some enhancements. As an >>example: don't save capture moves in the killer table. They will be tried early >>anyway. >> >>My own implementation has two (2) entries for each plydepth. Each entry includes >>a move and a counter. Each time one of the two moves is the 'best' one the >>counter for that move is incremented. When a new killer move is found it >>replaces the move with the lowest counter. The new move is stored with the >>counter set to zero. >>When moves are generated, the killer move with the highest counter is tried >>first and the other comes next (after the hash moves and captures) >> >>I'm sure you will find code for Killer tables in some of the source code samples >>available on the net. >> >>2) History heuristic. Another post gave you an address to Schaeffers original >>article so I will save my fingers... :) >> >> >>//Peter > > >Hi Peter, > >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 >... >... > >etc, they keep knocking each other out. Once in a great >while move A will come along making A a little higher yet, >until it is unlikely to defeat the low frequency A move. > >I use a simple scheme where killer A is always the last killer. >If a new killer comes along, it becomes the new killer A but >the old killer A gets put in the B slot. This works quite >well because often there is great "locality", a type of position >comes along where a new move tends to work as a killer for a >while and then a grandfather move changes the nature of the >position such that the original move is best again. > >I also find that for my progam it is better to only consider >moves that create cutoffs. When I always just save the best >move I get an increase in the node count. I don't know >why this should be though, perhaps it's time for me to revisit >this issue. > >I will try the counter idea which might work anyway despite >my objections. Things are not always the way they seem I >have discovered long ago. I can think of other possibilities >too. > >- Don the count is highly effective. You can encounter a position where move X is a killer every time you get there, until you try a move that finally refutes the killer, which will give you a *new* best move and killer. If you don't watch out, the old "highly effective" killer will be lost, or will be tried only after the new killer, and slow you down... The best example is a position where black's king is on e8 and black's rook is on a8 and white has a knight on b5. The "killer" is Nc7+, and most moves will be refuted by that, except for a king or rook move. But when you try the next move at the previous ply, you probably want to go back to the Nc7 killer first.
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.