Perft测试结果 - 找不到Bug？

我现在为我的坏英语道歉，我是意大利人。我正在用C＃编写一个象棋游戏的完整实现，Player vs Player和Player vs Computer，现在我有一些难以实现的NegaMax算法。对于谁是有兴趣，这里是我的github仓库：https://github.com/crybot/ChessEngine_NOGUI/tree/master/Chess%20Engine%20-%20NOGUI Perft测试结果 - 找不到Bug？

我试图让这个项目作为OO越好，所以，如果你认为我的设计是不正确，请告诉我:)

这里我的问题：

我实现对称地为所有玩家的工作很简单的评价函数：

public static float Evaluate(PieceColor playerColor, Game game) 
{ 
    float score = 0; 

    score += 1 * (game.board.GetNumberOfPieces(PieceType.Pawn, playerColor) 
    - game.board.GetNumberOfPieces(PieceType.Pawn, playerColor.GetOpposite())); 

    score += 3 * (game.board.GetNumberOfPieces(PieceType.Bishop, playerColor) 
    - game.board.GetNumberOfPieces(PieceType.Bishop, playerColor.GetOpposite())); 

    score += 3 * (game.board.GetNumberOfPieces(PieceType.Knight, playerColor) 
    - game.board.GetNumberOfPieces(PieceType.Knight, playerColor.GetOpposite())); 

    score += 5 * (game.board.GetNumberOfPieces(PieceType.Rook, playerColor) 
    - game.board.GetNumberOfPieces(PieceType.Rook, playerColor.GetOpposite())); 

    score += 9 * (game.board.GetNumberOfPieces(PieceType.Queen, playerColor) 
    - game.board.GetNumberOfPieces(PieceType.Queen, playerColor.GetOpposite())); 

    score += 0.1f * (game.GetPlayer(playerColor).GetMoves(game).Count); 

    return score; 
}

，这里是我的NegaMax功能，至极接受的游戏参数（包括博ard，players，ecc.ecc），由enum提供的playerColor和深度搜索;

我第一次扫描的EnginePlayer的所有可能的行动，然后我从NegaMax功能的比分，但东西是不工作...

private float NegaMax(Game game, PieceColor playerColor, int depth) 
{ 
    if (depth == 0) 
    return EvaluateMove(playerColor, game); 

    float max = float.MinValue; 
    float score; 

    foreach (Move move in game.GetPlayer(playerColor.GetOpposite()).GetMoves(game)) 
    { 
     game.board.SimulateMove(move); 
     score = Math.Max(max, -NegaMax(game, playerColor.GetOpposite(), depth - 1)); 

     game.board.CancelMove(move); 

     if (score > max) 
      max = score; 
    } 

    return max; 
} 


public Move ThinkMove(Game game, PieceColor playerColor, int depth) 
{ 

    Move bestMove = new NullMove(); 
    float bestScore = float.MinValue; 
    float temp = 0; 

    foreach (Move move in GetMoves(game)) 
    { 
     game.board.SimulateMove(move); 
     temp = NegaMax(game, playerColor, depth); 
     game.board.CancelMove(move); 

     if (temp > bestScore) 
     { 
      if (Judge.IsLegal(move, game)) 
      { 
       bestMove = move; 
       bestScore = temp; 
      } 
     } 
    } 

    if (bestMove is NullMove) 
    throw new NotImplementedException(); 
    return bestMove; 
}

我觉得这一切......我希望你会发现我做错了什么:) 谢谢。

编辑： 我实现了一个Perft，它显示了移动生成器的非修正。它帮助我们找到了一些相对容易发现的错误，但最后一些结果仍然是错误的。下面是结果：

Perft Depth: 1 
Nodes: 20 Captures: 0 Checks: 0 Castles: 0 Mates: 0 EnPassant: 0 

Perft Depth: 2 
Nodes: 400 Captures: 0 Checks: 0 Castles: 0 Mates: 0 EnPassant: 0 

Perft Depth: 3 
Nodes: 8902 Captures: 34 Checks: 12 Castles: 0 Mates: 0 EnPassant: 0 

Perft Depth: 4 
Nodes: 197281 Captures: 1610 Checks: 473 Castles: 0 Mates: 8 EnPassant: 0

这里是正确的结果：https://chessprogramming.wikispaces.com/Perft+Results分析

正如你所看到的，在深度4，我得到正确的节点，但不正确的捕获和检查值（当队友是正确）。

由于这些结果我试图通过将每移动所分析的节点在深度4到bug隔离，得到这些结果：

Move Nodes 
a2a3 8457 
a2a4 9329 
b2b3 9345 
b2b4 9332 
c2c3 9272 
c2c4 9744 
d2d3 11959 
d2d4 12435 
e2e3 13134 
e2e4 13160 
f2f3 8457 
f2f4 8929 
g2g3 9345 
g2g4 9328 
h2h3 8457 
h2h4 9329 
b1a3 8885 
b1c3 9755 
g1f3 9748 
g1h3 8881 
Total Nodes: 197281

