artificial-intelligence - 如何在游戏中使用换位表提高性能？

Question

我在我的游戏中使用 alpha-beta 修剪实现了迭代深化，我还添加了一个换位表来存储已经评估过的板。

现在，我正在执行以下操作:

在运行迭代深化时，在 depth = 0 时，它会评估所有位置并将其分数存储在 TT 中。

现在，当它以 depth = 1 重新运行时。如果它存在于 TT 中，我只需返回板的值。这会在 depth = 0 处停止算法，因为对于 depth = 0 板，所有值都已在 TT 中。

如果我在达到深度限制时从 TT 返回值，例如。 depth = MAX_DEPTH 那么大的子树将永远不会被切割。

所以，我不明白我应该如何重新使用存储在 TT 中的值来使我的游戏更快？

Answer 1

我将在这个答案中使用国际象棋来进行解释，当然这种稍加修改的推理也适用于其他棋盘游戏。

棋盘游戏程序中的换位表是将已经评估过的棋盘存储在缓存中的缓存。有一个易于处理的缓存值来唯一标识一个位置是很好的，比如:

WKe5Qd6Pg2h3h4 BKa8Qa7

因此，如果您到达某个位置，则检查缓存键是否存在，如果存在，则重用其评估。每当您访问 depth=0 的位置时，在对其进行正确评估后，就可以将其缓存。因此，如果进行了一些 Action ，在子变体中，您可以或多或少地跳过评估。例如，让我们考虑在起始位置白棋移动 1. Nf3 和黑棋回复 1... Nf6 的例子。在两层的结果位置之后，位置被缓存，白色的 2. Ng1 需要评估，因为这还没有评估也没有缓存，但黑色可能的 2... Ng8 不需要评估，因为它导致开始位置。

当然，您可以进行更积极的缓存并将位置存储到 depth = 1 甚至更多。

您需要确保不会错过游戏的一些战略细节。在国际象棋的情况下，您需要记住:

50 步法则的作用

3次重复抽奖

谁在移动

过去/现在是否有一些特殊的 Action ，例如caSTLing或en-passant，而在其他情况下则不然

因此，您可能希望在您的算法中添加一些进一步的细微差别，但要回答原始问题:游戏中已经出现的位置或在变化表中非常高的位置可以被缓存并或多或少地被忽略(在大多数情况下，越少意味着上述细微差别)