在alpha中出现意外的路径依赖

2018-06-20 00:31:34

我正在为老式的诺基亚tafl系列棋类游戏编写一个人工智能（这里的项目，这里是源文件）。他们已经足够接近国际象棋的知识，在这里申请国际象棋。（所讨论的变体是在7x7棋盘上以径向对称的起始位置进行播放，白色从中间开始，黑色从边缘开始。）我遇到了一个奇怪的问题，那就是我如何实施alpha-beta搜索：搜索到固定深度的结果，除了alpha-beta修剪之外没有启用优化，根据探索节点的顺序而变化。

在讨论的文件中，重要的方法是“探索”，“探索孩子”，“handleEvaluationResults”和“generateSuccessorMoves”。 'explore'检查是否存在换位表命中（在此测试的其他位置禁用），评估状态（如果它是胜利或叶节点）还是调用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修剪'之外没有任何功能），alpha-beta应该稳定，无论搜索顺序如何 - 在至少它应该返回一个相同值的节点。我错了吗？难道我做错了什么？

首先编辑：虽然我认为从这个问题的描述中可以明显看出，但我的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)

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

链接地址: http://www.djcxy.com/p/56321.html

上一篇: Unexpected path dependence in alpha

下一篇: How to account for move order in chess board evaluation