人工智能博弈树的

☼●○

☼●○

☼●○

☼●○●

☼○●

☼○●

☼○●

☼○2.3博弈树搜索20世纪60年代，研制出的西洋跳棋和国际象棋的博弈程序到达了巨匠级的程度。1958约翰•麦卡锡提出博弈树搜索算法1997年，IBM公司研制的“深蓝〞国际象棋程序，采用博弈树搜索算法，该程序战胜了国际象棋世界冠军卡斯帕罗夫。1.概述正在与深蓝下棋的卡斯帕罗夫博弈问题特点：双人对弈，轮番走步。信息完备，双方所得到的信息是一样的。零和，即对一方有利的棋，对另一方一定是不利的，不存在对双方均有利或无利的棋。1.概述博弈的特性两个棋手交替地走棋；竞赛的最终结果，是赢、输和平局中的一种；可用图搜索技术进展，但效率很低；博弈的过程，是寻觅置对手于必败态的过程；双方都无法干涉对方的选择。1.概述2.Grundy博弈下棋的双方是对立的，命名博弈的双方，一方为“正方〞，这类节点称为“MAX〞节点；另一方为“反方〞，这类节点称为“MIN〞节点。正方和反方是交替走步的，因此MAX节点和MIN节点会交替出现。2.Grundy博弈Grundy博弈是一个分钱币的游戏。有一堆数目为N的钱币，由两位选手轮番进展分堆，要求每个选手每次只把其中某一堆分成数目不等的两小堆。例如，选手甲把N分成两堆后，轮到选手乙就可以挑其中一堆来分，如此进展下去，直到有一位选手先无法把钱币再分成不相等的两堆时就得认输。2.Grundy博弈设初始形状为(7，MIN)，建立问题的形状空间图，图中一切终结点均表示该选手必输的情况，取胜方的目的是设法使棋局开展为终了在对方走步时的终结点上。MIN先走MAX必胜2.Grundy博弈结点A是MAX的搜索目的，而结点B，C那么为MIN的搜索目的。2.Grundy博弈搜索战略要思索的问题是：对MIN走步后的每一个MAX结点，必需证明MAX对MIN能够走的每一个棋局对弈后能获胜，即MAX必需思索应付MIN的一切招法，这是一个与的含意，因此含有MAX符号的结点可看成与结点。

