人工智能-博弈树的搜索

☼●○

☼●○

☼●○

☼●○●

☼○●

☼○●

☼○●

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

2.Grundy博弈人工智能-博弈树的搜索第11页对MAX走步后每一个MIN结点，只须证实MAX有一步能走赢就能够，即MAX只要考虑能走出一步棋使MIN无法招架就成，所以含有MIN符号结点可看成或结点。2.Grundy博弈人工智能-博弈树的搜索第12页对弈过程搜索图展现出与或图表示形式。实现一个取胜策略就是搜索一个解图问题，解图就代表一个完整博弈策略。2.Grundy博弈人工智能-博弈树的搜索第13页中国象棋一盘棋平均走50步，总状态数约为10161次方。假设1毫微秒走一步，约需10145次方年。结论：不可能穷举。3.极小极大搜索过程人工智能-博弈树的搜索第14页对各个局面进行评定评定目标：对后面状态提前进行考虑，而且以各种状态评定值为基础作出最好走棋选择。评定方法：用评价函数对棋局进行评定。赢评定值设为+∞，输评定值设为-∞，平局评定值设为0。评定标准：因为下棋双方是对立，只能选择其中一方为评定标准方。3.极小极大搜索过程人工智能-博弈树的搜索第15页MAX节点和MIN节点命名博弈双方，一方为“正方”，对每个状态评定都是对应于该方输赢。比如，赢2个，输1个等，都是指正方。正方每走一步，都在选择使自己赢得更多节点，所以这类节点称为“MAX”节点；3.极小极大搜索过程人工智能-博弈树的搜索第16页另一方为“反方”，对每个状态评定都是对应于对手输赢。比如，赢2个，输一个，其实是指自己输2个，赢1个。反方每走一步，都在选择使对手输得更多节点，所以这类节点称为“MIN”节点。3.极小极大搜索过程人工智能-博弈树的搜索第17页因为正方和反方是交替走步，所以MAX节点和MIN节点会交替出现。3.极小极大搜索过程人工智能-博弈树的搜索第18页正方（MAX节点）从全部子节点中，选取含有最大评定值节点。反方（MIN节点）从其全部子节点中，选取含有最小评定值节点。重复进行这种选取，就能够得到双方各个节点评定值。这种确定棋步方法，称为极小极大搜索法。

3.极小极大搜索过程人工智能-博弈树的搜索第19页3.极小极大搜索过程人工智能-博弈树的搜索第20页5-333-3022-30-23541-30689-3MINMAX0MAXMIN3.极小极大搜索过程人工智能-博弈树的搜索第21页015-333-3022-30-23541-30689-30-33-3-3-21-36-3031601MAXMINMAXMIN3.极小极大搜索过程人工智能-博弈树的搜索第22页

在九宫格棋盘上，两位选手轮番在棋盘上摆各自棋子(每次一枚)，谁先取得三线结果就取胜。设程序方MAX棋子用(×)表示，MAX先走。对手MIN棋子用(o)表示。比如：3.极小极大搜索过程MIN取胜人工智能-博弈树的搜索第23页

预计函数f(p)=(全部空格都放上MAX棋子之后，MAX三子成线数)－(全部空格都放上MIN棋子之后，MIN三子成线总数)

若P是MAX获胜格局，则f(p)=+∞；若P是MIN获胜格局，则f(p)＝-∞。3.极小极大搜索过程人工智能-博弈树的搜索第24页3.极小极大搜索过程预计函数值f(p)=6-4=2预计函数f(p)=(全部空格都放上MAX棋子之后，MAX三子成线(行、列、对角)数)－(全部空格都放上MIN棋子之后，MIN三子成线(行、列、对角)总数)当前棋局f(p)=2人工智能-博弈树的搜索第25页3.极小极大搜索过程一字棋第一阶段搜索树人工智能-博弈树的搜索第26页3.极小极大搜索过程一字棋第二阶段搜索树人工智能-博弈树的搜索第27页3.极小极大搜索过程一字棋第三阶段搜索树人工智能-博弈树的搜索第28页

设有一个摆放三个子棋盘残局，以下列图所表示，〇和╳在结束前有三步棋能够走，而且设走第一步是╳。这时存在着三个空格A，B，C，用博弈树搜索算法判断应该把棋子放到哪一格内。

