人工智能入門課件第4章 博弈與搜索VIP

作者朱福喜朱三元第4章

博弈與搜索

作者朱福喜朱三元博弈雖然自古就是人與人的對(duì)弈，但自從有了計(jì)算機(jī)以后，人們開始就有用計(jì)算機(jī)下棋的想法，早在60年代就已經(jīng)出現(xiàn)若干博弈程序，并達(dá)到較高的水平，現(xiàn)已出現(xiàn)計(jì)算機(jī)博弈程序能夠與人類博弈大師抗衡的局面。舉世瞻目的人機(jī)對(duì)弈是1997年IBM公司編制的深藍(lán)（deepblue）計(jì)算機(jī)與國際象棋大師卡斯帕羅夫?qū)?，取得了三勝二和一?fù)的好成績。博弈的研究不斷為人工智能提出新的課題，可以說博弈是人工智能研究的起源和動(dòng)力之一。圖4.1許峰雄博士代表IBM與國際象棋冠軍卡斯帕羅夫?qū)?.1概述

博弈一向被認(rèn)為是富有挑戰(zhàn)性的智力的游戲，有著難以言語的魅力。博弈問題常與對(duì)策問題聯(lián)系在一起。對(duì)策論（GameTheory）用數(shù)字方法研究對(duì)策問題。一般將對(duì)策問題分為零和對(duì)策和非零和對(duì)策。最典型的零和對(duì)策問題是我國古代齊王與田忌賽馬的問題。該問題是齊王與田忌都有可分為上、中、下三匹馬。齊王的上馬、中馬、下馬都比田忌相應(yīng)的上馬、中馬、下馬好，但田忌的上馬比齊王的中馬好，田忌的中馬比齊王的下馬好，聰明的田忌采取了下述對(duì)策后一舉取勝：

作者朱福喜朱三元非零和對(duì)策的例子有：囚犯難題（Theprisonerdilemma）。該問題是有兩個(gè)嫌疑犯A和B，暫時(shí)還沒有獲得他們犯罪的確定的證據(jù)?，F(xiàn)對(duì)他們判刑的規(guī)則是：

作者朱福喜朱三元博弈問題對(duì)人的深層次的知識(shí)研究提出了嚴(yán)峻的挑戰(zhàn)。如何表示博弈問題的狀態(tài)，博弈過程和博弈取勝的知識(shí)，這是目前人類仍在探討之中的問題。要提高博弈問題求解程序的效率，應(yīng)作到如下兩點(diǎn)：改進(jìn)生成過程，使之只生成好的走步，如按棋譜的方法生成下一步；改進(jìn)測試過程，使最好的步驟能夠及時(shí)被確認(rèn)。

作者朱福喜朱三元

要達(dá)到上述目的有效途徑是使用啟發(fā)式方法引導(dǎo)搜索過程，使其只生成可能贏的走步。而這樣的博弈程序應(yīng)具備：一個(gè)好的（即只產(chǎn)生可能贏棋步驟的）生成過程。一個(gè)好的靜態(tài)估計(jì)函數(shù)。下面介紹博弈中兩種最基本的搜索方法。4.2極小極大搜索過程4.2.1極小極大搜索的思想極小極大搜索策略是考慮雙方對(duì)弈若干步之后，從可能的步中選一步相對(duì)好的走法來走，即在有限的搜索深度范圍內(nèi)進(jìn)行求解。為此要定義一個(gè)靜態(tài)估計(jì)函數(shù)f，以便對(duì)棋局的勢態(tài)作出優(yōu)劣估計(jì)。這個(gè)函數(shù)可根據(jù)棋局優(yōu)劣勢態(tài)的特征來定義。這里規(guī)定：

MAX代表程序方

MIN代表對(duì)手方

P代表一個(gè)棋局（即一個(gè)狀態(tài)）

f（P）的大小由棋局勢態(tài)的優(yōu)劣來決定:

