【正文】 狀態(tài)的一系列招數(shù) ? 在井字棋搜索樹中， 因?yàn)?MAX先行，所以 MAX的任務(wù)是利用搜索樹確定最佳招數(shù) / 但是另一方 MIN也有發(fā)言權(quán) ? 因此 MAX制定取勝策略時(shí)必須不斷地考慮 MIN應(yīng)對(duì)條件下如何取勝 —即 MAX初始狀態(tài)下應(yīng)該采取什么招數(shù)，然后是MIN應(yīng)對(duì)造成的狀態(tài)下 MAX采取的招數(shù)，接著繼續(xù)考慮下一步應(yīng)對(duì)后的招數(shù) ... 第 2章 搜索技術(shù) 56 極大極小值 (1) ? 假設(shè)一個(gè)兩層的博弈樹 (因?yàn)榧词故蔷制宓牟┺臉湟蔡珡?fù)雜了 )，其中有 MAX節(jié)點(diǎn)和 MIN節(jié)點(diǎn) ? 博弈樹中，每個(gè)單方的招數(shù) (或稱走步 )是一層 / 雙方各走一招稱為一步 (博弈樹的深度是一步的 ) ? 給定一棵博弈樹，最優(yōu)策略可以通過檢查每個(gè)節(jié)點(diǎn)的極大極小值來決定 —記為MAXMIN(n)，所以也稱為極大極小決策 第 2章 搜索技術(shù) 57 極大極小值 (2) ? 如果博弈雙方都按照最優(yōu)策略進(jìn)行，那么一個(gè)節(jié)點(diǎn)的極大極小值就是對(duì)應(yīng)狀態(tài)的效用值 (對(duì)應(yīng) MAX) ? 對(duì)于某個(gè)節(jié)點(diǎn)，極大極小函數(shù)如下定義 ? MAX優(yōu)先選擇有極大值的狀態(tài) / MIN則選擇有極小值的狀態(tài) 第 5章 搜索技術(shù) ???????????節(jié)點(diǎn)為當(dāng)節(jié)點(diǎn)為當(dāng)為終止?fàn)顟B(tài)MINn)(minMAXn)(maxn當(dāng))()()()(sMINMA XsMINMA XnUtilitynMINMA Xnsonsnsons58 極大極小值 (3) 第 2章 搜索技術(shù) 3 12 8 2 4 6 14 5 2 A B D C 3 2 2 3 MAX MIN MAX 59 極大極小值 (4) ? 圖中 MAX先行，有 3個(gè)后繼 MIN節(jié)點(diǎn)，此時(shí) MAX的取值必須看 MIN如何取值 ? 每個(gè) MIN節(jié)點(diǎn)亦有 3個(gè)后繼 MAX節(jié)點(diǎn)，假設(shè)其取值已知 ? 因?yàn)?MIN節(jié)點(diǎn)只取其后繼節(jié)點(diǎn)中之最小者 (讓 MAX效用最小 )，故 B=3/C=2/D=2 ? MAX節(jié)點(diǎn)取 A/B/C中最大者，故 A=3 ? 最后根節(jié)點(diǎn) A的極大極小函數(shù)值 =3—引向具有最高極大極小值的后繼 第 2章 搜索技術(shù) 60 極大極小值算法說明 ? 簡單的遞歸算法 —按照定義計(jì)算每個(gè)后繼節(jié)點(diǎn)的極大極小值 / 搜索是從目標(biāo)到初始節(jié)點(diǎn)的反向推導(dǎo) ? 算法對(duì)博弈樹實(shí)行了深度優(yōu)先搜索 ? 如果博弈樹的最大深度為 m，每個(gè)節(jié)點(diǎn)的合法招數(shù)為 b，則 ? 算法的時(shí)間復(fù)雜度是 O(bm) ? 每次生成全部后繼節(jié)點(diǎn)的空間復(fù)雜度是 O(bm) ? 每次只生成一個(gè)后繼節(jié)點(diǎn)的空間復(fù)雜度是 O(m) 第 2章 搜索技術(shù) 61 極大極小值算法 Function MAXMINDECISION(state) returns an action inputs: state (current state in game) v← MAX VALUE(state) return the action in SUCCESSORS(state) with value v Function MAXVALUE(state) returns a utility value if TERMINALTEST(state) then return UTILITY(state) v← ∞ for a, s in SUCCESSORS(state) do v← MAX(v, MIN VALUE(s)) return v (a=action招數(shù) ) Function MINVALUE(state) returns a utility value if TERMINALTEST(state) then return UTILITY(state) v← +∞ for a, s in SUCCESSORS(state) do v← MIN(v, MAX VALUE(s)) return v 第 2章 搜索技術(shù) 62 ??剪枝 ? 極大極小值搜索的問題是狀態(tài)數(shù)隨著棋局步數(shù)的數(shù)量而指數(shù)級(jí)增長 — 不幸的是沒有辦法消除這種指數(shù)級(jí)增長，所幸的是可以有效將其減半 — 剪枝技術(shù) ? 應(yīng)用于極大極小值搜索樹中 — ??剪枝 ? 剪掉那些不可能影響最后決策的分支，返回和極大極小值算法同樣的結(jié)果 ? 例子的剪枝過程中 MAXMIN(n)= max(min(3,12,8), min(2,x,y), min(14,5,2))= max(3,min(2,x,y),2)=max(3,z,2)=3 第 2章 搜索技術(shù) 63 博弈樹的剪枝 (1) 第 2章 搜索技術(shù) 3 [∞, +∞] A B [∞,3] (a) [∞, +∞] 12 A B 3 [∞,3] (b) 64 博弈樹的剪枝 (2) 第 2章 搜索技術(shù) 12 A B [3, +∞] 3 8 [3,3] (c) 12 A B C [3, +∞] [∞,2] 3 8 2 [3,3] (d) 65 博弈樹的剪枝 (3) 第 2章 搜索技術(shù) [∞,14] 12 A B D C [3,14] [∞,2] 3 8 2 14 [3,3] (e) 12 A B D C [3,3] [∞,2] [2,2] 3 8 2 14 5 2 [3,3] (f ) 66 ??剪枝算法 (1) ? 在極大極小值算法基礎(chǔ)上增加了剪枝功能，即在返回值基礎(chǔ)上增加了判斷 Function ALPHABETASEARCH(state) returns an action inputs: state (current state in game) v← MAX VALUE(state, ∞, +∞) return the action in SUCCESSORS(state) with value v 第 2章 搜索技術(shù) 67 ??剪枝算法 (2) Function MAXVALUE(state,?, ? ) returns a utility value inputs: state ?, the value of the best alternative for MAX along the path to state ?, the value of the best alternative for MIN along the path to state if TERMINALTEST(state) then return UTILITY(state) v← ∞ for a, s in SUCCESSORS(state) do v← MAX(v, MIN VALUE(s,?, ? )) if v≥? then return v ? ← MAX( ?, v) return v 第 2章 搜索技術(shù) 68 ??剪枝算法 (3) Function MINVALUE(state, ?, ? ) returns a utility value inputs: state ?, the value of the best alternative for MAX along the path to state ? the value of the best alternative for MIN along the path to state if TERMINALTEST(state) then return UTILITY(state) v← +∞ for a, s in SUCCESSORS(state) do v← MIN(v, MAX VALUE(s, ?, ? )) if v≤? then return v ? ← MIN( ?, v) return v