缓存可以用于alpha-beta搜索算法吗? [英] Can a cache be used for an alpha-beta search algorithm?

问题描述

我正在研究minimax井字游戏算法.我使它工作正常，将树中的每个状态都缓存了.

I'm working on a minimax tic-tac-toe algorithm. I got it working fine, caching each state in the tree.

然后我实施了alpha-beta修剪，这似乎影响了游戏.我认为问题在于，如果修剪了任何后代(子代，孙代等)，则无法信任"节点.这是真的吗?

Then I implemented alpha-beta pruning, which seemed to affect the game. I think the problem is that nodes cannot be "trusted" if any of their descendants (children, grandchildren, etc.) were pruned. Is this true?

就目前而言，我只是在缓存状态，如果它们没有修剪后代.此图像显示了我的观点(不是井字游戏).最大的玩家是向上的三角形，该三角形应选择左侧的移动.但是，如果在alpha-beta修剪过程中缓存了右边的移动，则红色三角形的错误值为4，因此会错误地选择右边的移动.

For now, I'm only caching states if they don't have pruned descendants. This image shows my point (not tic tac toe). The max player is the upwards triangle, which should choose the move on the left. However, if the move on the right is cached during alpha-beta pruning, the red triangle will have a false value of 4, so the move on the right would be wrongly chosen.

推荐答案

如果用高速缓存"来表示换位表，则您不能总是信任换位表中的值.也就是说，当将值存储在转置表中时，还需要在该状态下存储用于搜索的alpha和beta值(可能还包括深度).如果alpha和beta值不相同*，则不能使用转置表中的值.

If by a "cache" you mean a transposition table, then you can't always trust the value in the transposition table. That is, when you store a value in a transposition table, you need to also store the alpha and beta values (perhaps the depth as well) used for the search below that state. If the alpha and beta values are not the same*, then you can't use the value from the transposition table.

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

*In practice they don't have to be identical, the table just needs to have values that include a superset of the values used at the current node you want to replace with the cached values.

在大型游戏中处理此问题的人员的附加信息.在节点上搜索时，最终值具有下限(alpha)和上限(beta).如果返回的值在alpha和beta之间，则您知道它是状态的真实值.如果它等于alpha或beta，则您知道它仅是最终值的界限.但是，您仍然可以使用此信息来帮助搜索.

Additional info for those dealing with this in larger games. When you search at a node you have a lower bound (alpha) and upper bound (beta) on the final value. If the returned value is between alpha and beta, then you know it is the true value of the state. If it is equal to alpha or beta, then you know it is only a bound on the final value. But, you can still use this information to help the search.

尤其是，假设您在当前搜索中具有alpha = 10和beta = 20，并且转置表中的值为[alpha = 12，beta = 30，value = 12].然后，当您在分支下方(重新)搜索时，可以使用alpha = 10和beta = 12的边界进行搜索.

In particular, suppose that you have alpha=10 and beta=20 in the current search and the value in the transposition table is [alpha = 12, beta = 30, value = 12]. Then, when you (re-)search below the branch, you can search with bounds of alpha=10 and beta=12.

这是因为您已经在上一次搜索中证明了该值是< = 12.得到最终结果后，可以更新换位表条目以反映此搜索中的其他信息.

This is because you've already proven that the value is <= 12 in the previous search. When you get the final result, you can then update the transposition table entry to reflect the additional information from this search.

这篇关于缓存可以用于alpha-beta搜索算法吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！