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