如何使用置换表提高游戏博弈的性能？

Question

我在游戏中实现了具有alpha-beta剪枝的迭代加深，并添加了置换表来存储已经评估过的棋盘。

现在，我的做法如下：

1. 当执行迭代加深时，在深度为0时，它会评估并将所有位置及其得分存储在置换表中。
2. 现在，当深度为1时重新运行。如果在置换表中存在该棋盘，则只需返回其值即可。因为在深度为0的情况下，所有的值都已经在置换表中。

如果在达到深度限制（例如深度=MAX_DEPTH）时从置换表返回值，则大的子树将永远不会被剪枝。

所以，我不明白如何重复使用存储在置换表中的值来加快我的游戏？

- Raj

Answer 1

我将在本回答中使用象棋来解释修辞，当然，稍加修改后这种推理也可以应用于其他棋类游戏。

棋盘游戏程序中的置换表是缓存，它存储已经评估过的棋盘。拥有一个易于处理的缓存值，可以唯一地标识一个位置，这非常好，例如：

WKe5Qd6Pg2h3h4 BKa8Qa7

因此，如果您到达某个位置，则检查缓存键是否存在，如果存在，则重用其评估。每当您访问深度为0的位置时，在正确评估后，它可以被缓存。因此，如果进行了一些移动，在子变化中，您可以更多或少地跳过评估。例如，让我们考虑这样一个例子：在起始位置，白方移动了1.Nf3，黑方回答了1... Nf6。在两个棋手走完之后的位置都被缓存之后，需要评估白方的2.Ng1，因为这还没有被评估或缓存，但是不需要评估黑方可能的2... Ng8，因为它导致的是起始位置。

当然，您可以更积极地缓存并存储深度为1或更深的位置。

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

- 50步规则的影响 - 三次重复和局 - 轮到谁走 - 过去/现在是否有特殊移动，如易位或兵过河而不在另一种情况下

因此，您可能需要将一些进一步的细微差别添加到算法中，但是为了回答最初的问题：已经出现在游戏中或在变化表中非常高的位置可以被缓存并且可以被更多或少地忽略（更多意味着在大多数情况下，更少意味着上述细微差别）。

- Lajos Arpad