Author: Peter Fendrich
Date: 10:24:58 06/22/98
Go up one level in this thread
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
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.