我需要帮助为 Othello 实施 Negascout（主要变异搜索）

Question

我正在尝试在我的 Othello ai 中实现 pvs，作为改进 alpha beta proning 的一种方法，但是当我实现它时，它实际上慢了大约一倍，我的问题是，我将如何实现它，我能做什么通过保留 min/man 而不必将其变成单个函数。我欢迎任何建议。我大致了解 pvs 的工作原理，但我仍然对某些事情感到困惑。我的评分函数为 x 给出正数，为 y 给出负数

def max_step(board,depth,path,a,b):
    if game_end(board):
        return score_end(board)
    if depth == 0:
        return score(board)
    my_moves = {i:score((k := make_move(board,i,"x"))) for i in find_indexses(board,"x")}
    if len(my_moves) == 0:
        return min_step(board,depth-1,path,a,b)
    results = []
    my_sorted_moves = dict(sorted(my_moves.items(), key=lambda item: item[1],reverse=True))
    result = None
    for move,index in enumerate(my_sorted_moves.keys()) :
        new_board = make_move(board,index,"x")
        if index == 0:
            result = min_step(new_board,depth-1,path+[board],a,b)
        else:
            result = min_step(new_board,depth-1,path+[board],b-1,b)
            if result > a and result < b:
                result = min_step(new_board,depth-1,path+[board],a,b)
        results.append(result)
        if result >= a:
            a = result
        if b <= a:
            break
    return max(results)

def min_step(board,depth,path,a,b):
    if game_end(board):
        return score_end(board)
    if depth == 0:
        return score(board)
    my_moves = {i:score((k := make_move(board,i,"o"))) for i in find_indexses(board,"o")}
    if len(my_moves) == 0:
        return min_step(board,depth-1,path,a,b)
    results = []
    my_sorted_moves = dict(sorted(my_moves.items(), key=lambda item: item[1]))
    result = None
    for move,index in enumerate(my_sorted_moves.keys()) :
        new_board = make_move(board,index,"o")
        if index == 0:
            result = max_step(new_board,depth-1,path+[board],a,b)
        else:
            result = max_step(new_board,depth-1,path+[board],b-1,b)
            if result > a and result < b:
                result = max_step(new_board,depth-1,path+[board],a,b)
        results.append(result)
        if result <= b:
            b = result
        if b <= a:
            break
    return min(results)

def find_next_move(board,token,depth):
    res = {}
    for moves in find_indexses(board,token):
        if token == "x":
            board1 = board
            board1 = make_move(board1,moves,"x")
            res[moves] = min_step(board1,depth-1,[board],-99999999,9999999)
        else:
            board1 = board
            board1 = make_move(board1,moves,"o")
            res[moves] = max_step(board1,depth-1,[board],-99999999,9999999)
    print(res)
    if token == "x":
        return max(zip(res.values(), res.keys()))[1]
    return min(zip(res.values(), res.keys()))[1]

我试图保持我的最小/最大函数完整，只是编辑它们以添加 pvs，但它不起作用，我也尝试只使用一个函数，但这对我来说在 othello 的上下文中没有意义，除了从此我不知道该怎么办

Answer 1

我强烈建议将其制作成一个可以作为任意一方运行的函数。通过创建基本相同的例程的两个副本，这两个副本都必须正确并保持完全一致，您在这里的麻烦就加倍了。

如果用 +1 和 -1 表示边，那么将位置分数乘以“边”会使问题在每个级别上成为纯粹的最大化问题。

(Nega)Scout 要求移动顺序非常好，以使其表现优于 alpha-beta，并且通常从先前 N-1 深度搜索的结果中获取其主要变化起点。如果你不进行迭代深化来获得相当好的 PV，那么我不确定会有明显的好处。

在 NegaScout 或 Alpha-Beta 中效果良好的另一个启发式是“杀手移动”启发式，如果它是合法移动，则值得在进行任何移动生成之前尝试（我不确定它在黑白棋中效果如何）。

如果你得到任何一个修剪窗口错误，你可能最终会做两次所有的工作，因为最初的乐观侦察搜索失败，所以它必须进行全窗口搜索，因此你的观察。

我建议选择一个具有少量合法步数的测试位置（如果需要的话，可以构建它不需要是一个合理的真实游戏位置），距离白方获胜还有 3 或 4 步，并且只有一个非常强的获胜步，然后跟踪第 2 层到第 4 层每个层的代码执行，看看哪里无法准确修剪。如果您将有效移动的数量保持在较低水平，那么您可以手动探索和映射整个游戏树。

如果您确实愿意，可以使用单独的最小值和最大值来完成此操作，但这会增加犯愚蠢错误的风险（即使您确实需要非常仔细地思考才能将其折叠为单个例程）。我建议将它们作为 Diff 之类的片段进行相互检查，以确保它们自我一致。

很容易犯栅栏错误或在某个地方漏掉“-”！

我认为 Wiki 中给出的Principal Variation Search 的例子是可以的。 为什么不尝试基于此的新功能，看看是否可以使其工作？