Difference between revisions of "Relative History Heuristic"

From Chessprogramming wiki
Jump to: navigation, search
m
Line 61: Line 61:
 
=Publications=
 
=Publications=
 
* [[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]
 
* [[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]] ('''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>
  
 
=External Links=
 
=External Links=
Line 70: Line 71:
  
 
'''[[Move Ordering|Up one Level]]'''
 
'''[[Move Ordering|Up one Level]]'''
 +
[[Category|Music]]

Revision as of 16:48, 19 December 2018

Home * Search * Move Ordering * Relative History Heuristic

The Relative History Heuristic was proposed by Mark Winands et al. [1] at the Computers and Games Conference 2004 in Ramat Gan as improvement of the History Heuristic.

History Heuristic

The disadvantage of the history heuristic is that it is biased towards moves that occur more often in a game than others. However, the history heuristic has as implicit assumption that all the legal moves occur roughly with the same frequency in the game (tree). For instance, assume we have a move which is quite successful when applicable (e.g., it then causes a cut-off) but it does not occur so often as a legal move in the game tree. This move will not obtain a high history score and is therefore ranked quite low in the move ordering. 

The Idea

The idea is to make the history scores (hhScore) relative to the scores of the butterfly heuristic (bfScore).

We believe that we can considerably improve the performance of the history heuristic in some games by making it relative instead of absolute: The score used to order the moves (movescore) is given by the following formula: 
moveScore = hhScore / bfScore;

or dependent on the increments:

moveScore = (Scale * hhScore) / bfScore;

Winands experienced with several increments for hhScore and bfScore, namely {1, depth, depth^2 and 2^depth}. The depth independent increment of 1 seemed to give best results in the game of Lines of Action. This is how the history array and butterfly boards may be updated, if a beta-cutoff occurs or not (ignoring PV-Nodes):

   if ( score >= beta ) { // cutoff
      if ( isNonCapture (move) )
         hhScore[move.from][move.to] += hhIncrement; 
      ...
      return score; 
   } else { // no cutoff
      if ( isNonCapture (move) )
         bfScore[move.from][move.to] += bfIncrement;
   }

Alternatives

Other approaches of relative history heuristic - proposed by Robert Hyatt, as tried in Crafty while playing with Late Move Reductions [2], and applied by Tord Romstad in Glaurung as mentioned by Marco Costalba, the developer of Stockfish [3] - rely on considering confirmed Cut-Nodes for updating the counters only. If a Fail-High occurs, hhScore is incremented as usual. Additionally, if the move which caused the Cut-Off was not the first one, one has to loop over all previously tried quite moves (still in the move-list), to increment their butterfly penalty scores. A similar idea was proposed by Jeff Rollason, Negative Plausibility [4] as implemented inside his Shogi program Shotest.

   if ( score >= beta ) { // cutoff
      if ( isNonCapture (move) ) 
         hhScore[move.from][move.to] += hhIncrement; 
      for ( all previous moves m) {
         if ( isNonCapture (m) )
            bfScore[m.from][m.to] += bfIncrement;
      }
      ...
      return score; 
   }

Peak History Reduction

A common idea was mentioned by Daniel Mehrmann in the same LMR-thread [5], what he called Peak History Reduction or PHR. He keeps track of the greatest hhScore, to consider all other history scores relative to this peak. But that doesn't address the cases, where moves occurred rarely were relative successful.

See also

Publications

External Links

References

Up one Level Music