搜索，游戏和解决问题：与对手的比赛

高速ETC办理

6年前

微信搜索“高速商务通”，马上办理ETC

两个玩家的游戏，例如国际象棋，西洋棋棋子，奥赛罗和围棋，都是确定性的，因为每个动作（一个动作）都会在同一个父状态下产生相同的子状态。相反，步步高是非确定性的，因为它的子状态取决于它

关于掷骰子的结果。这些游戏都是可观察的，因为每个玩家总是知道完整的游戏状态。例如扑克等许多纸牌游戏只能部分观察，因为玩家不知道其他玩家的牌，或者只是对他们有部分了解。

本章到目前为止讨论的问题具有确定性和可观察性。在下文中，我们将研究那些确定性和可观察性的游戏。此外，我们将自己限制为零和游戏。这些游戏中，每个玩家获得的每一个获得意味着对手失去相同的价值。增益和损失之和总是等于零。上面提到的游戏国际象棋，西洋棋棋子，奥赛罗和围棋也是如此。

1. Minimax搜索

每个球员的目标是做出最佳的动作，从而获得胜利。原则上，可以构建一个搜索树并完全搜索它（就像使用8-puzzle一样）进行一系列将导致胜利的动作。但是，有几个特点值得注意：

≈

1. 国际象棋中的有效分支因子大约是30到35.在每个玩家50次移动的典型游戏中，搜索树有超过30 100 10 148个叶子节点。因此，没有机会完全探索搜索树。此外，国际象棋通常会有时间限制。由于这种实时要求，搜索必须限制在树中适当的深度，例如八个半移动。由于在这个深度限制树的叶节点中，通常没有解决节点（即终止游戏的节点）启发式评估函数B用于董事会职位。该计划的游戏水平在很大程度上取决于该评估功能的质量。因此，我们将在Sect中进一步对待这一主题。6.5。

2. 在下面我们将调用我们希望优化Max和他的对手Min的游戏。对手的（Min）的移动事先不知道，因此实际的搜索树也不是。通过假设对手总能做出最佳动作，可以优雅地解决这个问题。较高的评价B（S）的位置小号，更好的位置小号是玩家最大和更糟糕的是他的对手民。Max试图最大限度地评估他的动作，而Min做出的动作导致评估尽可能低。

第 104 页的图 6.18 给出了一个具有四个半移动和所有叶片评估的搜索树。内部节点的评估作为其子节点的最大值或最小值递归导出，具体取决于节点的级别。

2. α-β修剪

通过在最大化和最小化之间切换，我们可以在某些情况下为自己节省大量工作。Alpha-beta修剪与深度优先搜索一起使用，达到预设的深度限制。以这种方式，从左侧搜索搜索树

图6.18 一个minimax游戏树，具有四个半移动的前瞻性

图6.19 一个alpha-beta游戏树，具有四个半移动的前瞻性。不遍历树的虚线部分，因为它们对最终结果没有影响

≥

≤

≥

对。与极小极大搜索一样，在最小节点中，最小值是从后继节点的最小值生成的，而最大节点中也是最大值。在图6.19中，该过程描绘了图6.18 中的树。在标记为a的节点处，在将第一个子项评估为值1之后，可以忽略所有其他后继者，因为最小值肯定为1.它甚至可能变得更小，但这是无关紧要的，因为最大值已经是3个等级以上。无论剩下的后继者的评估结果如何，最大值将保持值3.类似地，树将在节点b处被修剪。自从b的第一个孩子值为2，为b生成的最小值只能小于或等于2.但根节点的最大值已经确定为3.这不能通过值2更改。因此剩余的子树为b可以修剪。