极小极大算法的描述说，两个玩家都必须发挥最佳效果，因此算法是最佳的。直觉上是可以理解的。但是请任何人具体化，或者证明如果 min 播放不是最佳会发生什么？
谢谢
问问题
6613 次
3 回答
2
“最佳”的定义是您玩游戏以最小化对手最佳答案的“分数”（或您衡量的任何东西），这是由最小化您的最佳答案分数的游戏定义的，依此类推。
因此，根据定义，如果你打得不是最佳，你的对手至少有一条路径可以让他获得比你打得最佳时更高的分数。
找出什么是最优的一种方法是暴力破解整个游戏树。对于不那么琐碎的问题，您可以使用 alpha-beta 搜索，它可以保证最优而不需要搜索整个树。如果你的树仍然太复杂，你需要一个启发式方法来估计“位置”的分数是多少，并在某个深度停止。
这可以理解吗？
于 2011-06-10T13:00:33.103 回答
2
我对那个精确的问题有疑问。
当您考虑一下时，您会发现极小极大图包含所有可能的游戏，包括不良游戏。因此，如果玩家玩次优游戏，那么该游戏是树的一部分 - 但已被丢弃以支持更好的游戏。
它类似于 alpha beta。如果我故意牺牲一些棋子来创造空间，然后通过差距取得胜利，我就会陷入困境。即有一个更好的移动到树下。
使用 alpha beta - 假设在树中实际上是一系列失败的动作，然后是杀手动作 - 但在这种情况下，alpha 和 beta 充当窗口过滤器“a < x < b”，如果你会丢弃它有一个更好的游戏。如果您想象将 +/- 无穷大放入修剪后的分支中以查看会发生什么，您可以在 alpha beta 中看到它。
在任何情况下，两种算法都会重新计算每一步，这样如果玩家玩次优游戏，它们就会打开对对手更好的图分支。
冲洗重复。
于 2015-05-13T00:59:02.693 回答
0
考虑一个 MIN 节点，其子节点是终端节点。如果 MIN 播放不理想，则节点的值大于或等于 MIN 播放最佳时的值。因此，作为 MIN 节点的父节点的 MAX 节点的值只能增加。这个论点可以通过一个简单的归纳一直延伸到根。如果 MIN 的次优玩法是可以预测的，那么可以比 minimax 策略做得更好。例如，如果 MIN 总是落入某种陷阱并输了，那么设置陷阱保证了胜利，即使实际上对 MIN 有毁灭性的反应。
于 2020-11-20T19:09:21.223 回答