缓存可以用于 alpha-beta 搜索算法吗？
Can a cache be used for an alpha-beta search algorithm?
我正在研究极小极大井字游戏算法。我让它工作正常，在树中缓存每个状态。
然后我实施了 alpha-beta 修剪，这似乎影响了游戏。我认为问题是如果节点的任何后代（子孙等）被修剪，节点就不能 "trusted" 。这是真的吗？
目前，我只缓存没有修剪后代的状态。 This 图片显示了我的观点（不是井字游戏）。最大玩家是向上的三角形，应该选择左边的着法。但是，如果在 alpha-beta 修剪过程中缓存了右边的着法，则红色三角形的值为 4，因此右边的着法将被错误选择。
如果 "cache" 是指换位 table，那么您不能总是相信换位 table 中的值。也就是说，当您在转置 table 中存储一个值时，您还需要存储用于在该状态下搜索的 alpha 和 beta 值（可能还有深度）。如果 alpha 和 beta 值不相同*，则不能使用转置 table.
中的值
*在实践中，它们不必完全相同，table 只需要具有包含要用缓存值替换的当前节点所用值的超集的值。
编辑：为那些在大型游戏中处理此问题的人提供的附加信息。当您在节点处搜索时，最终值有下限 (alpha) 和上限 (beta)。如果返回值介于 alpha 和 beta 之间，那么您就知道它是状态的真实值。如果它等于 alpha 或 beta，那么您就知道它只是最终值的一个界限。但是，您仍然可以使用此信息来帮助搜索。
特别是，假设您在当前搜索中有 alpha=10 和 beta=20，并且转置 table 中的值为 [alpha = 12，beta = 30，value = 12]。然后，当您在分支下方（重新）搜索时，您可以使用 alpha=10 和 beta=12 的范围进行搜索。
这是因为您已经在之前的搜索中证明了该值 <= 12。当您获得最终结果时，您可以更新换位 table 条目以反映来自该搜索的附加信息。
我正在研究极小极大井字游戏算法。我让它工作正常，在树中缓存每个状态。
然后我实施了 alpha-beta 修剪，这似乎影响了游戏。我认为问题是如果节点的任何后代（子孙等）被修剪，节点就不能 "trusted" 。这是真的吗？
目前，我只缓存没有修剪后代的状态。 This 图片显示了我的观点（不是井字游戏）。最大玩家是向上的三角形，应该选择左边的着法。但是，如果在 alpha-beta 修剪过程中缓存了右边的着法，则红色三角形的值为 4，因此右边的着法将被错误选择。
如果 "cache" 是指换位 table，那么您不能总是相信换位 table 中的值。也就是说，当您在转置 table 中存储一个值时，您还需要存储用于在该状态下搜索的 alpha 和 beta 值（可能还有深度）。如果 alpha 和 beta 值不相同*，则不能使用转置 table.
中的值*在实践中，它们不必完全相同，table 只需要具有包含要用缓存值替换的当前节点所用值的超集的值。
编辑：为那些在大型游戏中处理此问题的人提供的附加信息。当您在节点处搜索时，最终值有下限 (alpha) 和上限 (beta)。如果返回值介于 alpha 和 beta 之间，那么您就知道它是状态的真实值。如果它等于 alpha 或 beta，那么您就知道它只是最终值的一个界限。但是，您仍然可以使用此信息来帮助搜索。
特别是，假设您在当前搜索中有 alpha=10 和 beta=20，并且转置 table 中的值为 [alpha = 12，beta = 30，value = 12]。然后，当您在分支下方（重新）搜索时，您可以使用 alpha=10 和 beta=12 的范围进行搜索。
这是因为您已经在之前的搜索中证明了该值 <= 12。当您获得最终结果时，您可以更新换位 table 条目以反映来自该搜索的附加信息。