History Reductions

On this page I will try to describe how the History Reductions (HR) technique is implemented in Pro Deo 1.1 which was good for a 20-30 elo improvement. It's rather different then what I have understood from fellow chess programmers.

Preface: the idea of HR is to reduce the search with 1 ply when a move in the tree repeatedly fails low (score < ALPHA).

Data structure: static int HR [pt][sq);      // piece_type & square

Initialization: pre-filled with 100 everytime the search starts. The value of 100 is parameter driven, see below overview.

Update HR table: when the value of a node is known in the tree the HR table is updated with +5 when the score is above ALPHA and with -1 when the score is below or equal ALPHA. Both values are parameter driven, see below overview.

Reduction: when entering a new node in the tree the value of that move is checked and when the value is below 50 the search is reduced with 1 ply. The value of 50 is parameter driven, see below overview.

This basically is it, however we are not there yet, a few exceptions must be made else HR won't work. But let's first examine what actually happens before going further. Because of the fact the HR table is updated with +5 or -1 (depending if a move fails high or fails low) actually means a reduction can only happen when 80% of that move has failed low and secondly that first a (small) safety buffer has be to crossed (from 100 to 50) before a reduction can happen anyway. Since all the values are parameter driven it's easy to increase or decrease the percentage or change the size of the safety buffer.

As already said we are not there yet, we need to add a few exceptions, we don't reduce the search in the following cases:
  • when move is best move from hash table.
  • when own king is in check.
  • when a move checks the opponent king.
  • when a move is a capture.
  • when the static score is greater then ALPHA.
The latter is very important else too many good nodes will be reduced. I realize that most chess programs don't have the static score at hand but a good alternative is to use the incremental score + margin instead. I refer to the LAZY EVAL page.

Last: and now things become complicated after all. After a reduction the HR table is edited, a value of 50 is stored. Why? Because it works best. HR is a strange and dangerous algorithm and its behaviour is hard to grasp. Storing 50 means the move won't be reduced so easily again, it's a kind of saftey measure. The value of 50 is parameter driven, see below overview.

Parameters
static int HR_INIT = 100;      // Initialization value HR table
static int HR_INC = 5;         // Update value HR table when score > ALPHA
static int HR_DEC = -1;        // Update value HR table when score <= ALPHA
static int HR_THRESHOLD = 50;  // Threshold value for reduction
static int HR_REPLACE = 50;    // Replace value after reduction
static int HR_MARGIN = 0;      // Margin for reduction (see below pseudo code)

Pseudo Code
if (best_move_from_hash_table)         -> no reduction, too dangerous.
if (own_king_is_in_check)              -> no reduction, too dangerous.
if (move_does_check_the_opponent_king) -> no reduction, too dangerous.
if (move_is_capture)                   -> no reduction, too dangerous.
if (static_score > ALPHA + HR_MARGIN)  -> no reduction, too dangerous.
if (HR[pt][sq] > HR_THRESHOLD)         -> no reduction, threshold not reached.
reduce_move();                         -> reduce search with 1 ply.
HR[pt][sq] = HR_REPLACE;               -> re-initialize safety buffer.

pt : piece_type
sq : square

HR_MARGIN is currently set to zero in Pro Deo 1.1, my last testing showed that 
using a value of 0.25 gave an even better result due to a much faster search.
It's understandable, many rubbish moves are then simply reduced.



Some final remarks.

  • From the beginning I used the [pt][sq] technique rather then the [sq][sq] approach because 1) to save data cache and 2) the ease of needing one table only. So I haven't tried [colour][sq][sq], it could be even better.
  • If you think your approach is better send me an email

  • I will be happy to explain when things are not clear or discuss alternative techniques preferable in the CCC forum.
Copyright © 1984 - Ed Schröder
Mail Me