Python国际象棋引擎Quiescence Search搜索耗时过长问题求助

我用Python的chess库开发国际象棋引擎，参考国际象棋编程维基的伪代码实现了静态搜索，但在测试局面运行时搜索耗时极长（10-20分钟）。打印搜索过程中的着法时，发现会持续输出大量着法。

测试局面FEN字符串：
r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w - - 0 1

我的实现代码 #

def search_all_captures(self, alpha, beta):
    evaluation = self.evaluate()
    if evaluation >= beta:
        return beta
    alpha = max(alpha, evaluation)

    moves = [capture for capture in self.board.generate_legal_captures()]

    move_dict = {}

    # Ordering moves
    for move in moves:
        guess = 0
        move_piece = self.board.piece_at(move.from_square)
        captured_piece = self.board.piece_at(move.to_square)

        if captured_piece:
            guess += 10 * vals_dict[captured_piece.piece_type] - vals_dict[move_piece.piece_type]

        if move.promotion:
            guess += vals_dict[move.promotion]

        if self.board.attackers(1 - self.color, move.to_square):
            for attacker in self.board.attackers(1 - self.color, move.to_square):
                piece = self.board.piece_at(attacker).piece_type
                guess -= vals_dict[piece]

        move_dict[move] = guess

    moves.sort(reverse=True, key=lambda move: move_dict[move])

    for move in moves:
        print(move)
        self.board.push(move)
        evaluation = -self.search_all_captures(-beta, -alpha)
        self.board.pop()

        if evaluation >= beta:
            return beta

        alpha = max(alpha, evaluation)

    return alpha

问题分析与解决办法 #

核心问题：无限递归循环

当前代码没有设置递归终止边界，当局面出现循环吃子（比如双方可以反复互相吃子）时，静态搜索会无限递归下去，导致搜索永不停止，耗时剧增。

具体修复方案

1. 添加深度限制
   给静态搜索函数增加深度参数，设定最大递归层数（比如4-6层），当深度耗尽时直接返回当前局面评估值，避免无限递归：

def search_all_captures(self, alpha, beta, depth=5):
    evaluation = self.evaluate()
    # 深度耗尽时直接返回
    if evaluation >= beta or depth == 0:
        return beta
    alpha = max(alpha, evaluation)

    moves = [capture for capture in self.board.generate_legal_captures()]
    # 其余代码不变

    for move in moves:
        # 递归时深度减1
        evaluation = -self.search_all_captures(-beta, -alpha, depth-1)
        # 其余代码不变

2. 加入重复局面检测
   使用Zobrist哈希记录当前搜索路径中的局面，若遇到重复局面则立即返回，避免循环搜索：

def search_all_captures(self, alpha, beta, depth=5, seen_positions=None):
    if seen_positions is None:
        seen_positions = set()
    current_hash = self.board.zobrist_hash()
    # 遇到重复局面直接返回当前评估值
    if current_hash in seen_positions:
        return self.evaluate()
    seen_positions.add(current_hash)

    evaluation = self.evaluate()
    if evaluation >= beta or depth == 0:
        seen_positions.remove(current_hash)
        return beta
    alpha = max(alpha, evaluation)

    moves = [capture for capture in self.board.generate_legal_captures()]
    # 其余代码不变

    for move in moves:
        evaluation = -self.search_all_captures(-beta, -alpha, depth-1, seen_positions)
        # 其余代码不变
    
    seen_positions.remove(current_hash)
    return alpha

3. 优化剪枝效率
   当前的着法排序已经用到了MVV-LVA（最大价值被吃子减去吃子价值）逻辑，可以保留。若想进一步提升剪枝效率，可简化被攻击位置的权重计算逻辑，减少不必要的遍历开销，但这不是导致耗时过长的核心原因。

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