對抗搜索
文章目錄
上文開篇我們說了為什么要學習一點算法：不求能上天飛黃騰達，但至少得知道將來干掉自己的是誰，不能走的不明不白，是不？
李開復曾經把基礎課程比擬為“內功”，把新的語言、技術、標準比擬為“外功”。 整天趕時髦的人最后只懂得招式，沒有功力，是不可能成為高手的。真正學懂計算機的人（不只是“編程匠”）都對數(shù)學有相當?shù)脑煸劊饶苡每茖W家的嚴謹思維來求證，也能用工程師的務實手段來解決問題——而這種思維和手段的最佳演繹就是“算法”。
對抗搜索是一類算法的算法的總稱，也是機器學習的一個分支。那我們?yōu)槭裁匆獙W習對抗搜索呢？實在點，學它對我們有什么用？能增收或撩妹不？你總得給我個理由是不！
為了回答這個問題，我們先看一下這張圖，也是AI的發(fā)展簡史：
從圖中可以看到，1997年Deep Blue世紀大戰(zhàn)和2016年AlphaGo擊敗李世石，其中的關鍵技術即是對抗搜索技術。在棋類游戲里AI已經超過了人類，另外，在我們數(shù)學部分第一講的概述中也提到了同樣的問題，AI在計算機視覺領域（如ImageNet的識別）等也是遠遠優(yōu)于人類的。**刺激不？危機不？**那怎么辦呢？
成年人別問那么多，直接干學就完了！
再舉一個棋類例子：設想你在玩井字棋：
井字棋是一種在3 * 3格子上進行的連珠游戲，和五子棋類似，分別代表O和X的兩個游戲者輪流在格子里留下標記（一般來說先手者為X），任意三個標記形成一條直線，則為獲勝。
正常情況下，你的目標是贏，除非...對方是個妹紙，如何輕松贏得棋局，學完這部分內容，你將贏棋把妹兩不誤！不說廢話了，開搞吧:joy:
老規(guī)矩，為了方便描述，我們先介紹幾個概念，有個先驗印象，對抗搜索涉及幾個常見概念：智能體、對抗搜索和博弈樹。
智能體
智能體（agents）：在信息技術尤其是人工智能和計算機領域，可以看作是能夠通過傳感器感知其環(huán)境，并借助于執(zhí)行器作用于該環(huán)境的任何事物。以人類為例，我們是通過人類自身的五個感官（傳感器）來感知環(huán)境的，然后我們對其進行思考，繼而使用我們的身體部位（執(zhí)行器）去執(zhí)行操作。類似地，機器智能體通過我們向其提供的傳感器來感知環(huán)境（可以是相機、麥克風、紅外探測器），然后進行一些計算（思考），繼而使用各種各樣的電機/執(zhí)行器來執(zhí)行操作。現(xiàn)在，你應該清楚在你周圍的世界充滿了各種智能體，如你的手機、真空清潔器、智能冰箱、恒溫器、相機，甚至你自己。
對抗搜索
對抗搜索也稱為博弈搜索，在人工智能領域可以定義為：有完整信息的、確定性的、輪流行動的、兩個游戲者的零和游戲（如象棋）。
游戲：意味著處理互動情況，互動意味著有玩家會參與進來（一個或多個）；
確定性的：表示在任何時間點上，玩家之間都有有限的互動；
輪流行動的：表示玩家按照一定順序進行游戲，輪流出招；
零和游戲：意味著游戲雙方有著相反的目標，換句話說：在游戲的任何終結狀態(tài)下，所有玩家獲得的總和等于零，有時這樣的游戲也被稱為嚴格競爭博弈；
關于零和，也可以這樣來理解：自己的幸福是建立在他人的痛苦之上的，二者的大小完全相等，因而雙方都想盡一切辦法以實現(xiàn)“損人利己”。零和博弈的結果是一方吃掉另一方，一方的所得正是另一方的所失，整個社會的利益并不會因此而增加一分。
例如下井字棋，一個游戲者贏了+1，則另一個一定輸了-1，總和等于零。
博弈樹
考慮兩個游戲者：MIN和MAX，MAX先行，然后兩人輪流出招，直到游戲結束。在游戲最后，給優(yōu)勝者積分，給失敗者罰分。
游戲可以形式地定義成含有下列組成部分的一類搜索問題：
初始狀態(tài)，包含棋盤局面和確定該哪個游戲者出招。
后繼狀態(tài)，返回(move,state)對（兩項分別為招數(shù)、狀態(tài)）的一個列表，其中每一對表示一個合法的招數(shù)和其結果狀態(tài)。
終止測試，測試判斷游戲是否結束，游戲結束的狀態(tài)稱為終止狀態(tài)。
效用（收益）函數(shù)，效用函數(shù)（又稱為目標函數(shù)或者收益函數(shù)），對終止狀態(tài)給出一個數(shù)值。在井字棋中，結果是贏、輸或平，分別賦予數(shù)值+1、-1或0。有些游戲有更多的可能結果，例如雙陸棋的收益范圍從-192到+192。
每方的初始狀態(tài)和合法招數(shù)定義了游戲的博弈樹。上圖給出了井字棋的部分博弈樹。在初始狀態(tài)，MIN有9個可能的走法。游戲交替執(zhí)行，MAX下X，MIN下O，直到我們到達了樹的葉節(jié)點對應的終止狀態(tài)，也就是說一方的三個棋子連成一條直線或者所有棋位都填滿了。葉節(jié)點上的數(shù)字指示了這個終止狀態(tài)對于MAX來說的效用值；值越高被認為對MAX越有利，而對MIN則越不利。所以MAX的任務是利用搜索樹（特別是終止狀態(tài)的效用值）來確定最佳的招數(shù)，即求解終止狀態(tài)為+1的招數(shù)。
上節(jié)提到的#字棋游戲，我們可以大概畫出它的博弈樹：
至于為什么需要這棵樹我相信你很容易想到，計算機最擅長什么？沒錯，就是機械式窮舉，試想一下，當你走了一步后，計算機準備執(zhí)行下一步，它就會考慮所有能走的情況，然后他會再窮舉你接下來的步驟然后再繼續(xù)加深...不過回過頭來想一下你就會發(fā)現(xiàn)這種方法更適用于一些棋盤比較小得如上面的#字棋，這樣計算機只需要很少的搜索深度，就能選擇最佳方案，因此一個設計優(yōu)秀的#字棋AI基本上你是贏不了的，除非你也有同他那樣的窮舉能力，那么輸贏就要取決于誰先走了。
有了這樣一棵博弈樹之后，有沒什么方法找到最優(yōu)解呢？我們介紹三種常見算法： 極小極大值算法、α-β剪枝、 蒙特卡羅樹搜索算法。
本節(jié)我們以例子形式展開介紹極小極大算法。
雖然就算是井字棋這樣的簡單游戲，但是想要畫出它的整個博弈樹對我們而言也太復雜了，所以我們將轉而討論一個更簡單的游戲：分硬幣游戲。
假設我們已經有一個評價每種決策的收益的估值函數(shù)。對于極大層節(jié)點，如果我們知道了它的每一步決策的收益值，那么它總是會選擇收益最大的那個決策，作為它的節(jié)點的收益值；反過來，對于極小層節(jié)點，它總是會選擇收益最小的（對我方收益最小，就是對方收益最大）那個決策。
游戲規(guī)則是：一堆硬幣，雙方輪流將它分成大小不能相等的兩堆，然后下一個人挑選任意一堆繼續(xù)分下去，雙方交替游戲，直到其中一個人無法繼續(xù)分下去，則對方獲得勝利。
假設我們剛開始有一堆7枚硬幣，輪到我方先分。我需要找到我當前應該怎么樣分這堆硬幣。或者說，需要找到當前能夠獲得最優(yōu)收益的決策，我們通過構造出一棵極大極小樹來做到。
首先，我們窮舉所有的可能的狀態(tài)。用矩形代表輪到我方做決策的極大層節(jié)點，用圓形代表輪到對方做決策的極小層節(jié)點，列舉出所有的狀態(tài)：
注意，到這里我們還沒有進行估值 ，因此這還不算是極大極小樹。下面我們來設計這個游戲的估值函數(shù)，很簡單，如果當前局面，我們已經贏了，那么收益為+1，如果我們輸?shù)袅?，那么收益?1，這個游戲沒有平局，所以只可能有這兩種收益值。
剛開始估值的時候，我們還位于根節(jié)點，我們對于整棵樹是一無所知的，就像下面這樣：
我們想要獲得根節(jié)點的估值，需要對根節(jié)點的子節(jié)點進行遍歷，首先對第一個子節(jié)點進行遍歷，發(fā)現(xiàn)還是不能判斷它的值，繼續(xù)遍歷（上節(jié)課提到的深度優(yōu)先）它的子節(jié)點，直到到達葉子節(jié)點：到了葉子節(jié)點，我們可以對它進行估值了，因為此時是極小層，需要對手進行決策，但是對手已經無法再繼續(xù)分下去了。所以，它的收益值為+1：這樣獲得了第一個葉子節(jié)點的估值，由于它的父節(jié)點只有唯一一個子節(jié)點，因此父節(jié)點的收益值也只能是+1，然后可以一直回溯上去，直到到達紅色的節(jié)點：此時，我們不能直接給紅色節(jié)點賦值了，因為它還有別的子節(jié)點，我們繼續(xù)遍歷它的子節(jié)點：遍歷到又一個葉子節(jié)點，發(fā)現(xiàn)它的收益是-1（我方失敗），再回溯回去：現(xiàn)在我們又回到了紅色節(jié)點，現(xiàn)在它的所有子節(jié)點的收益值都已經獲得了。注意，這個節(jié)點是一個**極大層節(jié)點**。我們說過，極大層節(jié)點總是會選擇收益最大的子節(jié)點，它的子節(jié)點一個是+1一個是-1，因此，它的值應該是最大的那個+1。我們繼續(xù)按照深度優(yōu)先的順序遍歷：到這里，當前紅色的節(jié)點是一個**極小層節(jié)點**，它總是選擇收益最小的決策，因此它的收益值是-1。 接下來，我們繼續(xù)按照這個思路進行遍歷，中間的過程我就省略了，最后的結果如下所示：
到這里，我們的極大極小樹已經構建完成了。
我們發(fā)現(xiàn)，當前的根節(jié)點的收益值居然是-1，也就是說，只要對方夠聰明，我們無論如何都無法取勝。
這就很絕望了，但是仔細想想，我們假設的前提是，對方是聰明絕頂，不犯錯誤的高手。
我們知道無論如何都會失敗，那可不可以賭對方會犯錯呢。
這樣一想，其實3種必敗的決策還是有一定的優(yōu)劣性的。比如，最右邊那個子節(jié)點，它的所有子樹跟子樹的子樹收益都是-1，也就是說，對方就算亂下，我們都必輸；而中間跟左邊那個子節(jié)點，如果對手下錯了，還有一一定幾率能夠通往+1的葉子節(jié)點的。因此，左邊兩個決策要比最右邊的決策要相對好那么一點兒。因此，在發(fā)現(xiàn)我們已經必敗的時候，依然能夠在決策中做一個取舍，選擇敗得不明顯的那種決策。
設想有兩個選手，橙色節(jié)點是MAX，藍色節(jié)點是MIN，每人輪流移動一步，MAX先開始：
第一步：MAX選手根據(jù)DFS深度優(yōu)先，生成整個博弈樹，根據(jù)效用函數(shù)UTILITY得到所有葉子節(jié)點值，如下圖，A是初始節(jié)點。
第二步：從葉子節(jié)點向上回溯，D節(jié)點是MAX節(jié)點，選擇最大值4，同理得到同一層節(jié)點的值。第三步：遞歸上一層，該層為MIN節(jié)點，選擇孩子節(jié)點的最小值，B節(jié)點為4，C節(jié)點為-3。第四步：再遞歸到上一層，是根節(jié)點A，選擇孩子節(jié)點最大值4。**因此對于MAX選手而言，最優(yōu)路徑為綠色路徑，取得最大值為4。**
擴展：復雜度分析
博弈樹中，分支因子（branching factor）是每個結點下的子結點數(shù)。如果各個結點分支因子不同，則可以計算平均分支因子。例如，在國際象棋中，如把一步合法走法算作一個“結點”，那么平均分支因子據(jù)信約為35。這表示棋手每一步走棋平均有大約35種合法走法，一盤棋一般每個游戲者走50步，那么搜索樹大約有35^100個節(jié)點。
如圖，b是分支因子數(shù)，d是游戲者走的步數(shù)之和。
上一小節(jié)我們介紹了極大極小樹，對于分硬幣這樣相對簡單的游戲，它還是能夠用得上的。但是呢，它必須得窮舉出所有的狀態(tài)。再從終結狀態(tài)開始，計算每個節(jié)點的估值，最后才能獲得當前最優(yōu)的決策。
極小極大值算法對博弈樹執(zhí)行了一個完整的深度優(yōu)先探索，問題是必須檢査的游戲狀態(tài)的數(shù)目隨著招數(shù)的數(shù)量指數(shù)級增長，比如即使是最簡單的“井”字棋，它的第一步有9種決策，然后對面有9*8=72種決策，…，最后一層的決策個數(shù)達到了 9! = 362880 種。如此簡單的游戲，在不做特殊處理的時候，都有幾十萬種決策（當然這個量級計算機還是能夠hold住的）。它的棋盤大小僅僅是3 X 3，五子棋是15 X 15，圍棋是19 X 19，想要窮舉出所有決策，幾乎是不可能的。
因此，我們不能夠像上一章那樣，每次都窮舉出所有的結果，再去慢慢找最優(yōu)決策。隨著樹的深度的增加，我們的節(jié)點個數(shù)是指數(shù)級上升的。這種情況下我們不得不搜索到一定程度，就停止繼續(xù)往下搜索。
當我們停下來以后，這個時候，由于我們游戲還沒有結束，我們如何判斷當前的結果的好壞？
我們需要設計一個評價函數(shù)（Evaluation function）對于當前局面進行評分。這個評價函數(shù)如何設計？主要是根據(jù)不同的游戲，還有人類的日常經驗來判斷。
我當時設計五子棋AI的時候，就人為的設計了一個評價當前局面的分數(shù)的函數(shù)。比如已經有5個子連成一線了，它就是最高分；如果有4個子連成一線，它就是次高分；還有雙3，…。這樣我們就能根據(jù)局面，獲得一個得分。當然，當對面調用這個評價函數(shù)的時候，獲得的分數(shù)前面要取一個負號。因為對手的最高分，就是我們的最低分。
有了評價函數(shù)，我們就可以隨時終止我們的搜索了。因為對于任何局面，我們都能夠給出一個收益得分 。我們可以限定我們的搜索的深度，隨時結束搜索。
但是我們的搜索空間仍然非常龐大。因為最開始的幾層，可做的決策是相當多的。
比如五子棋，第一步就有225種下法。而對手對應就有225224=50,400種決策；再往下一層，就有225224*223=11,239,200種。這才第三層，就已經快爆炸了。
一般五子棋的高手都能想到后面五六步，甚至十幾步。想要與之對抗，我們必須得想辦法減少我們的搜索數(shù)量，增加我們的搜索深度，這樣我們的AI才能看得更遠的未來，想得更多，這樣棋力才會變強。
在這里，我們借用剪枝技術消除搜索樹的很大一部分，應用到一棵標準的極小極大值樹上，它剪裁掉那些不可能影響最后決策的分支，仍然可以返回和極小極大值算法同樣的結果。
我們先來理解一下，怎么樣的搜索是沒有必要的，假設我們限定了搜索深度為3，我們從頭開始搜索，如下：
我們從根節(jié)點往下搜，直到第一個葉子節(jié)點：
此時，到達了第一個深度為3的節(jié)點，此時我們調用估值函數(shù)，假設我們獲得它的收益為3，現(xiàn)在我們回頭來看它的父節(jié)點：
由于，這個父親節(jié)點是MIN節(jié)點，我們知道，它總是會選擇子節(jié)點中最小值?，F(xiàn)在，子節(jié)點已經出現(xiàn)了一個值為3。
現(xiàn)在仔細想想，如果我們繼續(xù)獲得它的子節(jié)點的收益，為一個比3要大的值，假設為12好了。那么當前的父節(jié)點，必然不會選擇這個12，而會去選擇3。因此，這個父親節(jié)點的收益，無論如何，都不會超過3，那么它的取值范圍，我們可以認為是：（-∞，3]。也就是說，我們的子節(jié)點，其實更新了它的父節(jié)點的收益的一個上界值，如圖：
到這里，我們其實并沒有進行剪枝，只是找到了一個父節(jié)點的上界值（β值），我們還是得繼續(xù)搜索它的子節(jié)點：假如我們搜索到了12，我們依然試圖更新父節(jié)點的上界值（β值），但是因為比3要大，更新失敗了，繼續(xù)搜索下一個，直到搜索完所有的當然父節(jié)點的所有子節(jié)點：當它所有的子節(jié)點都被搜索完以后，我們其實可以知道當前節(jié)點的收益就是3了。這個時候我們可以修改它的下界為3，收益為3。
注意這個時候，其實跟之前的極大極小樹的搜索過程沒有區(qū)別，我們并沒有進行任何的剪枝。接下來繼續(xù)搜索：
我們確定了當前節(jié)點收益為3，再去看它的父節(jié)點，即根節(jié)點。根節(jié)點原本的收益值范圍是（-∞，+∞）。現(xiàn)在我們找到了一個子節(jié)點收益是3。
根節(jié)點是一個MAX節(jié)點，跟之前相反，子節(jié)點的收益值3，可以用來更新的是根節(jié)點的下界（α值）。至于為什么，可以類比一下之前的。我們現(xiàn)在已經有搜索到一個3，如果我們以后搜索到比3小的值，那么根節(jié)點在取最大值的時候，肯定會選擇更大的3，而不是其他值。因此最優(yōu)解的下界就是3，不會再更小了。
我們帶著根節(jié)點的取值區(qū)間[3, +∞)繼續(xù)往下搜索，把這個區(qū)間賦給下一個子節(jié)點：
往下繼續(xù)深度優(yōu)先遍歷，訪問它的第一個子節(jié)點。此時到達設定的深度3，我們調用評價函數(shù)，假設評價函數(shù)返回值為2：敲黑板，重點來了。
我們知道，當前子節(jié)點是一個收益為2的MAX節(jié)點。MAX節(jié)點可以更新父節(jié)點的上界。因此，父親節(jié)點的上界，被修改成了2。 這里就出現(xiàn)了一個矛盾的區(qū)間[3,2]，如下圖：
觀察當前的節(jié)點，它的收益值的取值區(qū)間是[3,2]。這明顯是不合理的，收益不可能下界是3，同時上界又是2。我們可以做出判斷，這個節(jié)點無論如何都不可能是最優(yōu)解。
由于這個區(qū)間已經產生了矛盾，我們可以直接給當前節(jié)點判死刑，跳過剩下所有的子節(jié)點了：
上面的操作叫做α-β剪枝！
可以這樣理解，收益值的可行區(qū)間一旦變成矛盾的，說明當前節(jié)點必然不會是獲得最優(yōu)的決策，那么我們可以直接跳過這個節(jié)點，不管它還有多少個子節(jié)點沒有被搜索。
Tips:?如果你覺得我上面一段很有道理，可以忽略這部分內容。
如果你是一個嚴謹?shù)膽岩烧撜?，心里不踏實，請繼續(xù)看下去下面的證明過程。
我們就來仔細分析討論一下，假如我們接著往下搜索會發(fā)生什么：
剩下的值無非就兩種情況，我們全都來討論一遍：
第一種，搜索到比2小的值，比如1：
那么它的父親節(jié)點是個MIN節(jié)點，會選擇比2更小的1，假設最后中間的節(jié)點收益就是這個1，再看根節(jié)點：由于根節(jié)點是MAX節(jié)點，因此，即使找到了收益更小的1，根節(jié)點并不會選擇它，而是選擇更大的值為3的左邊那個節(jié)點。
第二種情況，搜索到比2大的值，比如5：
它并不能代替2，所以中間節(jié)點的收益還是2。在根MAX節(jié)點做取舍的時候，依然還是會選擇更大的左邊的那個3的節(jié)點。
因此，我們可以放心地說，當發(fā)現(xiàn)收益值的區(qū)間產生矛盾的時候，我們當前的節(jié)點無論再怎么繼續(xù)搜索，也不可能出現(xiàn)最優(yōu)解了。這下可以放心跳過了。
證明完！
在這個例子里面，我們已經給中間那個點判了死刑，直接跳過它剩下的2個子節(jié)點，轉到了右邊那個節(jié)點。
老規(guī)矩，把父親節(jié)點的可行區(qū)間傳遞給當前子節(jié)點，繼續(xù)往下深度優(yōu)先遍歷：到了葉子節(jié)點，調用估值函數(shù)，假設這回返回的收益是14：由于14是MAX層，試圖更新父節(jié)點的上界。沒有產生矛盾區(qū)間，繼續(xù)往下搜。假設下一個搜索到的是1：更新上界，產生矛盾區(qū)間，停止繼續(xù)搜索。到這里我們遍歷了根節(jié)點的所有可能子節(jié)點，可以做出最終判斷，根節(jié)點的收益最終值為3，以及得到最優(yōu)的路徑：通過維護一個收益的可行區(qū)間，在搜索的過程中進行剪枝操作，就是所謂的α-β剪枝。
由于α-β剪枝剪掉的點，都是必然不可能是最優(yōu)解的節(jié)點，因此我們永遠不會錯過最優(yōu)解。同時，由于及時的剪枝操作，我們大大地減少了需要搜索的節(jié)點數(shù)量，節(jié)省下來的算力就能進行更多更深層次的搜索。
這就是傳說中的博弈樹跟α-β剪枝的原理了。
α-β剪枝可以用于樹的任何深度，而且很多情況下可以剪裁整個子樹，而不是僅剪裁葉節(jié)點。一般原則是：考慮在樹中某處的節(jié)點n，游戲者可以選擇移動到該節(jié)點。如果游戲者在n的父節(jié)點或者更上層的任何選擇點有一個更好的選擇m，那么在實際的游戲中就永遠不會到達n。所以一旦我們發(fā)現(xiàn)關于n的足夠信息（通過檢査它的某些后代），能夠得到上述結論，我們就可以剪裁它。
記住極小極大搜索是深度優(yōu)先的，所以任何時候我們不得不考慮樹中一條單一路徑上的節(jié)點。α-β剪枝的名稱就是從下面兩個描述這條路徑上任何地方的回傳值界限的參數(shù)得來的： α = 到目前為止我們在路徑上的任意選擇點發(fā)現(xiàn)的MAX的最佳（即極大值）選擇 β = 到目前為止我們在路徑上的任意選擇點發(fā)現(xiàn)的M1N的最佳（即極小值）選擇 α-β搜索不斷更新a和β的值，并且當某個節(jié)點的值分別比目前的MAX的α或者MIN的β值更差的時候剪裁這個節(jié)點剩下的分支（即終止遞歸調用）。
擴展：
完整算法
復雜度分析
下棋其實就是一個馬爾科夫決策過程（MDP），即根據(jù)當前的棋面狀態(tài)，確定下一步的該怎么走。
那么，該下哪一步才能確保后續(xù)贏棋的概率比較大呢？最容易想到的就是前述的一些方法：枚舉后續(xù)的每一種走法，然后計算每一步贏棋的概率，選擇概率最高的走，如下圖所示：
但是，對于圍棋而言，狀態(tài)空間實在是太大了，沒辦法枚舉：這種時候就是靠蒙特卡洛樹搜索了。它的方法也非常簡單，那就是“沒病走兩步”：* 在當前狀態(tài)的基礎上，選擇一個備選動作/狀態(tài)； * 從備選動作/狀態(tài)開始，“走兩步”，不需要枚舉后續(xù)所有狀態(tài)，只需要以一定的策略一直模擬到游戲結束為止； * 計算這次采樣的回報； * 重復幾次，將幾次回報平均，獲得該備選動作/狀態(tài)的價值。換個通俗點的說法，就是用**頻率估計概率**。只要采樣的樣本數(shù)越多，頻率越接近概率。
蒙特卡羅方法（Monte Carlo method）也稱統(tǒng)計模擬方法，是1940年代中期由于科學技術的發(fā)展和電子計算機的發(fā)明，而提出的一種以概率統(tǒng)計理論為指導的數(shù)值計算方法。是指使用隨機數(shù)（或更常見的偽隨機數(shù)）來解決很多計算問題的方法。
蒙特卡羅方法于20世紀40年代美國在第二次世界大戰(zhàn)中研制原子彈的“曼哈頓計劃”計劃的成員S.M.烏拉姆和J.馮·諾伊曼首先提出。數(shù)學家馮·諾伊曼用馳名世界的賭城–摩納哥的Monte Carlo來命名這種方法，為它蒙上了一層神秘色彩。在這之前，蒙特卡羅方法就已經存在。1777年，法國數(shù)學家布豐（Georges Louis Leclere de Buffon，1707—1788）提出用投針實驗的方法求圓周率π，這被認為是蒙特卡羅方法的起源。
當所求解問題是某種隨機事件出現(xiàn)的概率，或者是某個隨機變量的期望值時，通過某種“實驗”的方法，以這種事件出現(xiàn)的頻率估計這一隨機事件的概率，或者得到這個隨機變量的某些數(shù)字特征，并將其作為問題的解。
計算Pi
可以認為投針實驗，在正方形內，投入一定數(shù)量的針，計算落入圓內針的數(shù)量與總共數(shù)量比值，從而計算Pi。
蒙特卡羅求定積分
蒙特卡洛方法的一個重要應用就是求定積分。來看下面的一個例子
當我們在[a,b]之間隨機取一點x時，它對應的函數(shù)值就是f(x)。接下來我們就可以用f(x) * (b - a)來粗略估計曲線下方的面積，也就是我們需要求的積分值，當然這種估計（或近似）是非常粗略的。
如果博弈樹非常龐大，按照極小極大值算法和α-β剪枝，那么對抗搜索的時間效率是十分低下的。蒙特卡羅樹搜索算法就是優(yōu)化博弈樹搜索的算法。
下面先介紹UCB算法，這是MCTS的經典實現(xiàn)UCT（Upper Confidence bounds for Trees）里面用到的算法。公式如下：
其中v'表示當前樹節(jié)點，v表示父節(jié)點，Q表示這個樹節(jié)點的累計quality值，N表示這個樹節(jié)點的visit次數(shù)，C是一個常量參數(shù)（可以控制exploitation和exploration權重）。 這個公式的意思是，對每一個節(jié)點求一個值用于后面的選擇，這個值有兩部分組成，左邊是這個節(jié)點的平均收益值（越高表示這個節(jié)點期望收益好，越值得選擇，用于exploitation），右邊的變量是這個父節(jié)點的總訪問次數(shù)除以子節(jié)點的訪問次數(shù)（如果子節(jié)點訪問次數(shù)越少則值越大，越值得選擇，用戶exploration），因此使用這個公式是可以兼顧探索和利用的。
蒙特卡羅樹搜索(Monte Carlo Tree Search)是一種基于樹數(shù)據(jù)結構、能權衡探索與利用、在搜索空間巨大仍然比較有效的的搜索算法。主要包括Selection、Expansion、Simulation和Backpropagation四個階段。
1） Selection
在樹中找到一個最好的值得探索的節(jié)點，一般策略是先選擇未被探索的子節(jié)點，如果都探索過就選擇UCB值最大的子節(jié)點。
2） Expansion
在前面選中的子節(jié)點中走一步創(chuàng)建一個新的子節(jié)點，一般策略是隨機自行一個操作并且這個操作不能與前面的子節(jié)點重復。
3） Simulation
在前面新Expansion出來的節(jié)點開始模擬游戲，直到到達游戲結束狀態(tài)，這樣可以收到到這個expansion出來的節(jié)點的得分是多少。
4） Backpropagation
把前面expansion出來的節(jié)點得分反饋到前面所有父節(jié)點中，更新這些節(jié)點的quality value和visit times，方便后面計算UCB值。
通過不斷地模擬得到大部分節(jié)點的UCB值，然后下次模擬的時候根據(jù)UCB值有策略得選擇值得exploitation和exploration的節(jié)點繼續(xù)模擬，在搜索空間巨大并且計算能力有限的情況下，這種啟發(fā)式搜索能更集中地、更大概率找到一些更好的節(jié)點。
下面是論文的偽代碼實現(xiàn)：
其中TREE_POLICY就是實現(xiàn)了Selection和和Expansion兩個階段，DEFAULT_POLICY實現(xiàn)了Simulation階段，BACKUP實現(xiàn)了Backpropagation階段，基本思路和前面介紹的一樣。
簡單理解，蒙特卡羅樹搜索算法是一種模擬啟發(fā)算法，根據(jù)UCB算法選擇一個節(jié)點擴展，然后應用蒙特卡羅模擬方法計算葉子節(jié)點得分，向上傳播，循環(huán)往復。
在架構上，AlphaGo可以說是擁有兩個大腦，兩個神經網絡結構幾乎相同的兩個獨立網絡：策略網絡與評價網絡，這兩個網絡基本上是個13層的卷積神經網絡所構成，卷積核大小為5 * 5，所以基本上與存取固定長寬像素的圖像識別神經網絡一樣，只不過我們將矩陣的輸入值換成了棋盤上各個坐標點的落子狀況。
第一個大腦是策略網絡，基本上就是一個單純的監(jiān)督式學習，用來判斷對手最可能的落子位置。他的做法是大量的輸入這個世界上職業(yè)棋手的棋譜，用來預測對手最有可能的落子位置。在這個網絡中，完全不用去思考贏這件事，只需要能夠預測對手的落子即可。目前AlphaGo預測對手落子位置的正確率是57%（這是刊登在Nature文章時的數(shù)據(jù)，現(xiàn)在想必更高了）。那各位可能認為AlphaGo的弱點是否應該就在策略網絡，一方面是預測準確率不高，再者是如果下了之前他沒看過的棋局是不是就有機會可以贏過他?？上Р⒉皇?，因為AlphaGo的策略網絡有做了兩個層面增強。
第一個層面是利用了名為增強策略網絡（reinforced-learning (RL) policynetwork）的技術，他先使用部分樣本訓練出一個基礎版本的策略網絡，以及使用完整樣本建立出來的進階版策略網絡，然后讓兩個網絡對弈，后者進階版策略網絡等于是站在基礎版前的高手，因此可以讓基礎網絡可以快速的熟悉到高手可能落子的位置數(shù)據(jù)，進而又產生一個增強版，這個增強版又變成原有進階版的高手，以此循環(huán)修正，就可以不斷的提升對于對手（高手）落子的預測，RL網絡80%贏了基礎版本的策略網絡。
第二個層面則是現(xiàn)在的策略網絡不再需要在19 * 19的方格中找出最可能落子位置，改良過的策略網絡可以先通過卷積核排除掉一些區(qū)域不去進行計算，然后再根據(jù)剩余區(qū)域找出最可能位置，雖然這可能降低AlphaGo策略網絡的威力，但是這種機制卻能讓AlphaGo計算速度提升1000倍以上。也正因為AlphaGo一直是根據(jù)整體局勢來猜測對手的可能落子選擇，也因此人類耍的小心機像是刻意下幾步希望擾亂計算機的落子位置，其實都是沒有意義的。
第二個大腦是評價網絡。在評價網絡中則是關注在目前局勢的狀況下，每個落子位置的最后勝率（這也是我所謂的整體棋局），而非是短期的攻城略地。也就是說策略網絡是分類問題（對方會下在哪），評價網絡是評估問題（我下在這的勝率是多少）。評價網絡并不是一個精確解的評價機制，因為如果要算出精確解可能會耗費極大量的計算能力，因此它只是一個近似解的網絡，而且通過卷積神經網絡的方式來計算出卷積核范圍的平均勝率（這個做法的目的主要是要將評價函數(shù)平滑化，同時避免過度學習的問題），最終答案他會留到最后的蒙利卡羅搜索樹中解決。
當然，這里提到的勝率會跟向下預測的步數(shù)會有關，向下預測的步數(shù)越多，計算就越龐大，AlphaGo目前有能力自己判斷需要展開的預測步數(shù)。但是如何能確保過去的樣本能夠正確反映勝率，而且不受到對弈雙方實力的事前判斷（可能下在某處會贏不是因為下在這該贏，而是這個人比較厲害）。
因此，這個部分它們是通過兩臺AlphaGo對弈的方式來解決，因為兩臺AlphaGo的實力可以當作是相同的，那么最后的輸贏一定跟原來的兩人實力無關，而是跟下的位置有關。也因此評價網絡并不是通過這世界上已知的棋譜作為訓練，因為人類對奕會受到雙方實力的影響，通過兩臺對弈的方式，他在與歐洲棋王對弈時，所使用的訓練組樣本只有3000萬個棋譜，但是在與李世石比賽時卻已經增加到1億。由于人類對奕動則數(shù)小時，但是AlphaGo間對弈可能就一秒完成數(shù)局，這種方式可以快速地累積出正確的評價樣本。所以先前提到機器下圍棋最大困難點評價機制的部分就是這樣通過卷積神經網絡來解決掉。
選?。菏紫雀鶕?jù)目前的狀態(tài)，選擇幾種可能的對手落子模式。
展開：根據(jù)對手的落子，展開至我們勝率最大的落子模式（我們稱之為一階蒙地卡羅樹）。所以在AlphaGo的搜索樹中并不會真的展開所有組合。
評估：如何評估最佳行動（AlphaGo該下在哪？），一種方式是將行動后的棋局丟到評價網絡來評估勝率，第二種方式則是做更深度的蒙地卡羅樹（多預測幾階可能的結果）。這兩種方法所評估的結果可能截然不同，AlphaGo使用了混合系數(shù)（mixing coefficient）來將兩種評估結果整合，目前在Nature刊出的混合系數(shù)是50%-50%。
倒傳導：在決定我們最佳行動位置后，很快地根據(jù)這個位置向下通過策略網絡評估對手可能的下一步，以及對應的搜索評估。所以AlphaGo其實最恐怖的是，李世石在思考自己該下哪里的時候，不但AlphaGo可能早就猜出了他可能下的位置，而且正利用他在思考的時間繼續(xù)向下計算后面的棋路。
對抗搜索的適用范圍
有完整信息的、確定性的、輪流行動的、兩個游戲者的零和游戲，這時我們就可以用上對抗搜索算法。
對抗搜索的主要思想
對抗搜索的核心思想就是dfs遍歷一遍博弈樹。不難想到，如果博弈樹非常龐大，在不加優(yōu)化的情況下，對抗搜索的時間效率是十分低下的。因此，我們就需要對對抗搜索進行一定的優(yōu)化。
對抗搜索算法
極小極大值算法
α-β剪枝
蒙特卡羅樹搜索算法
本博客所有內容僅供學習，不為商用，如有侵權，請聯(lián)系博主謝謝。
[1] 斯圖爾特·羅素，人工智能：一種現(xiàn)代的方法（第3版）[M]，人民郵電出版社，2010
[2] Wu Fei，Adversarial Search–What To Do When Your “Solution” is Somebody Else’s Failure
[3] Wu Fei，Adversarial Search- Monte Carlo Tree Search selectively random sampling with simulations
[4] https://www.javatpoint.com/mini-max-algorithm-in-ai
[5] https://www.jiqizhixin.com/articles/monte-carlo-tree-search-beginners-guide
[6] http://jeffbradberry.com/posts/2015/09/intro-to-monte-carlo-tree-search/
[7] https://blog.csdn.net/chenxiaoran666/article/details/82809890
[8] https://blog.csdn.net/bitcarmanlee/article/details/82716641
[9] https://www.cnblogs.com/yifdu25/p/8303462.html
[10] https://www.cnblogs.com/neverguveip/p/9457226.html
