Author: Don Dailey
Date: 10:56:57 06/22/98
Go up one level in this thread
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
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.