How exactly to use "History Heuristic" in alpha-beta minimax?

Question

I'm making an AI for a chess game.

So far, I've successfully implemented the Alpha-Beta Pruning Minimax algorithm, which looks like this (from Wikipedia):

(* Initial call *)
alphabeta(origin, depth, -∞, +∞, TRUE)

function alphabeta(node, depth, α, β, maximizingPlayer)
    if depth = 0 or node is a terminal node
        return the heuristic value of node
    if maximizingPlayer
        for each child of node
            α := max(α, alphabeta(child, depth - 1, α, β, FALSE))
            if β ≤ α
                break (* β cut-off *)
        return α
    else
        for each child of node
            β := min(β, alphabeta(child, depth - 1, α, β, TRUE))
            if β ≤ α
                break (* α cut-off *)
        return β

Since this costs too much time complexity (going through all the trees one by one), I came across something called "History Heuristic".

The Algorithm from the original paper:

int AlphaBeta(pos, d, alpha, beta) 
{ 
    if (d=0 || game is over) 
        return Eval (pos);  // evaluate leaf position from current player’s standpoint 

    score = - INFINITY;     // preset return value 
    moves = Generate(pos);  // generate successor moves 

    for i=1 to sizeof(moves) do                // rating all moves 
        rating[i] = HistoryTable[ moves[i] ]; 
    Sort( moves, rating );                     // sorting moves according to their history scores 

    for i =1 to sizeof(moves) do { // look over all moves 
        Make(moves[i]); // execute current move 
        cur = - AlphaBeta(pos, d-1, -beta, -alpha); //call other player

        if (cur > score) {
            score = cur; 
            bestMove = moves[i];      // update best move if necessary 
        } 

        if (score > alpha) alpha = score;    //adjust the search window 
            Undo(moves[i]);                  // retract current move 

        if (alpha >= beta) goto done;        // cut off 
     } 

     done: 
     // update history score 
     HistoryTable[bestMove] = HistoryTable[bestMove] + Weight(d); 

     return score; 
} 

So basically, the idea is to keep track of a Hashtable or a Dictionary for previous "moves".

Now I'm confused what this "move" means here. I'm not sure if it literally refers to a single move or a overall state after each move.

In chess, for example, what should be the "key" for this hashtable be?

1. Individual moves like (Queen to position (0,1)) or (Knight to position (5,5))?

2. Or the overall state of the chessboard after individual moves?

If 1 is the case, I guess the positions of other pieces are not taken into account when recording the "move" into my History table?

Answer 1

I think the original paper (The History Heuristic and Alpha-Beta Search Enhancements in Practice, Jonathan Schaeffer) available on-line answers the question clearly. In the paper, the author defined move as the 2 indices (from square and to) on the chess board, using a 64x64 table (in effect, I think he used bit shifting and a single index array) to contain the move history.

The author compared all the available means of move ordering and determined that hh was the best. If current best practice has established an improved form of move ordering (beyond hh + transposition table), I would also like to know what it is.

Answer 2

You can use a transposition table so you avoid evaluating the same board multiple times. Transposition meaning you can reach the same board state by performing moves in different orders. Naive example:

1. e4 e5 2. Nf3 Nc6
1. e4 Nc6 2. Nf3 e5

These plays result in the same position but were reached differently.

http://en.wikipedia.org/wiki/Transposition_table

A common method is called Zobrist hashing to hash a chess position:

http://en.wikipedia.org/wiki/Zobrist_hashing

Answer 3

From my experience the history heuristic produces negligible benefits compared to other techniques, and is not worthwhile for a basic search routine. It is not the same thing as using transposition table. If the latter is what you want to implement, I'd still advise against it. There are many other techniques that will produce good results for far less effort. In fact, an efficient and correct transposition table is one of the most difficult parts to code in a chess engine.

First try pruning and move ordering heuristics, most of which are one to a few lines of code. I've detailed such techniques in this post, which also gives estimates of the performance gains you can expect.

Answer 4

In chess, for example, what should be the "key" for this hashtable be?

• Individual moves like (Queen to position (0,1)) or (Knight to position (5,5))?
• Or the overall state of the chessboard after individual moves?

The key is an individual move and the positions of other pieces aren't taken into account when recording the "move" into the history table.

The traditional form of the history table (also called butterfly board) is something like:

score history_table[side_to_move][from_square][to_square];

For instance, if the move e2-e4 produces a cutoff, the element:

history_table[white][e2][e4]

is (somehow) incremented (irrespectively from the position in which the move has been made).

As in the example code, history heuristics uses those counters for move ordering. Other heuristics can take advantage of history tables (e.g. late move reductions).

Consider that:

• usually history heuristics isn't applied to plain Alpha-Beta with no knowledge of move ordering (in chess only "quiet" moves are ordered via history heuristic);
• there are alternative forms for the history table (often used is history_table[piece][to_square]).