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.