有利于MAX的勢態(tài)，f（P）取正值有利于MIN的勢態(tài)，f（P）取負(fù)值勢態(tài)均衡，f（P）取零使用靜態(tài)函數(shù)進(jìn)行估計(jì)必須以下述兩個(gè)條件為前提：（１）雙方都知道各自走到什么程度、下一步可能做什么。（２）不考慮偶然因數(shù)影響。在這個(gè)前提下，博弈雙方必須考慮：（１）如何產(chǎn)生一個(gè)最好的走步。（２）如何改進(jìn)測試方法，能盡快搜索到最好的走步。MINMAX的基本思想是：（１）當(dāng)輪到MIN走步的結(jié)點(diǎn)時(shí)，MAX應(yīng)考慮最壞的情況（因此，f(p)取極小值）。（２）當(dāng)輪到MAX走步的結(jié)點(diǎn)時(shí)，MAX應(yīng)考慮最好的情況（因此，f(p)取極大值）。（３）當(dāng)評(píng)價(jià)往回倒推時(shí)，相應(yīng)于兩位棋手的對(duì)抗策略，不同層上交替的使用（１）、（２）兩種方法向上傳遞倒推值。4.2.2極小極大搜索算法極小極大過程的算法如下：1.T:=(s,MAX),OPEN:=(s),CLOSED:=();{開始時(shí)樹由初始結(jié)點(diǎn)構(gòu)成，OPEN表只含有s.}2.LOOP1:IFOPEN=()THENGOLOOP2;3.ｎ:＝FIRST(OPEN),REMOVE(n,OPEN),ADD_TO_LAST(n,CLOSED);//約定加到尾部

作者朱福喜朱三元4.IFn可直接判定為贏、輸或平局

THENf(n):=∞∨-∞∨0,GOLOOP1ELSEEXPAND(n)→ni,ADD({ni},T)IFd({n})<kTHENADD_TO_LAST({ni},OPEN),GOLOOP1ELSE計(jì)算f(ni),GOLOOP1;{n達(dá)到深度k,計(jì)算各端結(jié)點(diǎn)f值}5.LOOP2:IFCLOSED=NILTHENGOLOOP3ELSEnp:=LAST(CLOSED);

