Author: Don Dailey
Date: 11:08:44 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 History heuristic ----------------- There are 64 squares a piece can move from, and 64 squares a piece can move to. This means we can store a table of all possible moves (with many impossible ones taking up useless space!) with only 64x64 elements. This is only 4K of table entries. So let the move itself be an index into this table. Each element in the table is a simple counter. Every time a best move is found at any level of the search, increment the counter associated with this move. Now we have a big table, that given any move we can tell how succesful it has been as a cutoff (or best move.) You can use this information to sort the move list. Try to sort high scoring moves (according to the table) close to the front of the list. Generally, you would still put captures, killers and hash table moves up to the very front, but the rest of the moves you could sort according to this scheme. If you find the sorting takes too long, don't do it on the last couple of ply's of the main search. You may want to have a separate table for each color but it probably isn't necessary. One refinement is to increment the counter more heavily near the top of the tree. Your increment factor could be 2^n where n could be distance from leaf nodes. - Don
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.