我正在为古老的北欧棋类游戏tafl家族编写人工智能（项目在这里，相关源文件在这里）。这些游戏在总体上与国际象棋足够相似，因此国际象棋AI的知识在这里也适用。（所讨论的变体是在一个7×7的棋盘上进行的，起始位置呈径向对称，白棋从中间开始，黑棋从边缘开始。）我在实现alpha-beta搜索时遇到了一个奇怪的问题：在固定深度的搜索中，除了alpha-beta剪枝之外没有启用任何优化，搜索结果会根据节点探索的顺序而变化。

在相关文件中，重要的方法包括’explore’、’exploreChildren’、’handleEvaluationResults’和’generateSuccessorMoves’。’explore’方法会检查是否有转置表命中（在本次测试中已在其他地方禁用），如果是胜利状态或叶节点，则评估状态，否则调用exploreChildren。exploreChildren方法对子节点进行递归搜索。generateSuccessorMoves方法生成（并可选地排序）从当前状态出发的移动。handleEvaluationResults方法确定子节点评估是否引起了截断。

因此，我编写了一个最小的测试用例：generateSuccessorMoves首先不进行任何排序，然后只是随机打乱移动列表而不是排序。搜索结果在结果上、考虑对称性的结果上以及价值上都不相同：

MAIN SEARCH# cutoffs/avg. to 1st a/b a/bDepth 0: 0/0 0/0Depth 1: 0/22 0/1Depth 2: 42/0 3/0Finding best state...Best move: d3-g3 with path...    d3-g3    e1-f1    e4-e1xf1End of best path scored -477Observed/effective branching factor: 23.00/9.63Thought for: 72msec. Tree sizes: main search 893 nodes, continuation search: 0 nodes, horizon search: 0 nodesOverall speed: 12402.77777777778 nodes/secTransposition table stats: Table hits/queries: 0/0 Table inserts/attempts: 0/01. move: d3-g3 value: -477Using 5000msec, desired 9223372036854775807Depth 3 explored 1093 states in 0.037 sec at 29540.54/secMAIN SEARCH# cutoffs/avg. to 1st a/b a/bDepth 0: 0/0 0/0Depth 1: 0/21 0/2Depth 2: 104/0 2/0Finding best state...Best move: d3-f3 with path...    d3-f3    d2-c2    d5-f5xf4End of best path scored -521Observed/effective branching factor: 23.00/10.30Thought for: 37msec. Tree sizes: main search 1093 nodes, continuation search: 0 nodes, horizon search: 0 nodesOverall speed: 29540.540540540544 nodes/secTransposition table stats: Table hits/queries: 0/0 Table inserts/attempts: 0/07. move: d3-f3 value: -521

这显然是一个极端情况，但据我所知，在这种情况下（即除了’alpha-beta剪枝’之外没有任何功能），alpha-beta应该稳定，无论搜索的顺序如何——至少，它应该返回相同值的节点。我错了么？我做错了什么吗？

第一次编辑：虽然从问题的描述中似乎显而易见，但结果证明我的alpha-beta实现中存在一些未知的错误。进一步的测试显示，它与纯极小极大搜索的结果不一致。

第二次编辑：这是上面链接文件中实现的alpha-beta搜索的伪代码版本。

explore(depth, maxDepth, alpha, beta)    // 一些tafl变体具有规则，其中一个玩家在一回合中移动超过一次    // 每个游戏树节点都知道它是最大化还是最小化    var isMaximizing = this.isMaximizing()    var value = NO_VALUE    if(isTerminal(depth, maxDepth))        value = eval()    else        for(move in successorMoves)            if(cutoff) break            nodeValue = nextNode(move).explore(depth + 1, maxDepth, alpha, beta)            if(value == NO_VALUE) value = nodeValue            if(isMaximizing)                value = max(value, nodeValue)                alpha = max(alpha, value)                if(beta <= alpha) break            else                value = min(value, nodeValue)                beta = min(beta, value)                if(beta <= alpha) breakrootNode.explore(0, 5, -infinity, infinity)

回答：

结果证明这是我的错。我有一段代码，它递归地重新评估某个节点上方的节点，用于扩展搜索，而我是在错误的地方调用了它（在探索任何节点的所有子节点之后）。这种过早的回溯传播导致了错误的alpha和beta值，从而导致了过早的截断。