1、 作者作者 朱福喜朱福喜 朱三元朱三元第第4章章 博弈与搜索博弈与搜索 作者作者 朱福喜朱福喜 朱三元朱三元l博弈虽然自古就是人与人的对弈，但自从有了计算机以后，人们开始就有用计算机下棋的想法，早在60年代就已经出现若干博弈程序，并达到较高的水平，现已出现计算机博弈程序能够与人类博弈大师抗衡的局面。l举世瞻目的人机对弈是1997年IBM公司编制的深蓝（deep blue）计算机与国际象棋大师卡斯帕罗夫对弈，取得了三胜二和一负的好成绩。博弈的研究不断为人工智能提出新的课题，可以说博弈是人工智能研究的起源和动力之一。图4.1 许峰雄博士代表IBM与国际象棋冠军卡斯帕罗夫对弈4.1 概述概述 博弈一
2、向被认为是富有挑战性的智力的游戏，有着难以言语的魅力。博弈问题常与对策问题联系在一起。对策论（Game Theory）用数字方法研究对策问题。一般将对策问题分为零和对策和非零和对策。最典型的零和对策问题是我国古代齐王与田忌赛马的问题。该问题是齐王与田忌都有可分为上、中、下三匹马。齐王的上马、中马、下马都比田忌相应的上马、中马、下马好，但田忌的上马比齐王的中马好，田忌的中马比齐王的下马好，聪明的田忌采取了下述对策后一举取胜：作者作者 朱福喜朱福喜 朱三元朱三元l非零和对策的例子有：囚犯难题（The prisoner dilemma）。该问题是有两个嫌疑犯A和B，暂时还没有获得他们犯罪的确定的证据
3、。现对他们判刑的规则是：作者作者 朱福喜朱福喜 朱三元朱三元博弈问题对人的深层次的知识研究提出了严峻的挑战。如何表示博弈问题的状态，博弈过程和博弈取胜的知识，这是目前人类仍在探讨之中的问题。要提高博弈问题求解程序的效率，应作到如下两点：l改进生成过程，使之只生成好的走步，如按棋谱的方法生成下一步；l改进测试过程，使最好的步骤能够及时被确认。作者作者 朱福喜朱福喜 朱三元朱三元 要达到上述目的有效途径是使用启发式方法引导搜索过程，使其只生成可能赢的走步。而这样的博弈程序应具备：l一个好的（即只产生可能赢棋步骤的）生成过程。l一个好的静态估计函数。下面介绍博弈中两种最基本的搜索方法。4.2 极小极
4、大搜索过程极小极大搜索过程 4.2.1 极小极大搜索的思想极小极大搜索的思想l极小极大搜索策略是考虑双方对弈若干步之后，从可能的步中选一步相对好的走法来走，即在有限的搜索深度范围内进行求解。l为此要定义一个静态估计函数f，以便对棋局的势态作出优劣估计。这个函数可根据棋局优劣势态的特征来定义。这里规定：MAX代表程序方 MIN代表对手方 P 代表一个棋局（即一个状态）f（P）的大小由棋局势态的优劣来决定:有利于MAX的势态，f（P）取正值 有利于MIN的势态，f（P）取负值 势态均衡，f（P）取零使用静态函数进行估计必须以下述两个条件为前提：（）双方都知道各自走到什么程度、下一步可能做什么。（）
5、不考虑偶然因数影响。在这个前提下，博弈双方必须考虑：（）如何产生一个最好的走步。（）如何改进测试方法，能尽快搜索到最好的走步。MINMAX的基本思想是：（）当轮到MIN走步的结点时，MAX应考虑最坏的情况（因此，f(p)取极小值）。（）当轮到MAX走步的结点时，MAX应考虑最好的情况（因此，f(p)取极大值）。（）当评价往回倒推时，相应于两位棋手的对抗策略，不同层上交替的使用（）、（）两种方法向上传递倒推值。4.2.2 极小极大搜索算法极小极大搜索算法极小极大过程的算法如下：1.T:=(s,MAX),OPEN:=(s),CLOSED:=();开始时树由初始结点构成，OPEN表只含有s.2.LO
6、OP1:IF OPEN=()THEN GO LOOP2;3.:FIRST(OPEN),REMOVE(n,OPEN),ADD_TO_LAST(n,CLOSED);/约定加到尾部 作者作者 朱福喜朱福喜 朱三元朱三元4.IF n可直接判定为赢、输或平局THEN f(n):=-0,GO LOOP1 ELSE EXPAND(n)ni,ADD(ni,T)IF d(n)k THEN ADD_TO_LAST(ni,OPEN),GO LOOP1 ELSE 计算f(ni),GO LOOP1;n达到深度k,计算各端结点f值5.LOOP2:IF CLOSED=NIL THEN GO LOOP3 ELSE np:=L
7、AST(CLOSED);作者作者 朱福喜朱福喜 朱三元朱三元6.IF(npMAX)(f(nc iMIN)有值）（其中nci为np的下一层节点）THEN f(np):=MAX f(nci),REMOVE(np,CLOSED);若MAX所有子节点均有值，则该MAX取其极大值。IF(np MIN)(f(nci MAX)有值）THEN f(np):=MIN f(nci),REMOVE(np,CLOSED);若MIN所有子节点均有值，则该MIN取其极小值。作者作者 朱福喜朱福喜 朱三元朱三元7.GO LOOP2;8.LOOP3:IF f(s)=NIL THEN EXIT(ENDMark(Move,T);
8、s有值，或结束或标记走步其中ADD_TO_LAST约定加入节点到表的尾部，END表示失败或成功或平局退出，MARK标记一个走步。4.2.3 算法分析与举例算法分析与举例 该算法分三个阶段进行。l 第一阶段为步骤24，使用宽度优先法生成规定深度的全部博弈树，然后对其所有端节点计算其静态估计函数值。l 第二阶段为步骤57是从底向上逐级求非终结点的倒推估计值，直到求出初始节点的倒推值f(s)为止。f(s)的值应为max min.f(ni1i2i3ik)，其中nik表示深度为k的端节点。l 第三阶段，根据f(s)可选的相对好的走步，由Mark(Move,T)标记走步。例4.1 在九宫格棋盘上两位选手轮
9、流在棋盘上摆各自的棋子，每次一枚，谁先取得三子一线的结果就取胜。l 设程序方MAX的棋子用X表示 l 对手方MIN的棋子用O表示.作者作者 朱福喜朱福喜 朱三元朱三元静态估计函数为:+当p为MAX赢f(p)=-当p为MIN赢 全部空格放X后三字成一线的总数）-（全部空格放O后三字成一线的总数）例如，P的格局为：l 则可得f(p)=5 6=-1。l现在考虑走两步的搜索过程，即算法中K=2。利用棋盘对称性条件，则MAX走第一步棋调用算法产生搜索树如图所示。作者作者 朱福喜朱福喜 朱三元朱三元 作者作者 朱福喜朱福喜 朱三元朱三元 作者作者 朱福喜朱福喜 朱三元朱三元 作者作者 朱福喜朱福喜 朱三元
10、朱三元4.3-剪枝算法剪枝算法 作者作者 朱福喜朱福喜 朱三元朱三元 这时其中一个MIN节点要生成A,B,C,D四个节点，然后逐个计算其静态估计值，最后求得倒推值-，把它赋给这个结点。其实生成节点A后，如果马上进行静态估计，得知F(A)=-之后，就可以断定生成B,C,D以及进行估计是多余的，该MIN节点的倒推值一定是-。作者作者 朱福喜朱福喜 朱三元朱三元l-剪枝法就是把生成后继和倒推值估计结合起来，及时剪掉一些无用分枝，以此来提高算法的效率。l-剪枝法，采用有界深度优先策略进行搜索，当生成节点达到规定的深度时，就立即进行静态估计，而一旦某个非端节点有条件确定倒推值时，就立即赋值。当生成到节点
11、6后，节点1的倒推值可确定为-1。这时对于初始节点S来说，虽然其他子节点尚未生成，但由于S属于极大层，所以可以推断它的倒推值不会小于-1。我们定义极大层的这个下界值为。因此S的=-1。S的值为-1，说明的S倒推值不会比-1更小，但会不会比-1更大，还取决于其他后继节点倒推值。我们继续生成搜索树。当第8个节点生成后，其估计值为-1，就可以断定节点7的倒推值不可能大于-1。定义极小层的这个上界值为。因此现在可以确定节点7的=-1。有了极小层的值，容易发现时，节点7的其他子节点不必生成，因为S的极大值不可能比这个值小，再生成无疑是多余的，因此可以进行剪枝。只要在搜索过程中记住倒推值的上下界并进行比较
12、，当时就可以实现修剪操作。l,值还可以随时修正，但极大层的倒推值下界永不下降，因为实际的倒推值取后继节点最终确定的倒推值中的最大者。l 同理，极小层的倒推值上界永不上升，因为实际倒推值取后继节点最终确定的倒推值中的最小者。作者作者 朱福喜朱福喜 朱三元朱三元-过程的剪枝规则（1）剪枝：若任一极小值层节点的值小于或等于它任一先辈极大值层节点的值，即（先辈层）（后继层），则可中止该极小值层中这个节点以下的搜索。该节点最终的倒推值就确定为这个值。（2）剪枝：若任一极大值层节点的值大于或等于它任一先辈极小值层节点的值，即（后继层）（先辈层），则可以中止该极大值层中这个节点以下的搜索。这个MAX节点的最
13、终倒推值就确定为这个值。演示 作者作者 朱福喜朱福喜 朱三元朱三元4.4 AlphaGo搜索策略搜索策略为什么20年前AI就已经打败国际象棋的人类世界冠军，而直到现在围棋AI才取得成功呢？l 其一，围棋棋盘是1919，因此每一步可以选的合法走法远远大于象棋（围棋的分支因数Branching Factor是250，象棋只有35），也就是说围棋搜索空间相对于国际象棋来说大得多。l 其二，围棋的估值函数很难设计。象棋尚能用简单的统计棋子个数和子力来推断，围棋棋局千变万化，可能看似风平浪静其实暗藏杀机。这两个主要原因导致了围棋AI长久以来一直很难有大的进展。4.4.1 围棋博弈程序的发展围棋博弈程序的
14、发展直到2006年前后，发现了一种新的捜索策略，叫蒙特卡罗树搜索(MCTS，Monte Carlo Tree Search)，它是一种最佳优先搜索（Best-first search）算法，更适合于分支因子很大的博弈树搜索。前面提到，状态空间搜索都要有评估函数指导搜索。蒙特卡罗树搜索作为一种搜索策略，它的评估函数要可以达到判断盘终胜负这个最低要求，这恰好弥补了围棋程序在评估函数上的缺陷。蒙特卡罗树搜索策略加围棋专业知识的组合，经过近10年的发展，仍然无法挑战职业棋手，直到AlphaGo横空出世。AlphaGo完整继承了深蓝时代沿袭下来的“暴力搜索”算法框架，在状态空间搜索中使用的信息汇总策略也
15、与传统蒙特卡罗树搜索完全一样，而且在其选择策略中也同样使用大量手工编写的人门级围棋专业知识。“一鸣惊人”的AlphaGo，其实是从一个基本具备一流开源围棋软件水平的传统蒙特卡罗树搜索程序改造升级而来。4.4.1 围棋博弈程序的发展围棋博弈程序的发展4.4.1 围棋博弈程序的发展围棋博弈程序的发展图4.8 围棋博弈程序的分类4.4.2 AlphaGo博弈树搜索算法的改进 MCTS算法大致思想可类比MinMax算法：对于给定的当前根节点（某一棋局），通过计算机模拟推演以当前根节点出发的各种可能的走法，配合高效的“剪枝”算法来控制搜索空间大小，并用演算到最后一步的结果来反过来影响当前节点下一步棋的选
16、择。针对围棋相对于传统棋类AI的设计难点：l1）可能的走法太多（即Branching Factor较大）导致搜索空间非常大；l2）没有一个好的估值函数对进行中的围棋棋局计算一个静态得分。4.4.2 AlphaGo博弈树搜索算法的改进lMCTS提出解决方案：搜索空间更大，采取比Alpha-beta剪枝更激进的剪枝策略，只把有限的计算资源留给最最有希望的走法（即后面要讨论的选择（Selection）、扩展（Expansion）步骤要做的事情）；对于中间棋局好坏很难估计，那就干脆模拟到最后分出胜负为止（即后面要讨论的模拟Simulation）。4.4.2 AlphaGo博弈树搜索算法的改进MCTS算
17、法的基本思想和特点是：l将可能出现的状态转移过程用状态树表示；l从初始状态开始重复抽样，逐步扩展树中的节点；l在某个状态再次被访问时，可以利用已有的结果，提高效率；l在抽样过程中可以随时得到行为的评价。4.4.3 MCTS算法的四个基本步骤算法的四个基本步骤MCTS算法是一个多轮迭代算法，每一轮迭代都会以此经历四个阶段：选择（Selection），扩展（Expansion），模拟（Simulation）和回溯（Back Propagation）。图4.9 MCTS某一时刻搜索空间的情形4.4.3 MCTS算法的四个基本步骤算法的四个基本步骤l1)选择（Selection）：从根节点出发，自上而
18、下地选择一个“最最需要展开”的子节点，比如图4.9中选择（Selection）步骤当中，沿着粗线一路走到底的最下方的叶子节点。这个节点被选中，意味着当前状态下，系统认为沿着这个节点的这条路径，最有可能取胜。l2)扩展（Expansion）：对于上面被选中的节点，从它的子节点中挑选出一个最有希望的子节点，将它的子节点加入到博弈树的结构中，扩展的策略主要是逐次扩展的策略，该策略并非一次性将全部的字节点添加到树结构之中，而是设置一个窗口值，随这遍历次数的增加，逐次添加子节点到对应博弈树节点之下。4.4.3 MCTS算法的四个基本步骤算法的四个基本步骤l3)模拟（Simulation）：从刚刚扩展的这
19、个节点，继续向下模拟(向下模拟也称Rollout)，直到分出胜负。由于在这个阶段搜索深度需要达到最终分出胜负为止，所以会采用更加简单的搜索策略，以保证在合理时间内能够搜索到决胜节点。l4)回溯（Back Propagation）：既然模拟（Simulation）阶段已经搜索到最终的决胜节点，那么根据这个模拟（Simulation）的最终胜负，反过来更新祖先节点所在路径的估计值。具体来说，会更新这些节点所对应的得分，保证在下一轮迭代的时候这些节点会有更大的几率被选中。反之，如果模拟（Simulation）的最终结果是我方输，那么相应的节点都会受到惩罚，在下一轮迭代中会更小的几率被选中。4.4.3
20、 MCTS算法的四个基本步骤算法的四个基本步骤l 蒙特卡洛树搜索通过迭代来一步步地扩展博弈树的规模，UCT树是根据子节点的评价指标导引扩展的方向，这一评价指标便是UCB值。它表示在搜索过程中既要充分利用已有的知识，给胜率高的节点更多的机会，又要考虑探索那些暂时胜率不高的兄弟节点，这种对于“利用”（Exploitation）和“探索”（Exploration）进行权衡的关系便体现在UCT着法选择函数的定义上，即子节点Ni的UCB值按如下公式计算。4.4.3 MCTS算法的四个基本步骤算法的四个基本步骤l因此，MCTS的基本算法是：给胜率高的节点分配更多的计算力，计算越多越精确。经历过足够多轮的迭
21、代之后（或者限定时间耗尽），迭代结束。这时候，会从当前根节点的所有探索过的子节点中，选择一个得分最高的子节点，作为最终的下一步走法。4.4.3 MCTS算法的四个基本步骤算法的四个基本步骤蒙特卡洛树搜索（MCTS）算法的基本框架为：1.由当前局面建立根节点，生成根节点的全部子节点，分别进行模拟对局；2.从根节点开始，进行最佳优先搜索（包括上述4个基本步骤）；3.利用UCB公式计算每个子节点的UCB值，选择最大值的子节点；4.若此节点不是叶节点，则以此节点作为根节点，重复2；4.4.3 MCTS算法的四个基本步骤算法的四个基本步骤5.直到遇到叶节点，如果叶节点未曾经被模拟对局过，对这个叶节点模拟对局；否则为这个叶节点随机生成子节点，并进行模拟对局；6.将模拟对局的收益（一般胜为1负为0）按对应颜色更新该节点及各级祖先节点，同时增加该节点以上所有节点的访问次数；7.回到2，除非此轮搜索时间结束或者达到预设循环次数；8.从当前局面的子节点中挑选平均收益最高的给出最佳着法。
