Home * Search * Move Ordering * History Heuristic
Agache_-_La_Fortuna.jpg

History heuristic,
a dynamic move ordering method based on the number of cutoffs caused by a given move irrespectively from the position in which the move has been made. The Heuristic was invented by Jonathan Schaeffer in 1983 [1] and works as follows: on a cutoff we increment a counter in a special table, addressed either by [from][to] (the Butterfly Boards) or by [piece][to] [2] . The added value is typically depth * depth or 2 ^ depth, based on the assumption that otherwise moves from the plies near the leaves would have to much impact on the result. Values retrieved from that table are used to order non-capturing moves. This simple heuristics performs usually better than domain-dependent heuristics, though it may be combined with them. For example, in Rebel only a few non-captures are ordered by history heuristics, then a piece-square approach is used [3] . In the literature, history heuristic is often presented as depth-independent generalization of the killer moves. It is also said to reflect long-term plans in a position.
Alfred Agache: La Fortuna, 1885 [4]

Random Noise?

However, all of those statements were made at the time when typical search depth was much lower than today. Nowadays authors of the leading programs say that given enough search depth, history heuristic produces just a random noise. In Crafty it is not used anymore [5] , whereas Ed Schröder, author of Rebel, advocated not taking into account the cutoffs from the last couple of plies.

Update

This is how the history array may be updated, if a beta-cutoff occurs:
   if ( score >= beta ) { // cutoff
      if ( isNonCapture (move) )
         history[side2move][move.from][move.to] += depth*depth; // 1 << depth
      ...
      return score;
   }

See also


Selected Publications


Forum Posts

1995 ...

2000 ...

2005 ...

2010 ...


External Links


References

  1. ^ Jonathan Schaeffer (1983). The History Heuristic. ICCA Journal, Vol. 6, No. 3
  2. ^ Jos Uiterwijk (1992). Memory Efficiency in some Heuristics. ICCA Journal, Vol. 15, No. 2
  3. ^ Move Ordering in Rebel by Ed Schröder, also available as pdf
  4. ^ Alfred Agache: Alegoria da Fortuna, 1885, Palais des Beaux-arts, Lille, Category:Alfred Agache - Wikimedia Commons
  5. ^ Re: LMR: history or not? by Robert Hyatt from CCC, December 13, 2007

What links here?


Up one Level