《硕士学位论文－时序差分学习在非完备信息机器博弈中的应用.doc》由会员分享，可在线阅读，更多相关《硕士学位论文－时序差分学习在非完备信息机器博弈中的应用.doc（64页珍藏版）》请在三一文库上搜索。
1、 工学硕士学位论文时序差分学习在非完备信息机器博弈中的应用*工业大学2008年-国内图书分类号：TM151.3国际图书分类号：621.3工学硕士学位论文时序差分学习在非完备信息机器博弈中的应用硕士研究生 ：导 师 ：申 请 学 位 ：工学硕士学科、专业 ：计算机科学与技术所在单位 ：答辩日期 ：2008年授予学位单位：*工业大学Classified Index: TP399U.D.C: 621.3Dissertation for the Master Degree of EngineeringIMPERFECT INFORMATION GAMES BASED ON TEMPORAL DIFFE
2、RENCE LEARNING Candidate:Supervisor:Academic Degree Applied for:Master of EngineeringSpecialty: Computer ScienceAffiliation: Date of Defence:2008Degree-Conferring-Institution:*工业大学工学硕士学位论文摘 要完备信息博弈已经有很多应用比较成功的解决方案。当电脑走棋的时候，根据当前棋局创建一个部分的博弈树，利用估值函数对叶结点进行估值，通过估值的结果来进行极大极小值搜索，找到一个在根结点的最佳走步。这是很多的人工智能程序的核
3、心架构。然而，迄今为止非完备信息下的非常成功的人工智能博弈程序很少。非完备信息博弈问题的解决技术和完备信息有很大的差异，应用于完备信息的技术不一定能够成功的应用到非完备信息博弈中。在非完备信息博弈中，博弈双方仅拥有当前游戏状态的部分知识。在信息不明了的情况下，随机策略成为一个可行的选择。例如，对于桥牌游戏来讲，在评估玩家的出牌时，蒙特卡罗技术对各张看不到的牌进行抽样，随机的确定这些牌的种类，然后对获得的完备信息牌局进行极大极小值搜索，就好像每个玩家都知道所有的牌是什么一样。上述过程多次进行，选择平均来说最好的出牌。时序差分学习是机器学习领域强化学习技术的一种。传统的学习技术通过预测值和真实结果
4、之间的差值来调整描述状态的各种参数，而时序差分学习根据连续的预测之间的差值来调整。对现实生活中的大多数预测问题来说，时序差分相对于传统方法而言需要更少的内存，更低的计算时间复杂度。时序差分侧重于对运算效率的提升，结果和传统学习方法比较接近。本文探讨了时序差分学习在非完备信息机器博弈估值函数中的应用，并基于该算法结合蒙特卡罗抽样技术实现了一个具有自学习能力的四国军棋博弈系统。本文的主要研究成果和创新之处在于：1. 进一步扩充和精确化了四国军旗博弈中的蒙特卡罗抽样技术；2. 在已有四国军旗系统搜索框架的基础上，对估值函数、搜索算法等进行了优化，实现了适用于四国军棋游戏的历史启发搜索算法，大大提高了
5、搜索速度；3. 实现了四国军旗系统中基于时序差分学习的估值函数，可以动态调整智能体的行为。关键词 时序差分学习；非完备信息博弈；蒙特卡罗抽样；静态估值函数I*工业大学工学硕士学位论文AbstractThere are many successful solutions to perfect information games. When it is the computers turn to move, it creates some part of the game tree starting at the current position, evaluates the leaves of
6、this partial tree using an evaluation funcion, and then does a minimax search of this tree to determine the optimal move at the root. This idea is the core of many game-playing programs. However, there have been far fewer successful programs in the domain of imperfect information games. The solution
7、s to games with perfect information and those with imperfect information are very different. The techniques that apply to some do not usually apply to the others.In games of imperfect information, players have only partial knowledge about the current state. For the challenge of information gap, the
8、only way to deal with this is to use randomized strategies. Take the Brige game for one example. When evaluating a players choices, the Monte-Carlo method randomly deals the remaining unseen cards. Then the game is searched using minimax as if these cards are all known to all the players. This is do
9、ne a number of times and the move that is best on average is chosen as the final best move.Temporal Difference (TD) learning is a kind of Reinforcement Learning method.The conventional prediction-learning methods adjust itself by means of the difference between predicted and actual outcoms whereas T
10、D adjust itself by means of the difference between temporal successive predictions. For most real-world prediction problems, temporal-difference methods require less memory and less computation than conventional methods; and they produce more accurate predictions.This paper studies a machine learnin
11、g method- TD(), a kind of temporal difference learning in the evaluation function of imperfect information games.We combined MonteCarlo Sampling with TD and developed a program SiGuoJunQi which could adjust itself in practice. The main contributions and innovations are as follows:1. The Monte-Carlo
12、sampling framework is advanced and optimized;2. Based on the traditional game tree search model, a more effective and efficient model is proposed, including board representation, search method and evaluation function. A variant of history heuristic search method is applied in SiGuoJunQi. It can grea
13、tly reduce the computation complexity.3. The temporal difference learning machanism in the evaluation fucntion is discussed. An improved algorithm based on TD is also presented. The Agent in the Temporal Difference learning system can adjust its behavior and gain useful knowledge from the outside en
14、vironment. Keywords Temporal Difference Learning, Imperfect Information Game, Monte-Carlo Sampling, Static Linear Evaluation FunctionII*工业大学工学硕士学位论文目 录摘 要.IAbstractII第1章绪论.11.1 课题背景11.2 非完备信息博弈研究的目的和意义.11.3 时序差分学习研究的历史和现状.21.3.1 时序差分研究的历史21.3.2 时序差分研究的现状31.4 课题主要研究内容及论文结构.3第2章 基于蒙特卡罗抽样的非完备信息博弈52.1 完
15、备信息博弈.52.1.1 机器博弈系统52.1.2 机器博弈中的搜索算法72.2 非完备信息博弈和蒙特卡罗抽样.102.3蒙特卡罗抽样过程示例.132.3.1 对当前世界的猜测过程142.3.2 最佳走步链表的建立与查询172.4 本章小结.17第3章 基于时序差分方法的非完备信息博弈.193.1 时序差分方法原理.193.1.1 强化学习模型193.1.2 马尔可夫决策过程193.1.3 动态规划值迭代技术223.1.4 强化学习中的蒙特卡罗技术253.1.5 值函数估计时序差分263.2 时序差分在非完备信息博弈中的应用283.2.1 泛化时序差分学习技术283.2.1非完备信息机器博弈中
16、的时序差分学习313.2.2 时序差分调整过程示例333.3 本章小结.34第4章 四国军旗机器博弈系统.354.1 四国军旗系统简介.354.1.1 数据表示354.1.2 搜索算法364.1.3 估值函数384.2 实验结果分析.394.2.1 搜索算法394.2.2 实战棋局分析404.2.3 蒙特卡罗抽样过程414.3 本章小结.45结 论.46参考文献.49附录1.52攻读学位期间发表的学术论文54工业大学硕士学位论文原创性声明.55工业大学硕士学位论文使用授权书.55工业大学硕士学位涉密论文管理.55致 谢.56工业大学工学硕士学位论文第1章 绪论1.1 课题背景目前，对于解决二人
17、完备信息机器博弈已经有了一套基于搜索的通用技术，二人完备信息游戏诸如国际象棋、中国象棋等，机器棋手的博弈水平已经超过了人类的顶尖棋手1 2。2006年8月，在象棋大师与浪潮天梭的人机大战中，总的成绩人方以2胜5和3负惜败于超级计算机浪潮天梭3。而非完备信息机器博弈领域的相关研究还不十分成熟。然而，到目前为止，对于非完备信息博弈，还没有能够达到世界级大师水平的机器程序。而现实生活中所要面对的博弈问题大部分属于非完备信息机器博弈的范畴，所以，在非完备信息多人机器博弈中如何提高人工智能体的棋力，具有更广泛的现实意义。本文将一种机器学习算法时序差分学习引入到机器博弈的研究中，分析和比较了国内外机器博弈
18、领域的几种搜索算法，结合蒙特卡罗抽样技术对非完备信息多人博弈进行了探索性的研究。以四国军旗这种典型的非完备信息多人游戏来验证本文给出的时序差分算法的有效性。四国军棋是我国特有的一种棋类游戏，其复杂度要超过国外流行的同类游戏如桥牌和扑克。本文通过将时序差分学习算法融合进估值函数，同时结合在桥牌和扑克等游戏中取得成功的蒙特卡罗技术来处理非完备信息，设计并实现了一个四国军旗机器博弈系统。1.2 非完备信息博弈研究的目的和意义人工智能研究如何用计算机去模拟、延伸和扩展人的智能，如何把计算机用得更聪明，如何设计和建造具有高智能水平的计算机应用系统，如何设计和制造更聪明的计算机以及智能水平更高的智能计算机
19、等4。非完备信息机器博弈作为人工智能的重要研究领域，是检验人工智能发展水平的一个重要方面。博弈是人类社会中普遍存在的社会现象，小到益智游戏、各种争论、各种场合下的讨价还价，大到商家的竞争、国家的外交、各种流血和不流血的战争，只要局中的双方主体存在着某种利益冲突，博弈便表现为矛盾表现和求解的一种方式5。和完备信息博弈不同之处在于，非完备信息博弈中的博弈方由于无法获得所有的信息知识，因而无法准确预知对手会采取哪些对策。这和社会中商业竞争、军事战争等的情形十分类似，它的研究对于建立现实社会的决策支持系统有很强的参考价值。 1947年，Neumann和Morgenstern提出的博弈论6中，几乎所有的
20、工作集中于非完备信息的博弈。博弈论大部分用来处理现实生活中的模型，尤其是经济生活中的应用。现实生活中，完备信息的情况是很少的。在完备信息中，最优策略是一目了然的，但是非完备信息只能采用随机化策略(randomized strategies)来解决。1994年Bampton提出了蒙特卡罗抽样方法来解决非完备信息博弈问题7。他使用扑克作为典型案例来进行研究，首先随机的确定牌的种类，获得一个完备信息的牌局，然后使用极大极小树来进行搜索。进行多次抽样搜索后，选择平均情况下最好的那个出牌。加拿大Alberta大学的红心大战程序结合时序差分学习技术实现了一个自学习的系统8 9。工业大学深圳研究生院智能计算
21、研究中心对非完备信息机器博弈进行了立项研究，在国内尚属首例。1.3 时序差分学习研究的历史和现状1.3.1 时序差分研究的历史时序差分在棋类游戏中的应用有着很长的历史。时序差分学习技术最早是由Arthur Samuel发明的。1959年Arthur Samuel编制了一个通过和自己下棋来进行自学习的checker程序10。受到Samuel程序中的学习算法的启发，1988年Sutton提出了TD()算法11。Tesauro的TD-Gammon是TD()算法最成功的应用之一1213。它使用了人工神经网络，棋力可以和最好的backgammon人类棋手相媲美。很多作者已经讨论过TD()算法特别适用于b
22、ackgammon游戏的原因14 15。TD-Gammon从几十万个游戏棋局中进行自学习，它的估值函数是位置的一个平滑函数，这使得它可以比较容易的构建一个很好的人工神经网络来进行模拟。同时，由于backgammon游戏的随机性，TD-Gammon仅仅向下搜索一步，这样的浅搜索已经能够很好的对抗人类了，更深的搜索并不能大幅度的提高棋力(最新版本的TD-Gammon搜索三步深，但棋力的提高并不显著)。与之形成对比的是，为国际象棋、黑白棋和围棋找到一个恰当的人工神经网络，期望仅搜索一步深来达到人类的水平，是非常困难的。Baxter和Weaver提出了TD()算法在极大极小值搜索中的变种-TD-Lea
23、f()算法，并将之应用于国际象棋，开发出了KnightCap程序16。KnightCap仅仅下了308盘棋后积分就从1650升到了2100，人类初级棋手的积分为1500左右，KnightCap已经到达了中级棋手的水平。1.3.2 时序差分研究的现状时序差分学习最近研究的比较多的有时序差分网络(Temporal Difference Networks) 等17 18。时序差分网络可以对动态系统的知识进行学习和表示，通过预测向量的形式来描述动态系统的状态。蒙特卡罗抽样技术在被用来解决非完备信息博弈和非确定性信息博弈问题时取得了成功。在这种类型的游戏中，搜索的全空间过大，所以只选择全空间中一些具有代
24、表性的抽样来给出一个概率上能够承认的走步。这种方法已经成功的应用在了桥牌、扑克和纵横拼字游戏上。如果可以蒙特卡罗抽样技术和时序差分学习以一种有效和稳定的方式结合起来，就可以对非完备信息机器博弈中智能体的行为产生很大的影响。机器博弈领域是人工智能算法广为应用的一个领域。国内外的学者们已经对机器博弈作了广泛而深入的研究，然而非完备信息机器博弈领域的相关研究并不多，程序的效果也并不显著。军旗同牌类游戏中的红心大战、桥牌等都具有非完备信息的特点，它是我国特有的一种游戏类型，工业大学深圳研究生院智能计算中心在国内首家对其进行了立项研究，该中心开发的四国军旗机器博弈系统能够较好的模拟人类的智能 。本文在此
25、基础上做了进一步的研究，把时序差分学习和蒙特卡罗抽样算法结合起来，对非完备信息机器博弈领域作了一些相关的探讨和分析。1.4 课题主要研究内容及论文结构本论文共分为4章。第1章是绪论，介绍了时序差分的相关背景、对非完备信息博弈进行研究的目的和意义，以及时序差分研究的历史与现状。最后给出了本论文的主要研究内容及论文结构。第2章是基于蒙特卡罗抽样的非完备信息博弈。这一章首先讲述了完备信息机器博弈的研究成果和机器博弈系统的构成，并在此基础上详细介绍了蒙特卡罗抽样方法的执行过程，最后使用具体的例子来说明抽样过程。第3章是时序差分学习算法原理。本章首先介绍了强化学习的主要模型和技术，接着讨论了时序差分方法
26、，最后给出了基于时序差分学习的非完备信息博弈算法。第4章是四国军旗机器博弈系统。本章首先分析四国军旗系统的基本架构，然后给出了对原来四国军旗机器博弈系统的几个方面的优化，最后分析实验结果。47工业大学工学硕士学位论文第2章 基于蒙特卡罗抽样的非完备信息博弈2.1 完备信息博弈2.1.1 机器博弈系统一个基本的机器博弈系统主要包括四个部分：棋盘的表示方法、走法产生机制、博弈树搜索引擎和估值函数19，如图2-1所示。图2-1 一个机器博弈系统的构成Fig.2-1 Structure of a Games System棋盘表示方法通过使用一种合适的数据结构来描述和表达棋局，根据具体的博弈系统采用恰当
27、的数据结构，使得在这些数据结构上进行操作时的时间复杂度和空间复杂度都较小。例如对于中国象棋而言，我们可以采用下面的表示方法：使用一个字节表示一个特定的棋子，使用一个109的字节数组来表示棋局。象棋棋子种类为14种，加上没有棋子这种状态(可以使用0X00来表示)，共15种状态，而一个字节可以表示256种状态，完全可以表示所有的棋子。我们可以使用每个字节的前4位来表示棋子属于红方还是属于黑方(例如前4位是1表示是红方棋子，是2表示是黑方棋子)，使用每个字节的后4位来表示棋子的种类(如后4位是1表示是车，是2表示是马等)。这样我们如果想获取棋子的所属方，只需要右移4位后判断是1(表示红方棋子)还是2
28、(表示黑方棋子)，就可以确定了，而计算机进行移位运算的速度是很快的。109的数组中的每个位置分别对应棋盘上自左而右、自上而下的各个位置。例如数组中的第0个位置对应棋盘左上角的那个位置，第89个位置对应棋盘右下角的那个位置。这样表示的优点是直观形象，容易分析识别。 图2-2 中国象棋棋盘的数据表示Fig.2-2 Board Representation of China Chess走法产生机制是根据游戏的规则判断走步的合法性，也就是产生某一方可以走的所有合法走步。在博弈树中，它对当前的结点所对应的棋局进行分析，根据规则产生所有合法的走步，对当前结点执行这些走步后所获得的新结点作为当前结点的子结点
29、。不同的棋类游戏由于规则的不同，走法产生机制的复杂度也有较大差别。如对黑白棋来说，只有在自己棋子周围的空白位置才是合法的走步，扫描棋局，寻找到自己棋子周围的所有空白位置就可以了，而且由于黑白棋棋局较小，走步产生较快。但对于四国军棋游戏而言，棋盘的位置很多，而且棋子在不同位置上的走法也很不相同，在铁路线上在没有阻碍的情况下可以在一条铁路线上任意行走，在兵站或者行营中一次只能移动一个位置，铁路线和兵站等的分布没有规律，因而产生所有的合法走步需要进行详细的判断，有时需要多次扫描棋盘，时间复杂度较高。博弈树搜索引擎对所有的走步进行极大极小值搜索，利用估值函数对叶结点进行估值，通过估值来判断走步的优劣，
30、对整棵博弈树进行搜索后，返回最优的走步。搜索算法是程序运行效率的核心部分，一个优化的搜索算法可以大大提高搜索的效率。四国军棋由于走步较多，开局时合法走步数在50步左右，残局时走步可达到100步以上，平均走步在70步左右。在搜索深度为4的情况下需要搜索的叶结点的数目约为2400万个。在这样的时间复杂度下，如果进行完全搜索，显然是极为耗时的。在下一节中，将会详细讨论搜索算法。估值函数是机器博弈系统的核心与关键，直接关系到机器的智能水平，优化的估值函数能够准确的评估游戏棋局，从而显著地提高机器的智能。估值是依据既有的棋类知识来评估一个棋局优劣的过程。这一过程对具体的棋类知识依赖程度很深。本文采用时序
31、差分学习技术来对估值函数进行优化，通过机器学习的方法调整描述棋局的各个参数，来不断逼近理想的估值。在下一章将会讨论时序差分学习算法。2.1.2 机器博弈中的搜索算法2.1.2.1 博弈树基本搜索算法任何棋类游戏都要定义一棵有根的博弈树，一个结点就代表棋类的一个棋局，子结点就是这个棋局走一步可以到达的一个棋局。例如下图就是井字棋(Tic-tac-toe)的搜索树的一部分：图2-3 井字棋的搜索树Fig.2-3 Game Tree of Tic-Tac-Toe其中偶数层结点代表棋手甲(打X的玩家)走步时所面临的棋局，奇数层结点代表棋手乙(打O的玩家)走步时所面临的棋局，叶节点代表棋局结束时的棋局，
32、即棋手甲或者棋手乙获胜，或者是和局。假设某个中间结点的所有子结点都是叶节点，那么棋局会在一个回合内结束。假设棋手会挑选最好的走步。如果有一个走步使得他赢下棋局，那么他一定会走这个走步；如果没有可以赢的走步，但是有取得和局的走步，那么他会走这个取得和局的走步；如果所有的走步都使得对手获胜，则无论如何他都会输。由于游戏从开始到结束往往经历了很多走步，如果把博弈树从游戏开始一直展开到游戏结束，则这个完全博弈树太大了，时间复杂度极大，所以几乎所有的博弈树搜索程序都是向下搜索一定的深度，只是展开博弈树的一部分，例如在搜索4步以后停下来。由于棋局没有在叶子结点结束，我们只能用估值函数来猜测一下哪一方获胜。
33、这里假设玩家都是理性的，即每个玩家都会选择可以达到对自己有利的棋局的走步，棋手甲总是希望棋局达到估值较大的棋局，而棋手乙总是希望棋局到达对棋手甲来说估值较小的棋局。这被称为MinMax极大极小树搜索。从根结点到最优叶节点的路径称为主要变例(Principal Variation)20。极大极小树的基本原理就是对博弈树做部分展开，寻找主要变例，并走出变例的第一步。2.1.2.2 alpha-beta搜索这里根据博弈树的形状对极大极小树搜索算法进行分析。假设每个中间结点有同样多的子结点，其数量称为分支因子b(Branching Factor)21 22，博弈树搜索到固定的深度d，并且棋局不会在到达
34、搜索深度d之前结束。整个运算所花费的时间为：1bb2b3 + bd = bd * ( 1 1 / bd ) / ( 1 1 / b ), （2-1）公式右边括号里面的数值接近于1，所以整个运算所花费的时间接近于bd 。首先时间复杂度是指数级别的，这就意味着不能搜索太多层。其次搜索取决于分支因子b，在分支因子很小的棋类中(如西洋跳棋、黑白棋等)可以搜索得比国际象棋(一个棋局有30个左右的走步)或围棋(一个棋局有几百种走步)深得多。b越小，时间复杂度越小。alphabeta裁剪可以在很大程度上减少分支因子b，最好情况下可以减少到 bd/2 ,这意味着可以搜索到原来搜索深度的2倍。alpha-bet
35、a搜索由于过程简单、容易理解等优良特点被广泛应用，成为现在主流的搜索算法的基础。后来的搜索算法如历史启发算法、置换表算法等都是对alpha-beta算法的优化。本系统采用了历史启发算法来优化搜索，极大的加快了搜索速度，以较小的空间代价获得了较高的性能提升，下面主要介绍历史启发算法。2.1.2.3 历史启发算法alphabeta算法对于节点的排列非常敏感。对于同一层上的节点，如果排列合适，剪枝效率就很高，可以使实际搜索的结点数达到最少。历史启发算法是通过对结点排列顺序的修改来发挥alphabeta算法的效率。历史启发算法(History Heuristic)最早在1989年由Jonathan S
36、chaeffer提出23。在博弈树中，同一个走步会在不同的棋局中多次出现。例如在根结点为最上面图所示棋局的博弈树中，在根结点所产生的红方的所有的走步中，红方的连长走到右下角的行营的走步执行后，获得了图2-4所示的棋局；另一个走步红方的旅长走到右下角的行营里执行后获得了图2-5所示的棋局。在结点24和结点25中所对应的棋局产生的绿方所有走步中，都有绿工兵扛红军旗的走步。 图2-4 红方连长进入行营后获得的棋局 图2-5红方旅长进入行营后获得的棋局Fig.2-4 one Board State Fig.2-5 another Board State 历史启发算法维护一个历史表，这个历史表保存了前面
37、搜索到的走步的历史信息。假如某个走步在前面的博弈树搜索中被选定为最佳走步，则在历史表中为这个走步设定一个较大的分值。在以后的搜索中，依据历史表中出现的各个走步的分值对各个走步进行排序，前面搜索到的最佳走步排到了走步链表的前面，从而使得递归搜索时优先搜索这些前最佳走步。这样使得前面搜索获得的历史信息不断累积，并为后面的搜索提供参考。历史启发算法的依据为：一个走步如果在前面的搜索中是最佳走步的话，很有可能这个走步也是后面搜索的最佳走步。可以从前面的例子中看到，绿工兵抗军旗的走步（椭圆圈住部分）在图2-4所示的棋局中是最佳走步，同样的，在图2-5所示的棋局中也是最佳走步。2.2 非完备信息博弈和蒙特
38、卡罗抽样alpha-beta剪枝算法、状态空间搜索等可以解决完备信息机器博弈问题。然而，在非完备信息博弈中，博弈的真实状态往往是不可知的，比如四国军棋中对手的大多数棋子是隐藏的，进行博弈的玩家所掌握的信息是不对称的和不完备的，这使得非完备信息博弈的研究更具有挑战性。蒙特卡罗抽样作为一种启发式搜索方法来处理非完备信息博弈问题。蒙特卡罗方法又称为计算机随机模拟方法，是一种基于随机数的计算方法。这一方法源自于美国在第一次世界大战中研制原子弹的“曼哈顿计划”。该计划的主持人之一，数学家冯诺伊曼 (见图2-6)用驰名世界的赌城摩纳哥的蒙特卡罗市来命名这种方法，为它蒙上了一层神秘色彩。这种方法在应用物理、
39、原子能、固体物理、化学、生态学、社会学以及经济行为等领域中得到广泛利用24 25 26。蒙特卡罗方法的基本思想是：当所求解问题是某种随机事件出现的概率，或者是某个随机变量的期望值时，通过某种“实验”的方法，以这种事件出现的概率估计这一随机事件的概率，或者得到这个随机变量的某些数字特征，并将其作为问题的解。 图2-6冯诺伊曼 图2-7 投针问题Fig.2-6 John von Neumann Fig.2-7 the Needle ProblemMonte Carlo方法的基本思想很早以前就被人们所发现和利用。早在17世纪，人们就知道用事件发生的频率来决定事件的概率。1777年布丰在著作中提出了著
40、名的投针问题(needle problem)。依靠它，可以用蒙特卡罗方法近似的估计圆周率。投针问题描述如下：假定在水平面上画上许多距离为D的平行线，并且假定把一根长度为L的同质均匀的针随机的掷在此平面上，此针与平行线中任一条相交的频率是多少？布丰证明了，这个概率P是2*L/(D*)。变形后得到计算的公式：= 2 * L / (P * D); (2-2)把这一实验重复多次，记下相交的次数和总次数，D和L是已知的，就可以利用上述公式计算出的近似值。用这种方法得到的最好结果是意大利人拉泽里尼于1901年给出的，他只掷了3408次针，就得到了准确到6位小数的的值：3.1415929。根据同样的思想，可
41、以使用另一种方法来计算。考虑平面上的一个边长为1的正方形及其内部的一个形状不规则的图形，如何求出这个图形的面积呢？Monte Carlo方法是这样一种随机化的方法：向该正方形随机地投掷N个点落于图形内，则该图形的面积近似为M/N。参考图28，图中黑色的部分，也就是园的面积Sc /4,正方形的面积Ss为1，则向正方形中随机的投掷N个点，如果N足够大的话，落到园内的次数/投掷的总次数N近似为Sc/Ss = /4,因而可以利用蒙特卡罗方法来近似的估算的值。图2-8 圆周率的估计Fig.2-8 Estimate of 本世纪40年代电子计算机的出现，特别是近年来高速电子计算机的出现，使得用数学方法在计
42、算机上大量、快速地模拟这样的试验成为可能。借助计算机的高速运转能力，蒙特卡罗方法可以利用计算机针对某种概率模型进行数以万计的随机抽样。借助计算机技术，蒙特卡罗方法具有两大优点：一是简单，省却了繁复的数学推导和演算过程；二是快速，这归功于软硬件技术的进步。用于解决非完备信息博弈的蒙特卡罗方法描述如下：基于对棋局当前可能状态的猜测，得出相应的完备信息棋局，通过对这些子问题空间进行典型抽样的分析，找到一个在大多数可能棋局下都表现优良的走步。一个二人非完备信息游戏的博弈树可以表示成下图的形式：w1w2图2-9非完备信息博弈树的一种形式Fig.2-9 Extensive Form Representat
43、ion of a Game with Possible Worlds在图2-9所示的非完备信息博弈树中，根结点叫做随机结点(chance node)27，随机结点不表示某个确定的棋局状态，而是表示许多个可能的棋局状态，实际的棋局状态是这些可能状态中的一种。图2-9中除了根结点是随机结点外，其余结点都确定的表示一个棋局状态。世界(world)28是指非完备信息博弈的一个可能结果，如图2-9中最下面使用椭圆括住的w1和w2就是两个典型的世界。蒙特卡罗抽样算法的基本思想是猜测当前棋局是某种可能世界而忽略其他世界，然后对这个世界进行完备信息的分析，得到在这个世界里各个分支的收益。重复以上步骤，将得到的
44、在各个世界各分支中取得的收益取加权和，具有最大收益加权和的分支即为最佳走步。一个世界是非完备信息博弈的一个可能结果，如图2-9中w1和w2即为该博弈过程的两个世界。考虑一个具有分支M1、M2、Mm的极大值结点，它具有n个世界，如图2-10。如果eij表示这个结点的Mi分支在世界wj的极大极小价值，我们能够写出一个价值函数f，如下： (2-3)其中Pr(wj)表示wj世界可能出现的实际概率。这样，蒙特卡罗抽样实际上就是这样选择最佳走步的：首先生成各个eij，算出各个f(Mi)，最后用极大极小搜索来决定哪个f(Mi)最大。如果有足够的时间，可以生成所有的eij，但是在实际应用中，只能考虑一些有代表
45、性的世界的抽样。图2-10 在wj中选择最佳走步Fig.2-10 Finding the Best Action in wj可以把根结点矩形看作是面临的非完备信息棋局，下面的圆形可以看作是在根结点矩形执行走步后达到的下一个非完备信息棋局，也就是说，极大值结点就是当前面临的非完备信息棋局，在当前非完备信息棋局下可以产生m个合法走步，分支Mi代表的是执行走步i后获得的下一个非完备信息棋局，抽样获得一个完备信息棋局，对应于上面的世界wj，eij是对完备信息棋局wj应用估值函数后获得的估值。蒙特卡罗抽样的思想为：进行多次抽样，获得具体世界wj，根据抽样的结果wj来判断属于哪个分支Mi，然后累加到这个分支的价值函数f(Mi)上，抽样过程结束之后，选择价值函数f(Mi)最大的分支所对应的走步作为最终的最佳走步。由于上述抽样过程计算较繁琐，本文采用蒙特卡罗抽样的一种变体