對抗搜尋算法
在本章中, 我們将對 包含兩個競争的決策者的對抗式決策 問題模組化, 并介紹數個用于為這樣的問題找出可行解的算法: 對抗搜尋算法
Mini-Max Search
, 并進一步地介紹它的剪枝優化版本:
Alpha-Beta Pruning
.
對抗搜尋問題
我們考慮 由兩個智能體 之間, 資訊透明且對等 的, 通過 競争 實作的 零和博弈 問題. 稱這樣的問題為 對抗搜尋問題.
這樣的決策問題有兩方參與者, 彼此為 你死我活 的競争關系, 一方得利必然導緻另一方失利, 且兩方所得到利益的總和永遠為 0 0 0. 此外, 資訊對于雙方而言都是透明對等的, 交戰雙方由此為依據作出合理決策, 目标為讓自身利益最大化, 進而赢得遊戲.
我們接下來會介紹兩種算法:
Mini-Max
(最小最大) 算法, 以及
Alpha-Beta
剪枝算法.
Mini-Max
Mini-Max
我們以标準的棋類遊戲 (圍棋, 奧賽羅棋, 象棋等) 說明該算法. 此算法的核心是, 假設對手始終理性最大化, 一定能在任何局面下作出對自身最優的決策. 是以通過定義某個對目前局勢的 “評價”, 算法所服務的 “我方” 目标即為, 在上述假設的基礎上, 盡可能地選擇讓對手最終所得最小化 的決策, 也就是 “在假設對手總會最小化我方得利的前提下 (Mini), 盡可能地選擇能讓自身利益最大化的決策 (Max)”.
這樣的決策過程同樣可以使用 決策樹 表示. 這樣的決策樹具備一系列共同特征:
- 圖中的節點代表棋局的某一狀态, 且基于執子方的不同而被分為兩類: 由我方執子的
Maximizing Node
Minimizing Node
- 圖中的邊代表在上一狀态下作出的某種決策. 邊所連接配接的兩個節點之間的關系是: 從上一節點, 通過執行邊所代表的決策, 狀态轉移為新的節點.
在不考慮計算機運算能力限制的前提下, 顯然基于目前棋局下, 所向下推演所得到的最終局勢反推, 才能夠得到真正意義上的最優解. 實際上, 為了讓算法能夠在可接受的時間内執行完畢, 我們會定義一個 遞歸最大深度, 限制程式所能夠向下查找的決策步數.
由于對抗決策問題 回合制 的特性, 算法每一次執行得到的結果隻是 相對最優的, 下一步的決策. 從最底層向上考慮, 對屬于某一層的節點的打分隻會有下列三種情況:
- 考慮的是底層節點, 由于不能再繼續向下檢索, 程式隻能直接傳回節點本身的打分值.
- 考慮的是位于中間層的
max
- 考慮的是位于中間層的
min
是以, 我們采用 遞歸調用 的方式實作自底向下上的最優解評分.
def miniMaxValidation(Node, Depth):
if Depth == 0:
return staticValue(Node)
else if Node.isMaximizing() == true:
compute miniMaxValidation(Daughter, Depth-1) for each daughter
return the MAXIMUM among all results
else
compute miniMaxValidation(Daughter, Depth-1) for each daughter
return the MINIMUM among all results
基于上述算法, 我們可以得到某個節點的評分, 該評分所表示的是遵循算法的假設時, 我們所能得到的最大利益. 是以, 為了選出 相對最優的, 下一步的決策, 我們還需要在
miniMaxValidation()
上再包裝一層函數進行對節點的選擇:
def miniMaxhelper(Node, Depth):
if Node.isMaximizingNode == true:
compute miniMaxValidation(Daughter, Depth-1) for each daughter
return THE MOVE WHICH LEADS TO A MAXIMUM VALIDATION
else:
compute miniMaxValidation(Daughter, Depth-1) for each daughter
return THE MOVE WHICH LEADS TO A MINIMUM VALIDATION
将
miniMax
評價函數和
miniMax
外層包裝函數結合, 我們就得到了完整的
MiniMax
算法實作.
顯然, 在決策樹有限的情況下,
MiniMax
算法是完備的. 基于 “對手絕對理性” 的假設,
MiniMax
算法也一定能給出假設下的最優結果.
我們記決策樹的最大深度為 d d d, 決策樹考慮範圍内節點上有效走法 (有效決策) 數量的最大值為 n n n, 則由于
MiniMax
算法本質上是單純的深度優先搜尋, 其時間複雜度為 O ( n d ) O(n^d) O(nd).
MiniMax
算法是一種簡單有效的對抗手段, 由于考慮到了決策中的最壞情況, 是以即使對手犯錯也能得到一個不錯的解, 若對手完全理性則能傳回最優結果. 但搜尋樹的規模嚴重影響算法的運作時間. 為了緩解這一問題, 就必須要對搜尋樹剪枝.
Alpha-Beta
Alpha-Beta
Alpha-Beta
算法本質上是對
MiniMax
算法的剪枝改進版本, 不同之處在于
Alpha-Beta
會維護 根結點基于已進行的搜尋結果所知的我方的理論最高收益 和 對方基于已進行的搜尋結果所知的對我方的理論最大傷害. 在遞歸計算每一個節點的評價時, 算法會将每一個節點的評價和已知最優解進行比較, 進而及時 丢棄 對 進一步更優化已知解無益 的決策分支, 也就是 剪枝.
通過對
miniMax
評價函數作下述修改, 我們就能完成對
Alpha-Beta
算法的實作:
def miniMaxValidationwABPruning(Node, Depth, alpha, beta):
if Depth == 0:
return staticValue(Node)
else if Node.isMaximizing() == true:
alpha = NEGATIVE.INFINITY
for each Daughter in Node.daughters():
alpha = max(alpha, miniMaxValidation(Daughter, Depth-1, alpha, beta))
if alpha >= beta:
break
return alpha
else
beta = POSITIVE.INFINITY
for each Daughter in Node.daughters():
beta = min(alpha, miniMaxValidation(Daughter, Depth-1, alpha, beta))
if alpha >= beta:
break
return beta
注意此處的記号. 對于每一個節點, 我們都使用
alpha
和
beta
值分别表示目前基于現有的搜尋結果已知的, 該節點能夠給予我方利益的 下界 和 上界. 通過對每一個子節點時相應地對它們進行修正, 我們就可以在遞歸中一直更新并維護這兩個作為剪枝依據的關鍵資料.
在
Maximum
節點下, 由于算法基于己方利益考量, 故此處做出的選擇不可能進一步惡化現有的理論最大利益, 是以
Maximum
節點能且隻能更新和維護表示下界的
alpha
值.
在
Minimum
節點下, 由于算法基于對方利益考量, 故此處做出的選擇不可能進一步放大我方現有的理論最大利益, 是以
Minimum
節點能且隻能更新和維護表示上界的
beta
值.
同樣的, 在任何情形下一個有價值的解中都不可能出現
alpha >= beta
的情況. 是以, 該情形若出現, 我們就可以終止搜尋, 執行剪枝.
得益于剪枝,
Alpha-Beta
算法 (一般) 能夠更快地給出假設下的最優解.
上面的解釋可能艱深晦澀, 難以了解. 我們下面來看一個例子, 希望能夠對各位有所啟發:
我們考慮課上的Slides提到的例子, 逐漸解釋
Alpha-Beta Pruning
是如何用于解決該題, 并且執行剪枝的:
Alpha-beta Pruning
執行的搜尋是 自頂向下遞歸, 深度優先 的. 首先可看出第 1 , 3 1, 3 1,3 層為
Minimizing Node
, 第 2 , 4 2, 4 2,4 層為
Maximizing Node
.
在圖中的 每個節點 上, 都會相應地維護 它們自己的 α , β \alpha, \beta α,β. 其中, α \alpha α 表示利益下界, 如果不從父節點繼承的話初始化為 − ∞ -\infty −∞, 而表示利益上界的 β \beta β 節點值若不從父節點繼承的話被初始化為 ∞ \infty ∞.
我們的搜尋從根節點 A A A 開始. 由于根節點是
Minimizing Node
, 它的目的是維護 β \beta β (取得該節點上判斷的 β \beta β 的最小值, 是以該節點的 β \beta β 需要被初始化為 ∞ \infty ∞. 又因為它沒有父節點, 是以對它來說, 有: α = − ∞ \alpha = -\infty α=−∞.
從根節點 A A A 向下周遊它的第一個子節點 B B B. 由于 B B B 是
Maximizing Node
, 它的目的是維護 α \alpha α (取得該節點上判斷的 α \alpha α 的最大值, 是以該節點的 α \alpha α 需要被初始化為 − ∞ -\infty −∞. 而該節點的 β \beta β 從父節點繼承, 是以對它來說, 有: β = ∞ \beta = \infty β=∞.
基于深度優先搜尋思想, 我們再周遊 B B B 的第一個子節點 D D D. 由于 D D D 是
Minimizing Node
, 它的目的是維護 β \beta β (取得該節點上判斷的 β \beta β 的最小值, 是以該節點的 β \beta β 需要被初始化為 ∞ \infty ∞, 而 α \alpha α 從 B B B 繼承, 值為 − ∞ -\infty −∞.
B B B 更新 β \beta β 的方式是: 基于深度優先思想周遊其子節點, 選取子節點評分裡最小的那一個作為 β \beta β 的值. 顯然我們第一個周遊到的子節點是 I I I. I I I 是
Maximizing Node
, 它的目的是維護 α \alpha α (取得該節點上判斷的 α \alpha α 的最大值, 是以該節點的 α \alpha α 需要被初始化為 − ∞ -\infty −∞. 而該節點的 β \beta β 從父節點繼承, 是以對它來說, 有: β = ∞ \beta = \infty β=∞. 由于自身評分為 0 0 0, 它自己的 α \alpha α 被更新為 0 0 0. 由于自身已經是葉子節點, 是以達到最高遞歸深度, 開始回溯.
在回溯時, 将 I I I 的 α \alpha α 的值作為該節點的評分. 由此可知在将 I I I 和 D D D 的 β \beta β 值比對時, 0 < ∞ 0 < \infty 0<∞, D D D 的 β \beta β 值暫時被更新為較小的 0 0 0. 回溯到 D D D 節點後繼續周遊另一分支 J J J, 由于 J J J 的評分為 1 1 1, 是以 D D D 的 β \beta β 值保持為 0 0 0.
至此 D D D 這一支子樹已經周遊完成, 繼續回溯到 B B B. 将 D D D 和 B B B 做比較, 由于 D D D 是
Minimizing Node
, 取它的 β \beta β 值作為它的評分. 是以可知 B B B 的 α \alpha α 值暫時被更新為 0 0 0.
繼續周遊另一分支 E E E, 不難看出在周遊完該分支後, B B B 的 α \alpha α 值被更新為 3 3 3.
此時再從 B B B 開始周遊 F F F. 由于此時 B B B 節點的 α = 2 , β = ∞ \alpha = 2, \beta = \infty α=2,β=∞, M M M 的評分為 1 1 1, 是以得出 F F F 有 α = 2 , β = 1 \alpha=2, \beta=1 α=2,β=1, 顯然違背了 α < β \alpha < \beta α<β 的條件. 是以分支 F F F 是一個非法分支, 需要從 M M M 處開始剪枝, 搜尋到此為止.
至此以 B B B 為根節點的子樹已經全部搜尋完畢, 下面需要将 B B B 的評分 2 2 2 (因為 α = 2 \alpha=2 α=2) 回傳到根節點 A A A 處用于更新根節點的 β \beta β 的值.
基于更新規則可知根節點的 β \beta β 被更新為 2 2 2. 然後, 我們帶着更新後的 β \beta β 周遊到 C C C, 此時 C C C 滿足 α = − ∞ , β = 2 \alpha=-\infty, \beta=2 α=−∞,β=2. 同樣地對 C C C 的子節點執行深度優先搜尋并使用同樣的方法判斷每個子節點的評分并回傳給父節點更新父節點的 α \alpha α 或 β \beta β 值, 在周遊完節點 H H H 後可得 C C C 此時滿足 α = 3 , β = 2 \alpha=3, \beta=2 α=3,β=2. 由于此時再度違背了 α < β \alpha < \beta α<β 的條件, 是以從此開始我們從節點 C C C 的第二棵子樹 H H H 處開始剪枝, 不再搜尋剩下的子樹.
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)