提升奥赛罗AI性能：Negascout (PVS) 算法实现指南

def negamax(board, depth, alpha, beta, player_multiplier):
    # 终止条件：游戏结束或达到搜索深度
    if game_end(board):
        return player_multiplier * score_end(board) # 终局得分，乘以 player_multiplier 转换为当前玩家视角
    if depth == 0:
        return player_multiplier * score(board) # 局面评估，乘以 player_multiplier 转换为当前玩家视角

    # 生成当前玩家的所有合法走法
    moves = find_legal_moves(board, player_multiplier)

    # 如果没有合法走法，表示当前玩家跳过回合，轮到对手
    if not moves:
        # 深度减1，alpha/beta 翻转，玩家乘数翻转
        return negamax(board, depth - 1, -beta, -alpha, -player_multiplier)

    # 走法排序（对 PVS 性能至关重要）
    # 这里只是一个占位符，实际需要更复杂的排序逻辑
    sorted_moves = sort_moves_by_heuristic(moves, board, player_multiplier)

    max_score = -float('inf')

    for move in sorted_moves:
        new_board = make_move(board, move, player_multiplier)

        # 递归调用 NegaMax，对子节点进行搜索
        # 注意：子节点的 alpha/beta 窗口需要翻转，player_multiplier 也需要翻转
        score = -negamax(new_board, depth - 1, -beta, -alpha, -player_multiplier)

        max_score = max(max_score, score)
        alpha = max(alpha, max_score) # 更新 alpha 值

        if alpha >= beta: # Beta 剪枝
            break

    return max_score

def negascout_pvs(board, depth, alpha, beta, player_multiplier):
    # 终止条件
    if game_end(board):
        return player_multiplier * score_end(board)
    if depth == 0:
        return player_multiplier * score(board)

    moves = find_legal_moves(board, player_multiplier)
    if not moves:
        return negascout_pvs(board, depth - 1, -beta, -alpha, -player_multiplier)

    # 走法排序：这是 PVS 性能的关键
    # 实际应用中，这里会使用 PV 表、杀手走法、历史启发等高级排序策略
    sorted_moves = sort_moves_by_heuristic(moves, board, player_multiplier)

    best_score = -float('inf')
    first_move = True

    for move in sorted_moves:
        new_board = make_move(board, move, player_multiplier)

        if first_move:
            # 第一个子节点：进行全窗口搜索
            score = -negascout_pvs(new_board, depth - 1, -beta, -alpha, -player_multiplier)
            first_move = False
        else:
            # 后续子节点：尝试零窗口搜索 (Null Window Search)
            # 窗口为 [-alpha-1, -alpha]，如果结果在这个狭窄窗口内，则表示该分支可能不如当前最佳
            # 否则，如果结果超出 -alpha，则说明它可能是一个更好的走法，需要进行全窗口重搜索
            score = -negascout_pvs(new_board, depth - 1, -alpha - 1, -alpha, -player_multiplier)

            # 如果零窗口搜索结果大于 alpha 且小于 beta，则需要进行全窗口重搜索
            # 这是因为零窗口搜索可能错过了真实值，需要用更宽的窗口再次确认
            if alpha < score < beta: # 注意：这里的 score 已经是子节点的负值
                score = -negascout_pvs(new_board, depth - 1, -beta, -score, -player_multiplier) # score 作为新的 beta

        best_score = max(best_score, score)
        alpha = max(alpha, best_score) # 更新 alpha

        if alpha >= beta: # Beta 剪枝
            break

    return best_score