AB╳╳╳〇〇C〇棋盘残局举例：3.极小极大搜索过程人工智能-博弈树的搜索第29页AB╳╳╳〇〇C〇╳B╳╳╳〇〇C〇╳〇╳╳╳〇〇C〇╳B╳╳╳〇〇〇〇0A╳╳╳╳〇〇C〇〇╳╳╳╳〇〇C〇A╳╳╳╳〇〇〇〇AB╳╳╳〇〇╳〇〇B╳╳╳〇〇╳〇A〇╳╳╳〇〇╳〇-1-

0-

10-

-

0MAX节点MIN节点终端节点3.极小极大搜索过程人工智能-博弈树的搜索第30页

对于棋盘残局中╳来说，最好选择，是将╳放在C位置上，这时能够造成平局局面。

3.极小极大搜索过程人工智能-博弈树的搜索第31页-剪支法引入在极小极大法中，必须求出全部终端节点评定值，当预先考虑棋步比较多时，计算量会大大增加。为了提升搜索效率，引入了经过对评定值上下限进行预计，从而降低需进行评定节点范围

-剪支法。4.-搜索过程人工智能-博弈树的搜索第32页

作为正方出现MAX节点，假设它MIN子节点有N个，那么当它第一个MIN子节点评定值为时，则对于其它子节点，假如有高过，就取那最高值作为该MAX节点评定值；假如没有，则该MAX节点评定值为。总之，该MAX节点评定值不会低于，这个就称为该MAX节点评定下限值。4.-搜索过程

MAX节点评定下限值

人工智能-博弈树的搜索第33页MIN节点评定上限值

作为反方出现MIN节点，假设它MAX子节点有N个，那么当它第一个MAX子节点评定值为时，则对于其它子节点，假如有低于，就取那个低于值作为该MIN节点评定值；假如没有，则该MIN节点评定值取。总之，该MIN节点评定值不会高过，这个就称为该MIN节点评定上限值。4.-搜索过程人工智能-博弈树的搜索第34页

剪支法

MAX节点

MIN节点=

剪支ABCD4.-搜索过程

设MAX节点下限为，则其全部MIN子节点中，其评定值上限小于等于节点，其以下部分搜索都能够停顿了，即对这部分节点进行了剪支。人工智能-博弈树的搜索第35页

设MIN节点上限为，则其全部MAX子节点中，其评定值下限大于等于节点，其以下部分搜索都能够停顿了，即对这部分节点进行了剪支。MAX节点

MIN节点=

剪支ABCD4.-搜索过程

剪支法

人工智能-博弈树的搜索第36页ABCDEFGHIJKLNOM4.-搜索过程MAX节点MAX节点MIN节点终端节点35652164人工智能-博弈树的搜索第37页MAX节点(5,

)35652164(6,

)(2,

)(-,5)(-,2)(5,

)MIN节点终端节点

剪支

剪支ABCDEFGHIJKLNOMMAX节点4.-搜索过程人工智能-博弈树的搜索第38页一字棋第一阶段

-剪支方法4.-搜索过程人工智能-博弈树的搜索第39页4.-搜索过程极大节点下界为。极小节点上界为。剪支条件：后辈节点值≤祖先节点值时，剪支后辈节点值≥祖先节点值时，剪支简记为：极小≤极大，剪支极大≥极小，剪支人工智能-博弈树的搜索第40页4.-搜索过程86-31453-3503-3022-30-2309-300-303305411-31661abcdefghijkmnMAXMINMAXMIN人工智能-博弈树的搜索第41页改进方法

使用

-剪支技术，当不满足剪支条件(即

)时或

值比

值大不了多少或极相近时，这时也能够进行剪支，方便有条件把搜索集中到会带来更大效果其它路径上，这就是中止对效益不大一些子树搜索，以提升搜索效率。

4.-搜索过程人工智能-博弈树的搜索第42页

不严格限制搜索深度。当抵达深度限制时，如出现博弈格局有可能发生较大改变时，则应多搜索几层，使格局进入较稳定状态后再中止，这么可使倒推值计算结果比较合理，防止考虑不充分产生影响，