为Minimax算法实现着法排序引发无限循环问题求助

我正在开发一款简易国际象棋AI，原本Minimax算法在使用合法着法列表时运行正常。但添加基于吃子价值排序着法的函数后，Minimax调用该函数返回的列表时陷入无限循环。我已通过打印语句调试着法排序，但仍未明确问题所在，且已确保Minimax会检查空数组，但问题未解决。

原着法排序函数 #

#move ordering algorithm
def order_moves(BOARD, moves):
  
  ordered_moves = []

  for move in moves:
    #go through the legal moves and check if there is a piece captured
    if BOARD.is_capture(move):
      moving_piece = BOARD.piece_at(move.from_square)
      captured_piece = BOARD.piece_at(move.to_square)
      
      #get capture value by subtracting moving from captured piece
      #it is important to get absolute values for both since black pawn =-100, while white =100
      #and append the move and value to a list
      if captured_piece is not None:
        capture_value = (abs(PIECE_VALUE[captured_piece.symbol()])-abs(PIECE_VALUE[moving_piece.symbol()]))
        ordered_moves.append((move, capture_value))
        
  #sort through the list for moves with best capture value
  ordered_moves.sort(key=lambda x: x[1], reverse=True)
  sorted_moves = [move[0] for move in ordered_moves]
  
  return sorted_moves

原Minimax函数 #

# minimax algorithm
def minimax(BOARD, DEPTH, MAXIMIZE, counter, alpha=-math.inf, beta=math.inf):
  
    # create a list of legal moves and counter
    moves = list(BOARD.legal_moves)
    counter = counter + len(moves)
    opening_move = reader.get(BOARD)
  
    # initialize best move and scores
    max_score = -math.inf
    min_score = math.inf
    best_move = None
  
    # make sure depth is >1 and there are legal moves
    if DEPTH == 0 or not moves:
        return None, counter

    # prioritize playing book moves
    opening_move = reader.get(BOARD)
    if opening_move is not None:
        best_move = opening_move.move
        return best_move, counter

    # check for checkmate before proceeding with moves
    outcome = BOARD.outcome()
    if outcome is not None and outcome.result() in ["1-0", "0-1"]:
        return None, counter + 1

    #order the moves
    ordered_moves = order_moves(BOARD, moves)
    
    # if maximizing player, select the best move
    #go through all moves
    if ordered_moves is None:
      return None, counter
    else:
      for i in ordered_moves:
        b = deepcopy(BOARD)
        b.push(i)
        # recursively call minimax with the new board
        temp_move, temp_counter = minimax(b, DEPTH - 1, not MAXIMIZE, counter, alpha, beta)

        # push temp move and get the counter
        if temp_move is not None:
            b.push(temp_move)
            counter = temp_counter
        # evaluate the board and get node score
        score = evals(b, PIECE_VALUE, MAXIMIZE)
        # if maximizer, set the best move to the best score
        if MAXIMIZE:
            alpha = max(alpha, score)
            if score > alpha:
                alpha = score
            # if new score is better than stored max score, assign i as the best move
            if score > max_score:
                max_score = score
                best_move = i
        # if minimizer, set the best move to the worst score
        else:
            beta = min(beta, score)
            if score < beta:
                beta = score
            # if new score is worse than stored min score, assign i as the best move
            if score < min_score:
                min_score = score
                best_move = i
        if beta <= alpha:
            break
    return best_move, counter

问题原因 #

1. 着法排序函数丢失非吃子着法：原函数仅收集并返回吃子着法，完全丢弃了非吃子的合法着法。当局面无吃子着法时，ordered_moves为空列表，Minimax的循环无法执行，直接返回None，导致后续递归逻辑异常。
2. Minimax递归逻辑错误：递归调用后错误地将子节点返回的最佳着法再次push到局面中，导致评估的并非当前着法后的局面，完全偏离了Minimax的核心逻辑，同时可能引发错误的得分计算。
3. 返回值设计缺陷：原Minimax函数未返回子局面的评估得分，而是自行修改局面后重新评估，导致得分计算错误，无法正确选择最佳着法。

修复方案 #

1. 修复着法排序函数 #

确保返回所有合法着法，先按吃子价值排序吃子着法，再追加非吃子着法：

# 着法排序算法
def order_moves(BOARD, moves):
    capture_moves = []
    non_capture_moves = []

    for move in moves:
        if BOARD.is_capture(move):
            moving_piece = BOARD.piece_at(move.from_square)
            captured_piece = BOARD.piece_at(move.to_square)
            
            if captured_piece is not None:
                # 计算吃子价值：被吃子价值 - 移动子价值（取绝对值消除颜色影响）
                capture_value = abs(PIECE_VALUE[captured_piece.symbol()]) - abs(PIECE_VALUE[moving_piece.symbol()])
                capture_moves.append((move, capture_value))
        else:
            non_capture_moves.append(move)
    
    # 按吃子价值降序排序
    capture_moves.sort(key=lambda x: x[1], reverse=True)
    # 合并排序后的吃子着法与非吃子着法
    sorted_moves = [move[0] for move in capture_moves] + non_capture_moves
    
    return sorted_moves

2. 修复Minimax函数逻辑 #

调整返回值为（最佳着法，评估得分，计数器），移除错误的局面修改逻辑，严格遵循Minimax核心逻辑：

import math
from copy import deepcopy

# Minimax算法（带Alpha-Beta剪枝）
def minimax(BOARD, DEPTH, MAXIMIZE, counter, alpha=-math.inf, beta=math.inf):
    moves = list(BOARD.legal_moves)
    counter += len(moves)
    opening_move = reader.get(BOARD)

    # 终止条件：深度耗尽或无合法着法
    if DEPTH == 0 or not moves:
        return None, evals(BOARD, PIECE_VALUE, MAXIMIZE), counter

    # 优先使用开局库着法
    if opening_move is not None:
        return opening_move.move, evals(BOARD, PIECE_VALUE, MAXIMIZE), counter

    # 检查将死局面
    outcome = BOARD.outcome()
    if outcome is not None:
        # 将死得分：白方获胜得正无穷，黑方获胜得负无穷
        score = math.inf if outcome.result() == "1-0" else -math.inf
        return None, score, counter + 1

    # 获取排序后的着法列表
    ordered_moves = order_moves(BOARD, moves)

    best_move = None
    if MAXIMIZE:
        max_score = -math.inf
        for move in ordered_moves:
            b = deepcopy(BOARD)
            b.push(move)
            # 递归获取子局面的最佳得分
            _, child_score, temp_counter = minimax(b, DEPTH - 1, False, counter, alpha, beta)
            counter = temp_counter

            # 更新最大得分与最佳着法
            if child_score > max_score:
                max_score = child_score
                best_move = move

            # Alpha-Beta剪枝
            alpha = max(alpha, child_score)
            if beta <= alpha:
                break
        return best_move, max_score, counter
    else:
        min_score = math.inf
        for move in ordered_moves:
            b = deepcopy(BOARD)
            b.push(move)
            # 递归获取子局面的最佳得分
            _, child_score, temp_counter = minimax(b, DEPTH - 1, True, counter, alpha, beta)
            counter = temp_counter

            # 更新最小得分与最佳着法
            if child_score < min_score:
                min_score = child_score
                best_move = move

            # Alpha-Beta剪枝
            beta = min(beta, child_score)
            if beta <= alpha:
                break
        return best_move, min_score, counter

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