搜索(博弈樹的啟發(fā)式搜索).ppt

1、搜索策略,博弈樹的啟發(fā)式搜索,2,博弈問題,如下棋、打牌、競技、戰(zhàn)爭等一類競爭性智能活動(dòng)稱為博弈。博弈有很多種，我們討論最簡單的“二人零和、全信息、非偶然”博弈，其特征如下： 雙人對弈，對壘的雙方輪流走步。 零和。即對一方有利的棋，對另一方肯定是不利的，不存在對雙方均有利、或均無利的棋。對弈的結(jié)果是一方贏，而另一方輸，或者雙方和棋。 信息完備，對壘雙方所得到的信息是一樣的，不存在一方能看到，而另一方看不到的情況。 任何一方在采取行動(dòng)前都要根據(jù)當(dāng)前的實(shí)際情況，進(jìn)行得失分析，選取對自已為最有利而對對方最為不利的對策，不存在擲骰子之類的碰運(yùn)氣因素。即雙方都是很理智地決定自己的行動(dòng)。,博弈是一類富有智

2、能行為的競爭活動(dòng)，如下棋、打牌、戰(zhàn)爭等。博弈可分為雙人完備信息博弈和機(jī)遇性博弈。所謂雙人完備信息博弈，就是兩位選手對壘，輪流走步，每一方不僅知道對方已經(jīng)走過的棋步，而且還能估計(jì)出對方未來的走步。對弈的結(jié)果是一方贏，另一方輸；或者雙方和局。這類博弈的實(shí)例有象棋、圍棋等。所謂機(jī)遇性博弈，是指存在不可預(yù)測性的博弈，例如擲幣等。對機(jī)遇性博弈，由于不具備完備信息，因此我們不作討論。,4,5,這里我們主要討論雙人完備信息博弈問題。 在雙人完備信息博弈過程中，雙方都希望自己能夠獲勝。因此，當(dāng)任何一方走步時(shí)，都是選擇對自己最為有利，而對另一方最為不利的行動(dòng)方案。 假設(shè)博弈的一方為MAX，另一方為MIN。在博弈

3、過程的每一步，可供MAX和MIN選擇的行動(dòng)方案都可能有多種。從MAX方的觀點(diǎn)看，可供自己選擇的那些行動(dòng)方案之間是“或”的關(guān)系，原因是主動(dòng)權(quán)掌握在MAX手里，選擇哪個(gè)方案完全是由自己決定的；而對那些可供MIN選擇的行動(dòng)方案之間則是“與”的關(guān)系，原因是主動(dòng)權(quán)掌握在MIN的手里，任何一個(gè)方案都有可能被MIN選中，MAX必須防止那種對自己最為不利的情況的發(fā)生。,6,若把雙人完備信息博弈過程用圖表示出來，就可得到一棵與/或樹，這種與/或樹被稱為博弈樹。在博弈樹中，那些下一步該MAX走步的節(jié)點(diǎn)稱為MAX節(jié)點(diǎn)，而下一步該MIN走步的節(jié)點(diǎn)稱為MIN節(jié)點(diǎn)。博弈樹具有如下特點(diǎn)： （l）博弈的初始狀態(tài)是初始節(jié)點(diǎn)；

4、（2）博弈樹中的“或”節(jié)點(diǎn)和“與”節(jié)點(diǎn)是逐層交替出現(xiàn)的； （3）整個(gè)博弈過程始終站在某一方的立場上，所有能使自己一方獲勝的終局都是本原問題，相應(yīng)的節(jié)點(diǎn)是可解節(jié)點(diǎn)；所有使對方獲勝的終局都是不可解節(jié)點(diǎn)。例如，站在MAX方，所有能使MAX方獲勝的節(jié)點(diǎn)都是可解節(jié)點(diǎn)，所有能使MIN方獲勝的節(jié)點(diǎn)都是不可解節(jié)點(diǎn)。,一.博弈樹概述,博弈問題空間模型化,只考慮兩個(gè)游戲者: MAX和MIN, 兩個(gè)人輪流出招,直到游戲結(jié)束. 四元組： （初始狀態(tài)，操作集合，終止測試（非目標(biāo)測試），判定函數(shù)） 初始狀態(tài)：包括棋局的局面和確定該哪個(gè)游戲者出招 后繼函數(shù)：返回(move,state)對的一個(gè)列表,其中每一對表示一個(gè)合法

