alpha-beta 搜索中意外的路径依赖？

Question

我正在为古老的 Norse tafl 棋盘游戏系列 (project here, source file at issue here) 编写人工智能。他们已经足够接近国际象棋了，国际象棋 AI 的知识可以在这里应用。（有问题的变体在 7x7 棋盘上播放，起始位置呈径向对称，白色从中间开始，黑色从边缘开始。）我运行对我如何实现 alpha 感到好奇-beta 搜索：搜索到固定深度的结果，除了 alpha-beta 修剪之外没有启用优化，根据探索节点的顺序而变化。

在问题文件中，重要的方法是'explore'、'exploreChildren'、'handleEvaluationResults'和'generateSuccessorMoves'。 'explore' 检查是否有换位 table 命中（此测试在其他地方禁用），评估状态是胜利还是叶节点，或者调用 exploreChildren。 exploreChildren 对子节点进行递归搜索。 generateSuccessorMoves 生成（并可选地排序）退出当前状态的移动。 handleEvaluationResults 确定子评估是否导致中断。

所以，我写了一个最小的测试用例：generateSuccessorMoves 首先不进行任何排序，然后只是打乱移动列表而不是对其进行排序。搜索的结果在结果上不等价，考虑对称性的结果也不等价，在值上也不等价：

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

显然，这是一个极端的情况，但我的理解是，在这种情况下（即除了 'alpha-beta pruning' 之外没有任何特征）的 alpha-beta 应该是 stable，无论搜索的顺序是——最起码应该return一个相同值的节点。我错了吗？我做错了什么吗？

第一次编辑：虽然我认为从这个问题的描述中可以看出这一点，但事实证明我的 alpha-beta 实现中存在一些未知的错误。进一步的测试表明它不提供与纯极小极大相同的结果。

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

explore(depth, maxDepth, alpha, beta)
    // some tafl variants feature rules where one player moves more than once in a turn
    // each game tree node knows whether it's maximizing or minimizing
    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) break


rootNode.explore(0, 5, -infinity, infinity)

Answer 1

原来是我的错。我有一些代码递归地重估某个节点上方的节点，用于扩展搜索，我在错误的地方调用它（在探索任何节点的所有子节点之后）。早期的反向传播导致不正确的 alpha 和 beta 值，因此导致提前截止。

alpha-beta 搜索中意外的路径依赖？

Unexpected path dependence in alpha-beta search?

artificial-intelligence

alpha-beta-pruning