2.Grundy博弈对MAX走步后的每一个MIN结点，只须证明MAX有一步能走赢就可以，即MAX只需思索能走出一步棋使MIN无法招架就成，因此含有MIN符号的结点可看成或结点。2.Grundy博弈对弈过程的搜索图呈现出与或图表示的方式。实现一种取胜的战略就是搜索一个解图的问题，解图就代表一种完好的博弈战略。2.Grundy博弈中国象棋一盘棋平均走50步，总形状数约为10的161次方。假设1毫微秒走一步，约需10的145次方年。结论：不能够穷举。3.极小极大搜索过程对各个局面进展评价评价的目的：对后面的形状提早进展思索，并且以各种形状的评价值为根底作出最好的走棋选择。评价的方法：用评价函数对棋局进展评价。赢的评价值设为+∞，输的评价值设为-∞，平局的评价值设为0。评价的规范：由于下棋的双方是对立的，只能选择其中一方为评价的规范方。3.极小极大搜索过程MAX节点和MIN节点命名博弈的双方，一方为“正方〞，对每个形状的评价都是对应于该方的胜负的。例如，赢2个，输1个等，都是指正方的。正方每走一步，都在选择使本人博得更多的节点，因此这类节点称为“MAX〞节点；3.极小极大搜索过程另一方为“反方〞，对每个形状的评价都是对应于对手的胜负的。例如，赢2个，输一个，其实是指本人输2个，赢1个的。反方每走一步，都在选择使对手输得更多的节点，因此这类节点称为“MIN〞节点。3.极小极大搜索过程由于正方和反方是交替走步的，因此MAX节点和MIN节点会交替出现。3.极小极大搜索过程正方〔MAX节点〕从一切子节点中，选取具有最大评价值的节点。反方〔MIN节点〕从其一切子节点中，选取具有最小评价值的节点。反复进展这种选取，就可以得到双方各个节点的评价值。这种确定棋步的方法，称为极小极大搜索法。3.极小极大搜索过程3.极小极大搜索过程5-333-3022-30-23541-30689-3MINMAX0MAXMIN3.极小极大搜索过程015-333-3022-30-23541-30689-30-33-3-3-21-36-3031601MAXMINMAXMIN3.极小极大搜索过程在九宫格棋盘上，两位选手轮番在棋盘上摆各自的棋子(每次一枚)，谁先获得三线的结果就取胜。设程序方MAX的棋子用(×)表示，MAX先走。对手MIN的棋子用(o)表示。例如：3.极小极大搜索过程MIN取胜估计函数f(p)=(一切空格都放上MAX的棋子之后，MAX的三子成线数)－(一切空格都放上MIN的棋子之后，MIN的三子成线的总数)假设P是MAX获胜的格局，那么f(p)=+∞；假设P是MIN获胜的格局，那么f(p)＝-∞。3.极小极大搜索过程3.极小极大搜索过程估计函数值f(p)=6-4=2估计函数f(p)=(一切空格都放上MAX的棋子之后，MAX的三子成线(行、列、对角)数)－(一切空格都放上MIN的棋子之后，MIN的三子成线(行、列、对角)的总数)当前棋局f(p)=23.极小极大搜索过程一字棋第一阶段搜索树3.极小极大搜索过程一字棋第二阶段搜索树3.极小极大搜索过程一字棋第三阶段搜索树设有一个摆放三个子的棋盘残局，如以下图所示，〇和╳在终了前有三步棋可以走，而且设走第一步的是╳。这时存在着三个空格A，B，C，用博弈树搜索算法判别应该把棋子放到哪一格内。AB╳╳╳〇〇C〇棋盘残局举例：3.极小极大搜索过程AB╳╳╳〇〇C〇╳B╳╳╳〇〇C〇╳〇╳╳╳〇〇C〇╳B╳╳╳〇〇〇〇0A╳╳╳╳〇〇C〇〇╳╳╳╳〇〇C〇A╳╳╳╳〇〇〇〇AB╳╳╳〇〇╳〇〇B╳╳╳〇〇╳〇A〇╳╳╳〇〇╳〇-1-0-10--0MAX节点MIN节点终端节点3.极小极大搜索过程对于棋盘残局中的╳来说，最好的选择，是将╳放在C的位置上，这时可以导致平局局面。3.极小极大搜索过程-剪支法的引入在极小极大法中，必需求出一切终端节点的评价值，当预先思索的棋步比较多时，计算量会大大添加。为了提高搜索的效率，引入了经过对评价值的上下限进展估计，从而减少需进展评价的节点范围的-剪支法。4.-搜索过程作为正方出现的MAX节点，假设它的MIN子节点有N个，那么当它的第一个MIN子节点的评价值为时，那么对于其它的子节点，假设有高过的，就取那最高的值作为该MAX节点的评价值；假设没有，那么该MAX节点的评价值为。总之，该MAX节点的评价值不会低于，这个就称为该MAX节点的评价下限值。4.-搜索过程MAX节点的评价下限值MIN节点的评价上限值作为反方出现的MIN节点，假设它的MAX子节点有N个，那么当它的第一个MAX子节点的评价值为时，那么对于其它子节点，假设有低于的，就取那个低于的值作为该MIN节点的评价值；假设没有，那么该MIN节点的评价值取。总之，该MIN节点的评价值不会高过，这个就称为该MIN节点的评价上限值。4.-搜索过程剪支法

MAX节点

MIN节点=

剪支ABCD4.-搜索过程设MAX节点的下限为，那么其一切的MIN子节点中，其评价值的上限小于等于的节点，其以下部分的搜索都可以停顿了，即对这部分节点进展了剪支。设MIN节点的上限为，那么其一切的MAX子节点中，其评价值的下限大于等于的节点，其以下部分的搜索都可以停顿了，即对这部分节点进展了剪支。MAX节点

MIN节点=

剪支ABCD4.-搜索过程剪支法

ABCDEFGHIJKLNOM4.-搜索过程MAX节点MAX节点MIN节点终端节点35652164MAX节点(5,)35652164(6,)(2,)(-,5)(-,2)(5,)MIN节点终端节点剪支剪支ABCDEFGHIJKLNOMMAX节点4.-搜索过程一字棋第一阶段-剪支方法4.-搜索过程4.-搜索过程极大节点的下界为。极小节点的上界为。剪支的条件：后辈节点的值≤祖先节点的值时，剪支后辈节点的值≥祖先节点的值时，剪支简记为：极小≤极大，剪支极大≥极小，剪支4.-搜索过程86-31453-3503-3022-30-2309-300-303305411-31661abcdefghijkmnMAXMINMAXMIN改良方法运用-剪支技术，当不满足剪支条件(即)时或值比值大不了多少或极相近时，这时也可以进展剪支，以便有条件把搜索集中到会带来更大效果的其他途径上，这就是中止对效益不大的一些子树的搜索，以提高搜索效率。

4.-搜索过程

不严厉限制搜索的深度。当到达深度限制时，如出现博弈格局有能够发生较大变化时，那么应多搜索几层，使格局进入较稳定形状后再中止，这样可使倒推值计算的结果比较合理，防止思索不充分产生的影响，这是