25,161
edits
Changes
Created page with "'''Home * Search * Move Ordering * History Heuristic''' border|right|thumb|[[Arts#Agache|Alfred Agache: La Fortuna, 188..."
'''[[Main Page|Home]] * [[Search]] * [[Move Ordering]] * History Heuristic'''
[[FILE:Agache - La Fortuna.jpg|border|right|thumb|[[Arts#Agache|Alfred Agache]]: La Fortuna, 1885 <ref>[[Arts#Agache|Alfred Agache]]: Alegoria da Fortuna, 1885, [https://en.wikipedia.org/wiki/Palais_des_Beaux-Arts_de_Lille Palais des Beaux-arts], [https://en.wikipedia.org/wiki/Lille Lille], [https://commons.wikimedia.org/wiki/Category:Alfred_Agache Category:Alfred Agache - Wikimedia Commons]</ref> ]]
'''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 <span style="background-color: #e0e0e0;">depth * depth</span> or <span style="background-color: #e0e0e0;">2 ^ 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>[http://members.home.nl/matador/chess840.htm#MOVE%20ORDERING Move Ordering in Rebel] by [[Ed Schroder|Ed Schröder]], also available as [http://members.home.nl/matador/Inside%20Rebel.pdf 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.
=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 [https://en.wikipedia.org/wiki/Pseudorandom_noise random noise] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=163477&t=18345 Re: LMR: history or not?] by [[Robert Hyatt]] from [[CCC]], December 13, 2007</ref> , whereas [[Ed Schroder|Ed Schröder]], advocated not taking into account the cutoffs from the last couple of plies.
=Update=
This is how the history [[Array|array]] may be updated, if a [[Beta-Cutoff|beta-cutoff]] occurs:
<pre>
if ( score >= beta ) { // cutoff
if ( isNonCapture (move) )
history[side2move][move.from][move.to] += depth*depth; // 1 << depth
...
return score;
}
</pre>
<span id="CMHist"></span>
=Counter Moves History=
A combination of the History Heuristic in conjunction with the [[Countermove Heuristic]], proposed by [[Bill Henry]] in March 2015 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55535 Improving History Tables] by [[Bill Henry]], [[CCC]], March 02, 2015</ref> , as already used by [[Álvaro Begué]] in his [[Checkers]] program 20 years before <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55535&start=2 Re: Improving History Tables] by [[Álvaro Begué]], [[CCC]], March 02, 2015</ref> , was implemented by [[Stockfish]] contributor [[Stefan Geschwenter]], further tuned and improved by the Stockfish community, and released in [[Stockfish|Stockfish 7]] in January 2016, dubbed '''Counter Moves History''' and mentioned to gain some Elo points <ref>[http://www.talkchess.com/forum/viewtopic.php?t=58935&start=2 Re: Stockfish 7 progress] by Lucas Braesch, [[CCC]], January 17, 2016</ref> . Stockfish's History and Countermove arrays are piece type and [[Target Square|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=
* [[Butterfly Boards]]
* [[Butterfly Heuristic]]
* [[Chessmaps Heuristic]]
* [[Countermove Heuristic]]
* [[History Leaf Pruning]]
* [[Killer Heuristic]]
* [[Late Move Reductions]]
: [[Late Move Reduction Test Results]]
* [[Neural MoveMap Heuristic]]
* [[Relative History Heuristic]]
* [[Vice#KillHist|Vice Video]]
=Selected Publications=
* [[Jonathan Schaeffer]] ('''1983'''). ''The History Heuristic''. [[ICGA Journal#6_3|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, pp. 1203–1212. ISSN 0162-8828, [http://ljk.imag.fr/membres//Jean-Guillaume.Dumas/Enseignements/Polys/Externes/schaeffer_history_heuristic.ps.gz zipped ps], [https://eprints.kfupm.edu.sa/70119/1/70119.pdf pdf]
* [[Jos Uiterwijk]] ('''1992'''). ''Memory Efficiency in some Heuristics''. [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]
=Forum Posts=
==1995 ...==
* [[@https://groups.google.com/forum/#!msg/rec.games.chess.computer/1uVIWZFB41k/qkPxZjtcFWwJ|(depth * depth) to replace (1 << depth)]] by [[Marcel van Kervinck]], [[Computer Chess Forums|rgcc]], January 29, 1996
* [https://www.stmintz.com/ccc/index.php?id=21072 Killer and history] by [[Jan Willem de Kort]], [[CCC]], June 22, 1998
* [https://www.stmintz.com/ccc/index.php?id=39692 History Heuristic on its own] by [[Chris Moreton]], [[CCC]], January 16, 1999
* [https://www.stmintz.com/ccc/index.php?id=68832 What is the History table?] by [[Leonid Liberman|Leonid]], [[CCC]], September 15, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=113078 What is the Success Rate of Killer/History Moves?] by [[Roberto Waldteufel]], [[CCC]], May 31, 2000
* [https://www.stmintz.com/ccc/index.php?id=127122 History Heuristic] by Larry Griffiths, [[CCC]], August 28, 2000
* [https://www.stmintz.com/ccc/index.php?id=143331 About history heuristics, killers and my futil. pruning code] by [[Severi Salminen]], [[CCC]], December 06, 2000 » [[Killer Heuristic]]
* [https://www.stmintz.com/ccc/index.php?id=278991 killers and history] by [[Nathan Thom]], [[CCC]], January 22, 2003 » [[Killer Heuristic]]
* [https://www.stmintz.com/ccc/index.php?id=280447 quiescent nodes, and history heuristic...] by [[Joel Veness]], [[CCC]], January 30, 2003
* [https://www.stmintz.com/ccc/index.php?id=354812 History Heuristic] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], March 16, 2004
* [https://www.stmintz.com/ccc/index.php?id=355221 About history and aging it] by [[Mikael Bäckman]], [[CCC]], March 17, 2004
* [https://www.stmintz.com/ccc/index.php?id=355347 History heuristic] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], March 18, 2004
* [https://www.stmintz.com/ccc/index.php?id=357112 Re: Artificial Intelligence in Computer Chess - *DETAILS* as promised] by [[Artem Petakov|Artem Pyatakov]], [[CCC]], March 28, 2004 » [[Artificial Intelligence]], [[Golch]]
==2005 ...==
* [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
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=37191 dynamically modified evaluation function] by [[Don Dailey]], [[CCC]], December 20, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=38406 Software Engineering] by [[Onno Garms]], [[CCC]], March 13, 2011 » [[Toga]]
* [http://www.talkchess.com/forum/viewtopic.php?t=40229 On history counters again] by [[Mincho Georgiev]], [[CCC]], August 31, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=46886 Killer and History: Increased Node Count] by [[Cheney Nattress]], [[CCC]], January 15, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48102 On history and piece square tables] by [[Evert Glebbeek]], [[CCC]], May 24, 2013 » [[Piece-Square Tables]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48160 Possible history table improvement] by [[László Gáspár|Laszlo Gaspar]], [[CCC]], May 30, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=50512 Improved history heuristic] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], December 16, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=51106 Recalculate history for remaining moves after each search] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], January 30, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=51992 Idea of different history] by [[Daniel José Queraltó]], [[CCC]], April 14, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55535 Improving History Tables] by [[Bill Henry]], [[CCC]], March 02, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=56332 History counters] by [[Robert Hyatt]], [[CCC]], May 12, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=56372 History heuristic and fixed depth search] by [[Peter Österlund]], [[CCC]], May 16, 2015 » [[Late Move Reduction Test Results]], [[Texel]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=2917 History Heuristic - a new idea on an old idea?] by thevinenator, [[Computer Chess Forums|OpenChess Forum]], Novembere 19, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=58935&start=2 Re: Stockfish 7 progress] by Lucas Braesch, [[CCC]], January 17, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=64619 History heuristic and quiet move generation] by [[Daniel José Queraltó]], [[CCC]], July 16, 2017 » [[Move Generation]]
=External Links=
* [http://members.home.nl/matador/hr.htm History Reductions] from [[Ed Schroder|Ed Schröder's]] [http://members.home.nl/matador/stuff.htm Programmer Corner]
* [https://en.wikipedia.org/wiki/Killer_heuristic Killer heuristic from Wikipedia]
=References=
<references />
'''[[Move Ordering|Up one Level]]'''
[[FILE:Agache - La Fortuna.jpg|border|right|thumb|[[Arts#Agache|Alfred Agache]]: La Fortuna, 1885 <ref>[[Arts#Agache|Alfred Agache]]: Alegoria da Fortuna, 1885, [https://en.wikipedia.org/wiki/Palais_des_Beaux-Arts_de_Lille Palais des Beaux-arts], [https://en.wikipedia.org/wiki/Lille Lille], [https://commons.wikimedia.org/wiki/Category:Alfred_Agache Category:Alfred Agache - Wikimedia Commons]</ref> ]]
'''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 <span style="background-color: #e0e0e0;">depth * depth</span> or <span style="background-color: #e0e0e0;">2 ^ 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>[http://members.home.nl/matador/chess840.htm#MOVE%20ORDERING Move Ordering in Rebel] by [[Ed Schroder|Ed Schröder]], also available as [http://members.home.nl/matador/Inside%20Rebel.pdf 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.
=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 [https://en.wikipedia.org/wiki/Pseudorandom_noise random noise] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=163477&t=18345 Re: LMR: history or not?] by [[Robert Hyatt]] from [[CCC]], December 13, 2007</ref> , whereas [[Ed Schroder|Ed Schröder]], advocated not taking into account the cutoffs from the last couple of plies.
=Update=
This is how the history [[Array|array]] may be updated, if a [[Beta-Cutoff|beta-cutoff]] occurs:
<pre>
if ( score >= beta ) { // cutoff
if ( isNonCapture (move) )
history[side2move][move.from][move.to] += depth*depth; // 1 << depth
...
return score;
}
</pre>
<span id="CMHist"></span>
=Counter Moves History=
A combination of the History Heuristic in conjunction with the [[Countermove Heuristic]], proposed by [[Bill Henry]] in March 2015 <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55535 Improving History Tables] by [[Bill Henry]], [[CCC]], March 02, 2015</ref> , as already used by [[Álvaro Begué]] in his [[Checkers]] program 20 years before <ref>[http://www.talkchess.com/forum/viewtopic.php?t=55535&start=2 Re: Improving History Tables] by [[Álvaro Begué]], [[CCC]], March 02, 2015</ref> , was implemented by [[Stockfish]] contributor [[Stefan Geschwenter]], further tuned and improved by the Stockfish community, and released in [[Stockfish|Stockfish 7]] in January 2016, dubbed '''Counter Moves History''' and mentioned to gain some Elo points <ref>[http://www.talkchess.com/forum/viewtopic.php?t=58935&start=2 Re: Stockfish 7 progress] by Lucas Braesch, [[CCC]], January 17, 2016</ref> . Stockfish's History and Countermove arrays are piece type and [[Target Square|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=
* [[Butterfly Boards]]
* [[Butterfly Heuristic]]
* [[Chessmaps Heuristic]]
* [[Countermove Heuristic]]
* [[History Leaf Pruning]]
* [[Killer Heuristic]]
* [[Late Move Reductions]]
: [[Late Move Reduction Test Results]]
* [[Neural MoveMap Heuristic]]
* [[Relative History Heuristic]]
* [[Vice#KillHist|Vice Video]]
=Selected Publications=
* [[Jonathan Schaeffer]] ('''1983'''). ''The History Heuristic''. [[ICGA Journal#6_3|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, pp. 1203–1212. ISSN 0162-8828, [http://ljk.imag.fr/membres//Jean-Guillaume.Dumas/Enseignements/Polys/Externes/schaeffer_history_heuristic.ps.gz zipped ps], [https://eprints.kfupm.edu.sa/70119/1/70119.pdf pdf]
* [[Jos Uiterwijk]] ('''1992'''). ''Memory Efficiency in some Heuristics''. [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]
=Forum Posts=
==1995 ...==
* [[@https://groups.google.com/forum/#!msg/rec.games.chess.computer/1uVIWZFB41k/qkPxZjtcFWwJ|(depth * depth) to replace (1 << depth)]] by [[Marcel van Kervinck]], [[Computer Chess Forums|rgcc]], January 29, 1996
* [https://www.stmintz.com/ccc/index.php?id=21072 Killer and history] by [[Jan Willem de Kort]], [[CCC]], June 22, 1998
* [https://www.stmintz.com/ccc/index.php?id=39692 History Heuristic on its own] by [[Chris Moreton]], [[CCC]], January 16, 1999
* [https://www.stmintz.com/ccc/index.php?id=68832 What is the History table?] by [[Leonid Liberman|Leonid]], [[CCC]], September 15, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=113078 What is the Success Rate of Killer/History Moves?] by [[Roberto Waldteufel]], [[CCC]], May 31, 2000
* [https://www.stmintz.com/ccc/index.php?id=127122 History Heuristic] by Larry Griffiths, [[CCC]], August 28, 2000
* [https://www.stmintz.com/ccc/index.php?id=143331 About history heuristics, killers and my futil. pruning code] by [[Severi Salminen]], [[CCC]], December 06, 2000 » [[Killer Heuristic]]
* [https://www.stmintz.com/ccc/index.php?id=278991 killers and history] by [[Nathan Thom]], [[CCC]], January 22, 2003 » [[Killer Heuristic]]
* [https://www.stmintz.com/ccc/index.php?id=280447 quiescent nodes, and history heuristic...] by [[Joel Veness]], [[CCC]], January 30, 2003
* [https://www.stmintz.com/ccc/index.php?id=354812 History Heuristic] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], March 16, 2004
* [https://www.stmintz.com/ccc/index.php?id=355221 About history and aging it] by [[Mikael Bäckman]], [[CCC]], March 17, 2004
* [https://www.stmintz.com/ccc/index.php?id=355347 History heuristic] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], March 18, 2004
* [https://www.stmintz.com/ccc/index.php?id=357112 Re: Artificial Intelligence in Computer Chess - *DETAILS* as promised] by [[Artem Petakov|Artem Pyatakov]], [[CCC]], March 28, 2004 » [[Artificial Intelligence]], [[Golch]]
==2005 ...==
* [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
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=37191 dynamically modified evaluation function] by [[Don Dailey]], [[CCC]], December 20, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=38406 Software Engineering] by [[Onno Garms]], [[CCC]], March 13, 2011 » [[Toga]]
* [http://www.talkchess.com/forum/viewtopic.php?t=40229 On history counters again] by [[Mincho Georgiev]], [[CCC]], August 31, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=46886 Killer and History: Increased Node Count] by [[Cheney Nattress]], [[CCC]], January 15, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=48102 On history and piece square tables] by [[Evert Glebbeek]], [[CCC]], May 24, 2013 » [[Piece-Square Tables]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48160 Possible history table improvement] by [[László Gáspár|Laszlo Gaspar]], [[CCC]], May 30, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=50512 Improved history heuristic] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], December 16, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=51106 Recalculate history for remaining moves after each search] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], January 30, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=51992 Idea of different history] by [[Daniel José Queraltó]], [[CCC]], April 14, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55535 Improving History Tables] by [[Bill Henry]], [[CCC]], March 02, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=56332 History counters] by [[Robert Hyatt]], [[CCC]], May 12, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=56372 History heuristic and fixed depth search] by [[Peter Österlund]], [[CCC]], May 16, 2015 » [[Late Move Reduction Test Results]], [[Texel]]
* [http://www.open-chess.org/viewtopic.php?f=5&t=2917 History Heuristic - a new idea on an old idea?] by thevinenator, [[Computer Chess Forums|OpenChess Forum]], Novembere 19, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=58935&start=2 Re: Stockfish 7 progress] by Lucas Braesch, [[CCC]], January 17, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=64619 History heuristic and quiet move generation] by [[Daniel José Queraltó]], [[CCC]], July 16, 2017 » [[Move Generation]]
=External Links=
* [http://members.home.nl/matador/hr.htm History Reductions] from [[Ed Schroder|Ed Schröder's]] [http://members.home.nl/matador/stuff.htm Programmer Corner]
* [https://en.wikipedia.org/wiki/Killer_heuristic Killer heuristic from Wikipedia]
=References=
<references />
'''[[Move Ordering|Up one Level]]'''
