Python实现井字棋minimax算法无法返回最优落子问题排查

使用Python编写井字棋Minimax算法时，程序在部分棋盘状态下可正常计算最优落子位置，但其余状态下只会返回遍历过程中遇到的第一个空格，无法输出最优解。
完整复现代码如下：

space = ' '
def rate_state(state):
    '''
    返回值规则：
    X获胜返回10
    O获胜返回-10
    无胜负返回0
    '''
    ter = terminate(state)
    if ter != False:
        if state[ter[0]] == 'X':
            return 10
        elif state[ter[0]] == 'O':
            return -10
    return 0

def terminate(state):
    '''
    返回值规则：
    存在玩家获胜时，返回连成一线的三个位置索引
    棋盘填满无胜负返回False
    '''
    win_pos = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]]
    for ws in win_pos:
        if state[ws[0]] != space and state[ws[0]] == state[ws[1]] and state[ws[0]] == state[ws[2]]:
            return [ws[0],ws[1], ws[2]]
    return False


def min_max(bord):
    def deep(state,isMax):
        state_scor = rate_state(state)
        if state_scor == 10:
            return state_scor
        elif state_scor == -10:
            return state_scor
        
        if terminate(state) == False:
            return 0
        
        if isMax:
            score = -1000
            for itr in range(len(state)):
                if state[itr] == space:

                    state[itr] = 'X'
                    score = max(score, deep(state, False))
                    state[itr] = space
            return score
        
        else:
            score = 1000
            for itr in range(len(state)):
                if state[itr] == space:
                    state[itr] = 'O'
                    score = min(score, deep(state, True))
                    state[itr] = space
            return score
    
    best_score = -1000
    best_move = 0

    for i in range(len(bord)):
        if bord[i] == space:
            bord[i] = 'X'

            move_sc = deep(bord, False)

            bord[i] = space

            if move_sc > best_score:
                best_score = move_sc
                best_move = i
    return best_move

# Minimax计算正常的测试棋盘
workin_board = [
            'O', ' ', 'X',
            ' ', ' ', ' ',
            'X', ' ', 'O',
]
# Minimax计算异常的测试棋盘，预期X的最优落子为索引4的中心位置
not_working_board = [
            'O', 'X', ' ',
            ' ', ' ', ' ',
            'X', ' ', 'O',
]

print('X的下一步落子位置索引为:',min_max(not_working_board))

测试现象：

• workin_board状态下minimax函数运行正常
• not_working_board状态下预期X的最优落子为索引4的中心位置，但函数返回错误结果。

核心bug在terminate函数的状态判断逻辑，直接导致递归提前终止：
现有terminate函数只要没检测到获胜连线，无论棋盘是否还有剩余空格，都会直接返回False。
回到递归函数deep的逻辑：只要检测到terminate(state) == False就直接返回0分，不会继续递归遍历后续落子的可能结果。
这就意味着：只要某一步落子不能直接让X获胜，这个落子的评分就会被直接打为0。所有非直接获胜的落子评分完全相同，函数自然只会返回遍历到的第一个空格。
部分棋盘能正常计算的原因也很简单：这类棋盘下存在落子后直接获胜的选项，这步落子的评分会被正确打为10，比其他0分的落子高，所以能返回正确结果。

需要调整terminate函数的状态区分逻辑，明确区分三种游戏状态：

• 有玩家获胜：返回获胜连线位置
• 游戏未结束（无获胜方且存在空格）：返回专属标识（比如None）
• 平局（无获胜方且棋盘填满）：返回False
  对应调整后核心代码如下：

def terminate(state):
    '''
    返回值规则调整：
    - 有玩家获胜：返回连成一线的三个位置索引
    - 游戏未结束（无赢家且有剩余空格）：返回None
    - 平局（无赢家且棋盘填满）：返回False
    '''
    win_pos = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]]
    for ws in win_pos:
        if state[ws[0]] != space and state[ws[0]] == state[ws[1]] and state[ws[0]] == state[ws[2]]:
            return [ws[0],ws[1], ws[2]]
    # 无获胜方时，先检查是否还有空格
    if space in state:
        return None
    return False

deep函数的逻辑不需要大改，因为只有平局状态下terminate才会返回False，原有判断逻辑可以正常工作：遇到平局返回0分，遇到未结束状态就继续递归遍历后续落子。
修复后测试not_working_board，函数会正确返回索引4的中心位置——该位置落子后X形成必胜局面，Minimax递归计算后会给这步落子打10分，其余落子最高只能到0分（平局），自然会选出最优解。

额外提个小问题：代码里变量名bord是拼写错误，正确拼写是board，不影响运行但会降低代码可读性，建议顺手修正。

内容的提问来源于stack exchange，提问作者Abdul Wahab Rana