【正文】 慮 MIN應對條件下如何取勝 —即 MAX初始狀態(tài)下應該采取什么招數(shù)，然后是MIN應對造成的狀態(tài)下 MAX采取的招數(shù)，接著繼續(xù)考慮下一步應對后的招數(shù) ... 第 2章 搜索技術(shù) 53 極大極小值 (1) ? 假設一個兩層的博弈樹 (因為即使是井字棋的博弈樹也太復雜了 )，其中有 MAX節(jié)點和 MIN節(jié)點 ? 博弈樹中，每個單方的招數(shù) (或稱走步 )是一層 / 雙方各走一招稱為一步 (博弈樹的深度是一步的 ) ? 給定一棵博弈樹，最優(yōu)策略可以通過檢查每個節(jié)點的極大極小值來決定 —記為MAXMIN(n)，所以也稱為極大極小決策 第 2章 搜索技術(shù) 54 極大極小值 (2) ? 如果博弈雙方都按照最優(yōu)策略進行，那么一個節(jié)點的極大極小值就是對應狀態(tài)的效用值 (對應 MAX) ? 對于某個節(jié)點，極大極小函數(shù)如下定義 ? MAX優(yōu)先選擇有極大值的狀態(tài) / MIN則選擇有極小值的狀態(tài) 第 5章 搜索技術(shù) ???????????節(jié)點為當節(jié)點為當為終止狀態(tài)MINn)(minMAXn)(maxn當)()()()(sMINMA XsMINMA XnUtilitynMINMA Xnsonsnsons55 極大極小值 (3) 第 2章 搜索技術(shù) 3 12 8 2 4 6 14 5 2 A B D C 3 2 2 3 MAX MIN MAX 56 極大極小值 (4) ? 圖中 MAX先行，有 3個后繼 MIN節(jié)點，此時 MAX的取值必須看 MIN如何取值 ? 每個 MIN節(jié)點亦有 3個后繼 MAX節(jié)點，假設其取值已知 ? 因為 MIN節(jié)點只取其后繼節(jié)點中之最小者 (讓 MAX效用最小 )，故 B=3/C=2/D=2 ? MAX節(jié)點取 A/B/C中最大者，故 A=3 ? 最后根節(jié)點 A的極大極小函數(shù)值 =3—引向具有最高極大極小值的后繼 第 2章 搜索技術(shù) 57 極大極小值算法說明 ? 簡單的遞歸算法 —按照定義計算每個后繼節(jié)點的極大極小值 / 搜索是從目標到初始節(jié)點的反向推導 ? 算法對博弈樹實行了深度優(yōu)先搜索 ? 如果博弈樹的最大深度為 m，每個節(jié)點的合法招數(shù)為 b，則 ? 算法的時間復雜度是 O(bm) ? 每次生成全部后繼節(jié)點的空間復雜度是 O(bm) ? 每次只生成一個后繼節(jié)點的空間復雜度是 O(m) 第 2章 搜索技術(shù) 58 極大極小值算法 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ù) 59 ??剪枝 ? 極大極小值搜索的問題是狀態(tài)數(shù)隨著棋局步數(shù)的數(shù)量而指數(shù)級增長 — 不幸的是沒有辦法消除這種指數(shù)級增長，所幸的是可以有效將其減半 — 剪枝技術(shù) ? 應用于極大極小值搜索樹中 — ??剪枝 ? 剪掉那些不可能影響最后決策的分支，返回和極大極小值算法同樣的結(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ù) 60 博弈樹的剪枝 (1) 第 2章 搜索技術(shù) 3 [∞, +∞] A B [∞,3] (a) [∞, +∞] 12 A B 3 [∞,3] (b) 61 博弈樹的剪枝 (2) 第 2章 搜索技術(shù) 12 A B [3, +∞] 3 8 [3,3] (c) 12 A B C [3, +∞] [∞,2] 3 8 2 [3,3] (d) 62 博弈樹的剪枝 (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 ) 63 ??剪枝算法 (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ù) 64 ??剪枝算法 (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ù) 65 ??剪枝算法 (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 第 2章 搜索技術(shù)