5、的著數(shù)和其結(jié)果狀態(tài) 終止測試：判斷游戲是否結(jié)束, 游戲結(jié)束的狀態(tài)稱為終止?fàn)顟B(tài) 判定函數(shù)：又稱為目標(biāo)函數(shù)或者收益函數(shù),對終止?fàn)顟B(tài)給出一個(gè)數(shù)值. （比如：可以-1表示輸，0表示和局，1表示贏）,博弈的初始格局是初始節(jié)點(diǎn),在博弈樹中，或節(jié)點(diǎn)和與節(jié)點(diǎn)是逐層交替出現(xiàn)的。,如果我們站在MAX方的立場上，則可供MAX方選擇的若干行動(dòng)方案之間是“或”關(guān)系，因?yàn)橹鲃?dòng)權(quán)操在MAX方手里，他或者選擇這個(gè)行動(dòng)方案，或者選擇另一個(gè)行動(dòng)方案，完全由MAX方自已決定。,當(dāng)MAX方選取任一方案走了一步后，MIN方也有若干個(gè)可供選擇的行動(dòng)方案，此時(shí)這些行動(dòng)方案對MAX方來說它們之間則是與關(guān)系，因?yàn)檫@時(shí)主動(dòng)權(quán)操在MIN方手里，這

6、些可供選擇的行動(dòng)方案中的任何一個(gè)都可能被MIN方選中，MAX方必須應(yīng)付每一種情況的發(fā)生。,9,對簡單的博弈問題，可以生成整個(gè)博弈樹，找到必勝的策略。但對于復(fù)雜的博弈，如國際象棋，大約有10120個(gè)節(jié)點(diǎn)，可見要生成整個(gè)搜索樹是不可能的。一種可行的方法是用當(dāng)前正在考察的節(jié)點(diǎn)生成一棵部分博弈樹，由于該博弈樹的葉節(jié)點(diǎn)一般不是哪一方的獲勝節(jié)點(diǎn)，因此，需利用估價(jià)函數(shù)f(n)對葉節(jié)點(diǎn)進(jìn)行靜態(tài)評估，對MAX有利的節(jié)點(diǎn)其估價(jià)函數(shù)取正值；那些對MIN有利的節(jié)點(diǎn)，其估價(jià)函數(shù)取負(fù)值；那些使雙方均等的節(jié)點(diǎn)，其估價(jià)函數(shù)取接近于0的值。,二. 極大極小過程,為了計(jì)算非葉節(jié)點(diǎn)的值，必須從葉節(jié)點(diǎn)向上倒推。對于MAX節(jié)點(diǎn)，由于

7、MAX方總是選擇估值最大的走步，因此，MAX節(jié)點(diǎn)的倒推值應(yīng)該取其后繼節(jié)點(diǎn)估值的最大值。對于MIN節(jié)點(diǎn)，由于MIN方總是選擇使估值最小的走步，因此MIN節(jié)點(diǎn)的倒推值應(yīng)取其后繼節(jié)點(diǎn)估值的最小值。這樣一步一步的計(jì)算倒推值，直至求出初始節(jié)點(diǎn)的倒推值為止。由于我們是站在MAX的立場上，因此應(yīng)選擇具有最大倒推值的走步。這一過程稱為極大極小過程。 下面給出一個(gè)極大極小過程的例子。,極小極大法,基本思想: 首先假定，有一個(gè)評價(jià)函數(shù)可以對所有的棋局進(jìn)行評估。 當(dāng)評價(jià)函數(shù)值大于0時(shí)，表示棋局對我方有利，對對方不利; 當(dāng)評價(jià)函數(shù)小于0時(shí)，表示棋局對我方不利，對對方有利; 而評價(jià)函數(shù)值越大，表示對我方越有利。當(dāng)評價(jià)函

