英语原文共 34 页，剩余内容已隐藏，支付完成后下载完整资料
摘要
分析了用于搜索博弈树的alpha-beta技术，试图为其行为提供一些洞察力。本文的第一部分是一个对该方法的解释性的介绍，以及对其正确性的证明和历史上的讨论。从某种意义上来说alpha;-beta;程序是最优的，利用各种随机数据，给出了其运行时间的界。
0.导入
用来玩游戏，如下象棋的计算机程序通常通过搜索一个潜在延续的树来选择他们的移动步骤。一种被称为“Alpha-beta剪枝”的技术，通常用于加快这种搜索过程，并且不会丢失信息。本文的目的是对 alpha-beta 程序进行分析，以获得对其性能特征的定量估计。
第一节定义与博弈树相关的基本概念。第二节介绍 alpha-beta 方法，以及一个相关的技术，这个技术很相似，但是没有那么强大，因为它不能做到“深度截断”。两种方法的正确性都被证明。第三节给出了实例以及算法的进一步发展。第四节讨论关于该方法在实践中应用的几点建议。第五节介绍阿尔法贝塔剪枝的历史。
第六节开始进行定量分析，推导出 alpha-beta 所需搜索量的下界，以及任何解决相同一般问题的算法所需搜索量的下界。第七节推导了上界，主要考虑没有深度截断时随机树的情况。结果表明，即使在这些假设条件不足的情况下，这个过程也是相当有效的。第八部分介绍如何在分析中引入一些深度截断。第九部分介绍了当连续步骤之间存在依赖关系时，效率会提高。本文基本上是自成一体的，除了后面几节中引用的一些数学结果。
- 博弈和位置值
我们正在处理的双人博弈可以被一系列“位置”值描述 ，即通过一组从一个位置移动到另一个位置的规则，博弈双方交替移动。我们假设规则不允许无限序列的位置，只有从每个位置起的有限的许多合法移动。它依据“infinity lemma”[11]，即对于每个位置 p 都有一个数字N(p)，以致没有从p开始的博弈持续步数超过N(p)次移动。
如果p是一个没有合法移动的位置，那么有一个整数值函数f(p)，它表示这个位置对轮到从p位置开始博弈的玩家的值；假设对另一个玩家的值是-f(p)。
如果p是一个从此开始有d个合法移动p1hellip;hellip;pd的位置，此时dgt;1，问题是要选择最好的一步。我们假设最佳移动是当博弈结束时，达到最大可能值的移动步，过程中博弈对手也会选择对他最有利的移动步。设F(p)是从位置p应对对方最佳防守策略可能达到的最大值，从以该位置起始移动的玩家的角度来看。该值(对这个玩家)在移动到位置pi后将变为-F（pi），我们有
F（p）= （1）
这个公式用来定义所有位置p的F（p），通过归纳从p开始可实现的最长博弈路径。
在大多数关于博弈的讨论中，使用了稍微不同的形式；博弈双方分别名为Max和Min，其中所有值都是从Max的视角给出的。因此，如果p是轮到Max移动的终端位置，它的值是f (p)如前所述，但如果p是轮到Min移动的终端位置，它的值是g（p）= -f（p）。
Max将尝试最大化最终值，而Min尝试将其最小化。现在有两个函数对应于（1），即
F（p）V= （2）
这是从p位置起始Max可以保证的最大值，还有
G（p）= （3）
这是Min可以实现的最优值。如前述一样，我们假设p1hellip;hellip;pd是从位置p起始的合法移动。通过归纳很容易证明F在(1)和(3)中的两个定义是相同的，并且对于所有p有G（p）=-F（p），因此这两个方法是等价的。
有时使用(3)和(4)的“minimax”框架而不是方程一的“负极大值”方法来推理博弈过程更为容易。 原因是如果我们一直从一方的角度来评估博弈的位置，我们有时就不会那么困惑了。 另一方面，当我们试图证明关于博弈的事情时，公式(1)是有利的，因为当我们想要建立我们的结果时，我们不必处理两个(有时甚至是四个或八个)独立的案例。方程式（1）与电路设计中出现的“异或”运算类似；异或逻辑运算的两个层次相当于一层的与运算加上一层的或运算。
函数F(p)是当博弈双方都采取最佳策略所能达到的最大终值，但是我们应该注意到这反映了一个保守的策略，这个策略在现实中并不总是最佳的，即当我们在现实世界中遇到劣等博弈者或非最优博弈者时。例如，假设有两个移动，到位置p1和p2，其中 p1确保平局 (值为0)但不可能获胜，而 p2根据对手是否忽略了一个相当微妙的获胜移步，有一定获胜或失败的可能。我们最好还是往p2边走边赌，这是我们赢的唯一机会，除非我们相信对手的能力。事实上，人类似乎可以通过采用这种策略来打败象棋程序。
- 算法的开发
下面的算法通过定义(1)清楚地计算了F(p) :
integer procedure F (position p):
begin integer m, i, t, d;
determine the successor positions p1hellip;pd;
if d = 0 then F := f(p) else
begin m := -;
for i := 1 step 1 until d do
begin t := -F(pi);
if t gt; m then m := t;
end;
F := m;
end;
end.
这里表示对于博弈的所有终止位置都大于或等于|f (p)|的值，因此-是对于所有p都小于或等于。这个算法是一个“蛮力”搜索，遍历所有可能的延续；无穷引理向我们保证，这个算法将在有限步后终止。
通过使用“分支定界”技巧[14]，忽略那些不能比已知的动作更好的动作，是有可能改进暴力搜索法的。例如，如果F(p1)=-10，那么F(p)10，我们不必知道F(p2)的确切值，如果我们可以推导出F(p2)-10(即-F(p2)10)。 因此，如果p21是p2的合法移动，以致F(p21)10，我们就不必费心去探索p2的其他移动。在博弈术语中，到p2的移步可以被“驳回”(相对于另一种移动p1)，如果对方可以给p2一个至少和他给p1一样最优的回复。一旦移动被反驳，我们不需要寻找最好的反驳。
这种推理方式导致了一种计算技术，避免了大部分由F完成的计算。我们将F1定义为一个关于两个参数p和界限的过程，我们的目标是实现以下条件：
F1(p, bound)= F(p) 若F(p)lt;bound,
F1(p, bound)bound 若F(p)bound.
这些关系不能完全定义F1，但是它们足够强大，可以计算任意起始位置p的F(p)，因为它们暗示了F1（p，）=F（p）。
下面的算法符合这种分枝定界的思想。
integer procedure F1(position p, integer bound):
begin integer m, i, t, d;
determine the successor positions P1hellip;Pd;
if d = 0 then F1 := f(p) else
begin m := -;
for i := 1 step 1 until d do
begin t := -F1(pi,-m);
if tgt;m then m:= t;
if mbound then go to done;
end;
done: F1 : = m;
end;
end.
我们可以证明这个过程满足(6)，证明如下：for循环第i次迭代的开始时，我们有“不变”条件m=max（-F（p1）hellip;hellip;-F（pi-1）），正如程序F中一样。(空集上的max运算通常被定义为-。)
如果我们同时引入上下界，这个过程还可以进一步改进，这个想法被称为Alpha-beta剪枝，它是单边分枝定界法的一个有意义的扩展。(不幸的是，它不适用于所有的分支定界算法，它只在探索一个博弈树时有效。)我们定义了一个由三个参数p，alpha和beta组成的程序F2，对于alphalt;beta，满足以下类似于（6）的条件：
F2(p, alpha, beta)alpha 若F(p)alpha,
F2(p, alpha, beta)=F(p) 若alpha lt; F(p) lt; beta,
F2(p, alpha, beta)beta 若F(p) beta.
同样，这些条件并没有完全指定F2，但是它们暗示F2（p，-，）=F（p）。
事实证明，当用编程语言表达时，这种改进的算法看起来与其他算法只有一点点不同：
integer procedure F2 (position p, integer alpha, integer beta):
begin integer m, i, t, d;
determine the successor positions p1hellip;pd;
if d = 0 then F2 := f(p) else
begin m := alpha;
for i := 1 step 1 until d do
begin t : = - F2(pi, -beta, -m);
if t gt; m then m := t;
if mbeta then go to done;
end;
done: F2 : = m;
end;
end.
既然我们已经发现了极大极小程序的两个改进，很自然地我们会问是否还有进一步改进的可能。有没有一个“alpha-beta-gamma”程序F3，用来表示目前为止发现的第二大值，或者其他什么花招？下面的第六节说明，答案是否定的，或者至少在某种意义上，F2程序是最佳的。
- 例子和改进
作为这些步骤的一个例子，考虑图1中的树，它代表了一个位置，有三个后继，每个后继都有三个后继，等等。直到我们在四步后达到34=81个位置是可能的，这81个位置根据的前81位数随机分配f值。图1表示从frsquo;s计算出来的F值，因此，树顶的根节点经过两方面的最佳发挥后，有效值为2。
图2显示了与程序F1（p，）评估相同的情况。注意，在81个终端位置中，只有36个被检查，并且在2层的一个节点现在具有“近似”值3，而不是其真实值7；但这个近似值当然不会影响顶部的值。图3显示的情况与全Alpha-beta剪枝程序评估的情况相同。在任何博弈树中，F2（p，-， ）总是检查与F1（p，）相同的节点，直到达到前视的第四级；这是下面理论的结果。然而，在4，5hellip;hellip;层，程序F2偶尔能够做到“深度截断”，这是F1无法做到的。图3与图2的比较表明，在这个例子中有五个深度截断点。
图一 博弈树的完全评价
图二 由程序F1（分枝定界策略）评估的图一的博弈树
图三 由程序F2（alpha-beta策略）评估的图一的博弈树
所有这些例证都以第一部分的“negamax”模型来呈现结果；如果读者喜欢以“minimax”模型来看待它，忽略图1-3中所有的负号是有效的。第2部分的程序可随时转换为minimax约定，例如以下列两个程序取代F2:
integer procedure F2 (position p, integer alpha, integer beta):
begin integer m, i, t, d;
determine the successor positions P1hellip;pd;
if d = 0 then F2 := f(p) else
begin m := alpha;
for i := 1 step 1 until d do
begin t : = G2(pi, m, beta);
if t gt; m then m := t;
if mbeta then go to done;
end;
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[237745]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
