井字棋Minimax算法实现异常：AI无法选择最优落子

核心错误分析 #

1. 胜负得分逻辑完全颠倒 #

原terminalState函数中，玩家（X）获胜返回1，AI（O）获胜返回-1。但AI作为Maximizer（最大化得分），这会导致AI主动追求让玩家获胜的结果，完全违背Minimax算法的设计逻辑。正确的得分逻辑应为：

• AI（O）获胜：返回正分（如10）
• 玩家（X）获胜：返回负分（如-10）
• 平局：返回0

2. 未区分"游戏未结束"与"平局"状态 #

原terminalState函数在游戏未结束时返回0，与平局的返回值混淆，导致Minimax无法正确终止递归。需修改为：

• 有赢家：返回对应得分
• 棋盘已满无赢家：返回0（平局）
• 游戏未结束：返回None

3. Max/Min函数未处理无空位边界 #

当棋盘已满时，maxValue和minValue会返回初始的-inf或inf，导致递归逻辑出错，需在循环结束后判断是否有有效得分，若无则返回平局分0。

4. 未引入深度权重优化落子选择 #

原代码未考虑获胜步数，AI可能选择延迟获胜的路径。通过在得分中加入深度权重（如得分 - 深度），可让AI优先选择最快获胜的落子。

修正后的完整代码 #

import math

board = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

def displayTable():
    for _ in range(30):
        print('-', end='')
    print('-')
    for row in board:
        print('|', end='')
        for cell in row:
            if cell == 0:
                print('         |', end='')
            else:
                print(f'   {cell}   |', end='')
        print()
        for _ in range(30):
            print('-', end='')
        print('-')

def getUserMove():
    print("Enter the x, y coordinates (0-indexed, comma-separated without spaces):")
    while True:
        usermove = input()
        userArray = usermove.split(',')
        if len(userArray) != 2:
            print("Invalid input format! Try again.")
            continue
        try:
            x, y = int(userArray[0]), int(userArray[1])
        except ValueError:
            print("Please enter valid integers! Try again.")
            continue
        if x < 0 or x > 2 or y < 0 or y > 2:
            print('Spot out of range! Try again.')
            continue
        if board[x][y] != 0:
            print('Spot already taken! Try again.')
            continue
        board[x][y] = 'X'
        break

def terminalState(gameboard):
    # 检查行胜负
    for i in range(3):
        if gameboard[i][0] == gameboard[i][1] == gameboard[i][2] != 0:
            return 10 if gameboard[i][0] == 'O' else -10
    # 检查列胜负
    for i in range(3):
        if gameboard[0][i] == gameboard[1][i] == gameboard[2][i] != 0:
            return 10 if gameboard[0][i] == 'O' else -10
    # 检查对角线胜负
    if gameboard[0][0] == gameboard[1][1] == gameboard[2][2] != 0:
        return 10 if gameboard[0][0] == 'O' else -10
    if gameboard[2][0] == gameboard[1][1] == gameboard[0][2] != 0:
        return 10 if gameboard[2][0] == 'O' else -10
    # 检查平局
    if all(cell != 0 for row in gameboard for cell in row):
        return 0
    # 游戏未结束
    return None

def maxValue(board, depth):
    best_score = -math.inf
    for i in range(3):
        for j in range(3):
            if board[i][j] == 0:
                board[i][j] = 'O'
                score = minimax(board, depth + 1, False)
                board[i][j] = 0
                best_score = max(best_score, score)
    # 无空位时返回平局分
    return best_score if best_score != -math.inf else 0

def minValue(board, depth):
    best_score = math.inf
    for i in range(3):
        for j in range(3):
            if board[i][j] == 0:
                board[i][j] = 'X'
                score = minimax(board, depth + 1, True)
                board[i][j] = 0
                best_score = min(best_score, score)
    # 无空位时返回平局分
    return best_score if best_score != math.inf else 0

def minimax(board, curDepth, isMaximizing):
    state = terminalState(board)
    if state is not None:
        # 深度权重：AI尽快赢得分更高，玩家尽快输得分更低
        return state - curDepth if isMaximizing else state + curDepth
    if isMaximizing:
        return maxValue(board, curDepth)
    else:
        return minValue(board, curDepth)

def aiMove(board):
    best_score = -math.inf
    aimovex, aimovey = -1, -1
    for i in range(3):
        for j in range(3):
            if board[i][j] == 0:
                board[i][j] = 'O'
                # AI落子后，轮到玩家（Minimizer）回合
                score = minimax(board, 0, False)
                board[i][j] = 0
                if score > best_score:
                    best_score = score
                    aimovex, aimovey = i, j
    board[aimovex][aimovey] = 'O'

displayTable()
while terminalState(board) is None:
    getUserMove()
    if terminalState(board) is not None:
        displayTable()
        break
    aiMove(board)
    displayTable()

final_state = terminalState(board)
if final_state == -10:
    print('Congratulations! You won!')
elif final_state == 10:
    print('You tried your best. Thank you for playing')
else:
    print('Tie game. Thank you for playing')

修正点说明 #

1. 得分逻辑修正：将AI获胜得分改为10，玩家获胜改为-10，确保AI（Maximizer）主动追求获胜。
2. 状态区分：terminalState返回None表示游戏未结束，0表示平局，±10表示胜负，避免递归混淆。
3. 深度权重优化：在Minimax返回得分时加入深度调整，AI会优先选择最快获胜的路径。
4. 边界处理：在maxValue和minValue中处理无空位情况，返回平局分0，避免无效值传递。
5. 输入逻辑优化：简化getUserMove的输入验证，提升用户体验。

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