关于换位表的困惑（国际象棋编程）

Question

我目前正在使用换位 tables 进行移动排序。使用迭代加深搜索，我存储上一次迭代的极小极大值，以便为下一次迭代排序移动。一切都很好。

这是我的困惑：

如果我在我的换位中找到某个位置table，那么我使用之前计算的分数进行移动排序（来自迭代深化的前一次迭代）。但是，如果这个位置的分数被更新（在 minimax 被 returned 之后），并且在另一个子树中再次找到该位置（迭代深化的相同迭代） - 我不想只将它用于移动排序...我应该能够return这个值，因为现在已经为这次迭代计算了这个值并且是绝对值。

这是我的问题：有两个转置 table 是标准的吗？一个用于上一次迭代，一个用于迭代深化的当前迭代。所以我会首先检查当前迭代的 table ，看看是否已经计算了 minimax 值，然后简单地 return 这个值。如果它不在这个 table 中，我会在上一次迭代中使用 table 来进行移动排序。如果两者都不是，那么它是我在这次搜索中从未见过的新位置。

这个思路是正确的，还是有更高效的方法？

Answer 1

通常，您不仅希望在 table 中存储最后找到的状态的极小极大值，而且还希望在将状态存储在 [=12] 中时在迭代中使用的深度限制=].这样，当您稍后在 table 中查找它时，您可以通过将 table 条目中存储的深度限制与您的当前深度限制。如果它们相等，则您知道 table 条目是在当前迭代中最后更新的，并且您可以直接使用存储在 table 中的值而无需任何额外的搜索

Answer 2

我同意@Dennis_Soemers。您应该保存深度，甚至可能 alpha/beta 边界添加到您的换位 table。不，你不应该需要两个 table。

让我们在 table.

上检查 Stockfish 源代码

https://github.com/official-stockfish/Stockfish/blob/master/src/tt.h

/// TTEntry struct is the 10 bytes transposition table entry, defined as below:
///
/// key        16 bit
/// move       16 bit
/// value      16 bit
/// eval value 16 bit
/// generation  6 bit
/// bound type  2 bit
/// depth       8 bit

table 的保存函数定义为：

void save(Key k, Value v, Bound b, Depth d, Move m, Value ev, uint8_t g)

现在，如果您有两个相同的位置，从深度 d-1 和 d。你可以这样做：

// My hash key is now position + depth
Key my_hash_key = k + d

您可以轻松检查上一次迭代和当前迭代：

Key previous_iter_key = my_position_key + d-1
probe(previous_iter_key ...)

Key current_iter_key = my_position_key + d
probe(current_iter_key ...)

关于换位表的困惑（国际象棋编程）

Confusion about Transposition Tables (chess programming)

chess

artificial-intelligence