8、數(shù)值等于正無窮大時(shí)，表示我方必勝。 評價(jià)函數(shù)值越小，表示對我方越不利。當(dāng)評價(jià)函數(shù)值等于負(fù)無窮大時(shí)，表示對方必勝; 假設(shè)雙方都是對弈高手，在只看一步棋的情況下，我方一定走評價(jià)函數(shù)值最大的一步棋，而對方一定走評價(jià)函數(shù)值最小的一步棋。,人下棋的思考方式,人下棋實(shí)際上采用一種試探性的方法: 假定走了一步棋,看對方會有哪些應(yīng)法; 再根據(jù)對方的每一種應(yīng)法,看我方是否有好的回應(yīng); 這一過程一直進(jìn)行下去,直到若干步后,找到一個(gè)滿意的走法為止. 極大極小搜索方法模擬的就是人的這樣一種思維過程.,極大極小搜索方法是一種在有限搜索深度范圍進(jìn)行求解的方法.,定義一個(gè)靜態(tài)估計(jì)函數(shù)f,以便對棋局的葉子節(jié)點(diǎn)作出優(yōu)劣估值,2

9、.非葉子節(jié)點(diǎn)的估值由倒推取值的方法取得,a.MAX走步必然選擇對自己最有利的一步,如A節(jié)點(diǎn)的估計(jì)值是3,b.MIN走步必然選擇對自己最有利的一步,如D節(jié)點(diǎn)的估計(jì)值是2,1.首先按照一定的搜索深度生成出給定深度d以內(nèi)的所有狀態(tài)，計(jì)算所有葉節(jié)點(diǎn)的評價(jià)函數(shù)值。,獲得根節(jié)點(diǎn)取值的那一分枝，即為所選擇的最佳走步,節(jié)點(diǎn)A,輪到MAX下棋.,算法框架 整個(gè)算法分為四個(gè)步驟： 1、以當(dāng)前狀態(tài)為根結(jié)點(diǎn)產(chǎn)生一個(gè)博弈樹。 2、對博弈樹的每一個(gè)葉結(jié)點(diǎn)，利用判定函數(shù)給出它的判定值。 3、從葉結(jié)點(diǎn)開始，一層一層地回溯。在回溯過程中，利用最大/最小判定為每一個(gè)結(jié)點(diǎn)給出其判定值。 4、MAX方選擇下一層中判定值最大的結(jié)點(diǎn)，作

