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.
However, all of those statements were made at the time when typical search depth was much lower than today. Nowadays some authors say that given enough search depth, history heuristic produces just a random noise[5] , whereas Ed Schröder, 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:
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 Geschwenter, 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 [8] . 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.
Jonathan Schaeffer (1989). The History Heuristic and Alpha-Beta Search Enhancements in Practice. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 11, No. 11, pp. 1203–1212. ISSN 0162-8828, zipped ps, pdf
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.
Table of Contents
Random Noise?
However, all of those statements were made at the time when typical search depth was much lower than today. Nowadays some authors say that given enough search depth, history heuristic produces just a random noise [5] , whereas Ed Schröder, 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: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 Geschwenter, 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 [8] . 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.See also
Late Move Reduction Test Results
Selected Publications
Forum Posts
1995 ...
2000 ...
2005 ...
2010 ...
2015 ...
External Links
References
What links here?
Up one Level