两个玩家的游戏，例如国际象棋，西洋棋棋子，奥赛罗和围棋，都是确定性的，因为每个动作（一个动作）都会在同一个父状态下产生相同的子状态。相反，步步高是非确定性的，因为它的子状态取决于它
关于掷骰子的结果。这些游戏都是可观察的，因为每个玩家总是知道完整的游戏状态。例如扑克等许多纸牌游戏只能部分观察，因为玩家不知道其他玩家的牌，或者只是对他们有部分了解。
本章到目前为止讨论的问题具有确定性和可观察性。在下文中，我们将研究那些确定性和可观察性的游戏。此外，我们将自己限制为零和游戏。这些游戏中，每个玩家获得的每一个获得意味着对手失去相同的价值。增益和损失之和总是等于零。上面提到的游戏国际象棋，西洋棋棋子，奥赛罗和围棋也是如此。
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可以修剪。
相同的推理适用于节点c。但是，相关的最大节点不是直接父节点，而是根节点。这可以概括。
•
在每个叶节点处，计算评估。
•
•
对于每个最大节点，当前最大子值保存在α中。对于每个最小节点，当前最小子值保存在β中。
§
≤
如果在最小节点k处当前值βα，则k下的搜索可以结束。这里α是从根到k的路径中最大节点的最大值。
§
≥
如果在最大节点l处当前值αβ，则在l下的搜索可以结束。这里β是从根到l的路径中最小节点的最小值。
甲LPHA乙ETA中号AX（节点，α，β）
如果DepthLimitReached（Node）返回（评级（节点））NewNodes =后继者（节点）
α =最大值（α，A LPHA B ETA M IN（第一（NewNodes），α，β））
NewNodes = Rest（NewNodes）返回（α）
甲LPHA乙ETA中号IN（节点，α，β）
如果DepthLimitReached（Node）返回（评级（节点））NewNodes =后继者（节点）
β =最小值（ β，A LPHA B ETA M AX（第一个（新节点）， α，β））
NewNodes = Rest（NewNodes）返回（β）
如果 β ≤ α 收益（ α ）
而NewNodes =∅
如果 α ≥ β 返回（ β ）
而NewNodes =∅
图6.20具有两个函数A
LPHA B
ETA M
IN和A L的 alpha-beta搜索算法–
PHA B ETA M AX
图6.20中给出的算法是深度优先搜索的扩展，具有两个交替调用的函数。它使用上面定义的α和β值。
复杂性 alpha-beta修剪节省的计算时间在很大程度上取决于子节点遍历的顺序。在最坏的情况下，alpha-beta修剪不提供任何优势。对于恒定的分支因子b，在深度d处评估的叶节点的数量nd等于
nd = bd。
在最好的情况下，当被递减排序的最大的节点的后继者，且m的继任√在我 MUM节点递增排序，有效科顺
因子减少到b。在国际象棋中，这意味着大幅度降低效果
分支因子从35到约6.然后只有
ND = √ b d = BD / 2
将创建叶节点。这意味着深度限制以及搜索范围都会被alpha-beta修剪加倍。但是，这仅适用于最佳排序的后继者，因为子节点的评级在创建它们时是未知的。如果子节点随机排序，然后将支化因子降低至b 3 / 4和叶节点与数
3 d
nd
= b 4。
例如，使用相同的计算能力，使用alpha-beta修剪的国际象棋计算机可以计算前方的八个半移动而不是六个，有效分支因子大约为14.通过推导这些参数可以找到完整的分析。 [Pea84]。
在每个分支机构订购继任者。从而我们达到有效b √ – [R 的清因子
大约7到8，距理论最佳值35 [Nil98]不远。
3.
非确定性游戏
Minimax搜索可以推广到所有具有非确定性动作的游戏，例如步步高。每个玩家在移动之前都会滚动，这会受到掷骰子结果的影响。因此，在游戏树中，序列中有三种类型的级别
每个骰子滚动节点分支六种方式。因为我们无法预测模具的价值，所以我们对所有轧辊的平均值进行平均，并按照[RN10]的平均值进行搜索。