作者朱福喜朱三元6.IF(np∈MAX)∧(f(nc∈iMIN)有值）（其中nci為np的下一層節(jié)點(diǎn)）

THENf(np):=MAX{f(nci)},REMOVE(np,CLOSED);{若MAX所有子節(jié)點(diǎn)均有值，則該MAX取其極大值。}IF(np∈MIN)∧(f(nci∈MAX)有值）

THENf(np):=MIN{f(nci)},REMOVE(np,CLOSED);{若MIN所有子節(jié)點(diǎn)均有值，則該MIN取其極小值。}

作者朱福喜朱三元7.GOLOOP2;8.LOOP3:IFf(s)=NILTHENEXIT(END∨Mark(Move,T));{s有值，或結(jié)束或標(biāo)記走步}其中ADD_TO_LAST約定加入節(jié)點(diǎn)到表的尾部，END表示失敗或成功或平局退出，MARK標(biāo)記一個(gè)走步。4.2.3算法分析與舉例

該算法分三個(gè)階段進(jìn)行。第一階段為步驟2－4，使用寬度優(yōu)先法生成規(guī)定深度的全部博弈樹，然后對(duì)其所有端節(jié)點(diǎn)計(jì)算其靜態(tài)估計(jì)函數(shù)值。第二階段為步驟5－7是從底向上逐級(jí)求非終結(jié)點(diǎn)的倒推估計(jì)值，直到求出初始節(jié)點(diǎn)的倒推值f(s)為止。f(s)的值應(yīng)為maxmin….{f(ni1i2i3…ik)}，其中nik表示深度為k的端節(jié)點(diǎn)。第三階段，根據(jù)f(s)可選的相對(duì)好的走步，由Mark(Move,T)標(biāo)記走步。例4.1在九宮格棋盤上兩位選手輪流在棋盤上擺各自的棋子，每次一枚，誰先取得三子一線的結(jié)果就取勝。設(shè)程序方MAX的棋子用X表示對(duì)手方MIN的棋子用O表示.

作者朱福喜朱三元靜態(tài)估計(jì)函數(shù)為:+∞

當(dāng)p為MAX贏f(p)=-∞

當(dāng)p為MIN贏全部空格放X后三字成一線的總數(shù)）

-（全部空格放O后三字成一線的總數(shù)）例如，P的格局為：

則可得f(p)=5–6=-1?，F(xiàn)在考慮走兩步的搜索過程，即算法中K=2。利用棋盤對(duì)稱性條件，則MAX走第一步棋調(diào)用算法產(chǎn)生搜索樹如圖所示。

作者朱福喜朱三元

作者朱福喜朱三元

作者朱福喜朱三元

作者朱福喜朱三元4.3α-β剪枝算法

作者朱福喜朱三元

這時(shí)其中一個(gè)MIN節(jié)點(diǎn)要生成A,B,C,D四個(gè)節(jié)點(diǎn)，然后逐個(gè)計(jì)算其靜態(tài)估計(jì)值，最后求得倒推值-∞，把它賦給這個(gè)結(jié)點(diǎn)。其實(shí)生成節(jié)點(diǎn)A后，如果馬上進(jìn)行靜態(tài)估計(jì)，得知F(A)=-∞之后，就可以斷定生成B,C,D以及進(jìn)行估計(jì)是多余的，該MIN節(jié)點(diǎn)的倒推值一定是-∞。

作者朱福喜朱三元α-β剪枝法就是把生成后繼和倒推值估計(jì)結(jié)合起來，及時(shí)剪掉一些無用分枝，以此來提高算法的效率。α-β剪枝法，采用有界深度優(yōu)先策略進(jìn)行搜索，當(dāng)生成節(jié)點(diǎn)達(dá)到規(guī)定的深度時(shí)，就立即進(jìn)行靜態(tài)估計(jì)，而一旦某個(gè)非端節(jié)點(diǎn)有條件確定倒推值時(shí)，就立即賦值。當(dāng)生成到節(jié)點(diǎn)6后，節(jié)點(diǎn)1的倒推值可確定為-1。這時(shí)對(duì)于初始節(jié)點(diǎn)S來說，雖然其他子節(jié)點(diǎn)尚未生成，但由于S屬于極大層，所以可以推斷它的倒推值不會(huì)小于-1。我們定義極大層的這個(gè)下界值為α。因此S的α=-1。

S的α值為-1，說明的S倒推值不會(huì)比-1更小，但會(huì)不會(huì)比-1更大，還取決于其他后繼節(jié)點(diǎn)倒推值。我們繼續(xù)生成搜索樹。當(dāng)?shù)?個(gè)節(jié)點(diǎn)生成后，其估計(jì)值為-1，就可以斷定節(jié)點(diǎn)7的倒推值不可能大于-1。定義極小層的這個(gè)上界值為β。因此現(xiàn)在可以確定節(jié)點(diǎn)7的β=-1。有了極小層的β值，容易發(fā)現(xiàn)α≥β時(shí)，節(jié)點(diǎn)7的其他子節(jié)點(diǎn)不必生成，因?yàn)镾的極大值不可能比這個(gè)β值小，再生成無疑是多余的，因此可以進(jìn)行剪枝。只要在搜索過程中記住倒推值的上下界并進(jìn)行比較，當(dāng)α≥β時(shí)就可以實(shí)現(xiàn)修剪操作。α,β值還可以隨時(shí)修正，但極大層的α倒推值下界永不下降，因?yàn)閷?shí)際的倒推值取后繼節(jié)點(diǎn)最終確定的倒推值中的最大者。同理，極小層的倒推值上界β永不上升，因?yàn)閷?shí)際倒推值取后繼節(jié)點(diǎn)最終確定的倒推值中的最小者。

