optimization - 用 alpha beta 剪枝理解 minimax

Question

抱歉，图片来自我的笔记。

最后一天，我一直在阅读极小极大树和 alpha 数据修剪，并为我的项目做一些准备。这是 c 中奥赛罗的一个实现。

我已经阅读了大量关于它的资源，我知道它被问了很多。在我开始我的评估功能之前，我想完全理解这一点。

在所附图像中，我无法弄清楚该功能Min_Node(pos)和Max_Node(pos)确切的功能，任何输入将不胜感激。

如果有人在实现这个和我对奥赛罗的评估功能时有任何提示或事情我应该注意，我愿意接受我能找到的任何帮助。

Answer 1

此处也描述的极小极大算法需要在博弈树中给定当前位置的情况下找到最优值的移动。该位置由棋盘配置和当前玩家组成（对于某些游戏，可以仅根据棋盘配置决定）。通常移动的值是递归定义的；对于处于 eding 位置的棋盘（它是游戏树的一个叶子），值是1玩家一是否赢了，-1如果玩家二赢了，并且0对于平局游戏。移动的值是通过执行该移动并递归评估该值来确定的。然后，选择最大（对于玩家一）或最小（对于玩家二）的移动；在递归评估中，该值是当前位置的子树根的所有叶子的最大值（或最小值）。这显然是原始问题中提到的功能应该是什么。

如此处所述的Alpha-beta-pruning是这种方法的改进。由于已知最佳值（它们是1或-1），一旦找到具有所需值的移动，就可以停止评估。

这种方法独立于实际游戏。但是，我建议第一步使用更简单的游戏（例如井字游戏）作为可能更容易调试的玩具示例。

Answer 2

我设法弄清楚最大和最小节点是什么，在这种情况下，Max_Node(pos)检查这是否是玩家，它返回真，因为这应该被最大化并Min_Node(pos)检查它是否是对手，如果是真的，那么它应该被最小化。