History Heuristic

From Chessprogramming wiki

Home *Search *Move Ordering * History Heuristic

Alfred Agache - La Fortuna, 1885^[1]

History Heuristic,
a dynamic move ordering method based on the number of cutoffs caused by a given move irrespectively from the position in which the move has been made. The Heuristic was invented byJonathan Schaeffer in 1983^[2] and works as follows: on acutoff we increment a counter in a special table, addressed either by[from][to] (theButterfly Boards) or by[piece][to]^[3] . The added value is typically a multiple ofdepth ordepth * depth, based on the assumption that otherwise moves from the plies near the leaves would have to much impact on the result. Values retrieved from that table are used to order non-capturing moves. This simple heuristics performs usually better than domain-dependent heuristics, though it may be combined with them. For example, inStockfish all quiet moves that are not hash moves are ordered by history, while inRebel only a few non-captures are ordered by history heuristics, then a piece-square approach is used^[4] . In the literature, history heuristic is often presented as depth-independent generalization of thekiller moves. It is also said to reflect long-term plans in a position.

Update

History Bonuses

This is how the historyarray may be updated, if abeta-cutoff occurs:

if ( score >= beta ) { // cutoff   if ( isNonCapture (move) )      history[sideToMove][move.from][move.to] += depth*depth;   ...   return score;}

Modern programs use a more sophisticated formula for history updates, namely thehistory gravity formula:

void update(Color sideToMove, Square from, Square to, int bonus){    int clampedBonus = clamp(bonus, -MAX_HISTORY, MAX_HISTORY);    history[sideToMove][from][to]        += clampedBonus - history[sideToMove][from][to] * abs(clampedBonus) / MAX_HISTORY;}

This scales up history updates when a beta cutoff is unexpected, and scales down history updates when a beta cutoff is expected. A beneficial side effect is that this formula also clamps history values from -MAX_HISTORY to MAX_HISTORY, which prevents oversaturated values.

History Maluses

When a quiet move fails high, it is also common to apply a penalty to all quiet moves that were previously searched. This not only prevents saturated history values, but also gives unpromising moves negative history. In programs with history gravity formula, this is done by applying negative bonus to the history array.

const int bonus = 300 * depth - 250;history.update(bestMove, bonus);for (Move move : quietsSearched){    history.update(move, -bonus); // Stronger programs have a separate formula for maluses}

Counter Moves History

A combination of the History Heuristic in conjunction with theCountermove Heuristic, proposed byBill Henry in March 2015^[5] , as already used byÁlvaro Begué in hisCheckers program 20 years before^[6] , was implemented byStockfish contributorStefan Geschwentner^[7], further tuned and improved by the Stockfish community, and released inStockfish 7 in January 2016, dubbedCounter Moves History and mentioned to gain some Elo points^[8]. Stockfish's History and Countermove arrays are piece type andto-square based, not butterfly based. Each entry indexed by a previous move, is a complete history table with counters indexed by the move refuting that previous move. Pushing the idea further, Stockfish appliesFollow Up History (FUH) tables, indexed by two consecutive moves of the same side^[9].

Continuation History

Continuation History is a generalization ofCounter Moves History and Follow Up History. Ann-ply Continuation History is the history score indexed by the move played n-ply ago and the current move. 1-ply and 2-ply continuation histories are most popular and correspond to Counter Moves History and Follow Up History respectively. Many programs, notablyStockfish, also makes use of 3, 4, 5, and 6-ply continuation histories.

Capture History

Capture History, introduced byStefan Geschwentner in 2016, is a variation on history heuristic applied on capture moves. It is a history table indexed by moved piece, target square, and captured piece type. The history table receives a bonus for captures that failed high, and maluses for all capture moves that did not fail high. The history values is used as a replacement for LVA inMVV-LVA.