Author: Robert Hyatt
Date: 18:21:33 01/22/03
Go up one level in this thread
On January 22, 2003 at 19:41:33, Nathan Thom wrote: >Hi all, I implemented a pretty quick killer move algorithm into LittleThought >last night from memory of what its supposed to do. > >A couple of questions: >1. First, i incremented the killers[from][to] array by the inverse of the >current depth (ie MAX_DEPTH - depth) when a cutoff occurred. In my code depth 0 >is the root and it increases downwards. I figured this would be better than >plain depth because cutoffs closer to the root node would be better. However i >found this to slow it down considerably. To test my theory, i changed it to >plain depth and it perfored much better than normal. So, can someone explain why >incrementing by depth was better than MAX_DEPTH - depth or this just some quirk >with my implementation/test positions? Also if someone has any ideas as to a >better incremental? > >2. What is a history move? why is it different from a killer move? > >Thanks. I'm not sure I follow what you are doing. First, an explanation of how they both work. 1. Killers. when you fail high at a ply, or you search all moves and find a new best move at a ply, you add that move to the killer list for that ply. Usually this killer list is a list of two moves. Typically they both have a "counter" and each time you go to add a move to the list and it is already there, you increment the counter for that move instead. If it isn't in the list, you replace the killer with the smallest counter. When you search, you search the killer with the largest count, after captures and hash move. Note that each ply has its own set of two moves + counters. So the idea of incrementing by anything other than 1 makes no real sense since killers apply to a specific ply only. 2. History. Here you use a "global" type of list, but there are no real moves in the history list, just counters. There are several ways to index into the history table, and I won't really touch on those. But when a move is best or causes a fail high, you increment the appropriate counter for that move, and you generally want to increment by some constant that varies inversely proportional to the depth. A selection sort is usually used to search the move with the largest history value first, again after the hash and good capture moves.
This page took 0.02 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.