国际象棋残局引擎最优走法输出异常，寻求技术修复支持

我正在开发一款国际象棋残局引擎，要求当棋盘棋子数D<5时，双方采取最优策略：

• 能将杀的一方尽快完成将杀
• 必被将杀的一方尽可能拖延回合
• 正确处理和棋场景

现有代码能计算初始FEN到衍生FEN的最小ply数，但无法提取正确的最优走法，例如在测试局面中会输出c1c8而非正确的c1c6。愿支付小额报酬寻求修复，可通过LinkedIn联系Jan Pax。

import chess
from collections import deque, defaultdict

def simplify_fen(fen):
    parts = fen.split(' ')
    return ' '.join(parts[:4])  # Normalize FEN string

def generate_moves_and_distances(board):
    initial_fen = simplify_fen(board.fen())
    queue = deque([(initial_fen, 0)])
    distances = defaultdict(lambda: defaultdict(lambda: float('inf')))
    visited = set()

    while queue:
        current_fen, current_depth = queue.popleft()
        
        if current_fen in visited:
            continue
        visited.add(current_fen)
        distances[initial_fen][current_fen] = current_depth

        current_board = chess.Board(current_fen)
        for move in current_board.legal_moves:
            current_board.push(move)
            next_fen = simplify_fen(current_board.fen())
            if next_fen not in visited or distances[initial_fen][next_fen] > current_depth + 1:
                distances[initial_fen][next_fen] = current_depth + 1
                queue.append((next_fen, current_depth + 1))
            current_board.pop()

    return distances

def minimax(board, depth, maximizing_player):
    if depth == 0 or board.is_game_over():
        evaluation = evaluate_board(board)
        if evaluation is None:
            return 0  # Neutrální hodnota pro nedeterminované pozice
        return evaluation

    if maximizing_player:
        max_eval = float('-inf')
        for move in board.legal_moves:
            board.push(move)
            eval = minimax(board, depth - 1, not maximizing_player)
            board.pop()
            if eval is not None:
                max_eval = max(max_eval, eval)
            else:
                max_eval = max(max_eval, 0)  # Neutrální hodnota pokud eval je None
        return max_eval
    else:
        min_eval = float('inf')
        for move in board.legal_moves:
            board.push(move)
            eval = minimax(board, depth - 1, not maximizing_player)
            board.pop()
            if eval is not None:
                min_eval = min(min_eval, eval)
            else:
                min_eval = min(min_eval, 0)  # Neutrální hodnota pokud eval je None
        return min_eval

def find_best_move(board, depth):
    best_move = None
    best_value = float('-inf')

    for move in board.legal_moves:
        board.push(move)
        value = minimax(board, depth - 1, False)
        board.pop()
        if value > best_value:
            best_value = value
            best_move = move

    return best_move

def evaluate_board(board):
    if board.is_checkmate():
        if board.turn:  # Black's turn, white gave checkmate
            return float('-inf')
        else:
            return float('inf')
    if board.is_stalemate() or board.is_insufficient_material():
        return 0
    return None  # No evaluation, return a neutral score

# Main usage
initial_fen = "5k2/8/3K4/6Q1/8/8/8/8 w - - 0 1"
initial_fen = "8/8/4k3/8/2K5/5Q2/8/8 w - - 0 1"
initial_fen = "8/5k2/8/8/8/8/8/1KQ5 w - - 0 1"

initial_fen = simplify_fen(initial_fen)
board = chess.Board(initial_fen)
AB = generate_moves_and_distances(board)

def print_distances_less_than_two(AB, initial_fen):
    for fen2 in AB[initial_fen]:
        if AB[initial_fen][fen2] < 2:
            print(f"From {initial_fen} to {fen2}: {AB[initial_fen][fen2]} moves")

print_distances_less_than_two(AB, initial_fen)

# Finding best move using minimax
best_move = find_best_move(board, 8)
print("Best move for white:", best_move)

