博弈树中多次切割的αβ剪枝外文翻译资料
2021-12-17 11:12
英语原文共 20 页
博弈树中多次切割的alpha;beta;剪枝
作者：Yngvi Bjornssonlowast;, Tony A. Marsland
（阿尔伯塔大学计算科学系，加拿大，阿尔伯塔省埃德蒙顿市）
翻译者：胡志成（武汉理工大学物联网专业）
目录
摘要
作为一种极大化极小值搜索过程，alpha;beta;算法的效率可以归于其在所谓的切割节点处的有效修剪; 理想情况下，只需要检查一次决策分支就可以确定最小极大值。 本文探讨了在切割节点上进行额外搜索剩余的决策分支的好处。 我们的研究结果显示，切割节点处前景好的决策替代方案数量与这一新的主要变化之间存在很强的相关性。 此外，我们引入了一种新的前向剪枝方法，该方法使用此附加信息来忽略潜在的无用子树。 我们还在国际象棋领域提供了新的修剪方法的实验结果。
介绍
在国际象棋、跳棋和奥赛罗等对局游戏中，alpha;beta;算法是最常用的搜索博弈树的方法。它比一个简单的蛮力极小化极大值搜索更为显著，因为它允许在保留正确的游戏树值的同时，对游戏树的大部分进行修剪。但是，随着搜索深度的增加，算法访问的节点数仍呈指数增长。这显然限制了搜索的范围，因为游戏程序必须满足外部时间限制：决策时间通常只有几分钟。总的来说，演算质量会进一步提高程序的前瞻性。1
多年以来，alpha;beta;算法以各种不同的方式得到了改进强化，而且还派生了许多更有效的变体。例如，虽然基础算法需要探索固定深度内所有的子树拓展，但实际上这种方式并不再使用。取而代之的是使用各种启发式方法改变搜索范围（通常称为搜索深度或搜索树高度），因此可以更深入地搜索某些决策子树。在构建决策树时， “有趣的”子树可以扩展衍生超出名义上的既定深度，而其他子树的扩展则可以提前终止。 后一种情况被称为预修剪，并且存在忽视某些可能的良好子树延续的风险。 该方法背后的基本原理是，通过修剪非有前途的线路节省的时间更好地用于更深入地搜索其他线路，以提高整体决策质量。
为了有效地应用预修剪，需要有良好的标准来确定忽略哪些子树。在这里，我们展示了一个新思路：玩家在切割节点处具有的良好移动替代方案的数量本身就可用于识别潜在的无用子树。此外，我们引入了一种新的前向修剪方法，称为多切割alpha;beta;修剪，它根据切割节点上有希望的决策子树数量做出修剪决策。 在极小极大的意义上，这样做能针对性的否定对于特定博弈子树及其后续步骤。 然而，我们的方法不是以去找如何否定子树为目标，而是使用浅层搜索来识别“好”的分支。 如果有多个这样分枝，多切割修剪假定会出现一个切割动作，从而阻止当前的博弈线更深地扩展。
-----------------------
注释说明：
1. 一些人工博弈的构建方式恰恰相反; 当演算最小极大值时，决策质量实际上随着搜索深度的增加而降低。 这种现象已被彻底研究，在博弈树搜索中被称为病理学[10]。 然而，在国际象棋或我们正在研究的其他游戏中没有看到这种病态。
在下面的章节中，我们简要介绍了博弈树搜索，并介绍了必要的术语和定义。我们介绍了我们的新修剪方案背后的基本思想，并提供了完整的技术基础。修剪方案本身也已经在一个实际的游戏程序中实现和测试。研究结果记录如下：首先建立了新的剪枝准则，然后在国际象棋领域进行了验证。最后，在得出结论之前，我们先解释一些相似的工程种要如何使用这种相互补充的思想的。
博弈树搜索
我们在这里研究关心的是两方零和完全信息博弈。这样一个博弈的重要点是双方都具备完美决策，并且可以通过递归地从每个游博弈状态扩展所有可能的延续，直到状态达到已知的结果。在此基础上，使用minimax规则将这些结果的值传播回初始状态。以这种方式展开的状态空间是一棵树，通常称为博弈树，其中树的根是初始状态，叶节点是终端状态。
2.1 极大极小值算法（Minimax）
使用极大化极小值算法。极大值（max）玩家移动到根，试图通过返回其子值的最大值来优化其收益。另一个玩家，极小值（Min），总是通过选择最小值来最小化Max的收益。然而，对于零和游戏，一个玩家的收益是另一个玩家的损失。因此通过从玩家决策选择的角度评估终端节点，并在它们备份树时否定这些值，可以将树中每个节点的值视当前行动的玩家的价值。这个框架被称为negamax[5]，它的优点是更简单、更统一，因为双方现在都在最大化他们的价值。我们使用这个框架作为后续讨论的基础。
至少在理论上，博弈的结果可以如上所述。然而，以这种方式扩展的博弈树的指数增长代价是令人望而却步的。因此，在实践中，游戏树只扩展到有限的深度D，并对产生的“叶节点”进行评估。它们的值使用minimax规则传播到树上，就像它们是真正的游戏结果值一样。备份这些值的规则可以按如下方式定义给出：
定义1（Vmm(n,d)）。一个扩展到指定深度d的博弈树的极大化极小值，Vmm(n,d)为
其中f（n）是一个评估函数，返回与节点n（相对于该点出度边）对应的博弈状态的真实值的估计值，sn是节点n的所有后续节点（继承者）的集合。
注意，这些叶节点的真实值通常是未知的，因为函数f（n）通常只能估计结果。通常，评估是一个衡量状态“优度”的数字。2 评估的确切含义并不重要；目的是提供叶节点的排名。价值越高，该状态越有可能获胜。同样需要注意，当d→infin;时，该方法简化为纯粹的无界极大极小搜索。
----------------
2 有时终端状态在搜索范围内是可达的，在这种情况下，估计是准确的。例如，在国际象棋中，老式状态是具有已知结果的终态。
算法1给出了一个计算深度受限博弈树的极大极小值的函数。函数mm（n，d）实现定义1。
最小的树和alpha-beta
找到一个博弈树的极小化极大值，并不是说必须要研究它的所有分支才行；只需要扩展一个所谓的极大极小树就可以了。因为极大化极小值仅取决于最小树中的节点；无论如何评估其他节点，根节点的值都不会更改。
最小树包含三种类型的节点：pv、cut和all节点。3更正式地说，我们可以如下确定最小树：
定义2（最小树）。对于一个pv节点或一个all节点，它们的每个子节点都是最小树的一部分，但是对于切割节点而言只有一个子节点是这样的。对于任何给定的博弈树，我们都可以通过如下标识其节点来获得最小树：
- 博弈树的根是一个pv节点。
- 在一个pv节点n上，至少有一个子节点必须要有其极小化极大值-Vmm(n)(当存在多个如此的子节点时，可以任意选择其中一个)。且该子节点也是一个pv节点，但是其他的子节点就都是剪切节点了。
- 在切割节点上，具有最小最大值Vmm（n）lt; Vmm（npv）的子节点n是all节点，其中n pv是n的最直接的pv节点前置节点。至少一个子节点必须具有该值；当有多个子节点时，可任意选择其中一个子节点。
- 一个all节点的所有子节点都是一个剪切节点。
从上面的定义可以清楚地看出，在任何博弈树中都可能存在不止一个最小子树，因为许多被切节点的子树都可以被界定为属于最小树。图1显示了一个广度一致、固定深度为3的博弈树示例。非着色节点表示一个可能的最小树。字母P、C和A分别表示pv、cut和all节点。
------------------------
3 Knuth和Moore[5]称这些类型为1、2和3节点，但这里使用了更具描述性的术语[8]，分别称它们为pv、cut和all节点。
Knuth和Moore[5]对alpha-beta剪枝算法进行了深入的分析，发现从任何最小子树的搜索中都可以找到最小最大值。搜索到某个节点n的一个子节点后，从该搜索返回的值是实际的极小化极大值n的下界。此外，此下界是对手的上界，可用于修剪n的其余子节点的子树（即标识不属于最小树的节点）。直观地说，如果对手找到一个使当前子树的值低于已在n处建立的下限的延续，则无需进一步搜索，当前节点将成为一个切割节点。下面的算法2显示了alpha-beta算法的Negamax公式。它通过分别命名为和的两个参数跟踪玩家可以实现的下限和上限。它跟踪玩家可以分别通过alpha和beta两个参数实现的下限和上限。在第9-10行检查修剪情况。如果移动返回的值大于或等于beta，则本地搜索将终止于该特定节点；这通常被称为beta切割（在算法的negamax公式中，alpha和beta切割之间没有区别）。为了确保找到树的值，alpha和beta的值分别初始化为负无穷和正无穷。
Alpha-beta 功能强化
alpha-beta算法的性能对检查树中节点的顺序很敏感。在最坏的情况下，它与minimax算法展开相同的穷尽树，而在最好的情况下，只需要遍历最小树。为了使alpha-beta算法达到最佳性能，必须首先在pv节点处扩展最佳策略子树，但在切割节点处，任何足以导致切断的移动都可以首先搜索。4 为了实现一个良好的移动排序，我们可以使用各种启发式方法（例如[13,14]），并且多年来，已经有人开发出了更有效的alpha;-beta;算法变体，充分利用了更好的移动排序。算法3，主变差搜索[6，7]就是这样一种变差。主驱动程序pvs探索预期的pv节点，而nws部分访问预期的cut-和all节点，使用pvs中建立的下限来减少搜索。直到搜索完节点后才我们才能知道它的真正类型。因此，在搜索过程中，我们将节点称为预期的pv、cut或all节点，这取决于我们对游戏树结构的当前视图。该算法将根节点（以及随后的pv节点）上探索的第一个节点视为pv节点。因此，该节点的值被视为最佳值，并使用NWS 程序搜索所有同级节点，以证明它们是劣等的。偶尔，其中一个同级返回一个更好的值，在这种情况下，算法研究该节点以建立新的主变量（第11-12行）。当以递归方式调用NWS（第22行）时，绑定被调整为一个等于估计函数返回值的最小粒度的值。例如，如果f（n）返回整数值，则设置为等于1。在第5节中，我们将展示如何将新的正向修剪方法融入到PVS算法中。
----------------------------------
4 由于存在不均匀的分支因子、实际搜索深度（通过搜索扩展=减少）的局部变化以及通过替代路径（换位）达到相同状态的可能性，许多可能的最小树的大小变化很大。为了提高效率，我们首先要搜索的不仅是一个返回足以导致中断的值的移动，而且是一个产生最小子树的移动。
选择性搜索
上面描述的所有算法都以深度优先的方式遍历博弈树。也就是说，在将注意力转向下一个分支之前，他们会充分探索树的每一个分支。它们都返回相同的极大极小值，主要的区别在于搜索效率：在更增强的算法中搜索较小的树（至少探索确定极大极小值所需的最小树）。存在一类不同的搜索博弈树的算法。这些算法以最佳的优先方式遍历树，通常比深度优先方法更有选择地搜索。他们暂时停止探索树枝去访问其他更有趣的子树，可能稍后会返回到废弃的树枝去更深入地搜索它们。然而，这些最佳优先算法通常不具有时间和空间效率，因此
资料编号：[4637]
