如何修复Mancala游戏中minimax算法的异常计算问题

尝试独立实现Minimax算法，已完成Node类与search_ahead搜索方法，但未编写AI类，目前遇到以下异常：

• 计算得到的所有估值不合理地偏向先手玩家；
• 手动推演分支后，计算值与实际对局结果不符；
• 当搜索深度大于3时，所有返回值均为负数。

深度为3时的示例输出 #

数值代表bottom玩家与top玩家的得分差：

pocket 8: [-1, -1, -1, -1, -1]
pocket 9: [0, -1, -1, -1, -1]
pocket 10: [-1, -1, -2, -2, -2]
pocket 11: [-1, -1, -2, -2, -2]
pocket 12: [-8, -1, -2, -2, -2]
pocket 13: [-1, -3, -2, -2, -2]
pocket 1: [-1, -1, -2, -2, -8, -3].

1. 估值偏向先手的核心原因 #

Minimax算法中玩家视角与max/min角色的对应逻辑错误：原代码所有层级均使用bottom得分 - top得分作为估值，未考虑top玩家（min方）的目标是最小化该差值，导致估值始终偏向先手的bottom玩家。修复时需根据当前玩家视角调整估值计算逻辑。

2. 推演结果不符的问题点 #

• Board.move_pieces中无效移动的move_again状态设置错误，导致无效移动被错误允许再次行动；
• 落子后的吃子逻辑存在边界判断错误，未正确处理对方口袋无棋子的情况；
• 递归中字符串与布尔值的判断不统一（如useful_list[1]==False与useful_list[1]=="False"混用），导致回合切换逻辑混乱。

3. 深度大于3返回全负的问题 #

递归终止时的估值未根据玩家视角调整，且高层级节点的max/min选择逻辑未正确跟随回合切换，导致错误的估值累加，最终出现全负结果。

import copy

class Board():
    def __init__(self, turn, position, pockets):
        # 移除冗余的game_state参数，简化初始化
        self.turn = turn
        self.position = position
        self.pockets = pockets.copy() if pockets else {}

    def make_pieces(self):
        # 初始化棋盘棋子数
        for i in range(1, 7):
            self.pockets[f"pocket_{i}"] = 4
        for i in range(8, 14):
            self.pockets[f"pocket_{i}"] = 4
        self.pockets["pocket_7"] = 0
        self.pockets["pocket_14"] = 0

    def move_pieces(self):
        starting_position = self.position
        valid_move = "True"
        move_again = "False"

        # 基础无效移动判断
        if starting_position in (7, 14):
            valid_move = "False"
            return [valid_move, move_again]
        if self.turn == "top" and 1 <= starting_position <=7:
            valid_move = "False"
            return [valid_move, move_again]
        if self.turn == "bottom" and 8 <= starting_position <=14:
            valid_move = "False"
            return [valid_move, move_again]
        if self.pockets[f"pocket_{starting_position}"] == 0:
            valid_move = "False"
            return [valid_move, move_again]

        # 执行棋子移动逻辑
        pieces = self.pockets[f"pocket_{starting_position}"]
        self.pockets[f"pocket_{starting_position}"] = 0
        current_pos = starting_position

        while pieces > 0:
            current_pos += 1
            # 跳过对方的得分口袋
            if self.turn == "bottom" and current_pos == 14:
                current_pos = 1
            if self.turn == "top" and current_pos ==7:
                current_pos =8
            if current_pos >14:
                current_pos =1

            self.pockets[f"pocket_{current_pos}"] +=1
            pieces -=1

        # 判断是否可以再次行动
        if (self.turn == "bottom" and current_pos ==7) or (self.turn == "top" and current_pos ==14):
            move_again = "True"
        else:
            # 修正后的吃子逻辑
            if self.turn == "bottom" and 1<= current_pos <=6 and self.pockets[f"pocket_{current_pos}"] ==1:
                opposite_pocket = 14 - current_pos
                if self.pockets[f"pocket_{opposite_pocket}"] >0:
                    self.pockets["pocket_7"] += self.pockets[f"pocket_{current_pos}"] + self.pockets[f"pocket_{opposite_pocket}"]
                    self.pockets[f"pocket_{current_pos}"] =0
                    self.pockets[f"pocket_{opposite_pocket}"] =0
            if self.turn == "top" and 8<= current_pos <=13 and self.pockets[f"pocket_{current_pos}"] ==1:
                opposite_pocket = 14 - (current_pos -7)
                if self.pockets[f"pocket_{opposite_pocket}"] >0:
                    self.pockets["pocket_14"] += self.pockets[f"pocket_{current_pos}"] + self.pockets[f"pocket_{opposite_pocket}"]
                    self.pockets[f"pocket_{current_pos}"] =0
                    self.pockets[f"pocket_{opposite_pocket}"] =0

        return [valid_move, move_again]

class Node():
    def __init__(self, game_state, pocket, depth, parent=None):
        self.game_state = game_state
        self.pocket = pocket
        self.depth = depth
        self.parent = parent
        self.children = []
        self.value = None  # 用单个值替代列表，简化估值传递逻辑

    def search_ahead(self):
        # 复制棋盘，避免修改原状态
        test_board = copy.deepcopy(self.game_state)
        test_board.position = self.pocket
        valid_move, move_again = test_board.move_pieces()

        if valid_move == "False":
            # 无效移动返回对应极差估值
            self.value = -float('inf') if self.game_state.turn == "bottom" else float('inf')
            if self.parent:
                return
            else:
                return self.value

        # 递归终止条件：搜索深度为1
        if self.depth ==1:
            bottom_score = test_board.pockets["pocket_7"]
            top_score = test_board.pockets["pocket_14"]
            # 根据玩家视角计算估值
            if self.game_state.turn == "bottom":
                self.value = bottom_score - top_score
            else:
                self.value = top_score - bottom_score
            if self.parent:
                self.parent.children.append(self)
            return self.value

        # 确定下一个玩家
        next_turn = test_board.turn if move_again == "True" else ("top" if test_board.turn == "bottom" else "bottom")
        test_board.turn = next_turn

        # 扩展子节点并递归搜索
        if next_turn == "bottom":
            for i in range(1,7):
                child_node = Node(test_board, i, self.depth-1, self)
                self.children.append(child_node)
                child_node.search_ahead()
            # 筛选有效估值并取最大值（bottom为max方）
            valid_values = [child.value for child in self.children if child.value != -float('inf')]
            self.value = max(valid_values) if valid_values else -float('inf')
        else:
            for i in range(8,14):
                child_node = Node(test_board, i, self.depth-1, self)
                self.children.append(child_node)
                child_node.search_ahead()
            # 筛选有效估值并取最小值（top为min方）
            valid_values = [child.value for child in self.children if child.value != float('inf')]
            self.value = min(valid_values) if valid_values else float('inf')

        # 传递估值给父节点或返回根节点值
        if self.parent:
            return self.value
        else:
            return self.value

# 测试代码
game_board = Board("bottom", 1, {})
game_board.make_pieces()

# 测试深度3的根节点
root_node = Node(game_board, 1, 3)
result = root_node.search_ahead()
print(f"Root node value (depth 3): {result}")

# 打印子节点估值
print("\nChild node values:")
for child in root_node.children:
    print(f"Pocket {child.pocket}: {child.value}")

内容的提问来源于stack exchange，提问作者Chris Porter