国际象棋：Alpha-Beta 中的错误
Chess: Bug in Alpha-Beta
我正在实现一个国际象棋引擎，并且我已经编写了一个相当复杂的 alpha-beta 搜索例程，其中包含静态搜索和换位 tables。但是，我观察到一个奇怪的错误。
评估函数使用的是方块 tables，就像这个用于棋子的方块：
static int ptable_pawn[64] = {
0, 0, 0, 0, 0, 0, 0, 0,
30, 35, 35, 40, 40, 35, 35, 30,
20, 25, 25, 30, 30, 25, 25, 20,
10, 20, 20, 20, 20, 20, 20, 10,
3, 0, 14, 15, 15, 14, 0, 3,
0, 5, 3, 10, 10, 3, 5, 0,
5, 5, 5, 5, 5, 5, 5, 5,
0, 0, 0, 0, 0, 0, 0, 0
};
轮到黑棋时，table 沿 x 轴反射。具体来说，如果你很好奇，查找是这样发生的，其中 A-H 列映射到 0-7，行从白色的一侧是 0-7：
int ptable_index_for_white(int col, int row) {
return col+56-(row*8);
}
int ptable_index_for_black(int col, int row) {
return col+(row*8);
}
因此，h4（坐标 7, 3）上的一枚棋子对于白棋值 3 分（厘兵），而 f6（坐标 5, 5）上的一枚棋子对于黑棋值 3 分棋子。
整个评估函数目前是piece-square tables和material.
在更大的搜索深度下，我的引擎正在选择一些真正可怕的动作。考虑从起始位置生成的这个输出：
Iterative Deepening Analysis Results (including cached analysis)
Searching at depth 1... d1 [+0.10]: 1.b1c3
(4 new nodes, 39 new qnodes, 0 qnode aborts, 0ms), 162kN/s
Searching at depth 2... d2 [+0.00]: 1.e2e4 d7d5
(34 new nodes, 78 new qnodes, 0 qnode aborts, 1ms), 135kN/s
Searching at depth 3... d3 [+0.30]: 1.d2d4 d7d5 2.c1f4
(179 new nodes, 1310 new qnodes, 0 qnode aborts, 4ms), 337kN/s
Searching at depth 4... d4 [+0.00]: 1.g1f3 b8c6 2.e2e4 d7d5
(728 new nodes, 2222 new qnodes, 0 qnode aborts, 14ms), 213kN/s
Searching at depth 5... d5 [+0.20]: 1.b1a3 g8f6 2.d2d4 h8g8 3.c1f4
(3508 new nodes, 27635 new qnodes, 0 qnode aborts, 103ms), 302kN/s
Searching at depth 6... d6 [-0.08]: 1.d2d4 a7a5 2.c1f4 b7b6 3.f4c1 c8b7
(21033 new nodes, 112915 new qnodes, 0 qnode aborts, 654ms), 205kN/s
Searching at depth 7... d7 [+0.20]: 1.b1a3 g8f6 2.a1b1 h8g8 3.d2d4 g8h8 4.c1f4
(39763 new nodes, 330837 new qnodes, 0 qnode aborts, 1438ms), 258kN/s
Searching at depth 8... d8 [-0.05]: 1.e2e4 a7a6 2.e4e5 a6a5 3.h2h4 d7d6 4.e5d6 c7d6
(251338 new nodes, 2054526 new qnodes, 0 qnode aborts, 12098ms), 191kN/s
在深度 8 处，注意黑棋以“... a7a6 ... a6a5”着法开局，根据方格 table 这一步很可怕。此外，"h2h4" 对白方来说是一个可怕的举动。为什么我的搜索功能会选择如此奇怪的动作？不是table这只会在更深的深度开始发生（深度 3 的移动看起来不错）。
而且，搜索经常会误打误撞！考虑以下位置：
引擎推荐了一个可怕的错误 (3...f5h3)，不知何故遗漏了明显的回复 (4.g2h3)：
Searching at depth 7... d7 [+0.17]: 3...f5h3 4.e3e4 h3g4 5.f2f3 g8f6 6.e4d5 f6d5
(156240 new nodes, 3473795 new qnodes, 0 qnode aborts, 17715ms), 205kN/s
不涉及静止搜索，因为错误发生在第 1 层 (!!)。
这是我的搜索功能的代码。很抱歉它太长了：我尽可能地简化了，但我不知道哪些部分与错误无关。我假设我的算法有点错误。
该实现几乎完全基于维基百科的 this one。 （更新：我已经大大简化了搜索，但我的错误仍然存在。）
// Unified alpha-beta and quiescence search
int abq(board *b, int alpha, int beta, int ply) {
pthread_testcancel(); // To allow search worker thread termination
bool quiescence = (ply <= 0);
// Generate all possible moves for the quiscence search or normal search, and compute the
// static evaluation if applicable.
move *moves = NULL;
int num_available_moves = 0;
if (quiescence) moves = board_moves(b, &num_available_moves, true); // Generate only captures
else moves = board_moves(b, &num_available_moves, false); // Generate all moves
if (quiescence && !useqsearch) return relative_evaluation(b); // If qsearch is turned off
// Abort if the quiescence search is too deep (currently 45 plies)
if (ply < -quiesce_ply_cutoff) {
sstats.qnode_aborts++;
return relative_evaluation(b);
}
// Allow the quiescence search to generate cutoffs
if (quiescence) {
int score = relative_evaluation(b);
alpha = max(alpha, score);
if (alpha >= beta) return score;
}
// Update search stats
if (quiescence) sstats.qnodes_searched++;
else sstats.nodes_searched++;
// Search hueristic: sort exchanges using MVV-LVA
if (quiescence && mvvlva) nlopt_qsort_r(moves, num_available_moves, sizeof(move), b, &capture_move_comparator);
move best_move_yet = no_move;
int best_score_yet = NEG_INFINITY;
int num_moves_actually_examined = 0; // We might end up in checkmate
for (int i = num_available_moves - 1; i >= 0; i--) { // Iterate backwards to match MVV-LVA sort order
apply(b, moves[i]);
// never move into check
coord king_loc = b->black_to_move ? b->white_king : b->black_king; // for side that just moved
if (in_check(b, king_loc.col, king_loc.row, !(b->black_to_move))) {
unapply(b, moves[i]);
continue;
}
int score = -abq(b, -beta, -alpha, ply - 1);
num_moves_actually_examined++;
unapply(b, moves[i]);
if (score >= best_score_yet) {
best_score_yet = score;
best_move_yet = moves[i];
}
alpha = max(alpha, best_score_yet);
if (alpha >= beta) break;
}
// We have no available moves (or captures) that don't leave us in check
// This means checkmate or stalemate in normal search
// It might mean no captures are available in quiescence search
if (num_moves_actually_examined == 0) {
if (quiescence) return relative_evaluation(b); // TODO: qsearch doesn't understand stalemate or checkmate
coord king_loc = b->black_to_move ? b->black_king : b->white_king;
if (in_check(b, king_loc.col, king_loc.row, b->black_to_move)) return NEG_INFINITY; // checkmate
else return 0; // stalemate
}
// record the selected move in the transposition table
evaltype type = (quiescence) ? qexact : exact;
evaluation eval = {.best = best_move_yet, .score = best_score_yet, .type = type, .depth = ply};
tt_put(b, eval);
return best_score_yet;
}
/*
* Returns a relative evaluation of the board position from the perspective of the side about to move.
*/
int relative_evaluation(board *b) {
int evaluation = evaluate(b);
if (b->black_to_move) evaluation = -evaluation;
return evaluation;
}
我这样调用搜索：
int result = abq(b, NEG_INFINITY, POS_INFINITY, ply);
编辑：即使我简化了搜索例程，错误仍然存在。引擎只是错误地去掉了碎片。通过将其加载到 XBoard（或任何其他 UCI 兼容的 GUI）并与强大的引擎进行对抗，您可以轻松地看到这一点。应 manlio 的要求，我上传了代码：
这是 GitHub 存储库（link 已删除；问题出在上面的代码片段中）。它将在 OS X 或任何 *nix 系统上使用 "make" 构建。
我很乐意查看实际的回购协议，但我在实施类似的游戏算法时多次遇到过这个确切的问题。我会告诉你是什么导致了我的问题，你可以检查你是否犯了同样的错误。这些是按照我认为最有可能解决您的问题的顺序列出的。
层不是移动，每次迭代移动应该增加 2（这就是层）
这个错误几乎总是通过对第一个玩家的几乎每一步都做出错误的选择来表示，因为他们永远看不到做出错误动作的后果。避免这种情况的方法是将步数增加 2（或更普遍地增加游戏中玩家的数量，但您使用的是 minmax，所以它是 2）。这确保每个玩家在下一轮之前总是寻找结果。
评价一定要站在当前玩家的立场上
这听起来很明显，但我发誓我每次实现评估功能时都会搞砸这个。在设计评价时，我们总是从第一个玩的玩家的角度来设计，而我们应该做的是将它设计为 return 当前玩家的评价。我们可以判断出轮到哪个玩家了，因为我们有全场状态，所以不需要传进去。
如果您的评估调用不是您的 minmax 函数中的第一个调用，那么这将特别难以调试，但您已经以这种方式实现了它，所以这不是问题。
评估函数必须是对称的
当它发生时，这是一个特别讨厌的错误。这个想法是，同一个玩家会根据他们是赢还是输来不同地评估同一个位置。
以国际象棋为例，作为获胜者，您希望赢得最少的步数，但如果您要输，则希望输掉最长的步数。一个典型的解决方案是说，如果你要赢，就为在较少步数中获胜而增加奖励，但如果你要输，就为更长的序列增加奖励。这会导致根据情况因相反原因添加奖励，并从评估中移除对称性，例如玩家 A 不等于 - 玩家 B。当你失去这种对称性时，你不能再将值传递回游戏树，你必须在每一步重新评估它们。
但诀窍在于，像这样进行调整总是错误的。通过深度静态评估，如果发现有保证的胜利，它就会提前结束。随着迭代深化解决方案，它仍然会先找到较早的胜利。除非对手失误，否则5中的伴侣永远不会是4中的伴侣，因此永远不需要这样的调整。
仔细检查你的换位没有冲突table
我看不到你的换位的实现 table，但是如果你处理的状态比你分配给存储的更多，那么你必须确保它是相同的位置，然后才能信任该值.我怀疑这是个问题，因为看起来您只查看了几百万个节点，但仔细检查总是好的。此外，请确保您的哈希函数足够随机以避免经常发生冲突。
mtd_f不应该请教换位table
mtd_f 是一个传递函数，它将在第一次调用 negamax 时正确处理转置 table。您在现在实施时不正确地使用了它的值，但仅删除该代码将清理实施并正确处理它。此外，您应该在每次迭代时将评估传递给 mtd_f 函数，而不是每次都尝试加载它。
if (score >= best_score_yet) {
应该是：
if (score > best_score_yet) {
否则你会考虑走坏棋。第一个 best_move_yet 将是正确的（因为 best_score_yet = NEG_INFINITY）但其他 score == best_score_yet 的动作不一定更好。
更改该行：
起始位置
Iterative Deepening Analysis Results (including cached analysis)
Searching at depth 1... d1 [+0.10]: 1.e2e4
(1 new nodes, 4 new qnodes, 0 qnode aborts, 0ms, 65kN/s)
(ttable: 1/27777778 = 0.00% load, 0 hits, 0 misses, 1 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 2... d2 [+0.00]: 1.e2e4 g8f6
(21 new nodes, 41 new qnodes, 0 qnode aborts, 0ms, 132kN/s)
(ttable: 26/27777778 = 0.00% load, 0 hits, 0 misses, 25 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 3... d3 [+0.30]: 1.d2d4 g8f6 2.c1f4
(118 new nodes, 247 new qnodes, 0 qnode aborts, 5ms, 73kN/s)
(ttable: 187/27777778 = 0.00% load, 0 hits, 0 misses, 161 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 4... d4 [+0.00]: 1.e2e4 g8f6 2.f1d3 b8c6
(1519 new nodes, 3044 new qnodes, 0 qnode aborts, 38ms, 119kN/s)
(ttable: 2622/27777778 = 0.01% load, 0 hits, 0 misses, 2435 inserts (with 0 overwrites), 1 insert failures)
Searching at depth 5... d5 [+0.10]: 1.g2g3 g8f6 2.f1g2 b8c6 3.g2f3
(10895 new nodes, 35137 new qnodes, 0 qnode aborts, 251ms, 184kN/s)
(ttable: 30441/27777778 = 0.11% load, 0 hits, 0 misses, 27819 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 6... d6 [-0.08]: 1.d2d4 g8f6 2.c1g5 b8c6 3.g5f6 g7f6
(88027 new nodes, 249718 new qnodes, 0 qnode aborts, 1281ms, 264kN/s)
(ttable: 252536/27777778 = 0.91% load, 0 hits, 0 misses, 222095 inserts (with 0 overwrites), 27 insert failures)
Searching at depth 7... d7 [+0.15]: 1.e2e4 g8f6 2.d2d4 b8c6 3.d4d5 c6b4 4.g1f3
(417896 new nodes, 1966379 new qnodes, 0 qnode aborts, 8485ms, 281kN/s)
(ttable: 1957490/27777778 = 7.05% load, 0 hits, 0 misses, 1704954 inserts (with 0 overwrites), 817 insert failures)
在测试位置时：
Calculating...
Iterative Deepening Analysis Results (including cached analysis)
Searching at depth 1... d1 [+2.25]: 3...g8h6 4.(q)c3d5 (q)d8d5
(1 new nodes, 3 new qnodes, 0 qnode aborts, 0ms, 23kN/s)
(ttable: 3/27777778 = 0.00% load, 0 hits, 0 misses, 3 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 2... d2 [-0.13]: 3...f5e4 4.c3e4 (q)d5e4
(32 new nodes, 443 new qnodes, 0 qnode aborts, 3ms, 144kN/s)
(ttable: 369/27777778 = 0.00% load, 0 hits, 0 misses, 366 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 3... d3 [+0.25]: 3...g8h6 4.c3e2 h6g4
(230 new nodes, 2664 new qnodes, 0 qnode aborts, 24ms, 122kN/s)
(ttable: 2526/27777778 = 0.01% load, 0 hits, 0 misses, 2157 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 4... d4 [-0.10]: 3...g8f6 4.e3e4 f5e6 5.f1b5
(2084 new nodes, 13998 new qnodes, 0 qnode aborts, 100ms, 162kN/s)
(ttable: 15663/27777778 = 0.06% load, 0 hits, 0 misses, 13137 inserts (with 0 overwrites), 2 insert failures)
Searching at depth 5... d5 [+0.15]: 3...g8f6 4.f1e2 h8g8 5.g2g4 f5e4 6.(q)c3e4 (q)f6e4
(38987 new nodes, 1004867 new qnodes, 0 qnode aborts, 2765ms, 378kN/s)
(ttable: 855045/27777778 = 3.08% load, 0 hits, 0 misses, 839382 inserts (with 0 overwrites), 302 insert failures)
我正在实现一个国际象棋引擎，并且我已经编写了一个相当复杂的 alpha-beta 搜索例程，其中包含静态搜索和换位 tables。但是，我观察到一个奇怪的错误。
评估函数使用的是方块 tables，就像这个用于棋子的方块：
static int ptable_pawn[64] = {
0, 0, 0, 0, 0, 0, 0, 0,
30, 35, 35, 40, 40, 35, 35, 30,
20, 25, 25, 30, 30, 25, 25, 20,
10, 20, 20, 20, 20, 20, 20, 10,
3, 0, 14, 15, 15, 14, 0, 3,
0, 5, 3, 10, 10, 3, 5, 0,
5, 5, 5, 5, 5, 5, 5, 5,
0, 0, 0, 0, 0, 0, 0, 0
};
轮到黑棋时，table 沿 x 轴反射。具体来说，如果你很好奇，查找是这样发生的，其中 A-H 列映射到 0-7，行从白色的一侧是 0-7：
int ptable_index_for_white(int col, int row) {
return col+56-(row*8);
}
int ptable_index_for_black(int col, int row) {
return col+(row*8);
}
因此，h4（坐标 7, 3）上的一枚棋子对于白棋值 3 分（厘兵），而 f6（坐标 5, 5）上的一枚棋子对于黑棋值 3 分棋子。
整个评估函数目前是piece-square tables和material.
在更大的搜索深度下，我的引擎正在选择一些真正可怕的动作。考虑从起始位置生成的这个输出：
Iterative Deepening Analysis Results (including cached analysis)
Searching at depth 1... d1 [+0.10]: 1.b1c3
(4 new nodes, 39 new qnodes, 0 qnode aborts, 0ms), 162kN/s
Searching at depth 2... d2 [+0.00]: 1.e2e4 d7d5
(34 new nodes, 78 new qnodes, 0 qnode aborts, 1ms), 135kN/s
Searching at depth 3... d3 [+0.30]: 1.d2d4 d7d5 2.c1f4
(179 new nodes, 1310 new qnodes, 0 qnode aborts, 4ms), 337kN/s
Searching at depth 4... d4 [+0.00]: 1.g1f3 b8c6 2.e2e4 d7d5
(728 new nodes, 2222 new qnodes, 0 qnode aborts, 14ms), 213kN/s
Searching at depth 5... d5 [+0.20]: 1.b1a3 g8f6 2.d2d4 h8g8 3.c1f4
(3508 new nodes, 27635 new qnodes, 0 qnode aborts, 103ms), 302kN/s
Searching at depth 6... d6 [-0.08]: 1.d2d4 a7a5 2.c1f4 b7b6 3.f4c1 c8b7
(21033 new nodes, 112915 new qnodes, 0 qnode aborts, 654ms), 205kN/s
Searching at depth 7... d7 [+0.20]: 1.b1a3 g8f6 2.a1b1 h8g8 3.d2d4 g8h8 4.c1f4
(39763 new nodes, 330837 new qnodes, 0 qnode aborts, 1438ms), 258kN/s
Searching at depth 8... d8 [-0.05]: 1.e2e4 a7a6 2.e4e5 a6a5 3.h2h4 d7d6 4.e5d6 c7d6
(251338 new nodes, 2054526 new qnodes, 0 qnode aborts, 12098ms), 191kN/s
在深度 8 处，注意黑棋以“... a7a6 ... a6a5”着法开局，根据方格 table 这一步很可怕。此外，"h2h4" 对白方来说是一个可怕的举动。为什么我的搜索功能会选择如此奇怪的动作？不是table这只会在更深的深度开始发生（深度 3 的移动看起来不错）。
而且，搜索经常会误打误撞！考虑以下位置：
引擎推荐了一个可怕的错误 (3...f5h3)，不知何故遗漏了明显的回复 (4.g2h3)：
Searching at depth 7... d7 [+0.17]: 3...f5h3 4.e3e4 h3g4 5.f2f3 g8f6 6.e4d5 f6d5
(156240 new nodes, 3473795 new qnodes, 0 qnode aborts, 17715ms), 205kN/s
不涉及静止搜索，因为错误发生在第 1 层 (!!)。
这是我的搜索功能的代码。很抱歉它太长了：我尽可能地简化了，但我不知道哪些部分与错误无关。我假设我的算法有点错误。
该实现几乎完全基于维基百科的 this one。 （更新：我已经大大简化了搜索，但我的错误仍然存在。）
// Unified alpha-beta and quiescence search
int abq(board *b, int alpha, int beta, int ply) {
pthread_testcancel(); // To allow search worker thread termination
bool quiescence = (ply <= 0);
// Generate all possible moves for the quiscence search or normal search, and compute the
// static evaluation if applicable.
move *moves = NULL;
int num_available_moves = 0;
if (quiescence) moves = board_moves(b, &num_available_moves, true); // Generate only captures
else moves = board_moves(b, &num_available_moves, false); // Generate all moves
if (quiescence && !useqsearch) return relative_evaluation(b); // If qsearch is turned off
// Abort if the quiescence search is too deep (currently 45 plies)
if (ply < -quiesce_ply_cutoff) {
sstats.qnode_aborts++;
return relative_evaluation(b);
}
// Allow the quiescence search to generate cutoffs
if (quiescence) {
int score = relative_evaluation(b);
alpha = max(alpha, score);
if (alpha >= beta) return score;
}
// Update search stats
if (quiescence) sstats.qnodes_searched++;
else sstats.nodes_searched++;
// Search hueristic: sort exchanges using MVV-LVA
if (quiescence && mvvlva) nlopt_qsort_r(moves, num_available_moves, sizeof(move), b, &capture_move_comparator);
move best_move_yet = no_move;
int best_score_yet = NEG_INFINITY;
int num_moves_actually_examined = 0; // We might end up in checkmate
for (int i = num_available_moves - 1; i >= 0; i--) { // Iterate backwards to match MVV-LVA sort order
apply(b, moves[i]);
// never move into check
coord king_loc = b->black_to_move ? b->white_king : b->black_king; // for side that just moved
if (in_check(b, king_loc.col, king_loc.row, !(b->black_to_move))) {
unapply(b, moves[i]);
continue;
}
int score = -abq(b, -beta, -alpha, ply - 1);
num_moves_actually_examined++;
unapply(b, moves[i]);
if (score >= best_score_yet) {
best_score_yet = score;
best_move_yet = moves[i];
}
alpha = max(alpha, best_score_yet);
if (alpha >= beta) break;
}
// We have no available moves (or captures) that don't leave us in check
// This means checkmate or stalemate in normal search
// It might mean no captures are available in quiescence search
if (num_moves_actually_examined == 0) {
if (quiescence) return relative_evaluation(b); // TODO: qsearch doesn't understand stalemate or checkmate
coord king_loc = b->black_to_move ? b->black_king : b->white_king;
if (in_check(b, king_loc.col, king_loc.row, b->black_to_move)) return NEG_INFINITY; // checkmate
else return 0; // stalemate
}
// record the selected move in the transposition table
evaltype type = (quiescence) ? qexact : exact;
evaluation eval = {.best = best_move_yet, .score = best_score_yet, .type = type, .depth = ply};
tt_put(b, eval);
return best_score_yet;
}
/*
* Returns a relative evaluation of the board position from the perspective of the side about to move.
*/
int relative_evaluation(board *b) {
int evaluation = evaluate(b);
if (b->black_to_move) evaluation = -evaluation;
return evaluation;
}
我这样调用搜索：
int result = abq(b, NEG_INFINITY, POS_INFINITY, ply);
编辑：即使我简化了搜索例程，错误仍然存在。引擎只是错误地去掉了碎片。通过将其加载到 XBoard（或任何其他 UCI 兼容的 GUI）并与强大的引擎进行对抗，您可以轻松地看到这一点。应 manlio 的要求，我上传了代码：
这是 GitHub 存储库（link 已删除；问题出在上面的代码片段中）。它将在 OS X 或任何 *nix 系统上使用 "make" 构建。
我很乐意查看实际的回购协议，但我在实施类似的游戏算法时多次遇到过这个确切的问题。我会告诉你是什么导致了我的问题，你可以检查你是否犯了同样的错误。这些是按照我认为最有可能解决您的问题的顺序列出的。
层不是移动，每次迭代移动应该增加 2（这就是层）
这个错误几乎总是通过对第一个玩家的几乎每一步都做出错误的选择来表示，因为他们永远看不到做出错误动作的后果。避免这种情况的方法是将步数增加 2（或更普遍地增加游戏中玩家的数量，但您使用的是 minmax，所以它是 2）。这确保每个玩家在下一轮之前总是寻找结果。
评价一定要站在当前玩家的立场上
这听起来很明显，但我发誓我每次实现评估功能时都会搞砸这个。在设计评价时，我们总是从第一个玩的玩家的角度来设计，而我们应该做的是将它设计为 return 当前玩家的评价。我们可以判断出轮到哪个玩家了，因为我们有全场状态，所以不需要传进去。
如果您的评估调用不是您的 minmax 函数中的第一个调用，那么这将特别难以调试，但您已经以这种方式实现了它，所以这不是问题。
评估函数必须是对称的
当它发生时，这是一个特别讨厌的错误。这个想法是，同一个玩家会根据他们是赢还是输来不同地评估同一个位置。
以国际象棋为例，作为获胜者，您希望赢得最少的步数，但如果您要输，则希望输掉最长的步数。一个典型的解决方案是说，如果你要赢，就为在较少步数中获胜而增加奖励，但如果你要输，就为更长的序列增加奖励。这会导致根据情况因相反原因添加奖励，并从评估中移除对称性，例如玩家 A 不等于 - 玩家 B。当你失去这种对称性时，你不能再将值传递回游戏树，你必须在每一步重新评估它们。
但诀窍在于，像这样进行调整总是错误的。通过深度静态评估，如果发现有保证的胜利，它就会提前结束。随着迭代深化解决方案，它仍然会先找到较早的胜利。除非对手失误，否则5中的伴侣永远不会是4中的伴侣，因此永远不需要这样的调整。
仔细检查你的换位没有冲突table
我看不到你的换位的实现 table，但是如果你处理的状态比你分配给存储的更多，那么你必须确保它是相同的位置，然后才能信任该值.我怀疑这是个问题，因为看起来您只查看了几百万个节点，但仔细检查总是好的。此外，请确保您的哈希函数足够随机以避免经常发生冲突。
mtd_f不应该请教换位table
mtd_f 是一个传递函数，它将在第一次调用 negamax 时正确处理转置 table。您在现在实施时不正确地使用了它的值，但仅删除该代码将清理实施并正确处理它。此外，您应该在每次迭代时将评估传递给 mtd_f 函数，而不是每次都尝试加载它。
if (score >= best_score_yet) {
应该是：
if (score > best_score_yet) {
否则你会考虑走坏棋。第一个 best_move_yet 将是正确的（因为 best_score_yet = NEG_INFINITY）但其他 score == best_score_yet 的动作不一定更好。
更改该行：
起始位置
Iterative Deepening Analysis Results (including cached analysis)
Searching at depth 1... d1 [+0.10]: 1.e2e4
(1 new nodes, 4 new qnodes, 0 qnode aborts, 0ms, 65kN/s)
(ttable: 1/27777778 = 0.00% load, 0 hits, 0 misses, 1 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 2... d2 [+0.00]: 1.e2e4 g8f6
(21 new nodes, 41 new qnodes, 0 qnode aborts, 0ms, 132kN/s)
(ttable: 26/27777778 = 0.00% load, 0 hits, 0 misses, 25 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 3... d3 [+0.30]: 1.d2d4 g8f6 2.c1f4
(118 new nodes, 247 new qnodes, 0 qnode aborts, 5ms, 73kN/s)
(ttable: 187/27777778 = 0.00% load, 0 hits, 0 misses, 161 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 4... d4 [+0.00]: 1.e2e4 g8f6 2.f1d3 b8c6
(1519 new nodes, 3044 new qnodes, 0 qnode aborts, 38ms, 119kN/s)
(ttable: 2622/27777778 = 0.01% load, 0 hits, 0 misses, 2435 inserts (with 0 overwrites), 1 insert failures)
Searching at depth 5... d5 [+0.10]: 1.g2g3 g8f6 2.f1g2 b8c6 3.g2f3
(10895 new nodes, 35137 new qnodes, 0 qnode aborts, 251ms, 184kN/s)
(ttable: 30441/27777778 = 0.11% load, 0 hits, 0 misses, 27819 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 6... d6 [-0.08]: 1.d2d4 g8f6 2.c1g5 b8c6 3.g5f6 g7f6
(88027 new nodes, 249718 new qnodes, 0 qnode aborts, 1281ms, 264kN/s)
(ttable: 252536/27777778 = 0.91% load, 0 hits, 0 misses, 222095 inserts (with 0 overwrites), 27 insert failures)
Searching at depth 7... d7 [+0.15]: 1.e2e4 g8f6 2.d2d4 b8c6 3.d4d5 c6b4 4.g1f3
(417896 new nodes, 1966379 new qnodes, 0 qnode aborts, 8485ms, 281kN/s)
(ttable: 1957490/27777778 = 7.05% load, 0 hits, 0 misses, 1704954 inserts (with 0 overwrites), 817 insert failures)
在测试位置时：
Calculating...
Iterative Deepening Analysis Results (including cached analysis)
Searching at depth 1... d1 [+2.25]: 3...g8h6 4.(q)c3d5 (q)d8d5
(1 new nodes, 3 new qnodes, 0 qnode aborts, 0ms, 23kN/s)
(ttable: 3/27777778 = 0.00% load, 0 hits, 0 misses, 3 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 2... d2 [-0.13]: 3...f5e4 4.c3e4 (q)d5e4
(32 new nodes, 443 new qnodes, 0 qnode aborts, 3ms, 144kN/s)
(ttable: 369/27777778 = 0.00% load, 0 hits, 0 misses, 366 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 3... d3 [+0.25]: 3...g8h6 4.c3e2 h6g4
(230 new nodes, 2664 new qnodes, 0 qnode aborts, 24ms, 122kN/s)
(ttable: 2526/27777778 = 0.01% load, 0 hits, 0 misses, 2157 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 4... d4 [-0.10]: 3...g8f6 4.e3e4 f5e6 5.f1b5
(2084 new nodes, 13998 new qnodes, 0 qnode aborts, 100ms, 162kN/s)
(ttable: 15663/27777778 = 0.06% load, 0 hits, 0 misses, 13137 inserts (with 0 overwrites), 2 insert failures)
Searching at depth 5... d5 [+0.15]: 3...g8f6 4.f1e2 h8g8 5.g2g4 f5e4 6.(q)c3e4 (q)f6e4
(38987 new nodes, 1004867 new qnodes, 0 qnode aborts, 2765ms, 378kN/s)
(ttable: 855045/27777778 = 3.08% load, 0 hits, 0 misses, 839382 inserts (with 0 overwrites), 302 insert failures)