Python Minimax算法井字棋Bot评估错误、节点异常问题求助

问题描述 #

我用Python写了基于Minimax算法的井字棋Bot，预期它能遍历所有可能局面给出最优走法，但实际存在局面评估错误、搜索节点数量异常，而且每次对局都会输。尝试调整局面评估逻辑，但问题依旧，求问题原因。

代码实现 #

mainboard = ["-", "-", "-", "-", "-", "-", "-", "-", "-"]
nodes = 0

def detectwin(b):
    signs = ["O", "X"]
    for s in signs:
        for i in range(3):
            j = 3 * i
            if ((b[0 + j]==s and b[1 + j]==s and b[2 + j]==s) or
                (b[0 + i]==s and b[1 + i]==s and b[2 + i]==s)):
                if s == "O": return 1
                if s == "X": return -1
        if ((b[0]==s and b[4]==s and b[8]==s) or
            (b[2]==s and b[4]==s and b[6]==s)):
                if s == "O": return 1
                if s == "X": return -1
    return 0

def evaluate(board):
    return detectwin(board)

def fullboard(board):
    return all(cell != "-" for cell in board)

def makemove(board, move, maximizingPlayer):
    if maximizingPlayer:
        board[move] = "O"
        return board
    else:
        board[move] = "X"
        return board

def undomove(board, move):
    board[move] = "-"
    return board

def minimax(board, depth, maximizingPlayer):

    global nodes

    if depth == 0 or fullboard(board) or detectwin(board) != 0:
        nodes += 1
        return evaluate(board)

    if maximizingPlayer:
        maxEval = -1000
        for i in range(9):
            if board[i] == "-":
                board = makemove(board, i , True)
                newEval = minimax(board, depth-1, False)
                maxEval = max(maxEval, newEval)
                board = undomove(board, i)
        return maxEval
    
    else:
        minEval = 1000
        for i in range(9):
            if board[i] == "-":
                board = makemove(board, i , False)
                newEval = minimax(board, depth-1, True)
                minEval = min(minEval, newEval)
                board = undomove(board, i)
        return minEval

def findbestmove(board, maximizingPlayer):

    global nodes
    
    if maximizingPlayer:
        bestmove = -1
        maxEval = -1000
        for i in range(9):
            if board[i] == "-":
                board = makemove(board, i , True)
                nodes = 0
                newEval = minimax(board, 9, False)
                print(f"Eval move {i}: {newEval} ({nodes} nodes)")
                if newEval > maxEval:
                    maxEval = newEval
                    bestmove = i
                board = undomove(board, i)
        return bestmove

def printboard(b):
    signs = ["No", "O", "X"]
    win = signs[detectwin(b)] + " wins"
    print(f'{b[0]} {b[1]} {b[2]}\n{b[3]} {b[4]} {b[5]}\n{b[6]} {b[7]} {b[8]}\n{win}\n')

print("Ready!")
while True:
    move = findbestmove(mainboard, True)
    mainboard = makemove(mainboard, move, True)
    printboard(mainboard)
    yourmove = int(input())
    mainboard = makemove(mainboard, yourmove, False)
    printboard(mainboard)

问题原因及修复方案 #

1. 评估函数未结合搜索深度，无法区分胜负优先级 #

当前evaluate函数仅返回固定值：1（O赢）、-1（X赢）、0（其他），但Minimax需要根据剩余可走步数调整评估值，让Bot优先选择最快获胜的路径，同时避免最快失败的局面。例如：

• O下一步就能赢，评估值应设为更高的数值（比如10 + 剩余步数）
• X下一步就要赢，评估值应设为更低的数值（比如-10 - 剩余步数）

修改后的评估逻辑示例：

def evaluate(board):
    win_result = detectwin(board)
    remaining = board.count("-")
    if win_result == 1:
        return 10 + remaining
    elif win_result == -1:
        return -10 - remaining
    else:
        return 0

2. Minimax的depth参数设置错误 #

在findbestmove中调用minimax时固定传入depth=9，但此时棋盘已有一个测试棋子，剩余最多可走步数为8，固定depth会导致搜索提前终止（depth=0时棋盘未结束）或过度搜索。正确做法是移除固定depth限制，仅在棋盘满或有胜负时终止递归。

修改后的minimax函数：

def minimax(board, maximizingPlayer):
    global nodes
    win_result = detectwin(board)
    if fullboard(board) or win_result != 0:
        nodes += 1
        return evaluate(board)

    if maximizingPlayer:
        maxEval = -1000
        for i in range(9):
            if board[i] == "-":
                board = makemove(board, i, True)
                newEval = minimax(board, False)
                maxEval = max(maxEval, newEval)
                board = undomove(board, i)
        return maxEval
    else:
        minEval = 1000
        for i in range(9):
            if board[i] == "-":
                board = makemove(board, i, False)
                newEval = minimax(board, True)
                minEval = min(minEval, newEval)
                board = undomove(board, i)
        return minEval

同时findbestmove中调用minimax时需去掉depth参数：newEval = minimax(board, False)

3. 胜负检测函数逻辑冗余 #

当前detectwin函数嵌套循环结构冗余，可优化为更清晰的分支判断，避免重复逻辑：

def detectwin(b):
    # 检查行
    for i in range(0,9,3):
        if b[i] == b[i+1] == b[i+2] != "-":
            return 1 if b[i] == "O" else -1
    # 检查列
    for i in range(3):
        if b[i] == b[i+3] == b[i+6] != "-":
            return 1 if b[i] == "O" else -1
    # 检查对角线
    if b[0] == b[4] == b[8] != "-":
        return 1 if b[0] == "O" else -1
    if b[2] == b[4] == b[6] != "-":
        return 1 if b[2] == "O" else -1
    return 0

4. 节点计数的全局变量问题 #

全局变量nodes在递归中被修改，虽单线程下不会出错，但可改为用函数参数传递计数，或用类封装状态，避免全局变量带来的潜在问题。

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