Difference between revisions of "History Heuristic"
(→Update: better update formula) |
(fix flipped clamp bounds) |
||
(6 intermediate revisions by one other user not shown) | |||
Line 4: | Line 4: | ||
'''History Heuristic''',<br/> | '''History Heuristic''',<br/> | ||
− | 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 <ref>[[Jonathan Schaeffer]] ('''1983'''). ''The History Heuristic''. [[ICGA Journal#6_3|ICCA Journal, Vol. 6, No. 3]]</ref> and works as follows: on a [[Beta-Cutoff|cutoff]] we increment a counter in a special table, addressed either by <span style="background-color: #e0e0e0;">[from][to]</span> (the [[Butterfly Boards]]) or by <span style="background-color: #e0e0e0;">[piece][to]</span> <ref>[[Jos Uiterwijk]] ('''1992'''). ''Memory Efficiency in some Heuristics''. [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]</ref> . The added value is typically a multiple of <span style="background-color: #e0e0e0;">depth</span> or <span style="background-color: #e0e0e0;">depth * depth</span>, 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 <ref>[https://web.archive.org/web/20070927195511/members.home.nl/matador/chess840.htm#MOVE%20ORDERING Move Ordering in Rebel] by [[Ed Schroder|Ed Schröder]], also available as [https://silo.tips/download/how-rebel-plays-chess-1 pdf]</ref> . In the literature, history heuristic is often presented as depth-independent generalization of the [[Killer Heuristic|killer moves]]. It is also said to reflect long-term plans in a position. | + | 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 <ref>[[Jonathan Schaeffer]] ('''1983'''). ''The History Heuristic''. [[ICGA Journal#6_3|ICCA Journal, Vol. 6, No. 3]]</ref> and works as follows: on a [[Beta-Cutoff|cutoff]] we increment a counter in a special table, addressed either by <span style="background-color: #e0e0e0;">[from][to]</span> (the [[Butterfly Boards]]) or by <span style="background-color: #e0e0e0;">[piece][to]</span> <ref>[[Jos Uiterwijk]] ('''1992'''). ''Memory Efficiency in some Heuristics''. [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]</ref> . The added value is typically a multiple of <span style="background-color: #e0e0e0;">depth</span> or <span style="background-color: #e0e0e0;">depth * depth</span>, 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 [[Stockfish]] all quiet moves that are not hash moves are ordered by history, while in [[Rebel]] only a few non-captures are ordered by history heuristics, then a piece-square approach is used <ref>[https://web.archive.org/web/20070927195511/members.home.nl/matador/chess840.htm#MOVE%20ORDERING Move Ordering in Rebel] by [[Ed Schroder|Ed Schröder]], also available as [https://silo.tips/download/how-rebel-plays-chess-1 pdf]</ref> . In the literature, history heuristic is often presented as depth-independent generalization of the [[Killer Heuristic|killer moves]]. It is also said to reflect long-term plans in a position. |
− | = | + | =Update= |
− | + | ||
+ | ==History Bonuses== | ||
− | |||
This is how the history [[Array|array]] may be updated, if a [[Beta-Cutoff|beta-cutoff]] occurs: | This is how the history [[Array|array]] may be updated, if a [[Beta-Cutoff|beta-cutoff]] occurs: | ||
<pre> | <pre> | ||
if ( score >= beta ) { // cutoff | if ( score >= beta ) { // cutoff | ||
if ( isNonCapture (move) ) | if ( isNonCapture (move) ) | ||
− | history[side2move][move.from][move.to] += depth*depth; | + | history[side2move][move.from][move.to] += depth*depth; |
... | ... | ||
return score; | return score; | ||
Line 20: | Line 20: | ||
</pre> | </pre> | ||
− | Modern programs use a more sophisticated formula for history updates: | + | Modern programs use a more sophisticated formula for history updates, namely the '''history gravity''' formula: |
<pre> | <pre> | ||
void update(Piece piece, Square to, int bonus) | void update(Piece piece, Square to, int bonus) | ||
{ | { | ||
− | int clampedBonus = clamp( | + | int clampedBonus = clamp(bonus, -MAX_HISTORY, MAX_HISTORY); |
history[piece][to] += clampedBonus - history[piece][to] * abs(clampedBonus) / MAX_HISTORY; | history[piece][to] += clampedBonus - history[piece][to] * abs(clampedBonus) / MAX_HISTORY; | ||
} | } | ||
Line 31: | Line 31: | ||
This scales up history updates when a beta cutoff is unexpected, and scales down history updates when a beta cutoff is expected. A beneficial side effect is that this formula also clamps history values from -MAX_HISTORY to MAX_HISTORY, which prevents oversaturated values. | This scales up history updates when a beta cutoff is unexpected, and scales down history updates when a beta cutoff is expected. A beneficial side effect is that this formula also clamps history values from -MAX_HISTORY to MAX_HISTORY, which prevents oversaturated values. | ||
+ | |||
+ | ==History Maluses== | ||
+ | |||
+ | When a quiet move fails high, it is also common to apply a penalty to all quiet moves that were previously searched. This not only prevents saturated history values, but also gives unpromising moves negative history. In programs with history gravity formula, this is done by applying negative bonus to the history array. | ||
+ | |||
+ | <pre> | ||
+ | |||
+ | const int bonus = 300 * depth - 250; | ||
+ | history.update(bestMove, bonus); | ||
+ | for (Move move : quiets_searched) | ||
+ | { | ||
+ | history.update(move, -bonus); // Stronger programs have a separate formula for maluses | ||
+ | } | ||
+ | |||
+ | </pre> | ||
<span id="CMHist"></span> | <span id="CMHist"></span> | ||
Line 41: | Line 56: | ||
'''Continuation History''' is a generalization of [[#Counter Moves History|Counter Moves History]] and Follow Up History. An '''n-ply Continuation History''' is the history score indexed by the move played n-ply ago and the current move. 1-ply and 2-ply continuation histories are most popular and correspond to Counter Moves History and Follow Up History respectively. Many programs, notably [[Stockfish]], also makes use of 3, 4, and 6-ply continuation histories. | '''Continuation History''' is a generalization of [[#Counter Moves History|Counter Moves History]] and Follow Up History. An '''n-ply Continuation History''' is the history score indexed by the move played n-ply ago and the current move. 1-ply and 2-ply continuation histories are most popular and correspond to Counter Moves History and Follow Up History respectively. Many programs, notably [[Stockfish]], also makes use of 3, 4, and 6-ply continuation histories. | ||
+ | |||
+ | =Capture History= | ||
+ | |||
+ | '''Capture History''', introduced by [[Stefan Geschwentner]] in 2016, is a variation on history heuristic applied on capture moves. It is a history table indexed by moved piece, target square, and captured piece type. The history table receives a bonus for captures that failed high, and maluses for all capture moves that did not fail high. The history values is used as a replacement for LVA in [[MVV-LVA]]. | ||
=See also= | =See also= | ||
Line 84: | Line 103: | ||
==2005 ...== | ==2005 ...== | ||
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=15337 Improving history tables] by [[Michael Sherwin]], [[CCC]], July 25, 2007 | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=15337 Improving history tables] by [[Michael Sherwin]], [[CCC]], July 25, 2007 | ||
+ | * [https://www.talkchess.com/forum/viewtopic.php?t=18345 LMR: history or not?] by [[Alessandro Scotti]], [[CCC]], December 13, 2007 | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=24920 killer moves and history heuristic table] by [[Stuart Cracraft]], [[CCC]], November 17, 2008 » [[Killer Heuristic]] | * [http://www.talkchess.com/forum/viewtopic.php?t=24920 killer moves and history heuristic table] by [[Stuart Cracraft]], [[CCC]], November 17, 2008 » [[Killer Heuristic]] | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=29611 Alternatives to History Heuristics] by [[Edsel Apostol]], [[CCC]], September 01, 2009 | * [http://www.talkchess.com/forum/viewtopic.php?t=29611 Alternatives to History Heuristics] by [[Edsel Apostol]], [[CCC]], September 01, 2009 |
Latest revision as of 11:23, 30 September 2024
Home * Search * Move Ordering * History Heuristic
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 a multiple of depth or depth * 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 Stockfish all quiet moves that are not hash moves are ordered by history, while 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.
Contents
Update
History Bonuses
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; ... return score; }
Modern programs use a more sophisticated formula for history updates, namely the history gravity formula:
void update(Piece piece, Square to, int bonus) { int clampedBonus = clamp(bonus, -MAX_HISTORY, MAX_HISTORY); history[piece][to] += clampedBonus - history[piece][to] * abs(clampedBonus) / MAX_HISTORY; }
This scales up history updates when a beta cutoff is unexpected, and scales down history updates when a beta cutoff is expected. A beneficial side effect is that this formula also clamps history values from -MAX_HISTORY to MAX_HISTORY, which prevents oversaturated values.
History Maluses
When a quiet move fails high, it is also common to apply a penalty to all quiet moves that were previously searched. This not only prevents saturated history values, but also gives unpromising moves negative history. In programs with history gravity formula, this is done by applying negative bonus to the history array.
const int bonus = 300 * depth - 250; history.update(bestMove, bonus); for (Move move : quiets_searched) { history.update(move, -bonus); // Stronger programs have a separate formula for maluses }
Counter Moves History
A combination of the History Heuristic in conjunction with the Countermove Heuristic, proposed by Bill Henry in March 2015 [5] , as already used by Álvaro Begué in his Checkers program 20 years before [6] , was implemented by Stockfish contributor Stefan Geschwentner [7], 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. Pushing the idea further, Stockfish applies Follow Up History (FUH) tables, indexed by two consecutive moves of the same side [9].
Continuation History
Continuation History is a generalization of Counter Moves History and Follow Up History. An n-ply Continuation History is the history score indexed by the move played n-ply ago and the current move. 1-ply and 2-ply continuation histories are most popular and correspond to Counter Moves History and Follow Up History respectively. Many programs, notably Stockfish, also makes use of 3, 4, and 6-ply continuation histories.
Capture History
Capture History, introduced by Stefan Geschwentner in 2016, is a variation on history heuristic applied on capture moves. It is a history table indexed by moved piece, target square, and captured piece type. The history table receives a bonus for captures that failed high, and maluses for all capture moves that did not fail high. The history values is used as a replacement for LVA in MVV-LVA.
See also
- Butterfly Boards
- Butterfly Heuristic
- Chessmaps Heuristic
- Countermove Heuristic
- History Leaf Pruning
- Killer Heuristic
- Late Move Reductions
Selected Publications
1980 ...
- Jonathan Schaeffer (1983). The History Heuristic. ICCA Journal, Vol. 6, No. 3
- 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
- Jos Uiterwijk (1992). Memory Efficiency in some Heuristics. ICCA Journal, Vol. 15, No. 2
- Eric Thé (1992). An analysis of move ordering on the efficiency of alpha-beta search. Master's thesis, McGill University
2000 ...
- Mark Winands, Erik van der Werf, Jaap van den Herik, Jos Uiterwijk (2004). The Relative History Heuristic. CG 2004, pdf
- Jeff Rollason (2006). Driving search with Plausibility analysis: Looking at the right moves. AI Factory, Winter 2006
- Jeff Rollason (2007). Negative Plausibility. AI Factory, Spring 2007 [10]
Forum Posts
1995 ...
- (depth * depth) to replace (1 << depth) by Marcel van Kervinck, rgcc, January 29, 1996
- Killer and history by Jan Willem de Kort, CCC, June 22, 1998
- History Heuristic on its own by Chris Moreton, CCC, January 16, 1999
- What is the History table? by Leonid, CCC, September 15, 1999
2000 ...
- What is the Success Rate of Killer/History Moves? by Roberto Waldteufel, CCC, May 31, 2000
- History Heuristic by Larry Griffiths, CCC, August 28, 2000
- About history heuristics, killers and my futil. pruning code by Severi Salminen, CCC, December 06, 2000 » Killer Heuristic
- killers and history by Nathan Thom, CCC, January 22, 2003 » Killer Heuristic
- quiescent nodes, and history heuristic... by Joel Veness, CCC, January 30, 2003
- History Heuristic by Renze Steenhuisen, CCC, March 16, 2004
- About history and aging it by Mikael Bäckman, CCC, March 17, 2004
- History heuristic by Sergei S. Markoff, CCC, March 18, 2004
- Re: Artificial Intelligence in Computer Chess - *DETAILS* as promised by Artem Pyatakov, CCC, March 28, 2004 » Artificial Intelligence, Golch
2005 ...
- Improving history tables by Michael Sherwin, CCC, July 25, 2007
- LMR: history or not? by Alessandro Scotti, CCC, December 13, 2007
- killer moves and history heuristic table by Stuart Cracraft, CCC, November 17, 2008 » Killer Heuristic
- Alternatives to History Heuristics by Edsel Apostol, CCC, September 01, 2009
2010 ...
- dynamically modified evaluation function by Don Dailey, CCC, December 20, 2010
- Software Engineering by Onno Garms, CCC, March 13, 2011 » Toga
- On history counters again by Mincho Georgiev, CCC, August 31, 2011
- Killer and History: Increased Node Count by Cheney Nattress, CCC, January 15, 2013
- On history and piece square tables by Evert Glebbeek, CCC, May 24, 2013 » Piece-Square Tables
- Possible history table improvement by Laszlo Gaspar, CCC, May 30, 2013
- Improved history heuristic by Sergei S. Markoff, CCC, December 16, 2013
- Followup moves by Stefan Geschwentner, FishCooking, January 12, 2014 » Counter Moves History
- Recalculate history for remaining moves after each search by Sergei S. Markoff, CCC, January 30, 2014
- Idea of different history by Daniel José Queraltó, CCC, April 14, 2014
2015 ...
- Improving History Tables by Bill Henry, CCC, March 02, 2015
- History counters by Robert Hyatt, CCC, May 12, 2015
- History heuristic and fixed depth search by Peter Österlund, CCC, May 16, 2015 » Late Move Reduction Test Results, Texel
- History Heuristic - a new idea on an old idea? by thevinenator, OpenChess Forum, Novembere 19, 2015
- Re: Stockfish 7 progress by Lucas Braesch, CCC, January 17, 2016
- History heuristic and quiet move generation by Daniel José Queraltó, CCC, July 16, 2017 » Move Generation
- CMH question by Vivien Clauzon, CCC, December 08, 2019 » Counter Moves History
2020 ...
- Quick history move by Harm Geert Muller, CCC, May 09, 2020
- History bonus by Michael Hoffmann, CCC, February 09, 2021
External Links
- History Reductions from Ed Schröder's Programmer Corner (Wayback Machine, July 30, 2007)
- Killer heuristic from Wikipedia
References
- ↑ Alfred Agache - Alegoria da Fortuna, 1885, Palais des Beaux-arts, Lille, Category:Alfred Agache - Wikimedia Commons
- ↑ Jonathan Schaeffer (1983). The History Heuristic. ICCA Journal, Vol. 6, No. 3
- ↑ Jos Uiterwijk (1992). Memory Efficiency in some Heuristics. ICCA Journal, Vol. 15, No. 2
- ↑ Move Ordering in Rebel by Ed Schröder, also available as pdf
- ↑ Improving History Tables by Bill Henry, CCC, March 02, 2015
- ↑ Re: Improving History Tables by Álvaro Begué, CCC, March 02, 2015
- ↑ Followup moves by Stefan Geschwentner, FishCooking, January 12, 2014 » Counter Moves History
- ↑ Re: Stockfish 7 progress by Lucas Braesch, CCC, January 17, 2016
- ↑ Re: CMH question by Lucas Braesch, CCC, December 09, 2019
- ↑ Negative Plausibility Move Ordering by Alessandro Damiani, CCC, July 09, 2009