和与这些结果，从更清晰的获得比较：

Sharper v0.17 by Albert Bertilsson 
divide 4 
b1c3 9755 
b1a3 8885 
g1h3 8881 
g1f3 9748 
a2a3 8457 
a2a4 9329 
b2b3 9345 
b2b4 9332 
c2c3 9272 
c2c4 9744 
d2d3 11959 
d2d4 12435 
e2e3 13134 
e2e4 13160 
f2f3 8457 
f2f4 8929 
g2g3 9345 
g2g4 9328 
h2h3 8457 
h2h4 9329 
Nodes: 197281 
Moves: 20

但即使这里的值是正确的...... 所以我尝试了深度5个perft得到这些结果：

Move Nodes 
a2a3 181046 
a2a4 217813 
b2b3 215255 
b2b4 216110 
c2c3 222861 
c2c4 240044 
d2d3 328511 
d2d4 361753 
e2e3 402988 
e2e4 405348 
f2f3 178891 
f2f4 198437 
g2g3 217210 
g2g4 214017 
h2h3 181044 
h2h4 218810 
b1a3 198572 
b1c3 234656 
g1f3 233491 
g1h3 198502 
Total Nodes: 4865359

，然后进行比较，以更清晰的结果：

Sharper v0.17 by Albert Bertilsson 
divide 5 
b1c3 234656 
b1a3 198572 
g1h3 198502 
g1f3 233491 
a2a3 181046 
a2a4 217832 
b2b3 215255 
b2b4 216145 
c2c3 222861 
c2c4 240082 
d2d3 328511 
d2d4 361790 
e2e3 402988 
e2e4 405385 
f2f3 178889 
f2f4 198473 
g2g3 217210 
g2g4 214048 
h2h3 181044 
h2h4 218829 
Nodes: 4865609 
Moves: 20

所以我意识到，这个问题是由兵卒的双重推动产生的移动造成的......但我真的不能找到bug ... 有没有人有同样的问题？ 或类似的东西，或只是一个提示找到该错误...

感谢所有:)

来源

2012-07-06 Crybot

什么不工作？引擎不是'聪明的'，或者它根本不搜索？ – 2012-07-06 15:32:24

起初它似乎在工作，但随后它试图通过将他的主教从g8移动到a3来在第二步中自我杀死。也有深度2有时会导致非法移动。 – Crybot 2012-07-06 15:36:44

你测试了你的移动发生器吗？ – 2012-07-06 15:37:19

你应该先确保招代是一致的，have a look here on how to。这被称为perft测试。另一个奇怪的是，我在你的算法中看不到'配偶'威胁：如果没有任何动作，并且国王处于捕获状态（否则是立场），你应该返回一个非常差的值。那么你应该采取一些策略来排序这些动作，以便从negamax算法中受益，然后采用一些'时间范围'策略（即，如果深度== 0时仍然捕获，会发生什么？）。如果您在移动世代中存在问题，请尝试用更有趣的位置挑战您的引擎，have a look here for example，或者如果您想要更难this is the file that I use for testing my engine。它包括含有FEN格式位置多的行，接着深度移动计数以下列格式：

D1 50; D2 279

这就是意味着（例如）在depth1 50点移动时，在深度279个移动2

的我建议的立场来自我对护目镜的旧研究，关于具有挑战性的位置。你需要能够support FEN notation，如果你还没有，我强烈建议实施，因为它是一个“事实上”在国际象棋引擎（而不仅仅是）世界中沟通职位的标准。

来源

2012-07-06 15:44:04

谢谢我会尝试，但只是为了好奇，你发现我的NegaMax算法出了什么问题，除了配偶的事情吗？ – Crybot 2012-07-06 15:57:08

我没有，但是你知道，用眼睛调试并不是那么容易:)无论如何，伴侣的事情会极大地影响你的引擎发挥的方式; – 2012-07-06 16:16:53

你可以看看我的问题的顶部？我添加了perft结果:) – Crybot 2012-07-09 15:14:25

你想通了吗？我遇到了同样的问题。通过这样说我的意思是我在初始位置获得了1610次捕捉（4）。

而且，this男人好像也有同样的问题。

我仔细地检查了代码（并用天真替代品替换了一些复杂的代码），但是找不到任何错误。毕竟，总的动作数是正确的，不是吗？

然后我意识到：1610 = 1576 + 34.这只是一个例子，我检查了其余的perft结果，并确定它是问题所在。

这些“标准”perft结果表中的捕获计数仅捕获深度等于0的叶节点，包括简短捕获。

来源

2013-08-06 05:12:39

Perft测试结果 - 找不到Bug？

回答

相关问题