History_Heuristic - peregrineshahin/ChessProgrammingWiki GitHub Wiki

title: History Heuristic

Home * Search * Move Ordering * History Heuristic

[ Alfred Agache - La Fortuna, 1885 [1] 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 [2] 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] [3] . 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 [4] . 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.

Optimisations to History Heuristic

In addition, there has been a new approach to also penalise moves that have been searched but failed to produce a beta cutoff should the node eventually fail high. This heuristic has been worth 5 to 10 elo in modern engines.

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;
   }

Counter Moves History

A combination of the History Heuristic in conjunction with the Countermove Heuristic, proposed by Bill Henry in March 2015 [6] , as already used by Álvaro Begué in his Checkers program 20 years before [7] , was implemented by Stockfish contributor Stefan Geschwentner [8], further tuned and improved by the Stockfish community, and released in Stockfish 7 in January 2016, dubbed Counter Moves History and mentioned to gain some Elo points [9]. Stockfish's History and Countermove arrays are piece type and to-square based, not butterfly based. Each entry indexed by a previous move, is a complete history table with counters indexed by the move refuting that previous move. Pushing the idea further, Stockfish applies Follow Up History (FUH) tables, indexed by two consecutive moves of the same side [10].

Continuation History

In recent times engines also have history tables for 4 plies before and even 6 plies before (in the case of Stockfish and Berserk), as an extension to counter moves history and follow up history.

See also

Late Move Reduction Test Results

Selected Publications

1980 ...

2000 ...

Forum Posts

1995 ...

2000 ...

2005 ...

2010 ...

2015 ...

2020 ...

External Links

References

  1. ↑ Alfred Agache - Alegoria da Fortuna, 1885, Palais des Beaux-arts, Lille, Category:Alfred Agache - Wikimedia Commons
  2. ↑ Jonathan Schaeffer (1983). The History Heuristic. ICCA Journal, Vol. 6, No. 3
  3. ↑ Jos Uiterwijk (1992). Memory Efficiency in some Heuristics. ICCA Journal, Vol. 15, No. 2
  4. ↑ Move Ordering in Rebel by Ed Schröder, also available as pdf
  5. ↑ Re: LMR: history or not? by Robert Hyatt from CCC, December 13, 2007
  6. ↑ Improving History Tables by Bill Henry, CCC, March 02, 2015
  7. ↑ Re: Improving History Tables by Álvaro Begué, CCC, March 02, 2015
  8. ↑ Followup moves by Stefan Geschwentner, FishCooking, January 12, 2014 » Counter Moves History
  9. ↑ Re: Stockfish 7 progress by Lucas Braesch, CCC, January 17, 2016
  10. ↑ Re: CMH question by Lucas Braesch, CCC, December 09, 2019
  11. ↑ Negative Plausibility Move Ordering by Alessandro Damiani, CCC, July 09, 2009

Up one Level