军旗游戏中的蒙特卡洛树搜索
Paolo Ciancarini lowast;, Gian Piero Favini
Dipartimento di Scienze dellrsquo;Informazione, University of Bologna, Italy
摘要
部分信息不确定情况下的决策游戏是很好的例子。特别是,一些游戏有这样一个巨大的状态空间和高度的不确定性,传统的算法和方法难以有效地运行。蒙特卡洛树搜索(mct)对计算机程序的水平带来了显著的提高，比如围棋游戏，,它已被用于部分信息游戏。然而,有些游戏特别单纯的mct的大树和减少信息方法是不够的:特别是,这是游戏长匹配的情况下,动态信息,和复杂的胜利条件。在本文中,我们探索的应用mct wargame-like棋盘游戏,军棋游戏。我们描述和研究三种MCTS-based方法,从一个非常简单的实现和搬到更精致版本特定的知识几乎为零的玩这个游戏。我们比较这些MCTS-based程序已知的最强minimax-based军棋游戏项目,获得更好的实验结果用更少的特定领域的知识。
- 介绍
部分信息游戏提供一个良好的模型和实验对于许多现实世界在不确定性的情况下涉及决定资金存放。他们作为一个计算机程序去完成是非常困难。这些游戏通常需要复杂的任务,如启发式搜索的结合,信仰规则重建和对手建模。
此外,一些游戏是特别具有挑战性的,因为随时可能的数量,无法区分的规则远远超过现在的计算机的存储和计算能力。在本文中,重点是一个这样的游戏,军棋游戏或看不见的象棋。这个游戏很有趣,原因至少有三个。首先,典型的代表是国际象棋,一个非常著名的游戏;然而，棋手觉察的范围是不同的,只能看到他们的一部分。其次,它是一个有巨大的数量的规则和有限的获取信息的手段的游戏。最后,不确定性的本质是完全动态的。这些问题把军棋游戏类别不同于其他部分信息游戏,比如西洋陆军棋或幻影围棋（部分信息围棋的变种）,其中新发现的信息对于剩下的游戏仍然有效。信息在军棋游戏是稀缺的,宝贵的,快速迭代的。
事实上,它甚至是一个古老的游戏,众所周知的博弈论者甚至讨论冯·诺依曼和Morgenstern[2]在盲棋下,在2005年第一次尝试构建一个基于蒙特卡罗抽样[3]的有效的军棋游戏程序。然而,它却被我们的第一个项目打败,在[4]中描述和基于极大极小的一种形式叫做metapositions博弈树的数据结构。这些被定义在[5]Shogi的变种的部分信息,这是日本国际象棋。我们的程序比其他程序好,但并不足以与人类最好的棋手媲美。
在本文中,我们目前研究在军棋游戏中使用不同方法进行蒙特卡洛树搜索。作为过去几年主要的游戏工具,蒙特卡洛树搜索已经得到了提高。传统的极大极小技术由于状态空间的大小和制定一个适当的评价函数的困难而不能产生良好的结果。围棋是主要的例子,尽管不是唯一的一个,一个艰难的环境在蒙特卡洛的极大极小树搜索能够大大提高计算机程序水平[6、7]。因为军棋游戏股票作为一个大型游戏的两个特点,一个难以表达的评价函数(与它对应的完整信息),这是再自然不过的测试类似的方法。
本文组织如下。第二部分包含高层介绍蒙特卡洛树搜索(mct),重点是其成功应用的幻影围棋。在第三节,我们介绍军棋游戏的游戏,它的规则和它相似但非常不同的幻影围棋。第四节包含军棋游戏最重要的研究成果,特别是那些与先前的蒙特卡洛方法。在第五节，我们给出了三个特定的高级视图方法,展示他们是相似的,不同的,相应的程序然后分别进行更详细的描述。
- 蒙特卡洛树搜索
蒙特卡洛树搜索(mct)是基于蒙特卡罗抽样的一些简单和旧方法的进化产物。虽然核心概念仍然是相同的——一个程序中大量的随机模拟游戏和挑选收益率最高的胜利的行动——比起纯粹的蒙特卡洛，它的特定的目的是使计算更快地收敛到正确的价值。这是通过指导模拟博弈树,随时间适应新的节点;更有前途的节点,在理论上,达到第一和访问更多节点可能没有实际作用。
蒙特卡洛树搜索是一个迭代的方法来执行同样的四个步骤,直到它的可用时间耗尽。这些步骤如下所示：
选择：该算法根据访问次数和平均值，从树中选择一个叶子节点。
膨胀：该算法可以任意添加新节点到树上。
模拟：该算法以某种方式模拟游戏的其余部分，一次或多次，并返回最终状态的值（或它们的平均值，如果模拟多次）。
反向传播算法：该值被传播到节点的祖先到根，并为这些节点计算新的平均值。
在执行这些阶段尽可能多的时间允许，该程序选择的根的孩子，已经收到了最多的访问，并发挥相应的行动。这未必一致选择平均值最高的节点。关于为什么平均最高的节点不作出一个很好的选择的讨论包含在[ 8 ]。
MCTS应该被认为是一种方法，而不是一个具体的算法，因为它不要求任何四个阶段的强硬政策。它没有真正指定如何选择一个叶子，当一个节点应该扩大，如何进行模拟，或者如何将它们的值传播到上面。然而在实践中对于上面的几个步骤研究，游戏程序更倾向于使用相同的算法变化。
选择一个任务是和n-bandit问题是类似的，因为程序需要之间取得平衡（花点时间探索新的节点）和开发（指挥模拟对已表现出的承诺，至此节点情况）。例如，程序使用UCT算法（置信上限用于树）在[ 6 ]第一次。该算法选择在每一个步骤的子节点其数量最大化。
其中VI是节点i的值，n是访问父节点的时间，Ni是访问的节点数量，和c是一个常数，有利于开发如果低，探索如果高。
扩展显着取决于正在考虑的游戏，它的状态空间和分支因子。在一般情况，大多数程序在访问了足够的次数后，将扩大一个节点。模拟也非常依赖于类型的游戏。有大量文献处理特定模拟围棋游戏策略。反向传播提供了使用哪个备份操作问题在计算节点的值。
2.1蒙特卡洛树搜索和部分信息在幻影围棋中的应用
蒙特卡洛树搜索已经成功地应用在大型、复杂的部分信息游戏,最明显的是幻影围棋。这个游戏的部分信息版本的经典游戏:玩家没有直接了解他的对手的棋子,但可以推断出它们的存在,如果他试图把自己的棋子放在一个十字路口,发现他不能。在这种情况下,他可以尝试另一个棋子。全面比较几个蒙特卡罗方法的幻影围棋，有或没有树搜索。我们对幻影围棋特别感兴趣,因为它的状态空间和分支系数远远大于其他(已经复杂)的部分信息游戏像扑克这样的好的蒙特卡洛策略的形成游戏。
幻象围棋的MCTS算法是比较简单的，他们主要是利用他们围棋同行的知识和方法：事实上，他们大多不去计划，因为在仿真阶段的不同程序每一次产生一个新的随机设置的对手的棋子，而不总是相同的。这是合理的，以怀疑这种方法在一个同样巨大的状态空间是否可以轻易的转换为其他游戏。或者说幻影围棋是一个特殊的情况，一个游戏，特别适合于MCTS。在下一节中我们将讨论军棋游戏,幻影围棋是什么围棋,并比较异同的两场比赛。
- 军棋
Kriegspiel，命名后，由普鲁士军队用来训练其军官的“战争游戏”，是一个发明的国际象棋变体，在十九世纪末变换成标准的国际象棋游戏。它已被研究由约翰·冯·诺依曼和Lloyd Shapley扮演的游戏理论家口径。它是在三个不同的棋盘，棋手每人一个加上裁判一个。他们以这样的方式，裁判看到所有的棋子，而棋手只能看到自己的。从裁判的角度，一个游戏的军棋游戏是一盘棋。然而玩家，只可以看到自己的棋子，而对手的是在黑暗中，仿佛隐藏的“雾的战争”。他转身，一个玩家选择移动和传达给他的裁判，因此两个对手之间没有直接通信。如果移动是非法的，裁判将拒绝移动，并要求棋手选择一个不同的。如果是合法的，裁判会通知棋手这一举动的后果，如果有的话。此信息取决于军棋游戏状况；看到[ 11 ]找出更多关于游戏。在互联网象棋俱乐部，其中最大的主机本场比赛的玩家，裁判的留言如下。
- 当此举是合法的,它不是一个检查或捕获,裁判会给任何信息,称“白色”或“黑了”。我们将称之为“沉默的裁判”因为走棋的棋手们没有接受任何信息。
- 当棋子捕获：在这种情况下,裁判会说捕获的棋子是否是兵还是捕获了其它棋子,但在后一种情况下他不会说捕获的是哪一种棋子。
- 当国王的玩家将在检查:在这种情况下,裁判将披露方向(或方向)
- 检查以下:等级、文件、短对角线,长对角线,骑士。
- 为了加快游戏中,当玩家拥有一个或多个捕获移动使用他的棋子,裁判将宣布(“兵试”),但不会告诉兵可以执行捕获。
- 比赛结束后,裁判宣布任何标准条件的将军或绘制游戏(如僵局或没有足够的材料或位置重复了三遍,等等)。
这些规则也应用于国际计算机奥林匹克竞赛，其中军棋比赛已在2006年和2009年举行。
表面上看，军棋和幻影围棋很相似。保持相同的规则，其完整的信息版本，只是增加了一层在战争迷雾的形式的不确定性由裁判员管理。一种军棋游戏记录是一个合法的棋牌游戏，就像一个幻影围棋游戏的成绩单是一个法律去游戏。两者都涉及移动尝试作为他们的核心机制；我非法尝试提供对游戏的状态信息。在这两个游戏中，玩家可以故意尝试移动只是为了信息收集的目的。另一方面，在两个游戏中也存在值得一提的差异。我们列出了一些最重要的区别。
- 不确定性的军棋游戏本质是强动力：而围棋的棋子，如果不是一成不变的，至少基本上是静态的，一旦发现永久性地降低不确定性的一大因素，信息在兵棋时代和快就过时了。一个需要考虑的不确定性意味着在这两场比赛中同样的事情，军棋在这方面是一个严酷的战场。
- 还有，军棋裁判可以回短信几十个组合，相比于幻象围棋的两回合，这使得更好的建立博弈树更加困难。
- 在幻影围棋始终存在一个序列的非法动作，将揭示游戏的全状态和消除不确定性；在军棋没有这样的东西存在。除了在比赛结束的时候，没有序列的走棋能揭示的裁判的棋盘。
- 在幽灵围棋不确定性增加得更快，而且在残局自动减少。相比之下，军棋游戏当棋子被抓获时不确定性永久降低，这很难保证发生。
- 在幽灵围棋，玩家的能力，以减少不确定性增加的游戏进展，因为有更多的对手的棋子，但这种额外的信息的效用往往会降低，因为关于它可以做的越来越少。在军棋游戏正好相反：就像战列舰，因为有较少的棋盘上的敌人和更少的盟友打他们，玩家有一个更难时间的进步，但任何信息都可以给他一个主要的优势。
- 比较它们的完整信息，最主要的差异是胜利条件。军棋游戏中获得胜利在任何时候都可以突然发生，而围棋则与分数的积累有关。从蒙特卡洛法的角度，分数累积的游戏往往比基于状态的游戏更容易。如果条件在一个任意的游戏中很难观测到，即使有相当大的实际优势，一次罕见的随机走棋可能造成将死。
因此，混合比较两个游戏得出的结果。至少，它们代表两种不同的不确定性，可以最好地描述为静态与动态不确定性。我们希望研究蒙特卡罗方法的有效性,特别是其特定的上下文中,动态的不确定性。
- 相关工作
研究军棋可分类如下。在上世纪70年代最早的文件处理实现军棋裁判的协议在这我们并不研究。研究如下年重点解决的军棋游戏的特定亚群，尤其是一些简单的残局。在2005年左右，出现军棋整个游戏的第一个严格的程序。我们讨论这些，有两个重点：蒙特卡洛和一个基于最大-最小的算法。
- 三种蒙特卡洛搜索算法
在本节中，我们提供三种蒙特卡洛树搜索方法玩军棋，我们标签A，B和C这些方法总结在图2可简述如下。方法一是MCTS算法保持尽可能忠实于文献，特别是现有的幻影围棋方法。在该算法中，一个可能的游戏状态随机生成W每个动作都是随机的和模拟，以及游戏是模拟自然的结束。方法B是MCTS，程序不会尝试生成对手的板的演化；而广告，只有裁判的消息是模拟的。换句话说，游戏模拟的观点从一个球员的局部点而不是裁判的无所不知的人。C是一个简化的近似方法方法B的算法可以通过切削仿真后仅一个移动探索更多的节点。
选择实现的节点计划的举措,如伪代码:对手在仿真中扮演相同的伪随机移动一步。选择不同的勘探常数c值对性能没有任何影响。主要有两种方法在幻影围棋中来猜测对手的未知的棋子:随机opponent-move猜测和概率opponent-move猜测。在前,一些棋子添加为对手走棋,其余的都是之前仿真的步骤,在后者,棋子被添加后,第一步根据他们走棋的频率在第一步。有人指出早期猜测优于晚期猜测。
一个有效的蒙特卡洛树搜索军棋程序需要收敛到一个更好的价值，更不用说更迅速，比方法A.减少大量的具体实现在模拟步骤中的噪声也是非常重要的。可见，在个别情况蒙特卡洛搜索，为标准的情况将决定，导致高度不稳定的结果。一个可能的解决方案可以放在运行模拟，但不是在个别游戏状态-而是，他们的看法，从电脑玩家的角度来看。这将节省我们的麻烦，无论是计算ND算法，产生合理的游戏状态，奖励智能发挥模拟。
方法C作出大胆的假设，估计方法B的抽象模型k = 1的值是真理，或至少接近真理，一个人可以得到。因为模拟假定通过加权平均，立即收敛，备份运营商也改变了从平均值到最大节点值。当然，这是最快的仿真策略，模糊了LIN仿真和UCT驱动评价函数之间（或者，更准确地说，一个成本函数中的寻路算法），它可以从一个节点到下一个非常不连续。如果接近我的成功，它意味着信息在军棋很稀少，这种短暂的性质，通过模拟更长的游戏相当有限，相比于全部勘探效益在短期精度。这强调选择策略模拟策略。另一种思考C方法的方法是模拟发生在树上。
有两个主要结论,从我们的实验。首先,他们表明蒙特卡洛树搜索算法能够在合理的时间内收敛到好的结果即使是在像军棋游戏一样非常困难的环境下,其漫长的模拟可能起初似乎是一个重要的方法的缺点。然而,应用蒙特卡罗方法必须精心设计。事实上,我们无法达到良好水平的发挥通过生成随机状态和运行模拟。相反,我们必须抽象的游戏模式,在这种模式中
全文共5960字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[144296]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
