與或圖與博弈搜索max詳解課件.ppt

《與或圖與博弈搜索max詳解課件.ppt》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第四章與或圖搜索問(wèn)題4.1與或圖搜索4.2AO*算法4.3博弈搜索4.4極大極小決策4.5?–?剪枝4.3博弈搜索從智能體角度看，博弈是多智能體之間的競(jìng)爭(zhēng)和對(duì)抗，在競(jìng)爭(zhēng)的環(huán)境中，每個(gè)智能體的目標(biāo)是沖突的，由此引出對(duì)抗搜索問(wèn)題—稱(chēng)為博弈。例如：一字棋、中國(guó)象棋、跳棋。本節(jié)探討兩個(gè)問(wèn)題—如何搜索到取勝的路徑/如何提高搜索效率相應(yīng)的方法—極大極小決策方法/?-?剪枝方法博弈游戲的描述兩個(gè)游戲者的博弈可以定義為一類(lèi)搜索問(wèn)題，其中包括：初始狀態(tài)：棋盤(pán)局面和哪個(gè)游戲者出招規(guī)則集：合法走步（招數(shù)）的一個(gè)列表終止測(cè)試：判斷游戲是否結(jié)束效用函數(shù)—或稱(chēng)目標(biāo)函數(shù)，對(duì)終止?fàn)顟B(tài)給出一個(gè)數(shù)值如輸贏和平局(以

2、-∞/+∞/0表示)雙方的初始狀態(tài)和合法招數(shù)定義了游戲的博弈樹(shù)—此為博弈搜索（最優(yōu)解是導(dǎo)致取勝的終止?fàn)顟B(tài)的一系列招數(shù)）博弈游戲的搜索策略完整的搜索策略：狀態(tài)數(shù)多，搜索分支多，效率低極大極小搜索策略：尋找一步好棋，待對(duì)手回敬后再考慮尋找另一步好棋關(guān)鍵：給定當(dāng)前狀態(tài)，如何從合法走步中選擇一個(gè)較優(yōu)招數(shù)（考慮雙方對(duì)弈若干步之后，再?gòu)漠?dāng)前狀態(tài)可能的走步中選一個(gè)相對(duì)較好的招數(shù)，即在有限的搜索深度范圍內(nèi)進(jìn)行求解。為此定義靜態(tài)估計(jì)函數(shù)ｆ，用來(lái)評(píng)價(jià)棋局優(yōu)劣）。約定：MAX代表程序方，MIN代表對(duì)手，MAX先走，f值范圍從-∞(對(duì)方贏)到+∞(程序方贏)，值越大對(duì)程序方越有利。極大極小策略分析312

3、82461452ABDC3223MAXMINMAX端節(jié)點(diǎn)的棋局值通過(guò)f(s)計(jì)算得到，其余節(jié)點(diǎn)采取倒推法計(jì)算；B、C、D是MIN走步節(jié)點(diǎn)，MAX考慮最壞情況，取子節(jié)點(diǎn)估值最小(MIN取極小)；Ａ是MAX走步節(jié)點(diǎn)，可考慮最好情況，取子節(jié)點(diǎn)估值最大者(MAX取極大)極大極小搜索過(guò)程算法分兩階段：2-4步用寬度優(yōu)先法生成規(guī)定深度的全部博弈樹(shù)，并計(jì)算端節(jié)點(diǎn)棋局值6-8步從底向上逐級(jí)倒推非端節(jié)點(diǎn)的棋局值。算法的結(jié)果(求當(dāng)前狀態(tài)的最佳走子算法)：當(dāng)前棋局的一步走法，而圖搜索找到的是從初始狀態(tài)到目標(biāo)狀態(tài)的解路徑極大極小策略的應(yīng)用示例ABCD在九宮格棋盤(pán)上，兩位選手輪流擺放棋子，先走出三子一線(xiàn)的

4、一方取勝。教材P68極大極小策略分析效率低MINMAX過(guò)程是把搜索樹(shù)的生成和棋局估值這兩個(gè)過(guò)程分開(kāi)進(jìn)行。見(jiàn)教材P71-∞1282461452ABDC223MAXMINMAX-∞?-?搜索策略基本思想將結(jié)點(diǎn)生成和倒推估值同時(shí)進(jìn)行，并根據(jù)一定的條件判斷，盡早修剪掉無(wú)用的分支。?-?搜索策略:剪枝示例(1)4AB[-∞,4](a)3AB4[-∞,3](b)3AB[3,+∞]48[3,3](c)3ABC[3,+∞][-∞,2]482[3,3](d)?-?搜索策略:剪枝示例(2)[-∞,14]3ABDC[3,14][-∞,2]48214[3,3](e)3ABDC[3,3][-∞,2][2,

5、2]4821452[3,3](f)總結(jié):在搜索過(guò)程中記住棋局倒推值的上下界（?和?）并進(jìn)行比較,便可以實(shí)現(xiàn)剪枝操作.?-?搜索策略:剪枝示例(3)?-?搜索策略在極大極小值算法基礎(chǔ)上增加了剪枝功能,并采用深度優(yōu)先策略進(jìn)行搜索。極大節(jié)點(diǎn)的棋局倒推值下界為?,極小節(jié)點(diǎn)的棋局倒推值上界為?。剪枝的條件：后輩節(jié)點(diǎn)的?值(MIN層)≤祖先節(jié)點(diǎn)的?值時(shí)(MAX層)，?剪枝后輩節(jié)點(diǎn)的?值(MAX層)≥祖先節(jié)點(diǎn)的?值時(shí)(MIN層)，?剪枝(剪枝:終止后輩節(jié)點(diǎn)以下的搜索過(guò)程)簡(jiǎn)記為：極小≤極大，剪枝極大≥極小，剪枝?-?搜索策略86-31453-3503-3022-30-2309-300-3033

6、05411-31661abcdefghijkmn注意：只有一個(gè)結(jié)點(diǎn)的值“固定”以后，其值才能向其父結(jié)點(diǎn)傳遞Ｋ＝４MINMINMAXMAX?-?剪枝的效率?-?剪枝的效率很大程度上取決于檢查后繼節(jié)點(diǎn)的次序—應(yīng)該先檢查那些可能最好的后繼如果能夠先檢查那些最好的后繼，則?-?剪枝算法只需檢查O(bd/2)個(gè)節(jié)點(diǎn)以決定最佳招數(shù)/極大極小值算法為O(bd)—有效分支因子b到b的平方根—效率大大提高