Relative History Heuristic

Home * Search * Move Ordering * Relative History Heuristic

The Relative History Heuristic was proposed by Mark Winands et al. 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 , and applied by Tord Romstad in Glaurung as mentioned by Marco Costalba, the developer of Stockfish - 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 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 , 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

• Bobby's Strategic Quiescence Search
• History Heuristic
• Butterfly Heuristic
• Butterfly Boards
• Killer Heuristic
• Countermove Heuristic
• Late Move Reductions
• History Leaf Pruning

Publications

• Mark Winands, Erik van der Werf, Jaap van den Herik, Jos Uiterwijk (2004). The Relative History Heuristic. CG 2004, pdf
• Jeff Rollason (2007). Negative Plausibility. AI Factory, Spring 2007

External Links

• Dolby - SAX-MAFIA live at Smolensk Chamber Theatre, 2007, YouTube Video

References

Up one Level