Difference between revisions of "History Heuristic"

From Chessprogramming wiki
Jump to: navigation, search
 
(8 intermediate revisions by the same 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 <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.  
+
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>[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.  
  
 
=Random Noise?=  
 
=Random Noise?=  
Line 21: Line 21:
 
<span id="CMHist"></span>
 
<span id="CMHist"></span>
 
=Counter Moves History=  
 
=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.  
+
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 Geschwentner]] <ref>[https://groups.google.com/d/msg/fishcooking/d8IhZZJSBGc/PrN-8dP26dIJ Followup moves] by [[Stefan Geschwentner]], [[Computer Chess Forums|FishCooking]], January 12, 2014 » [[History Heuristic#CMHist|Counter Moves History]]</ref>, 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.  
 
Pushing the idea further, Stockfish applies '''Follow Up History''' (FUH) tables, indexed by two consecutive moves of the same side <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=7&t=72531&start=1 Re: CMH question] by Lucas Braesch, [[CCC]], December 09, 2019</ref>.
 
Pushing the idea further, Stockfish applies '''Follow Up History''' (FUH) tables, indexed by two consecutive moves of the same side <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=7&t=72531&start=1 Re: CMH question] by Lucas Braesch, [[CCC]], December 09, 2019</ref>.
  
Line 38: Line 38:
  
 
=Selected Publications=  
 
=Selected Publications=  
 +
==1980 ...==
 
* [[Jonathan Schaeffer]] ('''1983'''). ''The History Heuristic''. [[ICGA Journal#6_3|ICCA Journal, Vol. 6, No. 3]]
 
* [[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]
+
* [[Jonathan Schaeffer]] ('''1989'''). ''[https://ieeexplore.ieee.org/document/42858 The History Heuristic and Alpha-Beta Search Enhancements in Practice]''. [[IEEE#TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 11, No. 11
 
* [[Jos Uiterwijk]] ('''1992'''). ''Memory Efficiency in some Heuristics''. [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]
 
* [[Jos Uiterwijk]] ('''1992'''). ''Memory Efficiency in some Heuristics''. [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]
 +
* [[Eric Thé]] ('''1992'''). ''[http://digitool.library.mcgill.ca/R/?func=dbin-jump-full&object_id=56753&local_base=GEN01-MCG02 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'''). ''[http://link.springer.com/chapter/10.1007/11674399_18 The Relative History Heuristic]''. [[CG 2004]],  [http://erikvanderwerf.tengen.nl/pubdown/relhis.pdf pdf]
 +
* [[Jeff Rollason]] ('''2006'''). ''[http://www.aifactory.co.uk/newsletter/2005_04_plausibility_analysis.htm Driving search with Plausibility analysis: Looking at the right moves]''. [[AI Factory]], Winter 2006
 +
* [[Jeff Rollason]] ('''2007'''). ''[http://www.aifactory.co.uk/newsletter/2007_01_neg_plausibility.htm Negative Plausibility]''. [[AI Factory]], Spring 2007 <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=7&t=28873 Negative Plausibility Move Ordering] by [[Alessandro Damiani]], [[CCC]], July 09, 2009</ref>
  
 
=Forum Posts=  
 
=Forum Posts=  
Line 59: Line 65:
 
* [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]]
 
* [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 ...==  
 
==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/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
Line 69: Line 76:
 
* [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=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=50512 Improved history heuristic] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], December 16, 2013
 +
* [https://groups.google.com/d/msg/fishcooking/d8IhZZJSBGc/PrN-8dP26dIJ Followup moves] by [[Stefan Geschwentner]], [[Computer Chess Forums|FishCooking]], January 12, 2014 » [[History Heuristic#CMHist|Counter Moves History]]
 
* [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=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
 
* [http://www.talkchess.com/forum/viewtopic.php?t=51992 Idea of different history] by [[Daniel José Queraltó]], [[CCC]], April 14, 2014
Line 79: Line 87:
 
* [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]]
 
* [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]]
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=72531 CMH question] by [[Vivien Clauzon]], [[CCC]], December 08, 2019 » [[#CMHist|Counter Moves History]]
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=72531 CMH question] by [[Vivien Clauzon]], [[CCC]], December 08, 2019 » [[#CMHist|Counter Moves History]]
 +
==2020 ...==
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73880 Quick history move] by [[Harm Geert Muller]], [[CCC]], May 09, 2020
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76540 History bonus] by [[Michael Hoffmann]], [[CCC]], February 09, 2021
  
 
=External Links=  
 
=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://web.archive.org/web/20180713063523/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/Wayback_Machine Wayback Machine], July 30, 2007)
 
* [https://en.wikipedia.org/wiki/Killer_heuristic Killer heuristic from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Killer_heuristic Killer heuristic from Wikipedia]
  
 
=References=  
 
=References=  
 
<references />
 
<references />
 
 
'''[[Move Ordering|Up one Level]]'''
 
'''[[Move Ordering|Up one Level]]'''
 
[[Category:Alfred Agache]]
 
[[Category:Alfred Agache]]

Latest revision as of 20:40, 11 February 2021

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.

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:

   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].

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