10、為它的下一狀態(tài)。 Function Minimax-Decision(state) return an action vMax-Value(state) return action in successors(state) with value v Function Max-Value(state) return a utility value if Terminal-Test(state) then return Utility(state) v- for s in successors(state) do v Max(v, Min_Value(s) Return v Function Mi

11、n-Value(state) return an utility value if Terminal-Test(state) then return Utility(state) v+ for s in successors(state) do v Min(v, Max_Value(s) Return v,14,例： 一字棋游戲。設(shè)有一個(gè)三行三列的棋盤，如下圖所示，兩個(gè)棋手輪流走步，每個(gè)棋手走步時(shí)往空格上擺一個(gè)自己的棋子，誰先使自己的棋子成三子一線為贏。設(shè)MAX方的棋子用標(biāo)記，MIN方的棋子用 標(biāo)記，并規(guī)定MAX方先走步。 解：為了對葉節(jié)點(diǎn)進(jìn)行靜態(tài)估值，規(guī)定估價(jià)函數(shù)e（P）如下： 若 P是 M

12、AX的必勝局， 則 e（P）= + ； 若 P是 MIN 的必勝局， 則 e（P）= - ；,若P對MAX、MIN都是勝負(fù)未定局，則 e（P）= e（+P）e（-P）其中，e（+P）表示棋局 P上有可能使 成三子一線的數(shù)目；e（-P）表示棋局 P上有可能使 成三子一線的數(shù)目。,二. 極大極小過程,15,例如，對圖1所示的棋局有估價(jià)函數(shù)值 e（P）6-42,在搜索過程中，具有對稱性的棋局認(rèn)為是同一棋局。例如，圖2所示的棋局可以認(rèn)為是同一個(gè)棋局，這樣可以大大減少搜索空間。圖3給出了第一著走棋以后生成的博弈樹。圖中葉節(jié)點(diǎn)下面的數(shù)字是該節(jié)點(diǎn)的靜態(tài)估值，非葉節(jié)點(diǎn)旁邊的數(shù)字是計(jì)算出的倒推值。從圖中可以看出

13、，對MAX來說S2是一著最好的走棋，它具有較大的倒推值。,16,圖3 一子棋的極大極小搜索,S0,S1,S2,S3,S4,S5,-1,1,-2,6-5=1,5-5=0,6-5=1,5-5=0,4-5=-1,5-6=-1,5-5=0,6-6=0,5-6=-1,4-6=-2,5-4=1,6-4=2,一字棋游戲極小極大樹,定義一個(gè)靜態(tài)估計(jì)函數(shù)f,以便對棋局的葉子節(jié)點(diǎn)作出優(yōu)劣估值,2.非葉子節(jié)點(diǎn)的估值由倒推取值的方法取得,a.MAX走步必然選擇對自己最有利的一步,如節(jié)點(diǎn)的估計(jì)值是1,b.MIN走步必然選擇對自己最有利的一步,如節(jié)點(diǎn)的估計(jì)值是-2,1.首先按照一定的搜索深度生成出給定深度d以內(nèi)的所有狀態(tài)

14、，計(jì)算所有葉節(jié)點(diǎn)的評價(jià)函數(shù)值。,獲得根節(jié)點(diǎn)取值的那一分枝，即為所選擇的最佳走步,MAX在初始節(jié)點(diǎn)時(shí)應(yīng)該怎么走,一字棋游戲極小極大樹,MAX在第二步應(yīng)該怎么走,-剪枝,在極小極大搜索方法中，由于要先生成指定深度以內(nèi)的所有節(jié)點(diǎn)，其節(jié)點(diǎn)數(shù)將隨著搜索深度的增加呈指數(shù)增長。這極大地限制了極小極大搜索方法的使用。 -剪枝的基本思想: 邊生成博弈樹邊計(jì)算評估各節(jié)點(diǎn)的倒推值，并且根據(jù)評估出的倒推值范圍，及時(shí)停止擴(kuò)展那些已無必要再擴(kuò)展的子節(jié)點(diǎn)，即相當(dāng)于剪去了博弈樹上的一些分枝，從而節(jié)約了機(jī)器開銷，提高了搜索效率。,A,- ,+ ,- , 3 ,3,12,8, 3, + ,- ,+ 2 ,2, 3 , 3 ,-

15、14 ,14, 3, 14 ,5,2, 2 , 2 , 3, 3 ,-剪枝,= 到目前為止我們在路徑上的任意選擇點(diǎn)發(fā)現(xiàn)MAX的最佳(即極大值)選擇 = 到目前為止我們在路徑上的任意選擇點(diǎn)發(fā)現(xiàn)MIN的最佳(即極小值)選擇,算法框架 (1) 對于一個(gè)與節(jié)點(diǎn)MIN，若能估計(jì)出其倒推值的上確界，并且這個(gè)值不大于 MIN的父節(jié)點(diǎn)(一定是或節(jié)點(diǎn))的估計(jì)倒推值的下確界，即，則就不必再擴(kuò)展該 MIN節(jié)點(diǎn)的其余子節(jié)點(diǎn)了(因?yàn)檫@些節(jié)點(diǎn)的估值對MIN父節(jié)點(diǎn)的倒推值已無任何影響)。這一過程稱為剪枝。 (2) 對于一個(gè)或節(jié)點(diǎn)MAX，若能估計(jì)出其倒推值的下確界，并且這個(gè)值不小于 MAX的父節(jié)點(diǎn)(一定是與節(jié)點(diǎn))的估計(jì)倒推值

16、的上確界，即，則就不必再擴(kuò)展該MAX節(jié)點(diǎn)的其余子節(jié)點(diǎn)了(因?yàn)檫@些節(jié)點(diǎn)的估值對MAX父節(jié)點(diǎn)的倒推值已無任何影響)。這一過程稱為剪枝。 算法特點(diǎn)：(1) MAX節(jié)點(diǎn)(包括起始節(jié)點(diǎn))的值永不減少；(2) MIN節(jié)點(diǎn)(包括起始節(jié)點(diǎn))的值永不增加。 和值的計(jì)算方法：(1) 一個(gè)MAX節(jié)點(diǎn)的值等于其后繼節(jié)點(diǎn)當(dāng)前最大的最終倒推值。(2) 一個(gè)MIN節(jié)點(diǎn)的值等于其后繼節(jié)點(diǎn)當(dāng)前最小的最終倒推值。,一字棋第一階段-剪枝方法,第一個(gè)被訪問的葉子節(jié)點(diǎn),訪問完節(jié)點(diǎn)1, 初始節(jié)點(diǎn)s的取值范圍是-1 ,+ ,開始訪問完節(jié)點(diǎn)7,訪問完節(jié)點(diǎn)8, 節(jié)點(diǎn)7的取值范圍是- ,-1 節(jié)點(diǎn)7的父節(jié)點(diǎn)是s 此時(shí), 節(jié)點(diǎn)7不必在分裂下去了,

