我正在开发一个极小化极大（minimax）井字游戏算法。算法已经正常运行，我对树中的每个状态进行了缓存。

接着我实现了alpha-beta剪枝，这似乎影响了游戏。我认为问题在于，如果一个节点的任何后代（子节点、孙节点等）被剪枝，那么这个节点就不能被“信任”。这是真的吗？

目前，我只在状态没有被剪枝的后代时才进行缓存。这张图片展示了我的观点（不是井字游戏）。向上三角形是最大化玩家，应该选择左边的移动。然而，如果在alpha-beta剪枝过程中缓存了右边的移动，红色三角形将错误地显示值为4，因此会错误地选择右边的移动。

回答：

如果你说的“缓存”是指转置表，那么你不能总是信任转置表中的值。也就是说，当你将一个值存储在转置表中时，你还需要存储用于该状态下搜索的alpha和beta值（可能还包括深度）。如果alpha和beta值不相同*，那么你就不能使用转置表中的值。

*实际上它们不必完全相同，表中只需要包含当前节点所需替换的缓存值的超集即可。

编辑：为处理大型游戏的用户提供额外信息。当你在节点上搜索时，你有一个最终值的下界（alpha）和上界（beta）。如果返回的值在alpha和beta之间，那么你知道这是该状态的真实值。如果它等于alpha或beta，那么你知道它只是最终值的一个界限。但你仍然可以使用这些信息来帮助搜索。

特别是，假设你在当前搜索中alpha=10且beta=20，而转置表中的值是[alpha = 12, beta = 30, value = 12]。那么，当你（重新）搜索该分支下时，你可以使用alpha=10和beta=12的界限进行搜索。

这是因为你已经证明了在之前的搜索中值是<= 12的。当你得到最终结果时，你可以更新转置表条目以反映这次搜索的额外信息。