计算机博弈原理与方法学概述.ppt

东北大学机器博弈研究室,第二章 计算机博弈原理与方法学概述,徐心和 徐长明东北大学机器博弈研究室2010.01,东北大学机器博弈研究室,主要内容,2.1 棋类介绍与分类2.2 计算机博弈的基本原理2.3 棋局要素的数据结构2.4 棋局评估2.5 博弈树展开与分析2.6 计算机博弈求解的基本搜索方法2.7 开局库与残局库2.8 结语,东北大学机器博弈研究室,原理与方法学涵义,研究“带有普遍性的、最基本的、可以作为其它规律基础的规律，具有普遍意义的道理”，研究在计算机博弈“学科上所采用的研究方式、方法的综合”。这里还仅仅是局限于完全信息的棋类博弈。这是一次探索性的归纳与提升，肯定还有不少缺陷与不足，今后还需要不断地完善和补充。由于目前国际象棋的资料比较丰富，有关方法学的内容主要还是来自国际象棋的计算机博弈。,东北大学机器博弈研究室,2.1 棋类介绍与分类,首先需要了解我们研究的对象棋类不含牌，棋牌性质有很大的区别一般说来：棋类完全信息动态博弈 牌类不完全信息动态博弈,东北大学机器博弈研究室,典型棋类介绍,中国象棋国际象棋围棋五子棋、六子棋各种民间棋类 中国的：牛角棋，一字棋，二虎棋，三通棋 国外的：点格棋，苏拉卡尔塔，亚马逊单人游戏：华容道,东北大学机器博弈研究室,人们为什么喜欢下棋？,1.目的在决出胜负，比出高低，并关联某种收获（物质的，精神的）；2.规则简单明确，成功与失败的判定标准简单；3.博弈过程透明、公平，不包含任何机会或偶然性（不公平点先手优势）；4.智力和经验决定胜负，问题的解决在认识意义上不需要过多的知识；5.变化无穷（很难走出同样的棋谱），激发创新，一种智力游戏。,东北大学机器博弈研究室,中国象棋（Chinese Chess）,棋盘 910棋子：红黑各7个兵种，16子各兵种的行棋规则和活动范围胜负判定准则长将、长拖时间约束60步不吃子判和,东北大学机器博弈研究室,国际象棋（Chess）,王King K(1)、后Queen Q(1)、车Rook R(2)、象Bishop B(2)、马Knight N(2)、兵Pawn P(8),东北大学机器博弈研究室,车：横冲直撞马：不怕蹩腿象：可以过河王：每步一格，不受区域限制王一旦被杀，即为输棋后=车+象，威力最大兵：第一步可以走两格，吃过路兵；之后前走斜吃王车易位（长易位，短易位）；兵升变相对子力值：Assigning the pawn a value of 1,the values of the other pieces are approximately as follows:knight 3,bishop 3,rook 5,and queen 9.,东北大学机器博弈研究室,围棋（Go/I-Go）,棋盘 1919轮流下子，谁占的地盘多谁胜。先下手为强，贴目（5-7）。规则最简单，计算机博弈难度最大。当前侧重解决1/4棋盘 Go 99,东北大学机器博弈研究室,五子棋（FIR-Five In A Row）,起源于中国发展在日本（连珠棋）Renju/Go-Moku棋盘 1515已被证明先手胜禁手换手金球制改进球制,东北大学机器博弈研究室,六子棋（Connect 6）,吴毅成教授发明棋盘 19196子连珠为胜先手下一子，然后每手下两子，削减先手优势复杂度显著提高台湾已经盛行欧洲也很关注,东北大学机器博弈研究室,一字棋,走子的距离不限，至少走一步，至多走到终点。不准逆行。可以走动任何一个棋位上的一个或多个棋子。但是必须停留在同一个目标棋位上。最后到达目的地的为胜（负）.,东北大学机器博弈研究室,二虎棋,布阵之后双方轮流走子，开局第一着棋由虎方先走。犬方每次只走一个子到临近空棋位。虎方同。虎方可跳吃，每次只吃一子。虎方吃够一定数量的犬方棋子就算获胜；犬方以围困虎方为目的，当虎方的全部棋子无法走动时才算犬方获胜。,东北大学机器博弈研究室,三通棋,全盘含有64个小正三角形，即64个棋位。双方棋子各32枚。开局后双方轮流布子，每方每着棋布子1枚。乙方有一次（只有一次）连续下两着棋的权利。当一方首先实现三通的时候终局并获胜。,东北大学机器博弈研究室,点格棋（Dots and Boxes）,将邻近的两点连成一边，四边构成方格；最后一个占边者获取这个格子。并要再连一边。最后占据方格多者为胜。关注死格（dead box）双环（double cross）长链（long chain）短链（short chain）环（circle）等。,东北大学机器博弈研究室,苏拉卡尔塔（Surakarta）,双方轮流走棋，不可不走；除了吃子之外，每个棋子每步只能走一格，可以沿垂直或 对角方向；沿着弧吃子，而且必须经过一个完整的弧。吃掉所有对方棋子一方获胜。,东北大学机器博弈研究室,亚马逊（Yamazons）,1988,Walter Zamkauskas,Argentina发明.每方4个国际象棋的“后”每个着法包括移动和设障各方争取更大的活动范围也是一种憋死牛的游戏无子可动一方判负,东北大学机器博弈研究室,华容道滑块类游戏,Chinese Sliding Block Puzzle。在国外将华容道和魔方、独粒钻石并列，被誉为“智力游戏界三大不可思议”。一次移动一个人物到空格区域，直到将曹操（最大的方块）移动到下面中央的箭头处。,东北大学机器博弈研究室,棋的分类,按参与人数分类（Player）：双人：象棋，围棋，五子棋 单人：华容道 多人：跳棋双人弈棋占绝大多数一般说来，参与人数越多，对手就越多，情况就越发复杂。,东北大学机器博弈研究室,按兵种多少分类（Pieces）,单一兵种（Stone）：围棋、五子棋、六子棋多兵种（Chessman）：国际象棋、中国象棋,东北大学机器博弈研究室,按着法分类（Move）,走子类：开局前双方摆好，开局后轮流走动棋子。如象棋、国际象棋、跳棋等，牛角棋，苏拉卡尔塔，亚马逊；添子类：开局前盘面无子，开局后轮流放入棋子。如围棋、五子棋、六子棋、点格棋等；吃子类：对局过程中可以吃掉对方的棋子。如象棋、国际象棋、围棋等；混合类：在填子的过程中可以吃子（围棋）；在走子过程中可以吃子，还可以填子（日本将棋）。通常情况弈棋双方轮流施着，各走（下）一步（Move）。但是有的棋类在一定条件下一方是可以连续施着的，即连续走多步，可称为轮（Turn）。如跳棋、西洋跳棋、黑白棋（Reversi,Othello）、点格棋（Dots and Boxes）等。,东北大学机器博弈研究室,日本将棋,东北大学机器博弈研究室,按胜负判决分类（Win-Lose-Draw）,擒获首领：象棋，国际象棋等摆成形状：连珠类井字棋，五子棋，六子棋等占领地域：围棋，点格棋等剩余子粒：黑白棋，苏拉卡尔塔等活动余地：亚马逊等到目标地：跳棋，一字棋，牛角棋等,东北大学机器博弈研究室,2.2 计算机博弈的基本原理,所谓基本原理就是：带有普遍性的、最基本的、可以作为其它规律基础的规律，具有普遍意义的道理。分析下棋：棋类要素了解棋盘、棋子、棋规（着法与胜负规则）弈棋要素用着法推演局面，从有利局面选择当前着法局面评估指标分析，需要具体棋种的特殊知识,东北大学机器博弈研究室,状态演化方程：,棋谱,(红方),(黑方),2.2.1 弈棋过程分析,东北大学机器博弈研究室,2.2.2 如何让计算机下棋？,棋类要素的数字化恰当的数据结构 棋盘、棋子、棋规（着法规则，胜负规则）用着法推演局面博弈树展开从有利局面选择当前着法博弈搜索局面评估指标定义与综合,东北大学机器博弈研究室,棋局状态展开示意图,东北大学机器博弈研究室,展开深度为4的博弈树,根节点为当前局面叶节点为展开终点双方轮流出手偶数层为本方奇数层为对方,东北大学机器博弈研究室,节点为局面，树枝为着法，根节点为当前局面，叶节点为展开相应深度的终点局面。如果叶节点还不是能够给出胜-负-和的最终局面，则要进行叶节点评估（Evaluation）。以便从有利局面选择当前着法。这便是博弈搜索的职能。搜索引擎根据极大-极小的搜索算法，找到对于本方而言最好的结局。然后找到最佳路径（Principal Variation 主要变例），从而找到相应的根着法（Root Move），即是本轮搜索所要给出的当前着法。不难看出，评估和搜索将成为博弈软件的重要部分。,博弈树搜索,东北大学机器博弈研究室,计算机博弈软件的构成,东北大学机器博弈研究室,2.3 棋局要素的数据结构,2.3.1 计算机博弈数据结构研究的内容所有的棋局元素，包括棋盘、棋子、棋局、着法、规则、知识等通过数字化（编码）成为数据元素，而各种数据元素又以特定的关系构成相应的数据结构进行存储和处理。,东北大学机器博弈研究室,棋类要素的数字化,以牛角棋为例编码 数据结构 棋盘编码（棋位编码）棋子编码 初始局面的表示 棋位向量：(100000023)棋子向量：(089),东北大学机器博弈研究室,2.3.2 计算机博弈数字化原则与意义,数据结构问题在计算机博弈中的重要性是不言而喻的。在展开和搜索博弈树期间，数以千百万计的着法和棋局被生成、存储、撤销，合理的数据结构可以显著地提高搜索速度和深度，节省内存空间，改进博弈效果。数据结构还对编程有着直接的影响。在采用宽度优先的搜索算法中，新被扩展的节点应该采用队列结构；而在深度优先的搜索算法中，则应该采用栈结构。编码问题要面向棋种，面向算法，面向编程。许多情况下适当的冗余是必要的。,东北大学机器博弈研究室,2.3.3 哈希变换与哈希表,众多棋类的成功经验表明，棋局的存储最好是采用Zobrist哈希技术加以实现，即将棋局转换为哈希数（Hash Number）。哈希技术的基本原理是将棋盘上双方棋子的代码和坐标位置转换为对应的64位随机数，将棋盘上全部棋子所对应的随机数异或求和，这个64位的哈希数便作为给定棋局的索引值（Zobrist键值），用作棋局的存储与查询。哈希数的最大优点就在于它求的是64位数的异或和，当在着法的作用下，棋局发生了变化，只要将相应变化棋子的哈希数再异或一次，便可以转变成新局面所对应的哈希数。,东北大学机器博弈研究室,位棋盘（Bit Board）,在着法生成和棋局评估的过程中，时常仅仅关心一些棋子的分布，这时可以用比特棋盘（亦称位棋盘）表示棋子的某种状态，它其实是棋子状态条件的布尔表示。如棋盘中哪些棋位上有红子？哪些棋位上有黑车等等。比特棋盘的定义为式中 为棋位（i,j）的布尔条件。,东北大学机器博弈研究室,2.4 棋局评估,如果在叶子节点不能给出胜-负-和的结果，那“有利局面”的选择就只能依靠局面的评估了。通常设计的评估函数需要考虑如下不同类型的知识，如子力、位置、空间、机动、拍节、威胁、形状、图案等方面，并通过量化后加权组合而成。,东北大学机器博弈研究室,2.4.1 子力(Material),在象棋和国际象棋中，它是所有子力价值的和；在围棋或黑白棋中，通常计算双方棋盘上棋子的数量。黑白棋有个有趣的反例：棋局只由最后的子数决定，而在中局根据子力来评价却是很差的思路，因为好的局势下子数通常很少。像五子棋、六子棋一类的游戏，子力是没有作用的，因为局面好坏仅仅取决于棋子在棋盘上的相互位置，看它是否能够发挥作用。,东北大学机器博弈研究室,2.4.2 位置(Position),棋子落于不同的棋位其作用可能差别很大。象棋中的车占中路，兵过河，马卧槽都是具有威胁性的位置。相反如果马窝心，兵下底又都不甚理想。围棋中的星位也是兵家必争之地。不同的位置给予不同的分值，以表示不同的价值。,东北大学机器博弈研究室,2.4.3 空间(Space),在某些棋类中，棋盘可以分为本方控制的区域和对方控制的区域，以及有争议的区域。在围棋中，这个思想被充分体现。而包括象棋在内的一些棋类也具有这种概念，本方的区域包括一些棋位，它被本方的棋子攻击或保护，而不被对方棋子攻击或保护。空间的评价就是简单地把这些区域加起来，如果所含棋位的重要程度存在差别，那就在区域的计算上增加棋位重要性的因素。,东北大学机器博弈研究室,2.4.4 机动(Mobility),各个棋子的机动性如何，关系到棋子可行着法的多少。如象棋中的马是可以“马踏八方”的，但是贴边或被憋腿，其活动余地大减。机动性越好，可行着法越多，选择有利局势的机会也越多。,东北大学机器博弈研究室,2.4.5 拍节(Tempo),某些情况下起决定作用的不是着法的多少，而是出招的拍节和数量的奇偶性等。以一数学游戏为例：有两堆石子，双方轮流从石堆中拿去几颗，每次只能从一堆石子中拿走至少一颗石子，拿完最后一堆者获胜。这个游戏的诀窍是：始终让对方面临两堆石子一样多的窘境。面向这样的问题时，先手方只要头一步让两堆石子数目一样多就可以了。然后对手从某一堆取走几颗，先手方便在另一堆取走同样数量的石子。,东北大学机器博弈研究室,图2-6 一个受制于节拍的象棋棋局,东北大学机器博弈研究室,2.4.6 威胁(Threat),威胁的思想是“步步紧逼”，或要取胜，或要吃子，使对方仅有招架之功，而无还手之力。在五子棋、六子棋中常常采用基于威胁的搜索。以五子棋为例，可通过不断地摆出“活3”、“冲4”的棋型的方法，将对方逼到防无可防的境地，从而取胜。,东北大学机器博弈研究室,2.4.7 形状(Shape),形状的好坏对于局面的影响一般是长远的，在浅层的搜索中不易发现。在象棋中，对手的空头跑，单车栓车马，就都是不好的形状，最终使本方处于被动的局面。形状对于连珠棋一类通过“摆成形状”而决定胜负的就更是评估的焦点。,东北大学机器博弈研究室,2.4.8 图案(Motif),一些常见的具有鲜明特点的图案，蕴涵着特殊的意义。许多图案在围棋中称之为模式，如33上下文模式，通过对大量高手对局中的模式提取和出现频率的统计，构造模式库，便可以由此提供下一手落子的最佳位置。,东北大学机器博弈研究室,2.4.9 棋局性能评估,从表面上看，棋局评估的越全面、越准确，棋力性能就会越高。其实不然。一般说来，棋力性能=知识速度，时间作为约束条件。评估中考虑的问题越多、越细致，耗费的时间则越多，必然影响到单位时间内搜索节点的数目，影响到搜索的速度和深度。在博弈软件的设计中通常存在“重知识”（评估）和“重速度”（搜索深度）两种倾向，并且都有成功的范例。,东北大学机器博弈研究室,2.5 博弈树展开与分析,博弈树是由树枝和节点构成单向无环图。树枝是着法，节点是由该着法生成的局面。博弈树展开的过程就是着法生成的过程。,东北大学机器博弈研究室,2.5.1 着法生成的不同策略,（1）选择生成。根据当前的棋局，只生成部分可行的着法，而不去考虑其它可行着法。比如象棋在被将军的局面下，仅需要考虑“避将着法；（2）渐进生成。先产生一些着法，并沿着某个着法延伸下去，直到证明这条路线坏到足以中止搜索的程度，再去生成和搜索其它的着法。比如象棋中先生成“吃子着法”，然后再考虑“非吃子着法”；（3）完全生成。一次产生所有的着法。显然这是一种稳妥而保守的做法。,东北大学机器博弈研究室,2.5.2 走子类着法生成方法,（1）棋盘扫描法（含射线法）。根据棋规，在当前棋局中逐一找到棋子可行的落址。该方法最为直观，编程也很简单。但是由于需要反复在棋盘上扫瞄，时间开销巨大，一般缺少实战意义。（2）模板匹配法。对于有特殊要求的走子类棋子，如象棋中的马和象，将根据走子规则“绘制”的模板套在棋子当前的位置上，通过模板找到可行的落址，形成可行着法。（3）预置表法。这是一种用空间换时间的生成策略。将全部棋子在所有棋位上的着法都预先放在表中。开局时自动生成，放入内存。弈棋过程中直接查找。,东北大学机器博弈研究室,2.5.3 添子类着法生成方法,一般说来，添子类的着法生成比较直观，即盘面上的合法空位便可以落子。五子棋和六子棋最为简单，下完的棋子不再会改变。黑白棋稍复杂些，下完的棋子可能会被后续着法所变换黑白，但每下一子棋盘上就多一子。围棋是最复杂的，由于存在提子的着法，所以局势是可逆的，对于打劫这样的着法还需要更为复杂的处理过程。,东北大学机器博弈研究室,2.5.4 博弈树展开与分析,博弈树代表的是从当前棋局（根节点）的演化和发展，是进行棋局分析的基础。树枝代表着法，节点代表棋局。分支多少用分支因子表示，节点的层数代表展开的深度。分支因子大，展开层数多，是博弈树规模庞大的原因。将博弈树全部展开（从初始棋局到分出胜负）的节点数，为该种棋树的复杂度。全部可行棋局的数量为状态复杂度。由于博弈树中有大量的重复状态，所以树的复杂度远高于状态复杂度。,东北大学机器博弈研究室,2.6 计算机博弈求解的基本搜索方法,2.6.1 优化搜索与博弈搜索搜索是一个非常宽泛的概念，也是有着广泛应用领域的技术。在各种规划问题中，如线性规划、非线性规划、整数规划等；在许多优化问题中，如旅行商问题、计划调度问题等，在无法得到解析解（含数值方法求解）的情况下，便会采取各种启发式搜索算法。如爬山法、分支定界法、禁忌搜索、模拟退火、遗传算法、蚁群算法等等。,东北大学机器博弈研究室,优化搜索与博弈搜索,优化搜索算法的共同特点：（1）单一决策主体，即统一的性能指标函数；（2）明确的目标函数和约束条件，通常可以用数学模型来描述；（3）基本为静态规划和优化问题，亦即单步决策问题。计算机博弈属于博弈和对策的范畴，是由两个非合作主体构成的、多步的、动态博弈问题，对弈双方有着对立的、二人零和的决策目标，其目标函数难以用数学模型来描述。目前能够用以描述的主要是博弈树。而普遍采用的求解方法就是在博弈树中搜索。博弈搜索的目标就是搜索最佳路径，搜索当前的最佳着法（根着法），并且亦步亦趋地进行下去。,东北大学机器博弈研究室,宽度优先与深度优先,博弈搜索从搜索方向上可以分为宽度优先搜索(Breadth-first search)和深度优先搜索(Depth-first search)。宽度优先能够保证在搜索树中找到一条通向目标节点的最短途径。但是巨大的时间和空间开销使得它在计算机博弈中很少采用。深度优先搜索的最大特点就是可以节省大量的节点存储空间。因为它是采用递归过程来遍历搜索树，即后序遍历，因此它所占用的动态空间十分有限。Alpha-Beta剪枝和置换表相结合的算法更使得博弈树的规模被数量级地减少。在最好的情况下，它处理的节点数是纯粹的“最小-最大”（极大极小）搜索的平方根的两倍，可以从15,000,000个减少到7,800个。,东北大学机器博弈研究室,基本搜索策略广度优先（Breadth-first search）,东北大学机器博弈研究室,基本搜索策略深度优先（Depth-first search）,东北大学机器博弈研究室,2.6.2 极大极小搜索,东北大学机器博弈研究室,MAX,MAX,MIN,3,MaxMin搜索（1）,由此产生最佳路径和最佳着法,东北大学机器博弈研究室,MAX,MAX,MIN,4,MaxMin搜索（2）,由此产生最佳路径和最佳着法,东北大学机器博弈研究室,广度优先极大极小搜索算法,东北大学机器博弈研究室,深度优先极大极小搜索算法,东北大学机器博弈研究室,2.6.3 Alpha-Beta搜索,一种基于剪枝（-cut-off）的深度优先搜索（depth-first search）。将走棋方定为MAX方，因为它选择着法时总是对其子节点的评估值取极大值，即选择对自己最为有利的着法；将应对方定为MIN方，因为它走棋时需要对其子节点的评估值取极小值，即选择对走棋方最为不利的、最有钳制作用的着法。,东北大学机器博弈研究室,MAX,MAX,MIN,4,4,剪枝（1）,由此产生最佳路径和最佳着法,=4,东北大学机器博弈研究室,在对博弈树采取深度优先的搜索策略时，从左路分枝的叶节点倒推得到某一层MAX节点的值，可表示到此为止得以“落实”的着法最佳值，记为。显然此值可作为MAX方着法指标的下界。在搜索此MAX节点的其它子节点，即探讨另一着法时，如果发现一个回合（2步棋）之后评估值变差，即孙节点评估值低于下界值，则便可以剪掉此枝（以该子节点为根的子树），即不再考虑此“软着”的延伸。此类剪枝称为剪枝。,东北大学机器博弈研究室,MAX,MAX,MIN,1,4,剪枝（2）,1,2,2,4,由此产生最佳路径和最佳着法,=4,东北大学机器博弈研究室,剪枝效果差别很大,不难发现，和最佳着法关系密切什么是最佳着法？怎样找到最佳着法？,（1）,（2）,东北大学机器博弈研究室,-剪枝（1）,MAX,MIN,MIN,7,7,由此产生最佳路径和最佳着法,=7,东北大学机器博弈研究室,同理，由左路分枝的叶节点倒推得到某一层MIN节点的值，可表示到此为止对方着法的钳制值，记为。显然此值可作为MAX方无法实现着法指标的上界。在搜索该MIN节点的其它子节点，即探讨另外着法时，如果发现一个回合之后钳制局面减弱，即孙节点评估值高于上界值，则便可以剪掉此枝，即不再考虑此“软着”的延伸。此类剪枝称为剪枝。,东北大学机器博弈研究室,-剪枝（2）,MAX,MIN,MIN,8,由此产生最佳路径和最佳着法,4,4,8,=4,东北大学机器博弈研究室,剪枝和剪枝具有同样规律,剪枝效果与最佳着法的位置密切相关与博弈树展开的顺序密切相关,（1）,（2）,东北大学机器博弈研究室,需要指出的是,-剪枝是根据极大-极小搜索规则的进行的，虽然它没有遍历某些子树的大量节点，但它仍不失为穷尽搜索的本性。-剪枝技巧的发现，一下便为博弈树搜索效率的提高开创了崭新的局面。,东北大学机器博弈研究室,东北大学机器博弈研究室,博弈树搜索过程,东北大学机器博弈研究室,2.6.4 负极大值搜索,博弈搜索是一种“变性”搜索。在偶数层进行“Max搜索”，而在奇数层进行“Min搜索”。这无疑给算法的实现带来一大堆麻烦。Knuth和Moore充分利用了“变性”搜索的内在规律，在1975年提出了意义重大的负极大值算法。它的思想是：父节点的值是各子节点值的变号极大值，从而避免奇数层取极小而偶数层取极大的尴尬局面。,东北大学机器博弈研究室,MAX,MAX,MIN,3,MaxMin搜索（1）,由此产生最佳路径和最佳着法,NegaMax,NegaMax,NegaMax搜索（1）,东北大学机器博弈研究室,负极大值算法（NegaMax algorithm）,此时需要特别注意的则是，如果叶节点是红方（走棋方）走棋，评估函数返回RedValue-BlackValue，如果是黑方（应对方）走棋，则返回BlackValue-RedValue。另外，由于负极大值计算等价于“Min搜索”，所以这里只进行剪枝，非常有利于编程实现和提高搜索速度。,东北大学机器博弈研究室,东北大学机器博弈研究室,2.6.5 基于蒙特卡洛模拟的博弈树搜索,蒙特卡洛树搜索（Monte-Carlo Tree Search,MCTS）是一种最佳优先搜索（Best-first search）算法，更适合于分支因子很大的博弈树搜索。比如围棋分支因子常常大于100，而亚马逊棋的分子因子可以大于1000，采用前述的Alpha-Beta搜索算法只能搜索很浅的几层，导致棋力水平难以提高。自从Bernd Brugmann等首先将蒙特卡洛模拟技术用于围棋的动态评估，进而出现把UCB1（Upper Confidence Bound）算法扩展到树搜索的UCT（UCB applied to Tree）算法，使得在短短的几年中，九路围棋的计算机程序已经可以和围棋高手对弈了。,东北大学机器博弈研究室,MCTS的基本思想,蒙特卡洛模拟对局就是从某一棋局出发，随机走棋。有人形象地比喻，让两个傻子下棋，他们只懂得棋规，不懂得策略，最终总是可以决出胜负。这个胜负是有偶然性的。但是如果让成千上万对傻子下这盘棋，那么结果的统计还是可以给出该棋局的固有胜率和胜率最高的着法。,东北大学机器博弈研究室,蒙特卡洛树搜索通过迭代来一步步地扩展博弈树的规模，UCT树是不对称生长的，其生长顺序也是不能预知的。它是根据子节点的性能指标导引扩展的方向，这一性能指标便是UCB值。它表示在搜索过程中既要充分利用已有的知识，给胜率高的节点更多的机会，又要考虑探索那些暂时胜率不高的兄弟节点，这种对于“利用”（Exploitation）和“探索”（Exploration）进行权衡的关系便体现在UCT着法选择函数的定义上，即子节点Ni的UCB值按如下公式计算。,东北大学机器博弈研究室,蒙特卡洛树搜索（MCTS）算法,1.由当前局面建立根节点，生成根节点的全部子节点，分别进行模拟对局；2.从根节点开始，进行最佳优先搜索；3.利用UCB公式计算每个子节点的UCB值，选择最大值的子节点；4.若此节点不是叶节点，则以此节点作为根节点，重复2；5.直到遇到叶节点，如果叶节点未曾经被模拟对局过，对这个叶节点模拟对局；否则为这个叶节点随机生成子节点，并进行模拟对局；6.将模拟对局的收益（一般胜为1负为0）按对应颜色更新该节点及各级祖先节点，同时增加该节点以上所有节点的访问次数；7.回到2，除非此轮搜索时间结束或者达到预设循环次数；8.从当前局面的子节点中挑选平均收益最高的给出最佳着法。,东北大学机器博弈研究室,开局库与残局库,2.7.1 开局库开局库几乎是每个棋类博弈程序必备的部件，它的好处在于：即使是再笨的程序，开局库能使得它在开局阶段看上去不那么业余。既能防止因为复杂的搜索而浪费大量时间，也能防止在开局阶段犯下战略性的错误。,东北大学机器博弈研究室,开局库的开发,开局库是将高手开局时的棋谱记载下来，仿照执行。由于开局形式多种多样，局面常常数以千万计。此时必须应用哈希技术才能方便存储和查找。对应于同一局面常常可以有多种着法，此时应该统计各种着法的胜率，作为随机选择时的依据。开局库还应该具有自学习的功能，可以随着程序见识的增长，补充新鲜的定式，或调整已有着法的胜率参数。,东北大学机器博弈研究室,2.7.2 残局库,残局库却不一定是博弈程序必备的部件。只有对于吃子类棋类，当盘面剩余子力不多进入残局时，仍然按照中局的搜索算法难以取得良好的效果。残局的评价指标发生变化。多数中局的目标是“谋取优势”，那在残局阶段则应该是：优势谋胜，劣势谋和，均势谋机。因此如何“谋胜”、“谋和”的策略显得十分重要。于是评价体系需要调整；,东北大学机器博弈研究室,许多局面致胜的途径十分特殊和单一，没有足够深度的搜索是难以发现的。如何通过“学习算法”将博弈大师丰富的残局知识存放到博弈系统中去，还是很有挑战性的研究课题。目前国际象棋根据回溯算法推演出子数有限的残局库，但对于中国象棋而言还有许多工作要做。,东北大学机器博弈研究室,2.8 结 语,计算机博弈原理与方法学既涉及到博弈论（对策论）、搜索原理等理论内容，又更多地涉及到数据结构、软件工程、程序设计方法学等方面的知识。计算机博弈属于计算机科学与应用学科的研究方向之一，又是人工智能领域的重要研究方向，应该属于智能科学与技术学科的一个分支。虽然这一方向的研究工作取得了举世瞩目的成果，但是相关的理论与应用技术的归纳与提升还有很多工作要做。这也是把计算机博弈技术应用到其它领域所不可或缺的基础性工作。,东北大学机器博弈研究室,致谢,象棋百科全书网站站长黄晨先生提供了丰富的资料，不仅对于本章的研究以很大的帮助，在中国计算机博弈领域的影响也是有目共睹的，在此一并表示感谢。,东北大学机器博弈研究室,在游戏软件的编写中提高素质！让创新的火花在机器博弈中迸发！,联系：http:/,