17、 即剪掉該枝,深度搜索,例,若以最理想的情況進(jìn)行搜索，即對MIN節(jié)點(diǎn)先擴(kuò)展最低估值的節(jié)點(diǎn)（若從左向右順序進(jìn)行，則設(shè)節(jié)點(diǎn)估計(jì)值從左向右遞增排序），MAX先擴(kuò)展最高估值的節(jié)點(diǎn)（設(shè)估計(jì)值從左向右遞減排序）。 則當(dāng)搜索樹深度為D，分枝因子為B時(shí)，若不使用-剪枝技術(shù)，搜索樹的端節(jié)點(diǎn)數(shù)ND=BD ；若使用-剪枝技術(shù)可以證明理想條件下生成的端節(jié)點(diǎn)數(shù)最少，有 ND2BD/2-1（D為偶數(shù)） NDB(D+1)/2+ B(D-1)/2-1（D為奇數(shù)） 比較后得出最佳-搜索技術(shù)所生成深度為D處的端節(jié)點(diǎn)數(shù)約等于不用-搜索技術(shù)所生成深度為D2處的端節(jié)點(diǎn)數(shù)。這就是說，在一般條件下使用-搜索技術(shù)，在同樣的資源限制下，可以向

18、前考慮更多的走步數(shù)，這樣選取當(dāng)前的最好優(yōu)先走步，將帶來更大的取勝優(yōu)勢。,剪枝效率,評價(jià)函數(shù),搜索算法幾乎不可能搜索全部空間直到終止?fàn)顟B(tài), 而應(yīng)該可能早的截?cái)嗨阉?把啟發(fā)式評價(jià)函數(shù)用于搜索中的狀態(tài),有效地把非終節(jié)點(diǎn)變成了葉子終止節(jié)點(diǎn). 評價(jià)函數(shù)與真正的效用函數(shù)一致 時(shí)間效率問題 對于非終止?fàn)顟B(tài),評價(jià)函數(shù)與取勝機(jī)會密切相關(guān) 大多數(shù)的評價(jià)函數(shù)的工作方式是: 計(jì)算狀態(tài)的不同特征值. 這些特征在一起定義了狀態(tài)的各種類別或等價(jià)類:每類中的狀態(tài)對所有特征都有相同的值.一般來說,任何給定的類都會包括某些致勝的狀態(tài),某些導(dǎo)致和局的狀態(tài)以及會導(dǎo)致失敗的狀態(tài).評價(jià)函數(shù)可以返回一個(gè)反映每個(gè)結(jié)果中狀態(tài)所占比例的單一值.

