可调整奇数尺寸棋盘的井字棋minimax算法异常问题排查

我正在开发一款支持可调整棋盘大小的井字棋游戏，AI对手采用minimax算法实现，仅支持奇数尺寸棋盘以保证对角线获胜规则始终生效。当前程序运行无报错，但minimax算法逻辑存在缺陷，玩家可以轻松击败AI，我反复核查代码未定位问题所在，以下是我的代码：

Main.py #

import TicTacToe
import Minimax

if (__name__ == "__main__"):
    t = TicTacToe.ttt(3)
    m = Minimax.Minimax(3, t)
    
    while (t.winner == None):
        if (t.turn == 1):
            playerInputI = int(input("Input row: "))
            playerInputJ = int(input("Input column: "))
            bestIndex = (playerInputI, playerInputJ)
        else:
            winner, bestIndex = m.minimax(t.grid, (-1, -1), 15, -1)
            t.winner = None
            t.findWinner(bestIndex, t.grid)
            

        t.updateGameGrid(bestIndex)
        print(t.grid)

    print(t.grid)

Minimax.py #

class Minimax:
    def __init__(self, gs, t):
        self.gridSize = gs
        self.ttt = t

    def minimax(self, state, currIndex, depth, turn):
        if (currIndex[0] != -1 and currIndex[1] != -1):
            winner = self.ttt.findWinner(currIndex, state)

            if (winner == -1):
                return winner - depth, currIndex
            elif (winner == -1):
                return winner + depth, currIndex
            elif (winner == 0):
                return 0, currIndex

            if (depth==0 and winner==None):
                return 0, currIndex
        
        evalLimit = -turn * 1000
        bestIndex = None
        for i in range(self.gridSize):
            for j in range(self.gridSize):
                if (state[i][j] == 0):
                    state[i][j] = turn

                    eval, newIndex = self.minimax(state, (i, j), depth-1, -turn)
                    state[i][j] = 0
                    if (turn > 0 and eval > evalLimit):
                        bestIndex = newIndex
                        evalLimit = eval
                    elif (turn < 0 and eval < evalLimit):
                        bestIndex = newIndex
                        evalLimit = eval
        
        return evalLimit, bestIndex

Tictactoe.py #

from random import randint

class ttt:
    def __init__(self, size):
        self.gridSize = size
        self.grid = self.createGrid()

        # If using minimax algorithm, user is maximizer(1) and computer is minimizer(-1)
        # If single player, then user is 1, computer is -1
        # If multiplayer, user1 is 1, user2 = -1
        self.turn = 1
        self.winner = None

    def createGrid(self):
        grid = []
        for i in range(self.gridSize):
            grid.append([])
            for j in range(self.gridSize):
                grid[i].append(0)


        # grid = [[-1, 1, 0], [0, -1, 0], [0, 0, 0]]

        return grid

    def updateGameGrid(self, index):
        if (self.grid[index[0]][index[1]] != 0):
            return

        self.grid[index[0]][index[1]] = self.turn
        winner = self.findWinner(index, self.grid)  

        self.turn = -self.turn
        
    def randomIndex(self):
        x = randint(0, self.gridSize-1)
        y = randint(0, self.gridSize-1)
        while (self.grid[x][y] != 0):
            x = randint(0, self.gridSize-1)
            y = randint(0, self.gridSize-1)
        return (x, y)

    def findWinner(self, index, grid):
        # Row
        found = True
        for j in range(self.gridSize-1):
            if (grid[index[0]][j] != grid[index[0]][j+1] or grid[index[0]][j] == 0):
                found = False
                break
        if (found):
            self.winner = self.turn
            return self.turn
        
        # Column
        found = True
        for i in range(self.gridSize-1):
            if (grid[i][index[1]] != grid[i+1][index[1]] or grid[i][index[1]] == 0):
                found = False
                break
        if (found):
            self.winner = self.turn
            return self.turn
        
        # Top Left to Bottom Right Diagonal
        if (index[0] == index[1]):
            found = True
            for i in range(self.gridSize-1):
                if (grid[i][i] != grid[i+1][i+1] or grid[i][i] == 0):
                    found = False
                    break
            if (found):
                self.winner = self.turn
                return self.turn

        # Top Right to Bottom Left Diagonal
        if (index[0] + index[1] == self.gridSize-1):
            found = True
            for i in range(self.gridSize-1):
                if (grid[self.gridSize-i-1][i] != grid[self.gridSize-i-2][i+1] or grid[self.gridSize-i-1][i] == 0):
                    found = False
                    break
            if (found):
                self.winner = self.turn
                return self.turn
            
        
        tie = True
        for i in range(self.gridSize):
            for j in range(self.gridSize):
                if (grid[i][j] == 0):
                    tie = False
        
        if (tie):
            self.winner = 0
            return 0

        return None

棋盘以二维数组表示，元素取值规则如下：-1对应O、1对应X、0对应空位，玩家方标识为1，AI方标识为-1，回合标识也采用1和-1，分别对应X和O的落子回合。

代码存在3处核心错误直接导致Minimax算法失效：

1. Minimax终止条件分支重复
   Minimax.py的终止条件判断里两个分支都写了winner == -1，漏掉了玩家获胜（winner=1）的判断逻辑，正确的分支应该是：

if (winner == -1): # AI获胜，作为极小化方深度越小分数绝对值越大
    return winner - depth, currIndex
elif (winner == 1): # 玩家获胜，作为极大化方深度越小分数越高
    return winner + depth, currIndex
elif (winner == 0):
    return 0, currIndex

2. findWinner误用全局回合属性
   Minimax递归是模拟落子的过程，但findWinner返回值用的是ttt实例全局的self.turn，而非当前模拟落子的玩家标识，导致胜负判断完全错误。需要给findWinner增加当前落子方参数：

• 方法定义改为def findWinner(self, index, grid, turn):
• 所有self.winner = self.turn改为self.winner = turn，return self.turn改为return turn
• updateGameGrid里调用改为winner = self.findWinner(index, self.grid, self.turn)
• Minimax里调用改为winner = self.ttt.findWinner(currIndex, state, turn)

3. 主逻辑AI落子后流程顺序错误
   Main.py里AI拿到最优落子后提前调用了findWinner，后续updateGameGrid会再次修改turn和胜负状态，直接覆盖了AI的胜负判断。删除else分支里的t.winner = None和t.findWinner(bestIndex, t.grid)两行即可，updateGameGrid会自动处理胜负和回合切换。

修改完成后AI即可正常进行胜负预判，不会再出现被轻易击败的问题。

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