TicTacToe递归Minimax函数返回None引发类型错误求助

问题现象 #

开发井字棋Minimax算法时，max_value和min_value函数偶尔返回None，触发错误：'>' not supported between instances of 'NoneType' and 'int'，错误出现在if aux < v:和if aux > v:语句处，打印aux时偶尔显示为None。

相关代码 #

def player(board):
    if Terminal(board) != False:
        return None
    else:
        if turn(board) == "X":
            value,move = max_value(board)
            return move
        else:
            value,move = min_value(board)
            return move
        
def max_value(board):
    if Terminal(board) != False:
        return Utility(board),None
    else:
        v = -1000
        move = None
        for action in Actions(board):
            aux,act = min_value(Result(board,action))
            print(aux)
            if aux > v:
                v = aux
                move = action
                if v == 1:
                    return v,move
        return v,move

def min_value(board):
    if Terminal(board) != False:
        return Utility(board),None
    else:
        v = 1000
        move = None
        for action in Actions(board):
            aux,act = max_value(Result(board,action))
            print(aux)
            if aux < v:
                v = aux
                move = action
                if v == -1:
                    return v,move
        return v,move

问题原因分析 #

aux出现None的核心原因是Utility函数在某些游戏结束状态下返回了None，或者Terminal函数的判断逻辑错误：

1. 如果Terminal函数未正确识别游戏结束状态（比如棋盘已满但未分胜负的平局场景），会进入非Terminal分支，但此时Actions返回空列表，不过这种情况v会是初始值（-1000/1000）而非None，所以更可能是前者。
2. Utility函数未覆盖所有Terminal状态，导致部分场景下返回None，进而让max/min_value返回(None, None)。

解决方法 #

1. 修复Utility函数

确保Utility在所有游戏结束状态下返回有效整数值：

• X获胜返回1
• O获胜返回-1
• 平局返回0
  示例实现：

def Utility(board):
    # 检查行、列、对角线是否有获胜者
    lines = [board[i] for i in range(3)] + \
            [[board[j][i] for j in range(3)] for i in range(3)] + \
            [[board[0][0], board[1][1], board[2][2]], [board[0][2], board[1][1], board[2][0]]]
    for line in lines:
        if line == ['X', 'X', 'X']:
            return 1
        elif line == ['O', 'O', 'O']:
            return -1
    # 无获胜者则是平局
    return 0

2. 修正Terminal函数逻辑

确保Terminal函数准确判断游戏结束状态：

• 有玩家获胜时返回True
• 棋盘已满但无获胜者时返回True
• 游戏未结束时返回False
  示例实现：

def Terminal(board):
    # 检查是否有获胜者
    lines = [board[i] for i in range(3)] + \
            [[board[j][i] for j in range(3)] for i in range(3)] + \
            [[board[0][0], board[1][1], board[2][2]], [board[0][2], board[1][1], board[2][0]]]
    for line in lines:
        if line == ['X', 'X', 'X'] or line == ['O', 'O', 'O']:
            return True
    # 检查棋盘是否已满
    for row in board:
        if ' ' in row:  # 假设空位用空格表示
            return False
    return True

3. 优化max/min_value函数（可选）

用-float('inf')和float('inf')替代固定数值作为初始值，同时添加防御性检查避免None值：

def max_value(board):
    if Terminal(board):
        return Utility(board), None
    v = -float('inf')
    move = None
    for action in Actions(board):
        aux, act = min_value(Result(board, action))
        # 防御性检查，跳过None值
        if aux is None:
            continue
        if aux > v:
            v = aux
            move = action
            if v == 1:
                return v, move
    return v, move

def min_value(board):
    if Terminal(board):
        return Utility(board), None
    v = float('inf')
    move = None
    for action in Actions(board):
        aux, act = max_value(Result(board, action))
        if aux is None:
            continue
        if aux < v:
            v = aux
            move = action
            if v == -1:
                return v, move
    return v, move

4. 验证Actions函数

确保Actions函数在游戏未结束时返回所有可行空位的列表，比如：

def Actions(board):
    moves = []
    for i in range(3):
        for j in range(3):
            if board[i][j] == ' ':  # 空位判断
                moves.append((i, j))
    return moves

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