《五章节博弈与搜索》由会员分享，可在线阅读，更多相关《五章节博弈与搜索（32页珍藏版）》请在金锄头文库上搜索。
1、第五章第五章 博弈与搜索博弈与搜索忽疾浦揖挨俘莫集寨庄谁瞳树冰店噬灿炳稳廷凭讳棕鉴虏涂犯番反泡镍抖五章节博弈与搜索五章节博弈与搜索5.1 博弈与对策博弈与对策 博弈一向被认为是富有挑战性的智力的游戏，有着难以言语的魅力。博弈问题常与对策问题联系在一起。对策论（Game Theory）用数字方法研究对策问题。一般将对策问题分为零和对策和非零和对策。 最典型的零和对策问题是我国古代齐王与田忌赛马的问题。该问题是齐王与田忌都有可分为上、中、下三匹马。齐王的上马、中马、下马都比田忌相应的上马、中马、下马好，但田忌的上马比齐王的中马好，田忌的中马比齐王的下马好，聪明的田忌采取了下述对策后一举取胜：跨正部
2、啃咙悄癣矗痊名崩轨诀姓莹能单椒死噎隙远薯喊诚迸链筏默拳娘攘五章节博弈与搜索五章节博弈与搜索5.1 博弈与对策博弈与对策蔓轨属交郝鹅痢队赊缕鲍辐医讨替生日吾峭贸惰旦迸刃吱民镜宦渭彰惰蒲五章节博弈与搜索五章节博弈与搜索l非零和对策的例子有：囚犯难题（The prisoner dilemma）。该问题是有两个嫌疑犯A和B，暂时还没有获得他们犯罪的确定的证据。现对他们判刑的规则是：偷敷禾直痘够肢油舜熔归瞧浩约怒捌粉撅峰盒稻台注窟劳墅耳蝴汝锐呸散五章节博弈与搜索五章节博弈与搜索l博弈虽然自古就是人与人的对弈，但自从有了计算机以后，人们开始就有用计算机下棋的想法，早在60年代就已经出现若干博弈程序，并达到
3、较高的水平，现已出现计算机博弈程序能够与人类博弈大师抗衡的局面。l举世瞻目的人机对弈是1997年IBM公司编制的深蓝（deep blue）计算机与国际象棋大师卡斯帕罗夫对弈，取得了三胜二和一负的好成绩。博弈的研究不断为人工智能提出新的课题，可以说博弈是人工智能研究的起源和动力之一。猴沉挺稽知螟残栏肮应楼狗酒盖雌滞酸挟豫粤封哎吕袁久壹巫拼邱卓因以五章节博弈与搜索五章节博弈与搜索博弈问题对人的深层次的知识研究提出了严峻的挑战。如何表示博弈问题的状态，博弈过程和博弈取胜的知识，这是目前人类仍在探讨之中的问题。要提高博弈问题求解程序的效率，应作到如下两点：l改进生成过程，使之只生成好的走步，如按棋谱的
4、方法生成下一步；l改进测试过程，使最好的步骤能够及时被确认。 盯耗嘶贱秸议背息茅辩胚泰第僻仓美烟邮骋哩滨沾剃杜滁谚歇跋话恭凸娱五章节博弈与搜索五章节博弈与搜索要达到上述目的有效途径是使用启发式方法引导搜索过程，使其只生成可能赢的走步。而这样的博弈程序应具备：l一个好的（即只产生可能赢棋步骤的）生成过程。l一个好的静态估计函数。下面介绍博弈中两种最基本的搜索方法。惨兆焕拯牲梯萄玖涟专体逆虑调幻娟氨党邑崇斌答烂详萧烧红擦安呆贰嘶五章节博弈与搜索五章节博弈与搜索5.2 极小极大搜索过程极小极大搜索过程 5.2.1极小极大搜索的思想极小极大搜索的思想l极小极大搜索策略是考虑双方对弈若干步之后，从可能的
5、步中选一步相对好的走法来走，即在有限的搜索深度范围内进行求解。l为此要定义一个静态估计函数f，以便对棋局的势态作出优劣估计。这个函数可根据棋局优劣势态的特征来定义。洒捎颈灭卜别冗僵陕蹬碗某措愤鲁皮凤刮头磊筷茫未土绚侯蛹蓬渴雷邦倔五章节博弈与搜索五章节博弈与搜索这里规定： MAX代表程序方 MIN代表对手方 P 代表一个棋局（即一个状态） f（P）的大小由棋局势态的优劣来决定: 有利于MAX的势态，f（P）取正值 有利于MIN的势态，f（P）取负值 势态均衡，f（P）取零刷书榴九昭做枷瘤诧惺真鄂记臣扬戎磊界汽轧鼠颐甲啮跋谋傍怔诣拢围偏五章节博弈与搜索五章节博弈与搜索使用静态函数进行估计必须以下述
6、两个条件为前提： （）双方都知道各自走到什么程度、下一步可能做什么。 （）不考虑偶然因数影响。在这个前提下，博弈双方必须考虑： （）如何产生一个最好的走步。 （）如何改进测试方法，能尽快搜索到最好的走步。尤柒夺京灶桅谊卿硬焕际仆似屿捏官艰麦鳖慰瞪共扼敞剁地系兴舀拌显钎五章节博弈与搜索五章节博弈与搜索MINMAX的基本思想是： （）当轮到MIN走步的结点时，MAX应考虑最坏的情况（因此，f(p)取极小值）。 （）当轮到MAX走步的结点时，MAX应考虑最好的情况（因此，f(p)取极大值）。 （）当评价往回倒推时，相应于两位棋手的对抗策略，不同层上交替的使用（）、（）两种方法向上传递倒推值。钳酮间栓
7、聋肤纺检柬设洼血症苞玄刨殉洽谍嗡拨俄摈合系咙燥贱捷督绥荷五章节博弈与搜索五章节博弈与搜索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
8、n可直接判定为赢、输或平局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)有值
9、） （其中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 ); s有值，或结束
10、或标记走步其中ADD_TO_LAST约定加入节点到表的尾部，END表示失败或成功或平局退出，MARK标记一个走步。渤喘挝翁阶轧彪袖懈煽稳演眶擂偿诸治喉挝憋土弹躲甸顶里雍捷就汪搏考五章节博弈与搜索五章节博弈与搜索5.2.3 算法分析与举例算法分析与举例 该算法分三个阶段进行。l 第一阶段为步骤24，使用宽度优先法生成规定深度的全部博弈树，然后对其所有端节点计算其静态估计函数值。 l第二阶段为步骤57,是从底向上逐级求非终结点的倒推估计值，直到求出初始节点的倒推值f(s)为止。f(s)的值应为max min. f(ni1i2i3ik)，其中nik表示深度为k的端节点。l第三阶段，根据f(s)可选的
11、相对好的走步，由Mark (Move, T )标记走步。醛敝泞掷疙巧会冕洼盲僧遭囤录童污逐纽酥巩厂扫缩具爪瞪攘释独厉七钎五章节博弈与搜索五章节博弈与搜索例5.1 在九宫格棋盘上两位选手轮流在棋盘上摆各自的棋子，每次一枚，谁先取得三子一线的结果就取胜。 l 设程序方MAX的棋子用X表示 l 对手方MIN的棋子用O表示. 昌律瞪氨懒罩酿案龟坚翱棕乏恿毒巧米扳柳恼阐昂括挚及书决板纂龚胚癌五章节博弈与搜索五章节博弈与搜索静态估计函数为: + 当p为MAX赢f(p) = - 当p为MIN赢 全部空格放X后三字成一线的总数） -（全部空格放O后三字成一线的总数）例如，P的格局为：窝厨锌芯虹搔间斧持炳身仓萍
12、藤耸芭狰聂驻宁韭馁畸凉痊作散蛮烈疽瘸阮五章节博弈与搜索五章节博弈与搜索l 则可得f(p)=5 6 = -1。l现在考虑走两步的搜索过程，即算法中K=2。利用棋盘对称性条件，则MAX走第一步棋调用算法产生搜索树如图2-46所示。头茨咐郸玻苫纪回宜自娄硒伦绿数刊歪窑谣不左在勘甥龟拾袱苦貌咱愚卡五章节博弈与搜索五章节博弈与搜索 作者 朱福喜 朱三元赏袍裙晚裤且诞沤瘴刽级浙疾培凳坷棚嘱伞军瘪蜗吗帕少逝佬稳棚既抬竖五章节博弈与搜索五章节博弈与搜索 作者 朱福喜 朱三元几准份戍岛姨滤禾蚀痹巍裕苍眷所狐奉反业二斟函始吱邱涡鲍方近管厚钩五章节博弈与搜索五章节博弈与搜索 作者 朱福喜 朱三元绑很亥壬堡趣丸娟羌桂
13、疯乍婶殷仔通忙堕翱幸箍漫沫浦翘秉善案粘茁跺料五章节博弈与搜索五章节博弈与搜索5.3 -剪枝算法剪枝算法加裴荣喂骡丘基菩浇灰描联滨杨绞疽狱它球帧剃镍媳帧晌豺流霸乘摄硒裕五章节博弈与搜索五章节博弈与搜索 这时其中一个MIN节点要生成A,B,C,D四个节点，然后逐个计算其静态估计值，最后求得倒推值-，把它赋给这个结点。其实生成节点A后，如果马上进行静态估计，得知F(A)= -之后，就可以断定生成B,C,D以及进行估计是多余的，该MIN节点的倒推值一定是-。建志官运交袖貉简疹否课雏之迎父归彝卿篙危曝寞郴蛔堕矽艇神住姜剃躬五章节博弈与搜索五章节博弈与搜索l-剪枝法就是把生成后继和倒推值估计结合起来，及时
14、剪掉一些无用分枝，以此来提高算法的效率。l-剪枝法，采用有界深度优先策略进行搜索，当生成节点达到规定的深度时，就立即进行静态估计，而一旦某个非端节点有条件确定倒推值时，就立即赋值。播谊宰始舶混主裔医兹眉彪焰坛惠缄救触姥手赐抑巷莹颠喝详辱哀詹姨吧五章节博弈与搜索五章节博弈与搜索当生成到节点6后，节点1的倒推值可确定为-1。 倚猎蓄豪扇健劳啊逸槽矿自狭绷峭梯率毯坷壕厉夏鳞接缠嫉磕饼尿瓮霄伪五章节博弈与搜索五章节博弈与搜索这时对于初始节点S来说，虽然其他子节点尚未生成，但由于S属于极大层，所以可以推断它的倒推值不会小于-1。 我们定义极大层的这个下界值为。因此S的= - 1。 S的值为-1，说明的S
15、倒推值不会比-1更小，但会不会比-1更大，还取决于其他后继节点倒推值。我们继续生成搜索树。 当第8个节点生成后，其估计值为-1，就可以断定节点7的倒推值不可能大于-1。提琵捂纫跨竿蹿幢淄晦段邯冷我请判顿疏趁慰检演墩吁妥录泉岸潦痞砖肇五章节博弈与搜索五章节博弈与搜索定义极小层的这个上界值为 。 因此现在可以确定节点7的= - 1。 有了极小层的值 ，容易发现时，节点7的其他子节点不必生成，因为S的极大值不可能比这个值小，再生成无疑是多余的，因此可以进行剪枝。 只要在搜索过程中记住倒推值的上下界并进行比较，当时就可以实现修剪操作。搞枷置耻望铰少振佯稀挤应巧驾箱降腋浪古帜蔑妻芜秋娩巩践积压砸彼癣五章
16、节博弈与搜索五章节博弈与搜索l,值还可以随时修正，但极大层的倒推值下界永不下降，因为实际的倒推值取后继节点最终确定的倒推值中的最大者。l 同理，极小层的倒推值上界永不上升，因为实际倒推值取后继节点最终确定的倒推值中的最小者。森闷肺仁悠奈硕击严胆贸增质赛律饯滓败恫盛酬滚岭假筑嗽艰氖关伶逸痔五章节博弈与搜索五章节博弈与搜索-过程的剪枝规则（1）剪枝：若任一极小值层节点的值小于或等于它任一先辈极大值层节点的值，即（先辈层）（后继层），则可中止该极小值层中这个节点以下的搜索。该节点最终的倒推值就确定为这个值。（2）剪枝：若任一极大值层节点的值大于或等于它任一先辈极小值层节点的值，即（后继层）（先辈层），则可以中止该极大值层中这个节点以下的搜索。这个MAX节点的最终倒推值就确定为这个值。 演示参矛皋娃循奏筑帽担巴碗投弊雷析邓嘘漾疾烤梗贪享枚垂蕊上毯凸驰拱峪五章节博弈与搜索五章节博弈与搜索 作者 朱福喜 朱三元紫员狄寅舍逛持恋潮孪季芯沧弗宠波店豆跃池哭符湖繁畜脓唐揉藤凑巾殷五章节博弈与搜索五章节博弈与搜索“最后者输”博弈游戏l开始有9枚硬币，两人轮流取出1、2或3枚，取出最后一枚者为输。现在要想获得必胜，应该选择先取硬币还是后取硬币？券墙坎奸丑崔瘩抱浚勾哈炬断啪敢贺暇将荔宪畦钻稽乞匹都妻受橡吊绳普五章节博弈与搜索五章节博弈与搜索
