如何在国际象棋引擎中记录最佳走棋序列？

一、添加完整走棋序列记录的实现方案 #

要记录完整的最佳走棋序列，需要修改搜索逻辑，跟踪每个节点的最佳后续走法。核心思路是让Search方法返回评估值的同时，返回该节点对应的最佳走棋序列，具体修改如下：

1. 新增搜索结果类 #

定义一个包含评估值和最佳序列的类，用于传递搜索结果：

public class SearchResult
{
    public int Eval { get; set; }
    public List<Move> BestSequence { get; set; } = new List<Move>();
}

2. 修改StartSearch方法 #

初始化全局序列变量，接收搜索结果并更新最佳走法和序列：

public static Move bestMove = Move.NullMove;
public static List<Move> bestMoveSequence = new List<Move>();

public static Move StartSearch(int depth)
{
    bestMove = Move.NullMove;
    bestMoveSequence.Clear();

    if (depth <= 0)
    {
        return bestMove;
    }
    
    SearchResult result = Search(depth, Infinity.negativeInfinity, Infinity.positiveInfinity, 0);
    bestMove = result.BestSequence.Count > 0 ? result.BestSequence[0] : Move.NullMove;
    bestMoveSequence = result.BestSequence;

    return bestMove;
}

3. 修改Search方法 #

调整返回类型为SearchResult，在递归中跟踪并传递最佳走棋序列：

public static int QuiescenceSearch(int alpha, int beta)
{
    // 保留原静态搜索逻辑，返回评估值
}

public static SearchResult Search(int depth, int alpha, int beta, int plyFromRoot)
{
    SearchResult result = new SearchResult();

    // 先检查重复局面，避免错误评估
    if (board.positionHistory.ContainsKey(board.currentZobristKey))
    {
        result.Eval = 0;
        return result;
    }

    // 置换表查找
    int ttVal = tt.LookupEvaluation(depth, plyFromRoot, alpha, beta);
    if (ttVal != TranspositionTable.lookupFailed)
    {
        Move ttMove = tt.GetStoredMove();
        if (plyFromRoot == 0)
        {
            bestMove = ttMove;
        }
        result.Eval = ttVal;
        return result;
    }

    if (depth == 0)
    {
        result.Eval = QuiescenceSearch(alpha, beta);
        return result;
    }

    List<Move> legalMoves = MoveGen.GenerateMoves(board);

    MateChecker.MateState mateState = MateChecker.GetPositionState(board, legalMoves);
    if (mateState != MateChecker.MateState.None)
    {
        result.Eval = mateState == MateChecker.MateState.Checkmate 
            ? -Evaluation.checkmateEval + plyFromRoot 
            : 0;
        return result;
    }

    MoveOrder.GetOrderedList(legalMoves);

    int evalType = TranspositionTable.UpperBound;
    Move currentBestMove = Move.NullMove;
    List<Move> currentBestSequence = new List<Move>();

    foreach (Move move in legalMoves)
    {
        board.MakeMove(move);

        SearchResult childResult = Search(depth - 1, -beta, -alpha, plyFromRoot + 1);
        int eval = -childResult.Eval;

        board.UnmakeMove(move);

        if (eval >= beta)
        {
            tt.StoreEvaluation(depth, plyFromRoot, beta, TranspositionTable.LowerBound, move);
            result.Eval = beta;
            // 记录剪枝时的走棋序列
            result.BestSequence.Clear();
            result.BestSequence.Add(move);
            result.BestSequence.AddRange(childResult.BestSequence);
            return result;
        }

        if (eval > alpha)
        {
            alpha = eval;
            evalType = TranspositionTable.Exact;
            currentBestMove = move;
            // 更新当前节点的最佳序列：当前走法 + 子节点的最佳序列
            currentBestSequence.Clear();
            currentBestSequence.Add(move);
            currentBestSequence.AddRange(childResult.BestSequence);
        }
    }

    result.Eval = alpha;
    result.BestSequence = currentBestSequence;

    // 循环结束后统一存储置换表，避免重复覆盖
    tt.StoreEvaluation(depth, plyFromRoot, alpha, evalType, currentBestMove);

    return result;
}

二、现有代码中的问题修正 #

1. 置换表（Transposition Table）问题 #

• 存储时机错误：原代码在foreach循环的每次迭代后都调用tt.StoreEvaluation，会导致同一节点的置换表条目被多次覆盖，应改为循环结束后仅存储一次最终结果。
• 重复局面检查位置错误：原代码仅在置换表命中后检查重复局面，未命中置换表的重复局面会被错误评估，应将重复局面检查放在置换表查找之前。

2. Alpha-Beta剪枝问题 #

• 根节点初始bestMove赋值不合理：原代码在排序合法走法后直接将bestMove设为第一个走法，若所有走法的评估值都不如初始值，会导致bestMove错误，应删除该赋值，仅在找到更优解时更新。
• 剪枝逻辑无问题：原代码的Beta剪枝逻辑正确，但需确保剪枝时正确记录走棋序列。

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