19、 一個(gè)線形的加權(quán)函數(shù)例子: EVAL(s)=w1f1(s)+wnfn(s) (合理嗎?),關(guān)于截?cái)嗨阉?截?cái)嗨阉髟谀成疃冉K止搜索, 并用評價(jià)函數(shù)對非終止結(jié)點(diǎn)進(jìn)行估值,并以此作為對未來棋局的判斷. 當(dāng)截?cái)嗟奈恢脛偤锰幱诰置娲蠓▌?dòng)的地方,該判斷會產(chǎn)生重大的偏差. 靜止的棋局 顯然, 評價(jià)函數(shù)只適用于那些靜止的棋局-也就是評估的價(jià)值在很近的未來不會出現(xiàn)很大的搖擺變化的棋局.例如在國際象棋中,有很好的吃招的棋局對于只統(tǒng)計(jì)子力的評價(jià)函數(shù)來說就不能算是靜止的。非靜止的棋局可以進(jìn)一步擴(kuò)展直到靜止的棋局.這種額外的搜索稱為靜止搜索. 地平線效應(yīng) 當(dāng)對手的應(yīng)對可能導(dǎo)致我方的重大損失并且是不可避免的情況, 如國

20、際象棋中黑棋領(lǐng)先較多,但對方白棋如果能夠把接近底線的兵推進(jìn)到底線升格為皇后,那么白棋基本上就贏了.黑棋會盡力的延緩這種情況發(fā)生,但搜索的深度有限, 黑棋的這種努力有可能不斷的把白兵升后的行棋推出”搜索的地平線”,將其推到無法檢測到的空間,稱為地平線效應(yīng).,28,上述極大極小過程是先生成與/或樹，然后再計(jì)算各節(jié)點(diǎn)的估值，這種生成節(jié)點(diǎn)和計(jì)算估值相分離的搜索方式，需要生成規(guī)定深度內(nèi)的所有節(jié)點(diǎn)，因此搜索效率較低。如果能邊生成節(jié)點(diǎn)邊對節(jié)點(diǎn)估值，從而可以剪去一些沒用的分枝，這種技術(shù)稱為-剪枝過程。,再論- 剪枝,=2,3,對于一個(gè)與節(jié)點(diǎn)來說，它取當(dāng)前子節(jié)點(diǎn)中的最小倒推值作為它倒推值的上界，稱該值為值。 對

21、于一個(gè)或節(jié)點(diǎn)來說，它取當(dāng)前子節(jié)點(diǎn)中的最大倒推值作為它倒推值的下界，稱該值為 值。,29,-剪枝的方法如下： （1） MAX節(jié)點(diǎn)的值為當(dāng)前子節(jié)點(diǎn)的最大倒推值； （2） MIN 節(jié)點(diǎn)的值為當(dāng)前子節(jié)點(diǎn)的最小倒推值； （3） - 剪枝的規(guī)則如下： 任何MAX節(jié)點(diǎn)n的值大于或等于它先輩節(jié)點(diǎn)的值，則n以下的分枝可停止搜索，并令節(jié)點(diǎn)n的倒推值為 。這種剪枝稱為剪枝。 任何MIN節(jié)點(diǎn)n的值小于或等于它先輩節(jié)點(diǎn)的值，則n以下的分枝可停止搜索，并令節(jié)點(diǎn)n的倒推值為。這種剪枝稱為剪枝。 下面看一個(gè)-剪枝的具體例子，如下頁圖所示。其中最下面一層端節(jié)點(diǎn)下面的數(shù)字是假設(shè)的估值。,再論- 剪枝,30,4,4,1,4,4,5,5,4,4,0,0,0,-6,0,0,4,-剪枝的例子,31,在上頁圖中，由節(jié)點(diǎn)K、L、M的估值推出節(jié)點(diǎn)F的倒推值為4，即F的值為4，由此可推出節(jié)點(diǎn)C的倒推值4。記C的倒推值的下界為4，不可能再比4小，故C的值為4 。由節(jié)點(diǎn)N的估值推知節(jié)點(diǎn)G的倒推值小于l，無論G的其他子節(jié)點(diǎn)的估值是多少，G