CS50 AI井字棋项目：Minimax树函数实现求助

现有代码问题分析 #

• Action函数逻辑混乱，未正确生成当前玩家的所有可行落子后的棋盘状态，无法为Minimax提供正确的决策分支。
• terminal函数未处理棋盘已满但无人获胜的平局场景，会导致递归无法正确终止。

修正与实现步骤 #

1. 修正Action函数 #

该函数应返回当前玩家在棋盘上所有可行落子后得到的新棋盘列表，每个新棋盘对应一种合法走法：

def actions(board):
    # 获取当前玩家
    current_player = player(board)
    valid_boards = []
    for i in range(9):
        if board[i] == " ":
            # 复制棋盘并落子
            new_board = copyArr(board)
            new_board[i] = current_player
            valid_boards.append(new_board)
    return valid_boards

2. 完善terminal函数 #

补充平局判断逻辑：

def terminal(s):
    winning_combinations = [
        [0, 1, 2], [3, 4, 5], [6, 7, 8],
        [0, 3, 6], [1, 4, 7], [2, 5, 8],
        [0, 4, 8], [2, 4, 6]
    ]
    # 检查是否有人获胜
    for combination in winning_combinations:
        if s[combination[0]] == s[combination[1]] == s[combination[2]] and s[combination[0]] != " ":
            utility = 1 if s[combination[0]] == "O" else -1
            return True, utility
    # 检查是否平局（棋盘无空格）
    if " " not in s:
        return True, 0
    # 游戏未结束
    return False, 0

3. 实现Minimax核心逻辑 #

Minimax通过递归模拟Max玩家（O，追求最高utility）和Min玩家（X，追求最低utility）的决策过程：

def max_value(board):
    is_terminal, util = terminal(board)
    if is_terminal:
        return util
    v = -float('inf')
    for action in actions(board):
        v = max(v, min_value(action))
    return v

def min_value(board):
    is_terminal, util = terminal(board)
    if is_terminal:
        return util
    v = float('inf')
    for action in actions(board):
        v = min(v, max_value(action))
    return v

def minimax(board):
    current_player = player(board)
    best_value = -float('inf') if current_player == "O" else float('inf')
    best_move = None

    for action in actions(board):
        if current_player == "O":
            # O是Max玩家，取最大价值的走法
            val = min_value(action)
            if val > best_value:
                best_value = val
                best_move = action
        else:
            # X是Min玩家，取最小价值的走法
            val = max_value(action)
            if val < best_value:
                best_value = val
                best_move = action
    return best_move

4. 测试整合 #

可以添加一个简单的游戏循环来测试AI：

def play_game():
    MakeArray()
    global array
    while True:
        print(StyleArray(array))
        # 玩家X走棋（手动输入位置0-8）
        x_pos = int(input("X玩家，请输入落子位置(0-8): "))
        if array[x_pos] != " ":
            print("该位置已被占用，请重新输入！")
            continue
        array[x_pos] = "X"
        # 检查游戏是否结束
        is_end, util = terminal(array)
        if is_end:
            print(StyleArray(array))
            if util == 1:
                print("O玩家获胜！")
            elif util == -1:
                print("X玩家获胜！")
            else:
                print("平局！")
            break
        # AI（O）走棋
        print("AI思考中...")
        array = minimax(array)
        # 检查游戏是否结束
        is_end, util = terminal(array)
        if is_end:
            print(StyleArray(array))
            if util == 1:
                print("O玩家获胜！")
            elif util == -1:
                print("X玩家获胜！")
            else:
                print("平局！")
            break

play_game()

关键说明 #

• max_value函数为Max玩家（O）计算当前棋盘的最大可能价值，递归调用min_value获取对手的最优回应。
• min_value函数为Min玩家（X）计算当前棋盘的最小可能价值，递归调用max_value获取对手的最优回应。
• minimax函数根据当前玩家类型，遍历所有可行走法，选择能带来最优价值的落子棋盘。

内容的提问来源于stack exchange，提问作者jake is the coolest