《第五章博弈与搜索.ppt》由会员分享,可在线阅读,更多相关《第五章博弈与搜索.ppt(32页珍藏版)》请在三一文库上搜索。
1、,第五章 博弈与搜索,5.1 博弈与对策,博弈一向被认为是富有挑战性的智力的游戏,有着难以言语的魅力。博弈问题常与对策问题联系在一起。对策论(Game Theory)用数字方法研究对策问题。一般将对策问题分为零和对策和非零和对策。 最典型的零和对策问题是我国古代齐王与田忌赛马的问题。该问题是齐王与田忌都有可分为上、中、下三匹马。齐王的上马、中马、下马都比田忌相应的上马、中马、下马好,但田忌的上马比齐王的中马好,田忌的中马比齐王的下马好,聪明的田忌采取了下述对策后一举取胜:,5.1 博弈与对策,非零和对策的例子有:囚犯难题(The prisoner dilemma)。该问题是有两个嫌疑犯A和B,
2、暂时还没有获得他们犯罪的确定的证据。现对他们判刑的规则是:,博弈虽然自古就是人与人的对弈,但自从有了计算机以后,人们开始就有用计算机下棋的想法,早在60年代就已经出现若干博弈程序,并达到较高的水平,现已出现计算机博弈程序能够与人类博弈大师抗衡的局面。 举世瞻目的人机对弈是1997年IBM公司编制的深蓝(deep blue)计算机与国际象棋大师卡斯帕罗夫对弈,取得了三胜二和一负的好成绩。博弈的研究不断为人工智能提出新的课题,可以说博弈是人工智能研究的起源和动力之一。,博弈问题对人的深层次的知识研究提出了严峻的挑战。如何表示博弈问题的状态,博弈过程和博弈取胜的知识,这是目前人类仍在探讨之中的问题。
3、要提高博弈问题求解程序的效率,应作到如下两点: 改进生成过程,使之只生成好的走步,如按棋谱的方法生成下一步; 改进测试过程,使最好的步骤能够及时被确认。,要达到上述目的有效途径是使用启发式方法引导搜索过程,使其只生成可能赢的走步。而这样的博弈程序应具备: 一个好的(即只产生可能赢棋步骤的)生成过程。 一个好的静态估计函数。 下面介绍博弈中两种最基本的搜索方法。,5.2 极小极大搜索过程,5.2.1极小极大搜索的思想 极小极大搜索策略是考虑双方对弈若干步之后,从可能的步中选一步相对好的走法来走,即在有限的搜索深度范围内进行求解。 为此要定义一个静态估计函数f,以便对棋局的势态作出优劣估计。这个函
4、数可根据棋局优劣势态的特征来定义。,这里规定: MAX代表程序方 MIN代表对手方 P 代表一个棋局(即一个状态) f(P)的大小由棋局势态的优劣来决定: 有利于MAX的势态,f(P)取正值 有利于MIN的势态,f(P)取负值 势态均衡,f(P)取零,使用静态函数进行估计必须以下述两个条件为前提: ()双方都知道各自走到什么程度、下一步可能做什么。 ()不考虑偶然因数影响。 在这个前提下,博弈双方必须考虑: ()如何产生一个最好的走步。 ()如何改进测试方法,能尽快搜索到最好的走步。,MINMAX的基本思想是: ()当轮到MIN走步的结点时,MAX应考虑最坏的情况(因此,f(p)取极小值)。
5、()当轮到MAX走步的结点时,MAX应考虑最好的情况(因此,f(p)取极大值)。 ()当评价往回倒推时,相应于两位棋手的对抗策略,不同层上交替的使用()、()两种方法向上传递倒推值。,5.2.2 极小极大搜索算法,极小极大过程的算法如下: 1. T:=(s, MAX ), OPEN:=(s), CLOSED:=( ); 开始时树由初始结点构成,OPEN表只含有s. 2. LOOP1: IF OPEN = ( ) THEN GO LOOP2; 3.:FIRST(OPEN),REMOVE( n, OPEN ), ADD_TO_LAST( n, CLOSED ); /约定加到尾部,4. IF n可直
6、接判定为赢、输或平局 THEN f(n):= -0, GO LOOP1 ELSE EXPAND( n )ni , ADD ( ni , T ) IF d( ni ) 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:= LAST(CLOSED);,6. IF (npMAX)(f(nc iMIN)有值) (其中nci为np的下一层节点) THEN f( np):=MAX f(nci), REMO
7、VE(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 ); s有值,或结束或标记走步 其中ADD_TO_LAST约定加入节点到表的尾部,END表示失败或成功或平局退出,MARK标记一个走步。,5.2.3 算法分析与举例,该算法分三个阶段进行。 第一阶段为步骤2
8、4,使用宽度优先法生成规定深度的全部博弈树,然后对其所有端节点计算其静态估计函数值。 第二阶段为步骤57,是从底向上逐级求非终结点的倒推估计值,直到求出初始节点的倒推值f(s)为止。f(s)的值应为max min. f(ni1i2i3ik),其中nik表示深度为k的端节点。 第三阶段,根据f(s)可选的相对好的走步,由Mark (Move, T )标记走步。,例5.1 在九宫格棋盘上两位选手轮流在棋盘上摆各自的棋子,每次一枚,谁先取得三子一线的结果就取胜。 设程序方MAX的棋子用X表示 对手方MIN的棋子用O表示.,静态估计函数为: + 当p为MAX赢 f(p) = - 当p为MIN赢 全部空
9、格放X后三字成一线的总数) -(全部空格放O后三字成一线的总数) 例如,P的格局为:,则可得f(p)=5 6 = -1。 现在考虑走两步的搜索过程,即算法中K=2。利用棋盘对称性条件,则MAX走第一步棋调用算法产生搜索树如图2-46所示。,作者 朱福喜 朱三元,作者 朱福喜 朱三元,作者 朱福喜 朱三元,5.3 -剪枝算法,这时其中一个MIN节点要生成A,B,C,D四个节点,然后逐个计算其静态估计值,最后求得倒推值-,把它赋给这个结点。其实生成节点A后,如果马上进行静态估计,得知F(A)= -之后,就可以断定生成B,C,D以及进行估计是多余的,该MIN节点的倒推值一定是-。,-剪枝法就是把生成
10、后继和倒推值估计结合起来,及时剪掉一些无用分枝,以此来提高算法的效率。 -剪枝法,采用有界深度优先策略进行搜索,当生成节点达到规定的深度时,就立即进行静态估计,而一旦某个非端节点有条件确定倒推值时,就立即赋值。,当生成到节点6后,节点1的倒推值可确定为-1。,这时对于初始节点S来说,虽然其他子节点尚未生成,但由于S属于极大层,所以可以推断它的倒推值不会小于-1。 我们定义极大层的这个下界值为。因此S的= - 1。 S的值为-1,说明的S倒推值不会比-1更小,但会不会比-1更大,还取决于其他后继节点倒推值。我们继续生成搜索树。 当第8个节点生成后,其估计值为-1,就可以断定节点7的倒推值不可能大
11、于-1。,定义极小层的这个上界值为 。 因此现在可以确定节点7的= - 1。 有了极小层的值 ,容易发现时,节点7的其他子节点不必生成,因为S的极大值不可能比这个值小,再生成无疑是多余的,因此可以进行剪枝。 只要在搜索过程中记住倒推值的上下界并进行比较,当时就可以实现修剪操作。,值还可以随时修正,但极大层的倒推值下界永不下降,因为实际的倒推值取后继节点最终确定的倒推值中的最大者。 同理,极小层的倒推值上界永不上升,因为实际倒推值取后继节点最终确定的倒推值中的最小者。,-过程的剪枝规则,(1)剪枝:若任一极小值层节点的值小于或等于它任一先辈极大值层节点的值,即(先辈层)(后继层),则可中止该极小值层中这个节点以下的搜索。该节点最终的倒推值就确定为这个值。 (2)剪枝:若任一极大值层节点的值大于或等于它任一先辈极小值层节点的值,即(后继层)(先辈层),则可以中止该极大值层中这个节点以下的搜索。这个MAX节点的最终倒推值就确定为这个值。 演示,作者 朱福喜 朱三元,“最后者输”博弈游戏,开始有9枚硬币,两人轮流取出1、2或3枚,取出最后一枚者为输。现在要想获得必胜,应该选择先取硬币还是后取硬币?,
链接地址:https://www.31doc.com/p-2582602.html