CS50 AI井字棋：X连成三子未触发胜利判定，O后续获胜排查

问题场景 #

• 以X玩家身份按以下步骤落子：[2][2]放X、[0][0]放O、[0][2]放X、[2][0]放O，随后在[1][2]放X连成三子，游戏未判定胜利，O继续在[1][0]落子连成三子获胜。
• 以O玩家身份游戏时，AI未选择制胜落子，反而优先堵棋。
• 其他场景下胜负判定正常，需定位故障根源。

原代码 #

"""
Tic Tac Toe Player
"""

import math
from random import randint
from copy import deepcopy

X = "X"
O = "O"
EMPTY = None


def initial_state():
    """
    Returns starting state of the board.
    """
    return [[EMPTY, EMPTY, EMPTY],
            [EMPTY, EMPTY, EMPTY],
            [EMPTY, EMPTY, EMPTY]]


def player(board):
    """
    Returns player who has the next turn on a board.
    """
    x_count = 0
    o_count = 0
    for i in range(3):
        for j in range(3):
            if board[i][j] == X:
                x_count += 1
            if board[i][j] == O:
                o_count += 1

    if x_count == o_count:
        return X
    else:
        return O


def actions(board):
    """
    Returns set of all possible actions (i, j) available on the board.
    """
    possible_actions = set()
    for i in range(3):
        for j in range(3):
            if board[i][j] == EMPTY:
                possible_actions.add((i, j))
    return possible_actions


def result(board, action):
    """
    Returns the board that results from making move (i, j) on the board.
    """
    copied_board = deepcopy(board)
    if copied_board[action[0]][action[1]] == EMPTY:
        copied_board[action[0]][action[1]] = player(board)
    else:
        raise Exception("Not a valid move")
    return copied_board


def winner(board):
    """
    Returns the winner of the game, if there is one.
    """
    # Check horizontally and vertically
    for i in range(3):
            if board[i][0] == board[i][1] == board[i][2]:
                return board[i][0]

            elif board[0][i] == board[1][i] == board[2][i]:
                return board[0][i]

    # Check diagonally
    if board[0][0] == board[1][1] == board[2][2]:
        return board[0][0]

    elif board[2][0] == board[1][1] == board[0][2]:
        return board[2][0]
        
    # Return None if tie, as in none of the above conditions were met
    else:
        return None
        

def terminal(board):
    """
    Returns True if game is over, False otherwise.
    """
    if winner(board) == X or winner(board) == O or (winner(board) == None and len(actions(board)) == 0):
        return True
    else:
        return False


def utility(board):
    """
    Returns 1 if X has won the game, -1 if O has won, 0 otherwise.
    """
    if winner(board) == X:
        return 1
    elif winner(board) == O:
        return -1
    else:
        return 0


def minimax(board):
    """
    Returns the optimal move for the current player on the board.
    """
    # Check for terminal state
    if terminal(board):
        return None

    # If X's turn
    elif player(board) == X:
        options = []
        for action in actions(board):
            score = min_value(result(board, action))
            # Store options in list
            options.append([score, action])
        # Return highest value action
        return sorted(options, reverse=True)[0][1]

    # If O's turn
    else:
        options = []
        for action in actions(board):
            score = max_value(result(board, action))
            # Store options in list
            options.append([score, action])
        # Return lowest value action
        return sorted(options)[0][1]


def max_value(board):
    """
    Returns the highest value option of a min-value result
    """
    # Check for terminal state
    if terminal(board):
        return utility(board)

    # Loop through possible steps
    v = -math.inf
    for action in actions(board):
        v = max(v, min_value(result(board, action)))
    return v


def min_value(board):
    """
    Returns the smallest value option of a max-value result
    """
    # Check for terminal state
    if terminal(board):
        return utility(board)
    
    # Loop through possible steps
    v = math.inf
    for action in actions(board):
        v = min(v, max_value(result(board, action)))
    return v 

故障根源分析 #

故障出在winner函数，核心逻辑错误是未排除「全空行/列」的情况，导致函数提前返回None，无法检测到真正的获胜连线。

具体来说：
在原winner函数的循环中，只要三个位置的值相等就返回该值，包括全为空（EMPTY即None）的情况。在X玩家的异常场景中，落子[1][2]后，中间列（第1列）全为空，满足board[0][1] == board[1][1] == board[2][1]，函数会在i=1时直接返回None并终止循环，不会继续检查第三列的三个X，导致winner返回None，terminal函数判定游戏未结束，O得以继续落子。

AI未下出制胜棋的问题同样源于此：Minimax算法依赖winner和terminal函数评估状态，当AI有机会连成三子时，winner函数可能因其他全空行/列提前返回None，导致Minimax无法识别该状态为制胜状态，从而做出错误决策。

修复后的winner函数 #

def winner(board):
    """
    Returns the winner of the game, if there is one.
    """
    # Check horizontally
    for i in range(3):
        if board[i][0] is not None and board[i][0] == board[i][1] == board[i][2]:
            return board[i][0]
    
    # Check vertically
    for i in range(3):
        if board[0][i] is not None and board[0][i] == board[1][i] == board[2][i]:
            return board[0][i]

    # Check diagonally
    if board[0][0] is not None and board[0][0] == board[1][1] == board[2][2]:
        return board[0][0]

    if board[2][0] is not None and board[2][0] == board[1][1] == board[0][2]:
        return board[2][0]
        
    # Return None if no winner
    return None

修复说明 #

1. 将行和列的检查拆分为两个独立循环，避免因某一行/列的检查提前终止另一方向的检查，逻辑更清晰。
2. 所有连线检查前先判断第一个元素不为None（即不是EMPTY），排除全空行/列的干扰。
3. 移除多余的else分支，直接在最后返回None，逻辑更简洁。

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