Relative History Heuristic

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.

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.