Minimax算法无法突破深度1搜索的问题排查求助

问题概述 #

实现国际象棋简易Minimax算法时，算法看似可运行，但存在逻辑错误：设置counter变量统计搜索树节点数量，无论将搜索深度设为3或5，counter始终返回15至20左右，怀疑算法无法搜索至深度1以上。

核心错误点分析 #

• 博弈角色递归传递错误：Minimax要求MAX（AI）和MIN（人类）玩家交替博弈，但当前代码中MAX层递归仍传True、MIN层仍传False，完全违背交替搜索逻辑。
• 节点计数未累加递归结果：递归调用minimax后，未将返回的counter更新到当前层，导致仅统计当前层节点数，深层节点数丢失。
• 递归后错误修改棋盘状态：将递归返回的temp_move再次push到棋盘，导致评估的不是对应深度的节点状态，而是额外多走一步的错误状态。
• 最优选择逻辑颠倒：MAX层应选评估分数最大的走法，代码却用min(score)；MIN层应选分数最小的走法，代码却用max(score)。

修正后的完整代码 #

# 导入所需库
import chess
import chess.polyglot
import math
from copy import deepcopy
import random

# 初始化棋盘
B = chess.Board()

# 定义搜索深度
DEPTH = 3

# 棋子价值映射
PIECE_VALUE = {
 'p':-1,
 'r':-5,
 'n':-3,
 'b':-3,
 'k':0,
 'q':-9,
 'P':1,
 'R':5,
 'N':3,
 'B':3,
 'K':0,
 'Q':9
}

# 最优走法选择入口
def random_ai(BOARD, PIECE_VALUE):
    print("选择最优走法")
    move = select(BOARD, PIECE_VALUE)
    return move

# 局面评估函数
def evals(BOARD, PIECE_VALUE):
    score = 0
    # 遍历棋盘累加所有棋子价值
    for i in range(64):
        piece = BOARD.piece_at(i)
        if piece is not None:
            score += PIECE_VALUE[piece.symbol()]
    return score

# 走法选择函数（调用Minimax）
def select(BOARD, PIECE_VALUE):
    counter = 0
    result = minimax(BOARD, DEPTH, True, counter)
    if result is not None:
        counter = result[2]
        print(f"节点计数: {counter}")
        return result[0]

# 修正后的Minimax算法
def minimax(BOARD, DEPTH, MAXIMIZE, counter):
    moves = list(BOARD.legal_moves)
    # 统计当前层节点数
    counter += len(moves)
    
    # 终止条件：到达搜索深度或无合法走法
    if DEPTH == 0 or not moves:
        return None, evals(BOARD, PIECE_VALUE), counter
    
    score_list = []
    if MAXIMIZE:
        # MAX玩家：寻找最大评估值
        for move in moves:
            board_copy = deepcopy(BOARD)
            board_copy.push(move)
            # 递归切换到MIN玩家
            _, child_score, counter = minimax(board_copy, DEPTH-1, False, counter)
            score_list.append(child_score)
        # 选择分数最大的走法
        best_idx = score_list.index(max(score_list))
        return moves[best_idx], max(score_list), counter
    else:
        # MIN玩家：寻找最小评估值
        for move in moves:
            board_copy = deepcopy(BOARD)
            board_copy.push(move)
            # 递归切换到MAX玩家
            _, child_score, counter = minimax(board_copy, DEPTH-1, True, counter)
            score_list.append(child_score)
        # 选择分数最小的走法
        best_idx = score_list.index(min(score_list))
        return moves[best_idx], min(score_list), counter

修正说明 #

1. 交替博弈逻辑：MAX层递归传递False切换到MIN层，MIN层传递True切换到MAX层，符合Minimax交替搜索规则。
2. 节点计数累加：递归调用后接收返回的counter，确保所有层级的节点数都被统计。
3. 移除错误棋盘操作：不再将递归返回的move push到棋盘，直接使用递归返回的评估分数。
4. 修正最优选择逻辑：MAX层选最大分数，MIN层选最小分数，匹配角色目标。
5. 优化终止条件：明确DEPTH == 0时直接评估局面，符合深度搜索的终止规则。

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