如何在 alpha-beta 最小最大值中使用“历史启发式”？

Question

我在为象棋游戏制作一个人工智能。

到目前为止，我已经成功实现了Alpha-Beta剪枝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 β

由于这花费了太多的时间复杂性(逐一遍历所有的树)，我遇到了一种叫做“历史启发式”的东西。

原始论文中的算法：

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

所以基本上，这个想法是跟踪一个散列表或者一个字典来记录以前的“移动”。

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

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

> < li>

个人移动，如(女王到位置(0，1))或(骑士到位置(5，5))？

还是棋盘在个人移动后的整体状态？

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

Answer 1

从我的经验来看，与其他技术相比，历史启发式产生的好处可以忽略不计，对于一个基本的搜索程序来说是不值得的。这与使用转置表不是一回事。如果你想实现后者，我仍然建议不要这样做。有许多其他的技术可以用少得多的努力产生好的结果。事实上，高效正确的转置表是象棋引擎中最难编码的部分之一。

首先尝试修剪和移动排序启发式方法，其中大部分是一到几行代码。我在这篇文章中详细介绍了这些技术，它还给出了您可以期望的性能提升的估计值。

Answer 2

您可以使用换位表，这样可以避免多次评估同一块电路板。换位意味着您可以通过以不同的顺序移动来达到相同的棋盘状态。天真的例子:

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

这些戏剧的结果是相同的位置，但到达的位置不同。

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

一种常见的方法称为Zobrist散列来散列国际象棋位置：

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

Answer 3

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

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