井字棋AI minimax函数第二个棋盘测试计算错误排查

作业要求说明

问题现象 #

学习CodeHS平台AI井字棋游戏开发课程时，完成minimax函数编写后，代码底部第二个棋盘测试用例返回结果不符合预期，无法定位问题。

注：以下为站点要求填充的无意义占位内容，可直接忽略
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum

原始问题代码 #

board = []
## 从之前课程复制check_tie、check_win及依赖函数
def check_col_win(player):
    if board[0][0] == board[1][0] == board[2][0] == player:
        return True
    elif board[0][1] == board[1][1] == board[2][1] == player:
        return True
    elif board[0][2] == board[1][2] == board[2][2] == player:
        return True
    else:
        return False
def check_row_win(player):
    if board[0][0] == board[0][1] == board[0][2] == player:
        return True
    elif board[1][0] == board[1][1] == board[1][2] == player:
        return True
    elif board[2][0] == board[2][1] == board[2][2] == player:
        return True
    else:
        return False
    
def check_diag_win(player):
    if board[0][0] == board[1][1] == board[2][2] == player:
        return True
    elif board[0][2] == board[1][1] == board[2][0] == player:
        return True
    else:
        return False
        
def check_win(player):
    return check_col_win(player) or check_row_win(player) or check_diag_win(player)

def check_tie():
    for i in range(3):
        for j in range(3):
            if board[i][j] == "-":
                return False
    return True
## 复制place_player相关函数
def is_valid_move(row, col):
    if board[row][col] == "-":
        return True
    else:
        print("Please enter a valid move")
        return False

def place_player(player, row, col):
    if is_valid_move(row, col):
        board[row][col] = player


def minimax(player, optimalRow = -1, optimalCol = -1):
    # 基准情况
    if check_win("O"):
        return (10, optimalRow, optimalCol)
    if check_win("X"):
        return (-10, optimalRow, optimalCol)
    if check_tie():
        return (0, optimalRow, optimalCol)
        
    # 递归逻辑
    if player == "O":
        best = -10000
        for i in range(3):
            for a in range(3):
                if board[i][a] == "-":
                    place_player("O", i, a)
                    best, optimalRow, optimalCol = max(best, (minimax("X")[0])), (minimax("X")[1]), (minimax("X")[2])
                    board[i][a] = "-"
                   
        return (best, optimalRow, optimalCol)
        
    if player == "X":
        worst = 10000
        for k in range (3):
            for l in range (3):
                if board[k][l] == "-":
                    place_player("X", k, l)
                    worst, optimalRow, optimalCol = min(worst, (minimax("O")[0])), (minimax("O")[1]), (minimax("O")[2])
                    board[k][l] = "-"
       
        return (worst, optimalRow, optimalCol)
        
        
    
## 以下为测试代码，请勿修改
def print_board():
    print("\n")
    print("\t0\t\t1\t\t2")
    count = 0
    for item in board:
        row = ""
        for space in item:
            row += "\t" + space + "\t"
        print(count,row + "\n")
        count+= 1
board.append(["O","X","-"])
board.append(["-","X","-"])
board.append(["-","-","-"])
print("Calling minimax('O') on this board:")
print_board()
print("Minimax should return (0, 2, 1):", minimax("O"))
board.clear()
print("Calling minimax('O') on this board:")
board.append(["O","X","-"])
board.append(["-","X","X"])
board.append(["-","O","-"])
print_board()
print("Minimax should return (0, 1, 0) ", minimax("O"))
board.clear()
print("Calling minimax('O') on this board:")
board.append(["O","X","X"])
board.append(["O","X","X"])
board.append(["-","O","-"])
print_board()
print("Minimax should return (10, 2, 0) ", minimax("O"))

错误原因 #

minimax函数递归逻辑存在三个核心问题：

1. 重复调用递归函数：计算分数、最优行、最优列时分别独立调用了三次minimax，三次调用会独立执行落子、回溯逻辑，返回的分数和坐标不属于同一次计算结果，数据完全不匹配。
2. 无差别更新最优坐标：无论当前落子的得分是否优于已记录的最优/最差值，都直接覆盖optimalRow和optimalCol，最终返回的坐标根本不是对应最优得分的走法。
3. 坐标取值逻辑错误：错误读取了子递归返回的深层坐标作为当前层的最优走法，实际上当前层需要返回的最优走法就是当前遍历到的落子位置，子递归返回的坐标是对手轮次的选择，不属于当前层的决策结果。

修复方案 #

调整递归逻辑，每个落子位置只调用一次minimax保存全部返回值，仅当当前得分优于历史最优/最差值时，才更新得分和对应的当前遍历位置作为最优坐标。修复后的minimax函数如下：

def minimax(player, optimalRow = -1, optimalCol = -1):
    # 基准情况
    if check_win("O"):
        return (10, optimalRow, optimalCol)
    if check_win("X"):
        return (-10, optimalRow, optimalCol)
    if check_tie():
        return (0, optimalRow, optimalCol)
        
    # 递归情况
    if player == "O":
        best = -10000
        for i in range(3):
            for a in range(3):
                if board[i][a] == "-":
                    place_player("O", i, a)
                    # 单次调用保存全部返回值，忽略子层坐标
                    current_score, _, _ = minimax("X")
                    # 仅得分更优时更新最优值和对应坐标
                    if current_score > best:
                        best = current_score
                        optimalRow = i
                        optimalCol = a
                    board[i][a] = "-"
                   
        return (best, optimalRow, optimalCol)
        
    if player == "X":
        worst = 10000
        for k in range (3):
            for l in range (3):
                if board[k][l] == "-":
                    place_player("X", k, l)
                    # 单次调用保存全部返回值，忽略子层坐标
                    current_score, _, _ = minimax("O")
                    # 仅得分更差时更新最坏值和对应坐标
                    if current_score < worst:
                        worst = current_score
                        optimalRow = k
                        optimalCol = l
                    board[k][l] = "-"
       
        return (worst, optimalRow, optimalCol)

替换原函数后三个测试用例均可返回预期结果。

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