fen3 = "8/5k2/8/8/8/8/8/1KQ5 w - -"
fen4 = "8/8/5k2/8/8/4Q3/8/1K6 w - -"

print(f"Od {fen3} do {fen4}: {AB[fen3][fen4]} moves")

问题根源分析 #

当前代码的核心缺陷在于无法区分"不同步数的将杀/拖延"：

1. 评估函数无步数权重：仅返回inf/-inf/0，所有能赢的走法被视为等价，程序随机选择而非最快的将杀路径
2. 败方无拖延逻辑：minimax仅简单取最小估值，未优先选择能延长游戏的走法
3. 未关联BFS预计算的步数：已有的generate_moves_and_distances结果未被用于指导最优走法选择

修复方案 #

1. 调整评估函数，加入将杀距离权重 #

结合预计算的步数，让估值体现"最快将杀/最长拖延"的优先级：

def evaluate_board_with_distance(board, distances, initial_fen):
    current_fen = simplify_fen(board.fen())
    if board.is_checkmate():
        # 胜方估值=极大值-剩余步数（鼓励更快将杀）
        # 败方估值=-极大值+剩余步数（鼓励拖延）
        if not board.turn:
            return float('inf') - distances[initial_fen][current_fen]
        else:
            return -float('inf') + distances[initial_fen][current_fen]
    if board.is_stalemate() or board.is_insufficient_material():
        return 0
    # 非终局局面，用距离最近将杀的步数辅助估值
    return 0

2. 修改minimax逻辑，支持双条件排序 #

让胜方优先选估值高+步数少的走法，败方优先选估值低+步数多的走法：

def minimax_with_distance(board, depth, maximizing_player, distances, initial_fen):
    if depth == 0 or board.is_game_over():
        return evaluate_board_with_distance(board, distances, initial_fen)

    if maximizing_player:
        max_eval = float('-inf')
        best_steps = float('inf')
        for move in board.legal_moves:
            board.push(move)
            eval = minimax_with_distance(board, depth-1, False, distances, initial_fen)
            current_steps = distances[initial_fen][simplify_fen(board.fen())]
            board.pop()
            # 估值更高优先，估值相同则选步数更少的
            if eval > max_eval or (eval == max_eval and current_steps < best_steps):
                max_eval = eval
                best_steps = current_steps
        return max_eval
    else:
        min_eval = float('inf')
        worst_steps = float('-inf')
        for move in board.legal_moves:
            board.push(move)
            eval = minimax_with_distance(board, depth-1, True, distances, initial_fen)
            current_steps = distances[initial_fen][simplify_fen(board.fen())]
            board.pop()
            # 估值更低优先，估值相同则选步数更多的
            if eval < min_eval or (eval == min_eval and current_steps > worst_steps):
                min_eval = eval
                worst_steps = current_steps
        return min_eval

3. 更新最优走法查找函数 #

def find_best_move_with_distance(board, depth, distances, initial_fen):
    best_move = None
    best_value = float('-inf')
    best_steps = float('inf')

    for move in board.legal_moves:
        board.push(move)
        current_fen = simplify_fen(board.fen())
        value = minimax_with_distance(board, depth-1, False, distances, initial_fen)
        current_steps = distances[initial_fen][current_fen]
        board.pop()
        if value > best_value or (value == best_value and current_steps < best_steps):
            best_value = value
            best_steps = current_steps
            best_move = move

    return best_move

4. 主函数调用修改 #

# Main usage
initial_fen = "8/5k2/8/8/8/8/8/1KQ5 w - - 0 1"
initial_fen = simplify_fen(initial_fen)

board = chess.Board(initial_fen)
distances = generate_moves_and_distances(board)

# 查找最优走法
best_move = find_best_move_with_distance(board, 8, distances, initial_fen)
print("Best move for white:", best_move)

优化说明 #

• 复用已有的BFS步数计算结果，避免重复开销
• 通过"估值+步数"双条件排序，严格符合"最快将杀/最长拖延"的最优策略
• 保留原代码的核心逻辑，仅针对性修改关键模块

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