作者朱福喜朱三元α-β過程的剪枝規(guī)則（1）α剪枝：若任一極小值層節(jié)點(diǎn)的β值小于或等于它任一先輩極大值層節(jié)點(diǎn)的α值，即α（先輩層）≥β（后繼層），則可中止該極小值層中這個(gè)節(jié)點(diǎn)以下的搜索。該節(jié)點(diǎn)最終的倒推值就確定為這個(gè)β值。（2）β剪枝：若任一極大值層節(jié)點(diǎn)的α值大于或等于它任一先輩極小值層節(jié)點(diǎn)的β值，即α（后繼層）≥β（先輩層），則可以中止該極大值層中這個(gè)節(jié)點(diǎn)以下的搜索。這個(gè)MAX節(jié)點(diǎn)的最終倒推值就確定為這個(gè)α值。演示

作者朱福喜朱三元4.4AlphaGo搜索策略為什么20年前AI就已經(jīng)打敗國際象棋的人類世界冠軍，而直到現(xiàn)在圍棋AI才取得成功呢？其一，圍棋棋盤是19

19，因此每一步可以選的合法走法遠(yuǎn)遠(yuǎn)大于象棋（圍棋的分支因數(shù)BranchingFactor是250，象棋只有35），也就是說圍棋搜索空間相對(duì)于國際象棋來說大得多。其二，圍棋的估值函數(shù)很難設(shè)計(jì)。象棋尚能用簡單的統(tǒng)計(jì)棋子個(gè)數(shù)和子力來推斷，圍棋棋局千變?nèi)f化，可能看似風(fēng)平浪靜其實(shí)暗藏殺機(jī)。這兩個(gè)主要原因?qū)е铝藝錋I長久以來一直很難有大的進(jìn)展。4.4.1圍棋博弈程序的發(fā)展直到2006年前后，發(fā)現(xiàn)了一種新的捜索策略，叫蒙特卡羅樹搜索(MCTS，MonteCarloTreeSearch)，它是一種最佳優(yōu)先搜索（Best-firstsearch）算法，更適合于分支因子很大的博弈樹搜索。前面提到，狀態(tài)空間搜索都要有評(píng)估函數(shù)指導(dǎo)搜索。蒙特卡羅樹搜索作為一種搜索策略，它的評(píng)估函數(shù)要可以達(dá)到判斷盤終勝負(fù)這個(gè)最低要求，這恰好彌補(bǔ)了圍棋程序在評(píng)估函數(shù)上的缺陷。蒙特卡羅樹搜索策略加圍棋專業(yè)知識(shí)的組合，經(jīng)過近10年的發(fā)展，仍然無法挑戰(zhàn)職業(yè)棋手，直到AlphaGo橫空出世。AlphaGo完整繼承了深藍(lán)時(shí)代沿襲下來的“暴力搜索”算法框架，在狀態(tài)空間搜索中使用的信息匯總策略也與傳統(tǒng)蒙特卡羅樹搜索完全一樣，而且在其選擇策略中也同樣使用大量手工編寫的人門級(jí)圍棋專業(yè)知識(shí)?！耙圾Q驚人”的AlphaGo，其實(shí)是從一個(gè)基本具備一流開源圍棋軟件水平的傳統(tǒng)蒙特卡羅樹搜索程序改造升級(jí)而來。4.4.1圍棋博弈程序的發(fā)展4.4.1圍棋博弈程序的發(fā)展圖4.8圍棋博弈程序的分類4.4.2AlphaGo博弈樹搜索算法的改進(jìn)

MCTS算法大致思想可類比MinMax算法：對(duì)于給定的當(dāng)前根節(jié)點(diǎn)（某一棋局），通過計(jì)算機(jī)模擬推演以當(dāng)前根節(jié)點(diǎn)出發(fā)的各種可能的走法，配合高效的“剪枝”算法來控制搜索空間大小，并用演算到最后一步的結(jié)果來反過來影響當(dāng)前節(jié)點(diǎn)下一步棋的選擇。

