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.

Most Popular

Video Clips
3500 Top Songs. More…

Pro Deo
version 1.2 More…

Chess Programming
Inside REBEL. More…

Pondering about Faith
A first try. More…

TOP-5000
My Music Project More…

Computer Chess Links

  • Computer Chess Historic Pictures.
  • CCC The Number One Forum.
  • ChessUSA Reliable company to buy to your chess software.
  • ChessBase The Home of the famous Fritz.
  • ChessPartner The Home of Chess Tiger, Gandalf and others.
  • Kasparov-DeepBlue The Immortal Match of 1997.
  • Wikipedia 1992, first time a microcomputer, the Chessmachine Gideon 3.1 by Ed Schroeder, wins the 7th World Computer Chess Championship in front of mainframes, supercomputers and special hardware.
Copyright © 1984 - Ed Schröder
Mail Me