井字棋Minimax算法未按预期响应，请求问题原因排查

我近期尝试实现一个返回井字棋最佳走法的基础API，尽可能自主编写代码。原本认为方案可行，但算法既不会阻止对手获胜，也无法实现预期功能。我并非寻求正确代码，而是想了解代码未达预期的原因。

测试场景：我走中心位置，AI回应走左上；我走右下，AI走中上；我走右上时，AI未按预期走右中阻止我获胜，反而走左中。推测问题出在minmax()的递归调用及数据传递环节，这已是第三次实现该算法，目前难以理清逻辑。了解多数井字棋算法实现采用嵌套列表表示棋盘行，但认为这并非问题根源，若有误也希望得到解释。

代码片段 #

from copy import deepcopy

def player(board: list[str | None]):
    """Returns the next player for a given board
    
    Assumes that X goes first for any given game
    """
    if board.count("X") > board.count("O"):
        return "O"
    return "X"


def result_of_move(board: list[str | None], move:int) -> list[str | None]:
    """Returns resultant board from a given move, based on current player
        
    <move> parameter must be an integer 0-8 (inclusive)
    Player move determined by player()
    For use by opponent models in determining resultant actions
    """
    if (move not in range(9)) or (board[move] != None):
        raise Exception("Invalid move!")

    board_copy = deepcopy(board)
    board_copy[move] = player(board)
    
    return board_copy


def available_actions(board: list[str | None]) -> list[int]:
    """Returns available move indices given a board state. 
    
    Agnostic to which player's turn it is, for use by opponent models to 
    populate search pahts
    """
    options = []
    for i, x in enumerate(board):
        if x is None:
            options.append(i)
    return options

def winner(board: list[str | None]):
    """Takes a board and returns winner if any, else None"""
    win_states = [
        [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 line in win_states:
        a, b, c = line
        if board[a] and board[a] == board[b] == board[c]:
            return board[a]
    return None
    

def is_terminal(board: list[str | None]) -> bool:
    """Returns whether game is over or not
    
    To be used as a base case check for recursive opponent models
    """
    if None not in board:
        return True
    if winner(board):
        return True
    return False

def board_utility(board: list[str | None]):
    if winner(board) == "X":
        return 1
    elif winner(board) == "O":
        return -1
    else:
        return 0


def minmax(board: list[str | None]):
    """Returns the optimal move value and index based on board input board
    
    This implements the minmax algorithm *without* alpha-beta pruning or depth-, 
    limiting, using full depth-first search. X is assumed the maximizing player
    """

    def max_value(board):
        value = -2
        move = None
        
        for action in available_actions(board):
            res = result_of_move(board, action)
            if is_terminal(res):
                return (board_utility(res), action)
            
            v = max(min_value(res)[0], value)
            
            if v >= value:
                value = v
                move = action
        return (value, move)
    
    def min_value(board):
        value = 2
        move = None
        
        for action in available_actions(board):
            res = result_of_move(board, action)
            if is_terminal(res):
                return (board_utility(res), action)
            
            v = min(max_value(res)[0], value)
            
            if v <= value:
                value = v
                move = action
        return (value, move)
        
    if is_terminal(board):
        return None
    
    if player(board) == "X":
        return max_value(board)[1]
    else:
        return min_value(board)[1]

核心问题分析 #

1. 终端状态的提前返回破坏遍历逻辑 #

在max_value和min_value函数中，遍历可用走法时只要遇到终端状态（即走法后游戏结束）就直接return，这会导致算法只检查第一个终端状态的走法，完全跳过后续所有可能的走法。比如，当某个走法能直接结束游戏，但并非当前玩家的最优选择时，函数会直接返回该走法，而不会比较其他走法的结果，这彻底违背了Minimax算法需要遍历所有后续状态并选择最优解的核心逻辑。

2. 效用值更新逻辑错误 #

• max_value函数：v = max(min_value(res)[0], value)的写法错误。正确逻辑应该是先获取子节点的效用值，再与当前记录的最大value比较，若子节点值更大则更新value和对应move。当前写法会导致value无法正确累积所有子节点的最优值，而是每次只取当前子节点值和旧value的最大值，后续判断v >= value时永远为真，无法正确筛选出最优走法。
• min_value函数：存在同样问题，v = min(max_value(res)[0], value)的写法错误，无法正确追踪最小效用值对应的走法。

3. 棋盘表示方式的验证 #

你采用的一维列表表示棋盘（索引0-8对应3x3网格）是完全可行的，并非问题根源。多数实现用嵌套列表只是为了直观对应行和列，一维列表在逻辑上没有任何问题，无需调整。

内容的提问来源于stack exchange，提问作者Danyal Ahmed