algorithm - 如何在 alpha-beta minimax 中使用 "History Heuristic"？

Question

我正在为国际象棋游戏制作 AI。

到目前为止，我已经成功实现了 Alpha-Beta Pruning Minimax 算法，它看起来像这样(来自维基百科):

(* 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 β

因为这花费了太多的时间复杂度(一棵一棵地遍历所有树)，我遇到了一个叫做 "History Heuristic" 的东西。 .

原始论文中的算法:

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; 
} 

所以基本上，这个想法是为之前的“移动”跟踪哈希表或字典。

现在我对这里的“移动”意味着什么感到困惑。我不确定它是字面上指的是单个 Action 还是每次 Action 后的整体状态。

例如，在国际象棋中，这个哈希表的“键”应该是什么？

1. 个人移动，例如(皇后到位置 (0,1))或(马到位置 (5,5))？

2. 还是棋盘走单后的整体状态？

如果 1 是这种情况，我猜在将“移动”记录到我的历史表中时没有考虑其他棋子的位置？

Answer 1

我认为在线提供的原始论文(The History Heuristic and Alpha-Beta Search Enhancements in Practice，Jonathan Schaeffer)清楚地回答了这个问题。在论文中，作者将移动定义为棋盘上的 2 个索引(从正方形和到)，使用 64x64 表(实际上，我认为他使用位移和单个索引数组)来包含移动历史。

作者比较了所有可用的移动排序方式，并确定 hh 是最好的。如果当前的最佳实践已经建立了移动排序的改进形式(超越 hh + 换位表)，我也想知道它是什么。