英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
Rminimax:一种最优化的随机极小极大算法。
Silvia Garcia Diez, Jerome Laforge和Marco Saerens。
摘要
本文提出了用于零和双人游戏的名为Rminimax算法，这是著名的MINIMAX算法的简单扩展。Rminimax算法通过以最佳方式随机化人工对手的策略来控制其强度。特别是，将人工智能(AI)应用于更糟糕或更好的解决方案，从而控制其强度。换句话说，我们的模型旨在将有限理性引入到极小极大算法中。这个框架通过在探索代价和探索深度中做出最优的选择，来考虑所有最优的选择。与其他的树探测技术相反，这个新算法考虑了树的完整路径，其中给定的熵是分布的。通过简单的递归关系有效地计算最优随机策略，同时保持与原始MINIMAX相同的复杂度。因此，Rminimax以一种原则性的方式为棋盘游戏实现了一个非确定性的强度适应性AI对手，从而避免了完全理性的假设。在两个游戏上的模拟显示，Rminimax的表现与预期相同。
介绍
人工智能技术[18], [23]，[31]广泛应用于现实行为视频游戏[20], [36]。这些方法的目的是寻找运动的路径，与计算机实体进行协作，学习过去的经验，提出游戏策略等。本文的重点是寻找完全信息零和双人游戏的策略[21], [24], [27]，如国际象棋和跳棋。这些游戏可以被看作是一种交替的游戏，从一个玩家到另一个玩家，在这个游戏中，要使当前玩家的利润最大化，对手最小化。这通常会使用众所周知的minimax算法[18], [20], [23], [31], [36]，大多数棋类游戏中都是直接或间接使用的(参见第I-A节，以更详细地介绍MINIMAX)。
从一开始，MINIMAX就假定双方都是完全理性的，因此，当遇到相同的情况时，玩家将采用相同的确定性策略。由于AI玩家的行为是完全可以预测的，游戏可能会让对手感到厌烦。本文通过提出一种简单的方法，将该策略随机化，同时仍保持最佳状态，从而解决了这一问题。其主要思想是控制博弈树的传播随机性，通过其香农熵进行量化，并为该熵选择最优的最小期望成本策略。这样，好的(低成本的)随机策略得到了青睐，而坏的(高成本)则被抛弃了。在博弈树的开发与探索之间进行权衡，因此，玩家的强度是通过改变熵来实现的。换句话说，模型的目标是将有限理性(见[29]和[43])引入到极小极大算法。该方法被称为Rminimax，是随机最短路径(RSP)框架[32]在博弈树中的应用。
总之，Rminimax的贡献是，通过模拟非理性的玩家，来控制玩家的强度，避免玩家的完全可预测性。
图 1 Minimax算法的例子
Minimax算法
基于对手是完全理性的前提下，minimax算法为双人零和游戏计算最优策略。为了说明minimax算法，假设有图1这样的博弈树， 最初只有叶节点的效用值被定义了。一旦子节点效用值已经被定义，max玩家pi;1就会获得子节点的效用值（utility value）的最大值，min玩家pi;2获得子节点的效用值的最小值。minimax算法就会递归地在博弈树的节点上进行操作，最终求出根节点的效用值，在图中根节点的效用值为7。
相关工作
由于MINIMAX的本质是搜索整个博弈树，因此减少搜索空间很有必要。最简单的方法是使用n-ply lookahead 策略[18]来限制搜索深度。另外，alpha-beta剪枝技术也很常见[22]。alpha-beta算法使用窗口将不相关的子树剪掉，因为这些子树永远不会成为最优策略的一部分。在[39]中提出了alpha-beta剪枝算法的多玩家版本。该算法[28]进一步降低了这个窗口的大小，拥有比AB更快的剪枝速度。尽管如此，这棵树可能会被大量的剪枝，从而导致了好的策略的消除。类似地，内存增强的测试驱动程序(MTD)[26]将AB窗口的大小限制为零。虽然这个剪枝算法更快，但最初的“猜测”，也就是最小的位置是必需的。这种算法也基于transposition tables，这些表在拥有巨大的搜索空间的游戏被使用。在搜索空间中经常出现重复的状态，“记住”这个决定比重新做整个搜索更有效。尽管MTD在搜索节点的数量上超过了NegaScout，但它仍然受到稳定性问题的困扰，它依赖于transposition tables，而且它对初始猜测也非常敏感。最后，在[30]中提出了一种计算持续搜索期望值的剪枝技术。已经证明[30]，这种方法也存在数值不稳定性。
opening book[5]是另一种应用于大型搜索空间游戏的改进技术。高效的开局和终局游戏策略被存储在book里面。事实证明，最初的策略对于减少搜索空间，以及引导游戏走向获胜状态至关重要。然而，即使搜索空间减少，交互时间仍然是必须考虑的关键特性。在计算时间未知的情况下，迭代深化技术可能是有用的。这样，一个策略可以随时交互，但是它的质量取决于最后一棵被探索的树的深度。通常，这种技术被用来选择一些具有较小深度的好策略，并通过进一步扩展来验证。静态剪枝[12]避免搜索树的分支，其启发式函数值是稳定的，因此没有变化。极大极小值也被扩展到像西洋双陆棋这样的偶然游戏。游戏树的一种版本，它有一种新的“机会”节点，代表游戏的概率状态(在[19]中提出了掷骰子的方法）。最后，通过一个启发式函数计算[2]得到正确得分的概率的随机方法。
在博弈论的文献[21], [24], [27]中可以找到一种涉及随机化策略的不同方法。混合策略是游戏中除了纯策略外的另一种选择，在游戏中，一些决策者相互作用，以最大化他们的回报。玩家必须在一组可能的动作中进行选择，每个动作都有相关的成本或奖励。与纯策略相比，混合策略允许玩家使用给定的概率p进行操作。paction isin;[0,1]。这些概率通常是通过博弈的纳什均衡来计算的，这与玩家A在考虑玩家B的决定时可以采用的最佳策略(预期收益)相对应。虽然具体的比赛对对手来说仍然未知，但他的动作的概率是预先知道的，让比赛变成假的。对双人回合的随机游戏的这些策略的扩展是随机游戏[33]。该技术试图通过选择一个最优策略来最大化一个玩家的期望收益，并且它的计算一直是几个研究 [25], [37] 的主题。
然而在AI社区中，很少有人关注如何给双人零和游戏的玩家强度建模。一个基本的方法是使用n层的lookahead算法[18]，以调整对手的能力。不幸的是，n可能很难调整，因为它取决于游戏和分支因素，对于非常低的值（nlt;6），AI很容易被人类打败(通常情况下，人类会提前想到6到8步)，而对于非常高的值(n gt; 8)，AI可能会变得难以战胜。另一个常用的技术是ε-greedy[41]，AI以1-ε的概率走最优的分支，走其他分支的概率遵循均匀分布，以ε/number_branches的概率采用其他分支。Boltzmann探索[41]，其中取分支的概率遵循Boltzmann分布的逆温度，这依赖于特定于状态的探索系数以及基于增加噪声的技术的评价函数。然而，这些技术关注的是当前的状态，这将他们的策略限制在局部决策上，无法找到给定的熵下的全局最优策略。
有限理性的概念已经在大量领域中得到应用，这些领域包括心理学和人工智能。在这最后一个类别中，我们从[43]找到了相关的研究，在这篇文章中，作者展示了博弈论与统计物理学之间的联系。他展示了香农的信息理论是如何为有限理性博弈理论提供框架的。特别是当我们知道玩家的混合策略和他们的预期成本时，玩家的可能行为的概率分布应该遵循Boltzmann分布。然而，作者并没有为他的思想提供一个精确的算法实现。这篇论文可以被看作是这些想法在双人零和游戏下的具体的实例。嵌套蒙特卡罗搜索[7]在博弈树的基础上的另一个有限理性算法，它将嵌套调用与随机性相结合，并且将最佳的移动序列记录下来。
本文提出的方法不仅关注于为对手的强度进行建模，而且还通过增加概率的方法来改善minimax的AI，使AI表现得更像人类，同时还保存最优策略。
Randomized minimax
MINIMAX已经被广泛应用于在双人零和游戏中模拟对手。尽管它在大多数情况下非常有用，但是它也有一些缺点。首先，对于两个玩家拥有完全理性的假设是不现实的，因为人类玩家经常会犯错。其次，它并没有解决某些游戏的搜索空间太大的问题，因此，使用启发函数通常是必要的，然而启发函数通常很难定义。第三，玩家的行为是确定的，因此是可以预测的。第四，就Minimax算法的最基本形式而言，控制玩家的强度是不可行的。本节的方法克服了这些缺点。
从博弈树可以看出，确定性策略导致从根节点(初始状态)到叶节点(终止状态，游戏的输赢)的路径是确定的。MINIMAX选择了最大化当前玩家增益的路径，同时最小化对手的增益。本文介绍了一种极大极小的变体，它将随机选择博弈树的所有可能路径。这种方法的优点有三:第一，避免了确定性策略，从而消除了游戏的可预测性;其次，没有假定玩家的完全理性;第三，可以控制玩家的强度。虽然本文没有解决搜索空间的问题，但是任何对于minimax有效的技术，都可以被用来减少被探索树的大小。
RSP framework
由于本文引入的Rminimax算法严重依赖于RSP模型，为了使本文尽可能独立，本小节提供了RSP框架的简短描述。有兴趣的读者请参阅原文[10], [32]来了解详情。
最初的RSP框架受到随机运输模型[3]的启发[0](参见[32]或[10]，用于在非循环图的特殊情况下进行替代推导)。让G是包含索引1的源节点和带有索引n的目的节点或目标节点的有向图，而且目标节点是吸收的;一旦节点n到达，路径停止，即从n中没有传出弧，非负的局部成本。与每一个弧相关。如果有许多目标节点，可以使用以下技巧:创建一个虚拟节点n，并添加每个目标节点与虚拟节点n之间的零成本弧。从1到n的所有路径(包括循环)的集合记为P1n。每个路径weierp;isin;P1n 是由一系列弧线组成的。这将源与目标节点绑定在一起。此外,让总成本C(weierp;)的路径weierp;是沿着weierp;这些局部成本的总和。路径随机化将由全局表现驱动;概率将分配到每个路径,有利于近最优路径有一个低成本C(weierp;)。因此，最优或稍微接近最优路径将被分配一个高概率，而导致高成本的路径将被惩罚。
Rminimax算法
运用RSP框架，使我们可以通过增大或减小theta;来使AI倾向于做出更好或更坏的选择。注意,当theta;值高,算法策略选择的AI球员pi;1而对于小价值，他会用一个糟糕的策略来塑造一个弱小的对手。作为一个例子的影响不同的theta;跃迁概率,让我们考虑以下情况:假设一个简单的二元博弈树只有三层,当前节点是根节点,目的是达到一个成功的节点,相关奖励(见仿真方法在第三节更多细节),玩力量theta;。每场比赛的费用是 1。一旦计算了所有的量，就得到了表I中所示的结果。必须注意到,当theta;→infin;,给出的最优策略极大极小算法恢复。theta;减小,过渡概率更偏向的最佳解决方案。在theta;→0时,分配的成本变得无关紧要,因此,战略是完全随机的概率p(几乎是均匀分布)。
类似的方法(虽然不是最优的)可以在强化学习中找到[6], [14], [35], [41]。在[6]的多主体系统中，典型的探索方法被纳入到强化学习中。其中一种方法是Softmax[40]技术(也称为Boltzmann探测)，它基于一个实用函数在每个可能的操作(树的分支)上应用Boltzmann分布。如[42]所述，玻尔兹曼分布提供了一种将随机勘探与开发结合起来的方法，而选择一个动作的可能性按其效用指数加权。在[9]中提出了另一种基于bandibase的方法，该方法能够高效地“削减”次优分支，并具有较高的可信度。这种技术还允许控制对树的探索和开发之间的权衡。最终,[8]提出了应用围棋的强盗技术,探索的偏见树根据先前的信息(如状态一直探索的次数或它导致了胜利的次数)找到最合适的策略探索。然而，大多数这些技术最终找到了一个最优策略，停止了对图形的探索，从而失去了它们的随机行为。另一方面，我们可能会发现[14]中提出的强化学习技术，它不断地探索图形。然而，最优政策的趋同已不能再被证明。
仿真结果
A. 有全博弈树的Rminimax
为了更好地了解Rminimax的行为，它首先被应用于由MINIMAX算法生成的全博弈树的井字游戏。为了想象我们的方法的性能,当两名球员不同的优势互动,100运行两个玩家之间进行不同强度的theta;。根据我们之前所述的模拟方法，在应用Rminimax时，两个玩家的性能都被记录下来。测试的值theta;是theta;1 =theta;2 = { 0.1,0.5,1,5,10}。
结果曲线如图2所示。可以观察到，所有的曲线都有相似的形状，但从不同的水平开始。这可以转化为AI玩家行为的高度相似。当theta;1gt;gt;theta;2 ，玩家1赢，而对theta;1lt;lt;theta;2 是玩家2在游戏中领先。这种行为符合我们预期,至于theta;→infin;，熵是0,因此，玩家选择一个最优策略,反之亦然。在theta;= infin;，游戏可以减少极大极小的策略。水平曲线开始依赖于theta;值之间的差异。
另一方面,曲线的斜率反映pi;1相对于pi;2的优势。实际上,当pi;1 首先行动时,它有一个优势。这可以观察到在图2中,在一个较低的斜率的theta;值显示为pi;2。
图
B. 有五层前瞻和启发式的Rminimax。
人工智能的另一个常用工具是启发式和评估功能[31]。本节研究了使用局部博弈树与启发式算法相结合的方法的性能。在这个实验中，被调查的游戏是connect4。当生成完整的游戏树时，计算代价很高，在这里实现了一个五层的lookahead方法，并结合使用启发式
全文共6421字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[12364]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
