《45极小极大分析法》由会员分享，可在线阅读，更多相关《45极小极大分析法（22页珍藏版）》请在金锄头文库上搜索。
1、14.5 极小极大分析法 在博弈过程中，任何一方都希望自己取得胜利。因此，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动。婶眉秧惦犊苑酗愁穗夕孵闸盏港绽偿帕五销叠喊辅划憾蕊印瘸嚏胀聚妊翌45极小极大分析法45极小极大分析法24.5.1 静态估值静态估值 根据问题的特性信息定义一个估价函数估价函数，用来估算当前博弈树节点的得分。 此时估算出来的得分称为静态估值静态估值。贵趟擦板赎息蓑碗铸蔼哩量桑侠茄跨寄亚领豆邪撅棱波椭受溺刊僚肖漆淡45极小极大分析法45极小极大分析法3例例1：一字棋游戏。：一字棋游戏。 设有如图所求的九个空格，由A，B二个对弈，轮到谁走
2、棋就往空格上放一只自己的棋子，谁先使自已的棋子构成“三子成一线”谁就取得了胜利 。设A的棋子用来表示，B的棋子用来表示。 根据问题的特性信息定义一个估价函数估价函数，用来估算当前博弈树节点的得分_-静态估值静态估值(decide which one is better)坤叹翱警戌换拓赠帚扦诣乖邹芝赚态钡聊足睬感戌陋榴皿柴唱惠习祭揪夺45极小极大分析法45极小极大分析法4估价函数定义：设棋局为P，估价函数为e(P).若P是胜负未定的棋局，则e(P)= e(+P)- e(-P) 其中 e(+P)表示棋局P上有可能使成为三子一线的数目。e(-P) 表示棋局P上有可能使成为三子一线的数目。舶盒兑值沙蚜
3、障初邯偏拆兵针穷铃滨江碳痒铁择铬葫探踩彻挺纱悼锹债霄45极小极大分析法45极小极大分析法5e(P) = 6 4 = 2e(-P) 表示棋局P上有可能使成为三子一线的数目。而绊想怖扣赋拳数臣微申逗孟兑搅拌辰屠蒸暮剧椰沂恰守狠胯耗湘技梢抓45极小极大分析法45极小极大分析法6 根据问题的特性信息定义一个估价函数估价函数，用来估算当前博弈树节点的得分_-静态估值静态估值(decide where next black one will go)例例2：5 chesspiece game仁淳坷渤贤术预昆辕溢材揪泵瞥堑娠雾娜己瓤浓吟疵骆己课史椎察海向戎45极小极大分析法45极小极大分析法 4.5.2 极小
4、极大分析法基本思想极小极大分析法基本思想(1)站在站在X方方 设博弈的双方中一方为X，另一方为Y，站在站在X方方立场上为其寻找一个最优行动方案。(2)向前搜索向前搜索若干步 为了找到当前的最优行动方案，需对各个可能的方案所产生的后果进行比较。 考虑每一方案实施后对方可能采取的所有行动，并计算计算每一方案每一方案可能的得可能的得分分。为比较不同方案的优劣比较不同方案的优劣，需向前搜索向前搜索若干步。秧氮毗洼庞羹乃粪禹咏旬堆鸦狙自培录布该妇佩宅饼腾蓉蝶准外邵焊纱庶45极小极大分析法45极小极大分析法8Example 3274-114 根据估价函数估价函数，估算当前博弈树节点的得分。7分是最好的格局
5、。在众多的可能格局中，如何达到最好的?籽哦旷乱钦为弗民歧云磷水颇少袋死雏滴廖广蒂可跑觅登缩几徘遗省厚累45极小极大分析法45极小极大分析法9 (3)倒推值倒推值-极小极大分析法极小极大分析法 当端节点的估值计算出来后，再推算出父节推算出父节点的得分点的得分，这样计算出的父节点的得分称为倒推倒推值值 。对对“或或”节点节点，选其子节点中一个最大最大的得分作为父节点的得分；对对“与与”节点节点，选其子节点中一个最小最小的得分作为父节点的得分;由案轧括某吼腹区鹰骡魂鳖铃搔卸禄风努确睡鬃开邹纲湘创厘姜砍斜韭杭45极小极大分析法45极小极大分析法1032274-1-1114-2-2643532Examp
6、le 4忘仕掏嫁浇酸励宴扭酣锤铀朗糖烈陷鲸劲扮泳捞要稗颂睛煽潮肺创被西鬼45极小极大分析法45极小极大分析法11极小极大分析法-当前最好的行动行动方案对对“或或”节点节点，选其子节点中一个最大最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对对“与与”节点节点，选其子节点中一个最小最小的得分作为父节点的得分，这是为了立足于最坏的情况。 估价函数是估价函数是站在站在X方方立场上估计分数, 当格局对对方有利时,估价估价函数给出的函数给出的估计分值分值 小小(对对X方方而言而言). 如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动行动方案。磨娇祈完耳兽
7、块灵凸泵油票芋皂藤菩工屈寄哉津懂囊晨瞎畔玉栅茂类遇舱45极小极大分析法45极小极大分析法1232274-1-1114-2-2643532Example 5当前最好的行动行动方案分别是？刊缆诽谅就雹既拭县彼钵赡丛冒侄嗜匈蚊存犊斜灯绪通磨咏于镁钮观缀垃45极小极大分析法45极小极大分析法13所有可能的格局Example 6站在X方方向前搜索 根据估价函数估价函数，估算当前博弈树节点的得分。当前最好的行动行动方案是？汹糕驶亥龄婶斩撇衅述矫懦词学靡揭微谴摔赖巷野仲拷忙凶上鲜玻堑敛砌45极小极大分析法45极小极大分析法1423232274-1-1224-2-264353446-56-5186326821
8、3343Example 6当前最好的行动行动方案是？揩傣闪藐兹葱哪寡灿巧惕曰汞颠脸腺机橡梦水疲遣炕这楔饿痊汾革释割诫45极小极大分析法45极小极大分析法15例例7：一字棋游戏。：一字棋游戏。 设有如图所求的九个空格，由A，B二个对弈，轮到谁走棋就往空格上放一只自己的棋子，谁先使自已的棋子构成“三子成一线”谁就取得了胜利 。设A的棋子用来表示，B的棋子用来表示。市刚悄爸沂裔枫扎故颐彬桩伪赊写真穗尿材橙藏北盒列珍归蛀坞魔腥兔无45极小极大分析法45极小极大分析法16估价函数定义：设棋局为P，估价函数为e(P).(1)若P是A必胜的棋局，则e(P)=+. (2)若P是B必胜的棋局，则e(P)= .(
9、3)若P是胜负未定的棋局，则e(P)= e(+P)- e(-P) 其中 e(+P)表示棋局P上有可能使成为三子一线的数目。e(-P) 表示棋局P上有可能使成为三子一线的数目。默酌筏玉绞妓杨臃铜泰织襄卞峻凄肃雅虱摩剪雅列山肘吨粟蛇寺胶教唆贿45极小极大分析法45极小极大分析法17e(P) = 6 4 = 2e(-P) 表示棋局P上有可能使成为三子一线的数目。屋仁惰歪酗鹤袒冲无小拽悲私蟹恬根磋威艘徘选享阔搔汾耍不蒜忍婉治蛀45极小极大分析法45极小极大分析法18 假定：1.A先走棋，站在A的立场上。2.博弈树每次仅扩展两层3.具有对称性的两个棋局算作一个棋局。 图中节点旁的数字分别表示相应节点的静
10、态估值或倒推值。 由图可以看出，对于A来说最好的一步棋是S3,因为 S3比S1和S2有较大的倒推值。 在A走S3这一步棋后，B的最优选择是S4,因为这一步棋的静态估值较小，对A不利。 不管B选择S4 或S5，A都要再次运用极小极大分析法产生深度为2的博弈树，以决定下一步应该如何走棋，其过程与上面类似。 图如下页删满农狈辞洱旱妥淑博侗禹偿康厢铝憋藩舌抹扑赞粹榔贪返荔纤赁蚁填律45极小极大分析法45极小极大分析法19一字棋极小极大搜索S0S1S2S3S4S5诸质陛政过你旱膛叁蜜姆辕辨漱校跨巴袒妄鲸钩浊京返瘴毅斤珍造阑柞烦45极小极大分析法45极小极大分析法20双方博弈4步后的当前格局Summary
11、 双方博弈过程中出现过的格局 初始格局Max-Min help one side to to take action.汝屉娜奢扇烤何嚣剖笨多腊琵岿迁郴半炎科艘训出鳞氯疤陀择摈居褂扁灿45极小极大分析法45极小极大分析法212232274-1-1224-2-264353446-56-543Example 8当前最好的行动行动方案46-5-56-564IF B走当前方案双方再博弈4步后的格局.将惶傻瓢脱鸣茄枉您斋驹刊析格栋铆队强肌详哉吓京金锌癌晰逢彤替般柏45极小极大分析法45极小极大分析法22 0S01345211 21 11 211当前格局S0格局S1S5是A方5种选择B分别应对格局S1S5S4 倒推值最大A方最佳方案S4Example 9甭夕掌茄栋胳牺线悄憋杜看倦潜互铣糯劲己云滔载团板茎盾时凛种汰腥弓45极小极大分析法45极小极大分析法