針對(duì)圍棋相對(duì)于傳統(tǒng)棋類AI的設(shè)計(jì)難點(diǎn)：1）可能的走法太多（即BranchingFactor較大）導(dǎo)致搜索空間非常大；2）沒有一個(gè)好的估值函數(shù)對(duì)進(jìn)行中的圍棋棋局計(jì)算一個(gè)靜態(tài)得分。4.4.2AlphaGo博弈樹搜索算法的改進(jìn)MCTS提出解決方案：搜索空間更大，采取比Alpha-beta剪枝更激進(jìn)的剪枝策略，只把有限的計(jì)算資源留給最最有希望的走法（即后面要討論的選擇（Selection）、擴(kuò)展（Expansion）步驟要做的事情）；對(duì)于中間棋局好壞很難估計(jì)，那就干脆模擬到最后分出勝負(fù)為止（即后面要討論的模擬Simulation）。4.4.2AlphaGo博弈樹搜索算法的改進(jìn)MCTS算法的基本思想和特點(diǎn)是：將可能出現(xiàn)的狀態(tài)轉(zhuǎn)移過程用狀態(tài)樹表示；從初始狀態(tài)開始重復(fù)抽樣，逐步擴(kuò)展樹中的節(jié)點(diǎn)；在某個(gè)狀態(tài)再次被訪問時(shí)，可以利用已有的結(jié)果，提高效率；在抽樣過程中可以隨時(shí)得到行為的評(píng)價(jià)。4.4.3MCTS算法的四個(gè)基本步驟MCTS算法是一個(gè)多輪迭代算法，每一輪迭代都會(huì)以此經(jīng)歷四個(gè)階段：選擇（Selection），擴(kuò)展（Expansion），模擬（Simulation）和回溯（BackPropagation）。圖4.9MCTS某一時(shí)刻搜索空間的情形4.4.3MCTS算法的四個(gè)基本步驟1)選擇（Selection）：從根節(jié)點(diǎn)出發(fā)，自上而下地選擇一個(gè)“最最需要展開”的子節(jié)點(diǎn)，比如圖4.9中選擇（Selection）步驟當(dāng)中，沿著粗線一路走到底的最下方的葉子節(jié)點(diǎn)。這個(gè)節(jié)點(diǎn)被選中，意味著當(dāng)前狀態(tài)下，系統(tǒng)認(rèn)為沿著這個(gè)節(jié)點(diǎn)的這條路徑，最有可能取勝。2)擴(kuò)展（Expansion）：對(duì)于上面被選中的節(jié)點(diǎn)，從它的子節(jié)點(diǎn)中挑選出一個(gè)最有希望的子節(jié)點(diǎn)，將它的子節(jié)點(diǎn)加入到博弈樹的結(jié)構(gòu)中，擴(kuò)展的策略主要是逐次擴(kuò)展的策略，該策略并非一次性將全部的字節(jié)點(diǎn)添加到樹結(jié)構(gòu)之中，而是設(shè)置一個(gè)窗口值，隨這遍歷次數(shù)的增加，逐次添加子節(jié)點(diǎn)到對(duì)應(yīng)博弈樹節(jié)點(diǎn)之下。4.4.3MCTS算法的四個(gè)基本步驟3)模擬（Simulation）：從剛剛擴(kuò)展的這個(gè)節(jié)點(diǎn)，繼續(xù)向下模擬(向下模擬也稱Rollout)，直到分出勝負(fù)。由于在這個(gè)階段搜索深度需要達(dá)到最終分出勝負(fù)為止，所以會(huì)采用更加簡單的搜索策略，以保證在合理時(shí)間內(nèi)能夠搜索到?jīng)Q勝節(jié)點(diǎn)。4)回溯（BackPropagation）：既然模擬（Simulation）階段已經(jīng)搜索到最終的決勝節(jié)點(diǎn)，那么根據(jù)這個(gè)模擬（Simulation）的最終勝負(fù)，反過來更新祖先節(jié)點(diǎn)所在路徑的估計(jì)值。具體來說，會(huì)更新這些節(jié)點(diǎn)所對(duì)應(yīng)的得分，保證在下一輪迭代的時(shí)候這些節(jié)點(diǎn)會(huì)有更大的幾率被選中。反之，如果模擬（Simulation）的最終結(jié)果是我方輸，那么相應(yīng)的節(jié)點(diǎn)都會(huì)受到懲罰，在下一輪迭代中會(huì)更小的幾率被選中。4.4.3MC