使用Minimax算法实现井字棋时无法生成最优移动的问题求助

问题核心原因 #

你的井字棋AI无法做出最优移动（总是选(3,3)、不阻挡对手），核心问题出在奖励函数逻辑颠倒和Minimax的最大化/极小化玩家身份匹配错误，导致AI的决策逻辑完全反向。

具体错误点 #

• reward函数逻辑错误：原代码中board.winner == board.turn的判断完全错误，board.turn是下一个玩家的回合，而非当前获胜玩家。比如AI（O，False）赢了后，turn会切换为人类玩家（X，True），此时判断会返回False，导致AI认为获胜是低分、失败是高分，决策完全颠倒。
• Minimax的maxi参数固定错误：原choose方法固定传入maxi=True，但AI是极小化玩家（要最小化人类的得分），人类是极大化玩家，两者的搜索方向完全相反，固定参数会导致AI决策逻辑混乱。
• find_winner函数冗余判断：循环遍历玩家列表的操作多余，可直接判断三连位置是否为同一非空玩家。

修复后的完整代码 #

from abc import ABC, abstractmethod
import math

# 棋盘节点抽象类
class Node(ABC):
    @abstractmethod
    def find_children(self):
        "生成所有可能的后续棋盘状态"
        return set()
    @abstractmethod
    def is_terminal(self):
        "判断当前节点是否为游戏结束状态"
        return True
    @abstractmethod
    def reward(self, player):
        "终端状态奖励：1=玩家获胜，0=玩家失败，0.5=平局"
        return 0

class MinimaxTreeSearch:
    def __init__(self, depth=9):  # 井字棋最多9步，设置depth=9可搜索所有可能结局
        self.depth = depth

    def choose(self, node, player):
        if node.is_terminal() or self.depth == 0:
            raise RuntimeError(f"choose called on terminal node {node}")
        # 根据玩家身份确定搜索方向：人类X是最大化玩家，AI O是极小化玩家
        is_maximizing = (player is True)
        best_move, _ = self.minimax(node, self.depth, is_maximizing, player)
        return best_move

    def minimax(self, node, depth, is_maximizing, current_player):
        if depth == 0 or node.is_terminal():
            return None, node.reward(current_player)
        
        moves = list(node.find_children())
        if is_maximizing:
            best_value = -math.inf
            best_move = None
            for move in moves:
                _, value = self.minimax(move, depth-1, False, current_player)
                if value > best_value:
                    best_value = value
                    best_move = move
            return best_move, best_value
        else:
            best_value = math.inf
            best_move = None
            for move in moves:
                _, value = self.minimax(move, depth-1, True, current_player)
                if value < best_value:
                    best_value = value
                    best_move = move
            return best_move, best_value

class ticboard(Node):
    def __init__(self, board_state=[None,]*9, winner=None, turn=True, terminal=False):
        self.board_state = board_state
        self.turn = turn  # True=人类X回合，False=AI O回合
        self.winner = winner
        self.terminal = terminal

    def find_children(self):
        if self.terminal:
            return set()
        return {self.make_move(i) for i, value in enumerate(self.board_state) if value is None}

    def reward(self, player):
        if not self.terminal:
            raise RuntimeError(f"reward called on non-terminal board {self}")
        if self.winner is None:
            return 0.5  # 平局
        return 1 if self.winner == player else 0  # 玩家获胜返回1，否则返回0

    def is_terminal(self):
        return self.terminal

    def make_move(self, index):
        board_state = self.board_state.copy()
        board_state[index] = self.turn
        turn = not self.turn
        winner = find_winner(board_state)
        is_terminal = (winner is not None) or not any(spot is None for spot in board_state)
        return ticboard(board_state, winner, turn, is_terminal)

    def to_pretty_string(self):
        to_char = lambda v: ("X" if v is True else ("O" if v is False else " "))
        rows = [
            [to_char(self.board_state[3 * row + col]) for col in range(3)] for row in range(3)
        ]
        return (
            "  1 2 3\n"
            + "\n".join(str(i + 1) + " " + " ".join(row) for i, row in enumerate(rows))
            + "\n"
        )

def play_game():
    tree = MinimaxTreeSearch(depth=9)
    board = ticboard()
    print(board.to_pretty_string())
    while True:
        # 人类玩家（X，True）回合
        row_col = input("enter row,col: ")
        row, col = map(int, row_col.split(","))
        index = 3 * (row - 1) + (col - 1)
        if board.board_state[index] is not None:
            print("Invalid move, try again!")
            continue
        board = board.make_move(index)
        print(board.to_pretty_string())
        if board.terminal:
            break
        # AI玩家（O，False）回合
        board = tree.choose(board, player=False)
        print(board.to_pretty_string())
        if board.terminal:
            break

def win_combos():
    return [
        [0,1,2], [3,4,5], [6,7,8],  # 横向三连
        [0,3,6], [1,4,7], [2,5,8],  # 纵向三连
        [0,4,8], [2,4,6]             # 斜向三连
    ]

def find_winner(board_state):
    for combo in win_combos():
        a, b, c = combo
        if board_state[a] == board_state[b] == board_state[c] and board_state[a] is not None:
            return board_state[a]
    return None

if __name__ == "__main__":
    play_game()

修复说明 #

1. 修正奖励逻辑：新增player参数，明确判断当前查询奖励的玩家是否为获胜者，返回正确的1/0/0.5分数。
2. 匹配玩家搜索方向：choose方法根据玩家身份（人类/AI）设置is_maximizing参数，确保Minimax搜索方向与玩家目标一致。
3. 拉满搜索深度：井字棋最多9步，设置depth=9可搜索所有可能结局，保证AI做出绝对最优决策。
4. 简化获胜判断：去掉冗余的玩家循环，直接检查三连位置是否为同一非空玩家。

内容的提问来源于stack exchange，提问作者Jakob Augsburg