国际象棋引擎的性能功能给出了自相矛盾的输出

Question

我目前正在用 C++ 开发国际象棋引擎，并且正在调试我的着法生成器。为此，我写了一个简单的 perft() 函数：

int32_t Engine::perft(GameState game_state, int32_t depth)
{
    int32_t last_move_nodes = 0;
    int32_t all_nodes = 0;

    Timer timer;
    timer.start();

    int32_t output_depth = depth;

    if (depth == 0)
    {
        return 1;
    }

    std::vector<Move> legal_moves = generator.generate_legal_moves(game_state);

    for (Move move : legal_moves)
    {
        game_state.make_move(move);

        last_move_nodes = perft_no_print(game_state, depth - 1);
        all_nodes += last_move_nodes;

        std::cout << index_to_square_name(move.get_from_index()) << index_to_square_name(move.get_to_index()) << ": " << last_move_nodes << "\n";

        game_state.unmake_move(move);
    }

    std::cout << "\nDepth: " << output_depth << "\nTotal nodes: " << all_nodes << "\nTotal time: " << timer.get_milliseconds() << "ms/" << timer.get_milliseconds()/1000.0f << "s\n\n";

    return all_nodes;
}

int32_t Engine::perft_no_print(GameState game_state, int32_t depth)
{
    int32_t nodes = 0;

    if (depth == 0)
    {
        return 1;
    }

    std::vector<Move> legal_moves = generator.generate_legal_moves(game_state);

    for (Move move : legal_moves)
    {
        game_state.make_move(move);

        nodes += perft_no_print(game_state, depth - 1);

        game_state.unmake_move(move);
    }

    return nodes;
}

深度 1 和 2 的初始国际象棋位置（FEN：rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1）的结果与 stockfish 的 perft 命令的结果相匹配，所以我假设它们正确：

h2h3: 1
h2h4: 1
g2g3: 1
g2g4: 1
f2f3: 1
f2f4: 1
e2e3: 1
e2e4: 1
d2d3: 1
d2d4: 1
c2c3: 1
c2c4: 1
b2b3: 1
b2b4: 1
a2a3: 1
a2a4: 1
g1h3: 1
g1f3: 1
b1c3: 1
b1a3: 1

Depth: 1
Total nodes: 20
Total time: 1ms/0.001s

h2h3: 20
h2h4: 20
g2g3: 20
g2g4: 20
f2f3: 20
f2f4: 20
e2e3: 20
e2e4: 20
d2d3: 20
d2d4: 20
c2c3: 20
c2c4: 20
b2b3: 20
b2b4: 20
a2a3: 20
a2a4: 20
g1h3: 20
g1f3: 20
b1c3: 20
b1a3: 20

Depth: 2
Total nodes: 400
Total time: 1ms/0.001s

结果在深度 3 处停止匹配，但是：

鳕鱼:

go perft 3
a2a3: 380
b2b3: 420
c2c3: 420
d2d3: 539
e2e3: 599
f2f3: 380
g2g3: 420
h2h3: 380
a2a4: 420
b2b4: 421
c2c4: 441
d2d4: 560
e2e4: 600
f2f4: 401
g2g4: 421
h2h4: 420
b1a3: 400
b1c3: 440
g1f3: 440
g1h3: 400

Nodes searched: 8902

我的引擎：

h2h3: 361
h2h4: 380
g2g3: 340
g2g4: 397
f2f3: 360
f2f4: 436
e2e3: 380
e2e4: 437
d2d3: 380
d2d4: 437
c2c3: 399
c2c4: 326
b2b3: 300
b2b4: 320
a2a3: 280
a2a4: 299
g1h3: 281
g1f3: 280
b1c3: 357
b1a3: 320

Depth: 3
Total nodes: 7070
Total time: 10ms/0.01s

我认为我的移动生成器只是有问题，并试图通过引擎在棋盘上给出不正确的值然后调用 perft() 和 depth = 2 来追踪错误它找出缺少哪些动作。但是对于我尝试过的所有动作，引擎突然开始输出我期望早点得到的正确结果！

这里是移动的例子 a2a3:

当在 stockfish 的初始位置上调用 perft() 时，它计算 a2a3 深度 3 的 380 个子节点.
当在 我的引擎 的初始位置调用 perft() 时，它计算 a2a3 深度 3 的 280 个子节点].
当在 我的引擎 的初始位置移动 a2a3 后的位置上调用 perft() 时，它会计算正确的数量深度 2、380 处的总节点数：

h7h5: 19
h7h6: 19
g7g5: 19
g7g6: 19
f7f5: 19
f7f6: 19
e7e5: 19
e7e6: 19
d7d5: 19
d7d6: 19
c7c5: 19
c7c6: 19
b7b5: 19
b7b6: 19
a7a5: 19
a7a6: 19
g8h6: 19
g8f6: 19
b8c6: 19
b8a6: 19

Depth: 2
Total nodes: 380
Total time: 1ms/0.001s

如果您知道这里可能有什么问题，请帮助我。谢谢！

编辑:

我发现了一些可能有助于解决问题的有趣的新事实，但我不知道如何处理它们：

出于某种原因，在 perft() 中这样使用 std::sort()：
```
std::sort(legal_moves.begin(), legal_moves.end(), [](auto first, auto second){     return first.get_from_index() % 8 > second.get_from_index() % 8; });
```
对合法移动向量进行排序会导致找到的初始位置（深度3）的总节点数从错误的7070变为（也是错误的）7331.
在 perft() 中调用 game_state.make_move() 后打印游戏状态时，它似乎对位置位板没有影响（其他属性按预期更改).这很奇怪，因为孤立，make_move() 方法工作得很好。

Answer 1

这就是您希望使用 perft 调试移动生成器的方式。

给定 startpos 作为 p1，为你的引擎和 sf 生成 perft(3)。（你做到了）
现在检查任何有不同节点的着法，你选择a2a3。（你做到了）
给定 startpos + a2a3 作为 p2，为 你的引擎 和 sf 生成 perft(2)。（你部分这样做了）
现在检查步骤 3 中具有不同节点的任何移动。假设移动 x。
给定 startpos + a2a3 + x 作为 p3，为 你的引擎 和 sf.

由于这只是 perft(1)，此时您将能够从生成器中找出错误的着法或遗漏的着法。设置板上的最后一个位置或 p3 并查看 wrong/missing 与 sf perft(1) 结果相比从您的引擎移动。

Answer 2

我不确定您是否能够确定问题所在，但从问题中提供的有限信息来看，我能假设的最好情况（以及我之前遇到的问题）是您的 unmake_move() 在捕获方面发挥作用，因为

您的性能仅在第 3 级失败 - 这是可能进行第一次合法捕获的时间，第 1 步和第 2 步可能没有合法捕获。
你的性能在 a2a3 之后的深度 1 处工作正常，而不是从一开始就在深度 3 处搜索

这可能意味着您的 unmake_move() 在深度大于 1 时失败，您需要恢复一些板的状态，而这些状态不能仅从您传入的 move 参数导出（例如 enpassant、casting rights 等。在你搬家之前）。

国际象棋引擎的性能功能给出了自相矛盾的输出

perft-function of chess engine is giving self-contradictory output

c++

recursion

c++17

chess