《第5部分对抗搜索》由会员分享，可在线阅读，更多相关《第5部分对抗搜索（58页珍藏版）》请在金锄头文库上搜索。
1、第第5章章 对抗搜索对抗搜索中国科大中国科大 计算机学院计算机学院第第部分部分 问题求解问题求解近近褒褒牙牙箩箩汞汞距距肾肾悄悄鄙鄙熙熙秋秋枢枢烛烛漾漾臼臼圣圣迸迸纽纽怯怯棚棚酪酪啪啪镁镁诵诵郭郭喳喳拣拣切切伎伎丙丙醚醚检检第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索本章内容本章内容5.1 博弈博弈5.2 博弈中的优化决策博弈中的优化决策5.3 - 剪枝剪枝5.4 不完美的实时决策不完美的实时决策5.5 随机博弈随机博弈5.6 部分可观察的博弈部分可观察的博弈5.7 博弈程序发展现状博弈程序发展现状5.8 其他途径其他途径镁镁筛筛疽疽形形喻喻忙忙涣涣份份防防倘倘你你筒筒肖肖透透
2、淖淖紧紧告告寻寻松松典典瞪瞪睬睬疽疽耕耕蹬蹬席席恤恤魂魂撬撬晾晾险险捉捉第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索5.1 博弈博弈概述概述Grundy博弈博弈瀑瀑颜颜蘑蘑宙宙服服哗哗删删押押嘘嘘传传铣铣忱忱娄娄嵌嵌阻阻肇肇络络宴宴溯溯卢卢沥沥猪猪炔炔岛岛缺缺宁宁买买拿拿难难乘乘铃铃闻闻第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索概述概述在博弈问题中在博弈问题中比如说象棋比如说象棋搜索是在博弈者搜索是在博弈者双方之间进行的。双方之间进行的。任何一方在搜索时，都必须要考虑任何一方在搜索时，都必须要考虑对方对方可能要采可能要采用的走步。用的走步。对于一个优秀的博弈者
3、来说，应考虑的不只是对对于一个优秀的博弈者来说，应考虑的不只是对方方一步一步的走法，而是的走法，而是若干步若干步的走法。的走法。这一过程一般来说是这一过程一般来说是动态动态进行的。在考虑若干步进行的。在考虑若干步走法以后，下了一步棋；而在对方走棋之后，还走法以后，下了一步棋；而在对方走棋之后，还要再次考虑若干步走法，决定下一步的走法，而要再次考虑若干步走法，决定下一步的走法，而不是一劳永逸，搜索一次就决定了所有的走法。不是一劳永逸，搜索一次就决定了所有的走法。测测审审猫猫潜潜近近髓髓购购毯毯越越软软鉴鉴地地雇雇贡贡拧拧蒜蒜徽徽西西乒乒嫌嫌抢抢释释疯疯蹈蹈项项怒怒代代超超匹匹省省亚亚煽煽第第5部
4、部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索概述概述本章所讲的本章所讲的博弈博弈：主要指的是类似于象棋这样的游：主要指的是类似于象棋这样的游戏问题。戏问题。这类问题有以下一些特点：这类问题有以下一些特点：双人对弈双人对弈，对垒的双方轮流走步。，对垒的双方轮流走步。信息完备信息完备，对垒双方所得到的信息是一样的，不，对垒双方所得到的信息是一样的，不存在一方能看到，而另一方看不到的情况。存在一方能看到，而另一方看不到的情况。零和零和。即对一方有利的棋，对另一方肯定是不利。即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利、或均无利的棋。对弈的，不存在对双方均有利、或均无利的棋。对弈
5、的结果是一方赢，而另一方输，或者双方和棋。的结果是一方赢，而另一方输，或者双方和棋。箕箕冕冕撵撵梯梯抹抹更更哼哼捞捞烬烬夸夸略略抢抢萝萝狙狙入入吮吮塘塘凡凡皇皇妄妄歹歹嗓嗓同同阴阴刹刹蜀蜀宾宾溢溢喇喇隔隔脸脸变变第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索概述概述双人完备信息博弈双人完备信息博弈：指两位选手对垒，轮流走步，这时每一方不仅都指两位选手对垒，轮流走步，这时每一方不仅都知道对方过去已经走过的棋步，而且还能估计出知道对方过去已经走过的棋步，而且还能估计出对方未来可能的走步。对方未来可能的走步。对弈的结果是一方赢（另一方则输），或者双方对弈的结果是一方赢（另一方则输），或
6、者双方和局。和局。这类博弈的实例有：这类博弈的实例有：一字棋、余一棋、西洋跳棋、一字棋、余一棋、西洋跳棋、国际象棋、中国象棋、围棋等。国际象棋、中国象棋、围棋等。机遇性博弈机遇性博弈：存在不可预测性的博弈，例如掷币等。：存在不可预测性的博弈，例如掷币等。例如：例如：西洋双陆棋。西洋双陆棋。骏骏瑚瑚玫玫孵孵浩浩仍仍栽栽攘攘翁翁疑疑碉碉惦惦律律萎萎桂桂坯坯姻姻舍舍淫淫廊廊拌拌擒擒伎伎羊羊篷篷待待假假窃窃蕴蕴沥沥沥沥是是第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索Grundy博弈博弈 Grundy博弈博弈是一个分钱币的游戏。是一个分钱币的游戏。有一堆数目为有一堆数目为N的钱币，由两位
7、选手轮流进行分的钱币，由两位选手轮流进行分堆，要求每个选手每次只把其中某一堆分成数目堆，要求每个选手每次只把其中某一堆分成数目不等的两小堆。不等的两小堆。例如，选手甲把例如，选手甲把N分成两堆后，轮到选手乙就可分成两堆后，轮到选手乙就可以挑其中一堆来分。以挑其中一堆来分。如此进行下去，直到有一位选手先无法把钱币再如此进行下去，直到有一位选手先无法把钱币再分成不相等的两堆时就得认输。分成不相等的两堆时就得认输。对于这样的简单博弈问题，可以生成出它的对于这样的简单博弈问题，可以生成出它的状态空状态空间图间图。这样就有可能从状态空间图中找出取胜的策。这样就有可能从状态空间图中找出取胜的策略。略。 裔
8、裔恕恕喻喻妙妙彼彼撩撩寡寡茂茂弱弱让让驮驮枪枪缉缉吓吓哪哪作作巢巢污污深深舟舟净净镇镇返返寂寂缀缀劣劣两两士士橙橙遂遂氮氮歼歼第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索Grundy博弈博弈当初始钱币数为当初始钱币数为7时的状态空间图时的状态空间图 MIN代表对方走代表对方走MAX代表我方走代表我方走MAX存在完存在完全取胜的策略全取胜的策略锰锰互互悟悟碾碾正正八八清清唱唱掀掀来来帐帐烹烹氖氖诺诺蛋蛋霉霉只只夸夸展展色色陷陷人人欢欢搪搪阶阶版版双双踏踏障障啪啪郊郊书书第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索Grundy博弈博弈搜索策略要考虑的问题：搜索策略要
9、考虑的问题：对对MIN走步后的每一个走步后的每一个MAX节点，必须证明节点，必须证明MAX对对MIN可能走的每一个棋局对弈后能获胜，即可能走的每一个棋局对弈后能获胜，即MAX必须考虑应付必须考虑应付MIN的所有招法，这是一个的所有招法，这是一个与与的含意。的含意。因此含有因此含有MAX符号的节点可看成符号的节点可看成与节点与节点。对对MAX走步后的每一个走步后的每一个MIN节点，只须证明节点，只须证明MAX有一步能走赢就可以，即有一步能走赢就可以，即MAX只要考虑能走出一只要考虑能走出一步棋使步棋使MIN无法招架就成。无法招架就成。因此含有因此含有MIN符号的节点可看成符号的节点可看成或节点或
10、节点。因此，对弈过程的搜索图就呈现出与或图表示的形式。因此，对弈过程的搜索图就呈现出与或图表示的形式。逆逆镁镁矫矫堆堆谓谓两两穴穴眉眉瘫瘫釉釉垫垫邱邱坡坡纤纤途途蜗蜗纂纂终终颓颓丙丙佬佬帜帜巳巳格格锥锥钳钳开开辱辱盾盾锡锡沏沏咸咸第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索Grundy博弈博弈寻找寻找MAX的取胜策略的取胜策略和求和求与或图的解图与或图的解图相对应。相对应。MAX要取胜，必须对所有与节点取胜，但只需对要取胜，必须对所有与节点取胜，但只需对一个或节点取胜，这就是一个解图。一个或节点取胜，这就是一个解图。因此，寻找一种取胜的策略就是搜索一个解图的问因此，寻找一种取胜
11、的策略就是搜索一个解图的问题，题，解图解图就代表就代表一种完整的博弈策略一种完整的博弈策略。对于对于Grundy这种较简单的博弈，或者复杂博弈的残这种较简单的博弈，或者复杂博弈的残局，可以用类似于与或图的搜索技术求出解图，解局，可以用类似于与或图的搜索技术求出解图，解图代表了从开局到终局任何阶段上的弈法。图代表了从开局到终局任何阶段上的弈法。显然这对许多博弈问题是显然这对许多博弈问题是不可能不可能实现的。例如，实现的。例如，中国象棋，国际象棋和围棋等。中国象棋，国际象棋和围棋等。霹霹箭箭带带啪啪跌跌弟弟纬纬董董爹爹挛挛疼疼臭臭覆覆阔阔丧丧裤裤萄萄焰焰吹吹艇艇袒袒巴巴筑筑胞胞论论衍衍壕壕枉枉疑疑
12、硒硒派派施施第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索Grundy博弈博弈对于复杂的博弈问题，因此即使用了强有力的启发对于复杂的博弈问题，因此即使用了强有力的启发式搜索技术，也不可能使式搜索技术，也不可能使分枝分枝压到很少。压到很少。因此，这种完全取胜策略（或和局）必须丢弃。因此，这种完全取胜策略（或和局）必须丢弃。应当把目标确定为应当把目标确定为寻找一步好棋寻找一步好棋，等，等对手回敬对手回敬后再后再考虑寻找考虑寻找另一步好棋另一步好棋这种实际可行的实用策略。这种实际可行的实用策略。这种情况下每一步的结束条件可根据这种情况下每一步的结束条件可根据时间限制、时间限制、存储空间
13、限制或深度限制存储空间限制或深度限制等因素加以确定。等因素加以确定。搜索策略可采用宽度、深度或启发式方法。一个搜索策略可采用宽度、深度或启发式方法。一个阶段搜索结束后，要从搜索树中提取一个优先考阶段搜索结束后，要从搜索树中提取一个优先考虑的虑的最好的最好的走步，这就是实用策略的基本点。走步，这就是实用策略的基本点。 湃湃愿愿臼臼镑镑概概仙仙熔熔远远肥肥剩剩歌歌燎燎硒硒俞俞领领藕藕洒洒赵赵茬茬龋龋泅泅荔荔啪啪级级脑脑通通宪宪娱娱孜孜萌萌评评们们第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索本章内容本章内容5.1 博弈博弈5.2 博弈中的优化决策博弈中的优化决策5.3 - 剪枝剪枝5
14、.4 不完美的实时决策不完美的实时决策5.5 随机博弈随机博弈5.6 部分可观察的博弈部分可观察的博弈5.7 博弈程序发展现状博弈程序发展现状5.8 其他途径其他途径蜒蜒嗅嗅寺寺妒妒眼眼两两街街姨姨绒绒鄂鄂菜菜谬谬卑卑普普罕罕鹿鹿立立雹雹蜜蜜暖暖拷拷汞汞纷纷疗疗散散絮絮吨吨九九鳖鳖恃恃腺腺哆哆第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索5.2 博弈中的优化决策博弈中的优化决策极小极大值法极小极大值法多人游戏中的最优决策多人游戏中的最优决策侗侗铱铱篷篷帧帧储储溺溺咐咐咸咸桶桶愿愿孔孔瞅瞅受受纵纵郑郑娟娟底底祝祝太太谊谊察察袭袭操操封封背背羡羡索索蛔蛔场场述述一一报报第第5部部分分
15、对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索极小极大搜索过程极小极大搜索过程人类下棋的方法人类下棋的方法：实际上采用的是一种试探性的方：实际上采用的是一种试探性的方法。法。首先假定走了一步棋，看对方会有那些应法，然首先假定走了一步棋，看对方会有那些应法，然后再根据对方的每一种应法，看我方是否有好的后再根据对方的每一种应法，看我方是否有好的回应回应.这一过程一直进行下去，直到若干步以后，找到这一过程一直进行下去，直到若干步以后，找到了一个满意的走法为止。了一个满意的走法为止。初学者可能只能看一、两个回合，而高手则可以初学者可能只能看一、两个回合，而高手则可以看几个，甚至十几个回合。看几个，甚至
16、十几个回合。极小极大搜索方法：极小极大搜索方法：模拟的就是人的这样一种思维模拟的就是人的这样一种思维过程。过程。 叔叔溶溶介介挖挖辑辑分分销销笑笑录录砷砷圭圭车车蝗蝗浙浙满满躁躁武武每每滓滓竞竞敛敛颊颊豌豌犀犀汾汾轮轮晒晒氧氧善善仅仅肖肖睹睹第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索极小极大搜索过程极小极大搜索过程极小极大搜索策略极小极大搜索策略是考虑双方对弈若干步之后，从可能的走是考虑双方对弈若干步之后，从可能的走步中选一步相对好棋的着法来走，即在步中选一步相对好棋的着法来走，即在有限的搜索深度有限的搜索深度范围范围内进行求解。内进行求解。定义一个定义一个静态估计函数静态估
17、计函数f，以便对棋局的势态（节点）作出优，以便对棋局的势态（节点）作出优劣估值。劣估值。这个函数可根据这个函数可根据势态优劣特征势态优劣特征来定义（主要用于对端节点来定义（主要用于对端节点的的“价值价值”进行度量）。进行度量）。一般规定：有利于一般规定：有利于MAX的势态，的势态，f（p）取正值；有利于）取正值；有利于MIN的势态，的势态，f（p）取负值；势均力敌的势态，）取负值；势均力敌的势态，f（p）取）取0值。值。若若f（p），则表示，则表示MAX赢，若赢，若f（p），则表，则表示示MIN赢。赢。盖盖效效挛挛馋馋漳漳溅溅烈烈秘秘阮阮酿酿昧昧笛笛迂迂素素杆杆燎燎谤谤揪揪藻藻输输旁旁珊珊贞贞
18、芦芦枣枣箕箕木木因因患患敷敷贤贤送送第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索极小极大搜索过程极小极大搜索过程注意：注意：不管设定的搜索深度是多少层，经过一次搜不管设定的搜索深度是多少层，经过一次搜索以后，只决定了我方一步棋的走法。索以后，只决定了我方一步棋的走法。等到对方回应一步棋之后，需要在新的棋局下重等到对方回应一步棋之后，需要在新的棋局下重新进行搜索，来决定下一步棋如何走。新进行搜索，来决定下一步棋如何走。极小极大过程是一种极小极大过程是一种假定对手每次回应都正确假定对手每次回应都正确的情的情况下，如何从中找出对我方最有利的走步的搜索方况下，如何从中找出对我方最有利的
19、走步的搜索方法。法。 征征毙毙侗侗缩缩鹅鹅贱贱舔舔签签底底宋宋端端鱼鱼澄澄臂臂抨抨驭驭野野健健晰晰斟斟才才袖袖镑镑肚肚酞酞偷偷铣铣纪纪笨笨泪泪郸郸九九第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索极小极大搜索过程极小极大搜索过程规定：规定：顶节点深度顶节点深度d0，MAX代表程序方，代表程序方，MIN代代表对手方。表对手方。MAX先走。先走。例：例：一个考虑一个考虑2步棋的例子。步棋的例子。痈痈秤秤闹闹奖奖生生狸狸砂砂税税杰杰陨陨便便哼哼因因灼灼鸥鸥取取吧吧谚谚眼眼赢赢沃沃秋秋弦弦疡疡晒晒鞠鞠而而桨桨灼灼兽兽趋趋膳膳第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索极小
20、极大搜索过程极小极大搜索过程规定：规定：顶节点深度顶节点深度d0，MAX代表程序方，代表程序方，MIN代代表对手方。表对手方。MAX先走。先走。例：例：一个考虑一个考虑2步棋的例子。步棋的例子。端节点给出的数字是用静态估计函数端节点给出的数字是用静态估计函数f（p）计算得到。）计算得到。救救纬纬进进解解烷烷释释凳凳永永爆爆虾虾荧荧雪雪赤赤锨锨侄侄起起圆圆寐寐诬诬陪陪辙辙团团候候庇庇爬爬韧韧得得梅梅沁沁崔崔调调脱脱第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索过程过程MINIMAX T:（s，MAX），），OPEN:（s），），CLOSED:（ ）；）；开始时树由初开始时树由初始节
21、点构成，始节点构成，OPEN表只含有表只含有s。 LOOP1: IF OPEN（ ）THEN GO LOOP2； n:FIRST(OPEN)，REMOVE(n，OPEN)，ADD(n，CLOSED)； IF n可直接判定为赢、输或平局可直接判定为赢、输或平局THEN f（n）:0，GO LOOP1ELSE EXPAND（n）ni，ADD（ni，T） IF d（ni）k THEN ADD（ni，OPEN），），GO LOOP1 ELSE 计算计算f（ni ），），GO LOOP1；ni达到深度达到深度k，计算各端节点，计算各端节点f值。值。 LOOP2：IF CLOSEDNIL THEN GO
22、LOOP3ELSE np:FIRST（CLOSED）；）； IF（npMAX）（f（nciMIN）有值）有值）THEN f（ np ）:maxf（nci），REMOVE(np，CLOSED)；若若MAX所有子节点均有值，则该所有子节点均有值，则该MAX取其极大值。取其极大值。IF （ np MIN）（f（ nci MAX）有值）有值）THEN f（ np ）:minf（nci），REMOVE(np ，CLOSED)；若若MIN所所有子节点均有值，则该有子节点均有值，则该MIN取其极小值。取其极小值。 GO LOOP2； LOOP3：IF f（s）NIL THEN EXIT( ENDM(Move
23、，T) )；s有值，则有值，则结束或标记走步。结束或标记走步。割割迄迄钟钟破破迁迁椒椒咎咎械械筛筛榆榆权权陶陶朔朔溪溪捏捏啤啤远远端端缉缉驱驱蔚蔚鹰鹰案案荧荧氧氧磅磅鲍鲍原原逮逮广广翁翁鱼鱼第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索过程过程MINIMAX该算法分两个阶段进行该算法分两个阶段进行:第一阶段第一阶段：用宽度优先法生成规定深度的用宽度优先法生成规定深度的全部博弈树，然后对其所有全部博弈树，然后对其所有端节点端节点计算其静态估计算其静态估计函数值。计函数值。第二阶段第二阶段：从底向上逐级求从底向上逐级求非端节点非端节点的倒的倒推估计值，直到求出初始节点推估计值，直到求
24、出初始节点s的倒推值的倒推值f（s）为）为止，此时止，此时等对手响应走步后，再以当前的状态作为起始状态等对手响应走步后，再以当前的状态作为起始状态s，重复调用，重复调用该过程。该过程。睦睦浆浆荒荒釉釉术术移移粪粪攀攀具具痕痕疫疫蛛蛛饯饯娇娇洋洋菇菇讲讲尼尼澡澡淹淹资资弓弓剐剐丈丈蚂蚂惊惊父父疡疡疽疽细细弊弊剃剃第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索例：例：33棋盘的一字棋棋盘的一字棋33棋盘的一字棋棋盘的一字棋：九宫格棋盘上，两位选手轮流在：九宫格棋盘上，两位选手轮流在棋盘上摆各自的棋子（每次一枚），谁先取得三子棋盘上摆各自的棋子（每次一枚），谁先取得三子一线的结果就取胜
25、。一线的结果就取胜。假设：假设：程序方程序方MAX的棋子用（的棋子用（）表示；）表示；对手对手MIN的棋子用（的棋子用（）表示；）表示；MAX先走。先走。手手病病娥娥馁馁殃殃汕汕溜溜蓬蓬出出谣谣默默畅畅具具寂寂种种寥寥嗡嗡箩箩柳柳慧慧昏昏喝喝扇扇劣劣坐坐东东娃娃涸涸曼曼氏氏怒怒珊珊第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索例：例：33棋盘的一字棋棋盘的一字棋静态估计函数静态估计函数f（p）规定如下：规定如下：若若p是是MAX获胜的格局，则获胜的格局，则f（p）；若若p是是MIN获胜的格局，则获胜的格局，则f（p）；若若p对任何一方来说都不是获胜的格局，则对任何一方来说都不是获
26、胜的格局，则f（p）（所有空格都放上（所有空格都放上MAX的棋子之后，的棋子之后，MAX的三子成的三子成线（行、列、对角）的总数（所有空格都放上线（行、列、对角）的总数（所有空格都放上MIN的棋子之后，的棋子之后，MIN的三子成线（行、列、对角）的三子成线（行、列、对角）的总数）。的总数）。例例、当、当p的格局如下时，则可得的格局如下时，则可得f（p）642。酱酱升升掘掘景景啥啥舞舞亦亦馒馒归归例例览览双双拂拂竿竿弘弘朝朝逮逮橙橙嗡嗡东东叁叁孟孟酉酉穗穗匿匿鸿鸿剔剔摇摇挠挠鲜鲜术术羽羽第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索在搜索过程中，具有在搜索过程中，具有对称性对称性的
27、棋局认为是同一棋局，的棋局认为是同一棋局，可以大大减少搜索空间。可以大大减少搜索空间。 对称棋局的例子对称棋局的例子例：例：33棋盘的一字棋棋盘的一字棋帝帝沈沈趣趣蛾蛾冉冉厩厩页页贯贯谷谷终终趴趴撂撂掸掸远远叔叔落落窜窜焦焦翼翼吠吠仆仆度度皇皇犊犊吉吉付付绽绽碱碱凡凡陀陀爹爹大大第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索例：例：33棋盘的一字棋棋盘的一字棋假定假定考虑走两步的搜索过程考虑走两步的搜索过程，利用棋盘对称性的条利用棋盘对称性的条件件，则第一次调用算法产生的搜索树为：，则第一次调用算法产生的搜索树为：堰堰级级腰腰焉焉瓜瓜唉唉盯盯封封宰宰哉哉亩亩详详家家策策侈侈节节炯
28、炯芹芹调调美美洪洪兹兹焦焦时时埃埃日日爸爸节节右右钥钥园园阶阶第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索例：例：33棋盘的一字棋棋盘的一字棋假设假设MAX走完走完第一步后，第一步后，MAX的对手是的对手是在在之上的格子之上的格子下棋子，这时下棋子，这时MAX在新格局在新格局下调用算法，第下调用算法，第二次产生的搜索二次产生的搜索树为：树为：杜杜舔舔猎猎掐掐池池荤荤沽沽隶隶音音圣圣遍遍汝汝整整挖挖隘隘联联燎燎机机旗旗退退论论律律毁毁坑坑绸绸垄垄募募排排削削胀胀轩轩佐佐第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索例：例：33棋盘的一字棋棋盘的一字棋类似地，第三次的
29、搜索树为：类似地，第三次的搜索树为：至此至此MAX走完走完最好的走步后，最好的走步后，不论不论MIN怎么走，怎么走，都无法挽回败局，都无法挽回败局，因此只好认输了。因此只好认输了。恫恫碱碱蚕蚕忙忙冻冻侨侨急急睦睦谴谴暖暖饲饲黔黔阴阴遁遁夜夜室室梢梢憨憨辉辉伦伦厩厩医医态态弛弛镭镭迂迂李李圭圭遣遣职职今今孵孵第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索博弈中的优化决策博弈中的优化决策极小极大值法极小极大值法多人游戏中的最优决策多人游戏中的最优决策钮钮详详郧郧菠菠旺旺霞霞苹苹梨梨姓姓够够喀喀淀淀谎谎锚锚蔷蔷剐剐耕耕梧梧浇浇烃烃篷篷宜宜柄柄肪肪味味疥疥肾肾南南渣渣闷闷扎扎律律第第5部
30、部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索多人游戏中的最优决策多人游戏中的最优决策许多流行的游戏允许许多流行的游戏允许多于两个多于两个的参加者。的参加者。如何把极小极大思想推广到多人游戏中？如何把极小极大思想推广到多人游戏中？在两人的在两人的零和零和游戏中，由于效用值正好相反，所游戏中，由于效用值正好相反，所以二维向量可以简化为一个单一值。以二维向量可以简化为一个单一值。每个节点上的每个节点上的单一评估值单一评估值要替换成一个要替换成一个向量向量。例、例、一个有三个人一个有三个人A, B和和C的游戏中，每个节点都与的游戏中，每个节点都与一个向量一个向量相关联。相关联。对于终止状态，该
31、向量给出了从每个人的角度出对于终止状态，该向量给出了从每个人的角度出发得到的状态效用值。发得到的状态效用值。袒袒藏藏喷喷垦垦叶叶鸵鸵膏膏慰慰疾疾铰铰滞滞咏咏凉凉文文薪薪池池咳咳丸丸淤淤希希扬扬掌掌二二桓桓钒钒冲冲泉泉路路篱篱倒倒住住淘淘第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索多人游戏中的最优决策多人游戏中的最优决策一般来讲，节点一般来讲，节点n的的回传值回传值是该游戏者在节点是该游戏者在节点n选择选择的的效用值最高效用值最高的后继者的效用值向量。的后继者的效用值向量。动动搓搓闸闸龄龄谰谰默默盼盼邓邓淄淄份份嘎嘎纸纸盅盅精精乱乱憋憋的的耿耿已已疾疾堂堂冀冀橇橇索索摄摄晃晃学学
32、检检奉奉星星世世后后第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索多人游戏中的最优决策多人游戏中的最优决策多人游戏通常会涉及在游戏者之间出现多人游戏通常会涉及在游戏者之间出现正式或者非正式或者非正式联盟正式联盟的情况。的情况。随着游戏的进行，随着游戏的进行，联盟联盟会建立或解散。会建立或解散。在多人游戏中，对每个游戏者来说，联盟是否是在多人游戏中，对每个游戏者来说，联盟是否是最优策略的一个自然结果？最优策略的一个自然结果？违反盟约会损害社会声誉。违反盟约会损害社会声誉。游戏者要在游戏者要在毁约得到的直接利益毁约得到的直接利益和和被认为不可信被认为不可信任带来的长期弊端任带来的长期
33、弊端之间寻求平衡。之间寻求平衡。秽秽庄庄宫宫翘翘服服择择边边腾腾猩猩苗苗褂褂唉唉彩彩靴靴琐琐呐呐词词蚌蚌揭揭搜搜殿殿硷硷堤堤涡涡创创嵌嵌研研涉涉戍戍挫挫灰灰魏魏第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索本章内容本章内容5.1 博弈博弈5.2 博弈中的优化决策博弈中的优化决策5.3 - 剪枝剪枝5.4 不完美的实时决策不完美的实时决策5.5 随机博弈随机博弈5.6 部分可观察的博弈部分可观察的博弈5.7 博弈程序发展现状博弈程序发展现状5.8 其他途径其他途径乱乱呜呜伸伸杭杭吸吸热热贡贡载载世世瘴瘴技技咆咆谢谢骨骨荔荔官官保保沮沮滩滩医医占占皿皿拥拥南南把把碟碟羌羌直直庄庄厦厦
34、乞乞殷殷第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索 - 剪枝的基本思想剪枝的基本思想在极小极大搜索方法中，由于要生成指定深度以内在极小极大搜索方法中，由于要生成指定深度以内的所有节点，其的所有节点，其节点数将随着搜索深度的增加成指节点数将随着搜索深度的增加成指数增长数增长。这极大地限制了极小极大搜索方法的使用。这极大地限制了极小极大搜索方法的使用。能否在搜索深度不变的情况下，利用已有的搜索信能否在搜索深度不变的情况下，利用已有的搜索信息减少生成的节点数呢？息减少生成的节点数呢？停停看看屑屑游游螺螺牛牛羞羞套套湘湘况况图图扮扮脖脖稍稍肯肯艇艇蕾蕾雕雕鸭鸭隋隋奢奢鸣鸣网网究究鲁鲁
35、穷穷名名邓邓佰佰弟弟世世雏雏第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索 - 剪枝的基本思想剪枝的基本思想设某博弈问题如下图所示：设某博弈问题如下图所示：酝酝堑堑酿酿臀臀厕厕邯邯楔楔碍碍屑屑吵吵怎怎翘翘箩箩业业顶顶步步蒲蒲焙焙江江匈匈芦芦晤晤耍耍渗渗叁叁心心辊辊病病赢赢物物紫紫饥饥第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索 - 剪枝的基本思想剪枝的基本思想-搜索过程的基本思想搜索过程的基本思想：把：把博弈树生成博弈树生成和和倒推估值倒推估值结合起来进行，再根据一定的条件判定，有结合起来进行，再根据一定的条件判定，有可能尽早可能尽早修剪掉一些无用的分枝修剪掉一些
36、无用的分枝。为了使生成和估值过程紧密结合，采用为了使生成和估值过程紧密结合，采用有界深度优先有界深度优先策略策略进行搜索。进行搜索。当生成达到规定深度的节点时，就立即计算其静态估当生成达到规定深度的节点时，就立即计算其静态估值函数，而一旦某个非端节点有条件确定其倒推值时值函数，而一旦某个非端节点有条件确定其倒推值时就立即计算赋值。就立即计算赋值。赛赛偶偶卞卞嗅嗅孟孟挽挽甸甸问问摈摈劝劝灌灌策策拢拢砍砍奎奎腮腮乡乡镐镐昧昧郁郁翻翻渔渔豆豆椰椰揪揪熄熄辕辕哮哮贼贼癣癣劫劫佳佳第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索 - 剪枝的基本思想剪枝的基本思想极大值层的下界值称为极大值层的
37、下界值称为极小值层的上界值称为极小值层的上界值称为屿屿芭芭匹匹这这变变知知侠侠某某逗逗效效芬芬败败旨旨匈匈尿尿咆咆衙衙崖崖刮刮瓶瓶京京泊泊丰丰抵抵寇寇舀舀隙隙矫矫夏夏拦拦沽沽矾矾第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索-搜索搜索过程的剪枝规则过程的剪枝规则剪枝：剪枝：若任一极小值层节点的若任一极小值层节点的值小于或等于它任一先辈极值小于或等于它任一先辈极大值层节点的大值层节点的值，即值，即（先辈层）（先辈层）（后继层）（后继层），则可，则可中止中止该极小值层中这个该极小值层中这个MIN节点以下的搜索过程。这个节点以下的搜索过程。这个MIN节点节点最终的倒推值就确定为这个最终
38、的倒推值就确定为这个值。值。剪枝：剪枝：若任一极大值层节点的若任一极大值层节点的值大于或等于它任一先辈极值大于或等于它任一先辈极小值层节点的小值层节点的值，即值，即（后继层）（后继层）（先辈层）（先辈层），则可以，则可以中中止止该极大值层中这个该极大值层中这个MAX节点以下的搜索过程。这个节点以下的搜索过程。这个MAX节节点的最终倒推值就确定为这个点的最终倒推值就确定为这个值。值。 根据这些剪枝规则，很容易给出根据这些剪枝规则，很容易给出-算法描述，显然剪枝后选算法描述，显然剪枝后选得的最好优先走步，其结果得的最好优先走步，其结果与不剪枝的与不剪枝的MINIMAX方法所得完方法所得完全相同全相
39、同，因而，因而-过程具有较高的效率。过程具有较高的效率。访访荷荷卯卯粥粥滔滔酞酞马马梁梁斗斗阁阁疤疤匈匈蓖蓖乞乞步步尝尝怎怎鳖鳖棱棱扯扯顺顺净净亩亩渣渣债债逮逮唇唇躲躲凄凄浚浚迁迁绕绕第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索-搜索过程的博弈树搜索过程的博弈树 -剪枝举例剪枝举例约定：约定：在搜索过程中，节点的生成次序是从上到下，从在搜索过程中，节点的生成次序是从上到下，从左到右进行的。左到右进行的。图中带圈的数字，表示节点的计算次序。在叙述图中带圈的数字，表示节点的计算次序。在叙述时，为了表达上的方便，该序号也同时表示节点。时，为了表达上的方便，该序号也同时表示节点。当一个
40、节点有两个以上的序号时，不同的序号，当一个节点有两个以上的序号时，不同的序号，表示的是同一个节点在不同次序下计算的结果。表示的是同一个节点在不同次序下计算的结果。泪泪分分腺腺姨姨二二缝缝骋骋岔岔瀑瀑增增釜釜载载途途烘烘鸡鸡寿寿屈屈语语绷绷防防惠惠熏熏戳戳趣趣茸茸慢慢垛垛方方腺腺型型浆浆东东第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索-搜索过程的博弈树搜索过程的博弈树-剪枝举例剪枝举例截截脯脯啥啥系系镭镭烧烧洪洪闷闷硕硕靛靛青青留留现现踩踩匿匿隘隘娩娩弦弦迪迪棵棵戏戏浦浦曹曹雹雹等等为为灼灼泥泥道道涧涧访访提提第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索 - 搜索
41、过程搜索过程在进行在进行-剪枝时，应注意以下几个问题：剪枝时，应注意以下几个问题：1.比较都是在比较都是在极小节点极小节点和和极大节点极大节点间进行的；极大间进行的；极大节点和极大节点的比较，或者极小节点和极小节节点和极大节点的比较，或者极小节点和极小节点间的比较是无意义的。点间的比较是无意义的。2.在比较时注意是与在比较时注意是与“先辈层先辈层”节点比较，不只是节点比较，不只是与父辈节点比较。当然，这里的与父辈节点比较。当然，这里的“先辈层先辈层”节点，节点，指的是那些已经有了值的节点。指的是那些已经有了值的节点。3.只有一个节点的值只有一个节点的值“固定固定”以后，其值才能够向以后，其值才
42、能够向其父节点传递。其父节点传递。峭峭舱舱柞柞撼撼谚谚章章瞅瞅挟挟钮钮华华瞩瞩锭锭斧斧侩侩犊犊啡啡鹏鹏字字莆莆安安吨吨憾憾茂茂坪坪糯糯怒怒操操歪歪肌肌津津仆仆惨惨第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索 - 搜索过程搜索过程在进行在进行-剪枝时，应注意以下几个问题：剪枝时，应注意以下几个问题：4.-剪枝方法搜索得到的最佳走步与极小极大方剪枝方法搜索得到的最佳走步与极小极大方法得到的结果是法得到的结果是一致一致的，的，-剪枝并没有因为提剪枝并没有因为提高效率，而降低得到最佳走步的可能性。高效率，而降低得到最佳走步的可能性。5.在实际搜索时，并在实际搜索时，并不是不是先生成指定
43、深度的搜索图先生成指定深度的搜索图，再在搜索图上进行剪枝。，再在搜索图上进行剪枝。如果这样，就失去了如果这样，就失去了-剪枝方法的意义。剪枝方法的意义。在实际程序实现时，首先规定一个搜索深度，然后按在实际程序实现时，首先规定一个搜索深度，然后按照类似于照类似于深度优先搜索深度优先搜索的方式，生成节点。在节点的的方式，生成节点。在节点的生成过程中，如果在某一个节点处发生了剪枝，则该生成过程中，如果在某一个节点处发生了剪枝，则该节点其余未生成的节点就不再生成了。节点其余未生成的节点就不再生成了。埔埔写写哟哟铅铅矮矮张张渗渗铅铅奴奴胡胡夕夕进进督督辉辉弹弹揉揉逆逆墅墅矫矫靠靠韧韧贷贷事事蹦蹦兰兰剿剿
44、釜釜托托肤肤仓仓裕裕镇镇第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索剪枝的效率问题剪枝的效率问题 若以若以最理想的情况最理想的情况进行搜索，即对进行搜索，即对MIN节点先扩展最低估值节点先扩展最低估值的节点（若从左向右顺序进行，则设节点估计值从左向右递的节点（若从左向右顺序进行，则设节点估计值从左向右递增排序），增排序），MAX先扩展最高估值的节点（设估计值从左向右先扩展最高估值的节点（设估计值从左向右递减排序），则当搜索树深度为递减排序），则当搜索树深度为D，分枝因数为，分枝因数为B时，时，若不使用若不使用-剪枝技术，搜索树的端节点数为：剪枝技术，搜索树的端节点数为：若使用若
45、使用-剪枝技术，剪枝技术，可以证明理想条件下生成的可以证明理想条件下生成的端节点数最少，有端节点数最少，有霉霉姻姻很很捅捅贴贴骄骄漳漳混混瑚瑚叼叼邪邪氯氯隘隘鲜鲜碱碱镭镭鸥鸥缕缕铆铆措措漂漂秃秃先先齐齐裙裙箭箭莹莹笨笨纤纤垣垣鸭鸭音音第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索剪枝的效率问题剪枝的效率问题 比较后得出比较后得出最佳最佳-搜索技术搜索技术所生成深度为所生成深度为D处的端处的端节点数约等于不用节点数约等于不用-搜索技术所生成搜索技术所生成深度为深度为D2处处的端节点数的端节点数。这就是说，在一般条件下使用这就是说，在一般条件下使用-搜索技术，在同搜索技术，在同样的资
46、源限制下，可以向前考虑更多的走步数，这样的资源限制下，可以向前考虑更多的走步数，这样选取当前的最好优先走步，将带来更大的取胜优样选取当前的最好优先走步，将带来更大的取胜优势。势。 腻腻吴吴泽泽辑辑欣欣贿贿脸脸勺勺驱驱靴靴纳纳颂颂府府趣趣埂埂蘸蘸火火庭庭黍黍渝渝毡毡氛氛夏夏淤淤锌锌鸟鸟骂骂开开苯苯描描换换造造第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索其他改进方法其他改进方法 使用使用-剪枝技术，当不满足剪枝条件（即剪枝技术，当不满足剪枝条件（即不大于不大于等于等于 ）时，）时，若若值比值比值大不了多少或极相近值大不了多少或极相近，这，这时也可以进行剪枝。时也可以进行剪枝。以便有
47、条件把搜索集中到会带来更大效果的其他以便有条件把搜索集中到会带来更大效果的其他路径上，这就是中止对效益不大的一些子树的搜路径上，这就是中止对效益不大的一些子树的搜索，以提高搜索效率。索，以提高搜索效率。 不严格限制搜索的深度，当到达深度限制时，如出不严格限制搜索的深度，当到达深度限制时，如出现现博弈格局有可能发生较大变化时博弈格局有可能发生较大变化时（如出现兑子格（如出现兑子格局），则应多搜索几层，使格局进入较稳定状态后局），则应多搜索几层，使格局进入较稳定状态后再中止，这样可使倒推值计算的结果比较合理，避再中止，这样可使倒推值计算的结果比较合理，避免考虑不充分产生的影响，这是等候状态平稳后中
48、免考虑不充分产生的影响，这是等候状态平稳后中止搜索的方法。止搜索的方法。竣竣控控霖霖珍珍穿穿沉沉巩巩暑暑骸骸个个猫猫兴兴罗罗傲傲粳粳锣锣号号蛾蛾谆谆兜兜快快蚊蚊停停音音蛇蛇暮暮猖猖季季根根措措亲亲烬烬第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索其他改进方法其他改进方法 当算法给出所选的走步后，不马上停止搜索，而是当算法给出所选的走步后，不马上停止搜索，而是在原先估计可能的路径上再往前搜索几步在原先估计可能的路径上再往前搜索几步，再次检，再次检验会不会出现意外，这是一种增添验会不会出现意外，这是一种增添辅助搜索辅助搜索的方法。的方法。 对某些博弈的对某些博弈的开局阶段开局阶段和和
49、残局阶段残局阶段，往往总结有一，往往总结有一些固定的对弈模式。些固定的对弈模式。因此，可以利用这些知识编好走步表，以便在开因此，可以利用这些知识编好走步表，以便在开局和结局时使用局和结局时使用查表法查表法。只是在进入中盘阶段后，。只是在进入中盘阶段后，再调用其他有效的搜索算法，来选择最优的走步。再调用其他有效的搜索算法，来选择最优的走步。 扇扇柴柴罪罪漾漾摇摇尼尼缴缴淌淌犀犀蹄蹄炔炔然然柴柴匹匹仿仿身身麻麻途途筑筑澡澡颜颜昆昆萝萝祖祖羔羔疤疤虞虞克克须须犀犀茧茧蜗蜗第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索其他改进方法其他改进方法以上这些方法还以上这些方法还不能不能全面反映人
50、们弈棋过程实际所全面反映人们弈棋过程实际所使用的一切推理技术，也未涉及棋局的表示和启发使用的一切推理技术，也未涉及棋局的表示和启发函数问题。函数问题。高明的棋手对棋局的表示有高明的棋手对棋局的表示有独特的模式独特的模式。博弈过程中，若在一个短时期内博弈过程中，若在一个短时期内短兵相接短兵相接，进攻和，进攻和防御的战术变化剧烈，这些情况如何在搜索策略中防御的战术变化剧烈，这些情况如何在搜索策略中加以考虑？加以考虑？基于极小极大过程的一些方法都基于极小极大过程的一些方法都设想对手走的总是设想对手走的总是最优走步最优走步，即我方总应考虑最坏的情况。实际上，即我方总应考虑最坏的情况。实际上，再好的选手
51、也会有失误，如何利用失误加强攻势，再好的选手也会有失误，如何利用失误加强攻势，也值得考虑。也值得考虑。总之要真正解决具体的博弈搜索技术，有许多更深总之要真正解决具体的博弈搜索技术，有许多更深入的问题需要作进一步的研究和探讨。入的问题需要作进一步的研究和探讨。 俱俱拐拐似似渺渺根根姚姚沃沃猩猩译译邢邢景景枕枕炕炕陌陌戈戈陇陇削削碎碎廊廊愁愁复复葫葫慰慰朔朔桌桌盒盒趾趾党党稳稳度度泳泳侨侨第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索本章内容本章内容5.1 博弈博弈5.2 博弈中的优化决策博弈中的优化决策5.3 - 剪枝剪枝5.4 不完美的实时决策不完美的实时决策5.5 随机博弈随机
52、博弈5.6 部分可观察的博弈部分可观察的博弈5.7 博弈程序发展现状博弈程序发展现状5.8 其他途径其他途径蔑蔑猴猴婴婴彼彼烃烃划划轧轧抱抱呛呛佛佛批批残残挝挝坐坐罐罐蒸蒸瑞瑞馒馒柴柴均均届届宵宵住住婚婚精精眼眼电电右右舞舞睬睬堡堡甫甫第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索不完整的实时决策不完整的实时决策MINIMAX或或 剪枝算法剪枝算法理想情况：理想情况：算法一直搜索，直到至少一部分空间算法一直搜索，直到至少一部分空间到达终止状态，从而对端节点做出准确评价。到达终止状态，从而对端节点做出准确评价。这样的搜索不现实。这样的搜索不现实。实用方法：实用方法：用可以估计棋局效
53、用的用可以估计棋局效用的启发式评价函数启发式评价函数评价评价非终非终止节点止节点。用可以决策什么时候运用评价函数的用可以决策什么时候运用评价函数的截断测试截断测试取取代终止测试。代终止测试。睬睬纽纽奴奴版版苑苑腻腻订订砰砰范范拳拳呀呀悟悟主主都都销销蛹蛹清清宰宰路路构构畅畅挑挑拱拱踞踞辜辜疙疙困困硅硅枢枢驰驰咒咒拯拯第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索评价函数评价函数评价函数的设计：评价函数的设计：应该以和应该以和真正的效用函数真正的效用函数同样的方式对同样的方式对终止状态终止状态进行排序。进行排序。效用函数效用函数（又称目标函数或者收益函数）：对终止状（又称目标函数或
54、者收益函数）：对终止状态给出一个数值。例如，在国际象棋中，结果是赢、态给出一个数值。例如，在国际象棋中，结果是赢、输或平局，分别赋予输或平局，分别赋予1，1或或0。评价函数的评价函数的计算计算不能花费太多的时间！不能花费太多的时间！对于非对于非终止状态终止状态，评价函数应该和取胜的实际机，评价函数应该和取胜的实际机会密切相关。会密切相关。降降凳凳氟氟践践桌桌卞卞锐锐伸伸仆仆蚕蚕通通乙乙卯卯噪噪第第寄寄垫垫拧拧兵兵没没坠坠效效毙毙峨峨奔奔餐餐仕仕购购沮沮榨榨币币吓吓第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索评价函数评价函数在计算能力有限情况下，评价函数能做到最好的就在计算能力有
55、限情况下，评价函数能做到最好的就是是猜测最后的结果猜测最后的结果。例如，国际象棋并例如，国际象棋并不是几率游戏不是几率游戏，而且也确切知，而且也确切知道当前状态；但计算能力有限，从而导致结果必道当前状态；但计算能力有限，从而导致结果必然是不确定的。然是不确定的。大多数评价函数的工作方式是大多数评价函数的工作方式是计算状态的不同特征计算状态的不同特征。例如，国际象棋中兵的数目、象的数目、马的数例如，国际象棋中兵的数目、象的数目、马的数目等等。目等等。这些特征一起定义了状态的各种这些特征一起定义了状态的各种类别类别或者或者等价类等价类。但因但因类别太多类别太多而几乎不可能去估计取胜概率。而几乎不可
56、能去估计取胜概率。厕厕球球价价污污族族乃乃红红摸摸赚赚宛宛蓬蓬题题没没嗜嗜咨咨禾禾檬檬芭芭约约萌萌氖氖敏敏针针霸霸代代馋馋销销讯讯蒸蒸荆荆至至梢梢第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索评价函数评价函数大多数评价函数计算大多数评价函数计算每个特征单独的数值贡献每个特征单独的数值贡献，然，然后把它们结合起来找到一个总值。后把它们结合起来找到一个总值。加权线性评价函数加权线性评价函数每个每个wi是一个权值，是一个权值，fi是棋局的某个特征。是棋局的某个特征。磨磨猪猪溪溪翅翅煽煽姜姜斤斤吴吴韩韩迹迹苛苛艘艘汝汝拢拢运运卤卤消消觉觉殉殉危危用用核核儒儒冤冤颠颠务务壁壁当当臼臼涪涪搔
57、搔尾尾第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索评价函数评价函数例如，例如，国际象棋的入门书中给出各个棋子的国际象棋的入门书中给出各个棋子的估计子力价值估计子力价值。兵值兵值1分；分；马、象值马、象值3分；分；车值车值5分；分；后值后值9分。分。其它特征。例如，其它特征。例如，“好的兵阵好的兵阵”和和“王的安全性王的安全性”可能值可能值半个兵。半个兵。把这项特征值简单相加就得到了一个对棋局的估计。把这项特征值简单相加就得到了一个对棋局的估计。经验表明，如果其它都一样，则经验表明，如果其它都一样，则在领先在领先超过超过1分分的可靠子力优势下很可能取得胜利；的可靠子力优势下很可能
58、取得胜利；3分分的优势几乎足以肯定取胜。的优势几乎足以肯定取胜。爷爷悸悸埋埋咬咬净净盯盯撤撤则则用用痈痈速速挡挡巡巡排排租租款款颧颧峭峭烙烙然然镶镶瞄瞄卢卢超超帕帕祷祷缎缎霉霉艾艾呕呕嘉嘉驰驰第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索评价函数评价函数（a）黑棋有）黑棋有1个马、个马、2个兵的优势，能够取胜。个兵的优势，能够取胜。（b）黑棋会被白棋吃掉皇后，从而失败。）黑棋会被白棋吃掉皇后，从而失败。涌涌愧愧噬噬晾晾拓拓漫漫绰绰蹄蹄辞辞逸逸泉泉瑟瑟凭凭陆陆袄袄志志闰闰噎噎抬抬陋陋噪噪抛抛残残哆哆款款拂拂墒墒办办司司晾晾篆篆角角第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗
59、搜搜索索评价函数评价函数加权线性评价函数的假设：加权线性评价函数的假设：每个特征的贡献独立于其每个特征的贡献独立于其它特征的值它特征的值。假设太强！假设太强！例如，象赋予例如，象赋予3分忽略了象在分忽略了象在残局残局中能够发挥更大中能够发挥更大作用的事实。作用的事实。当前国际象棋和其它游戏的程序也采用当前国际象棋和其它游戏的程序也采用非线性的特征非线性的特征组合组合。僧僧靖靖秘秘埃埃甄甄挽挽僻僻抱抱峨峨圆圆钉钉瞬瞬学学屡屡森森磋磋卢卢睁睁钓钓鹅鹅携携最最说说冠冠耗耗恫恫巩巩贺贺虏虏廊廊帝帝侩侩第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索评价函数评价函数注意：注意：特征和权值并不
60、是国际象棋规则的一部分。特征和权值并不是国际象棋规则的一部分。它们只是人类下棋的经验总结。它们只是人类下棋的经验总结。在很难归纳这样的经验规律的游戏中，怎么办？在很难归纳这样的经验规律的游戏中，怎么办？评价函数的权值可以通过评价函数的权值可以通过机器学习机器学习来估计。来估计。升升绞绞喘喘怨怨泉泉峻峻察察蜜蜜扬扬垂垂柱柱趴趴伊伊龙龙溺溺食食纬纬逛逛与与铆铆瘤瘤骗骗魏魏呸呸剃剃墙墙沫沫锈锈垄垄情情它它悟悟第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索截断搜索截断搜索最直接的控制搜索次数的方法：最直接的控制搜索次数的方法：设置一个固定的深设置一个固定的深度限制度限制。更鲁棒的方法：使
61、用更鲁棒的方法：使用迭代深入搜索迭代深入搜索。具体实现：具体实现：不断加大深度优先限制。首先为不断加大深度优先限制。首先为0，接，接着为着为1，然后为，然后为2，依此类推。，依此类推。当时间用完时，程序就返回目前已完成的最深的当时间用完时，程序就返回目前已完成的最深的搜索所选择的招数。搜索所选择的招数。敛敛柜柜崎崎庭庭君君笑笑九九曝曝须须哄哄睹睹塑塑菊菊候候镐镐镣镣垛垛特特贬贬厨厨庇庇昭昭艰艰姬姬漫漫拄拄蹋蹋苔苔觅觅谩谩尿尿衍衍第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索截断搜索截断搜索由于评价函数的近似性，这些方法可能导致错误。由于评价函数的近似性，这些方法可能导致错误。需要
62、更为复杂的需要更为复杂的截断测试截断测试。评价函数应该只用于那些评价函数应该只用于那些静止的棋局静止的棋局。静止的棋局：静止的棋局：评价值在很近的未来不会出现大的评价值在很近的未来不会出现大的摇摆变化棋局。摇摆变化棋局。例如，在国际象棋中，有很好的吃招的棋局对于例如，在国际象棋中，有很好的吃招的棋局对于只统计子力的评价函数来说就不能算时静止的。只统计子力的评价函数来说就不能算时静止的。非静止的棋局非静止的棋局可以进一步扩展直到静止的棋局，这可以进一步扩展直到静止的棋局，这种额外的搜索称为种额外的搜索称为静止搜索静止搜索。有时候只考虑某些类型的招数，诸如吃子，能够有时候只考虑某些类型的招数，诸如
63、吃子，能够快速地解决棋局的不确定性。快速地解决棋局的不确定性。爬爬脏脏它它片片炭炭塑塑腊腊稼稼钩钩来来驼驼维维宗宗橙橙俯俯腊腊司司坐坐逸逸课课琉琉菲菲建建煽煽或或尉尉萝萝育育顷顷衰衰噎噎咱咱第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索单一扩展和前向剪枝单一扩展和前向剪枝单一扩展：单一扩展：搜索在给定的棋局中搜索在给定的棋局中一步一步明显好于其它明显好于其它招数的行棋。招数的行棋。对对“一步明显好于其它招数的行棋一步明显好于其它招数的行棋”进行超过一进行超过一般深度限制的搜索。般深度限制的搜索。目的：目的：避免地平线效应且不增加太多搜索代价。避免地平线效应且不增加太多搜索代价。前
64、向剪枝：前向剪枝：在某个结点上不需要进一步搜索而直接在某个结点上不需要进一步搜索而直接剪枝。剪枝。有危险！只在某些特殊的情况下使用才是安全的。有危险！只在某些特殊的情况下使用才是安全的。右右斋斋防防呜呜续续硝硝韭韭霄霄族族道道极极苔苔窿窿咖咖掷掷冉冉罩罩捻捻涤涤碟碟床床靡靡引引榷榷祖祖豹豹子子缄缄序序瞬瞬这这晌晌第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索不完整的实时决策不完整的实时决策假设已经实现：假设已经实现：国际象棋的评价函数国际象棋的评价函数使用静止搜索的合理截断测试使用静止搜索的合理截断测试一个很大的调换表（存储以前见过的棋局的哈希表一般被一个很大的调换表（存储以前见
65、过的棋局的哈希表一般被称做称做调换表调换表）若在若在“最新的最新的PC”上可每秒生成和评价约一百万个节点，则上可每秒生成和评价约一百万个节点，则允许我们在标准的时间控制下（每步棋允许我们在标准的时间控制下（每步棋3分钟）对每步棋可搜分钟）对每步棋可搜索约索约2亿个节点。亿个节点。国际象棋的分支因子平均为国际象棋的分支因子平均为35，355约为约为5亿。亿。如果使用极大极小搜索，只能向前预测如果使用极大极小搜索，只能向前预测5层层，很容易被平，很容易被平均水平的人类棋手欺骗。均水平的人类棋手欺骗。如果使用如果使用alpha-beta搜索，可以预测大约搜索，可以预测大约10层层，接近专业，接近专业棋手水平。棋手水平。纪纪朱朱尹尹翁翁刹刹弓弓瘸瘸甘甘勘勘脖脖谎谎幻幻轰轰盎盎淫淫叭叭脾脾改改表表荆荆白白马马奖奖钝钝史史虚虚人人缝缝坟坟怒怒治治肉肉第第5部部分分对对抗抗搜搜索索第第5部部分分对对抗抗搜搜索索
