




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
作者朱福喜朱三元第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è)條件為前提:(1)雙方都知道各自走到什么程度、下一步可能做什么。(2)不考慮偶然因數(shù)影響。在這個(gè)前提下,博弈雙方必須考慮:(1)如何產(chǎn)生一個(gè)最好的走步。(2)如何改進(jìn)測試方法,能盡快搜索到最好的走步。MINMAX的基本思想是:(1)當(dāng)輪到MIN走步的結(jié)點(diǎn)時(shí),MAX應(yīng)考慮最壞的情況(因此,f(p)取極小值)。(2)當(dāng)輪到MAX走步的結(jié)點(diǎn)時(shí),MAX應(yīng)考慮最好的情況(因此,f(p)取極大值)。(3)當(dāng)評(píng)價(jià)往回倒推時(shí),相應(yīng)于兩位棋手的對(duì)抗策略,不同層上交替的使用(1)、(2)兩種方法向上傳遞倒推值。4.2.2極小極大搜索算法極小極大過程的算法如下:1.T:=(s,MAX),OPEN:=(s),CLOSED:=();{開始時(shí)樹由初始結(jié)點(diǎn)構(gòu)成,OPEN表只含有s.}2.LOOP1:IFOPEN=()THENGOLOOP2;3.n:=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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 西藏考安全員證考試試題及答案
- 土木質(zhì)量管理培訓(xùn)考試試題及答案
- 玉林小學(xué)期中考試試題及答案
- 新團(tuán)員入團(tuán)考試試題選擇題及答案
- 資產(chǎn)評(píng)估大學(xué)期末考試試題及答案
- 2025辦公室租賃合同范本正式版
- 珠海市網(wǎng)約車考試試題及答案
- 重慶教師面試題目及答案
- 2025如何制定租房合同
- 中職韓語教師面試題及答案
- 醫(yī)院實(shí)驗(yàn)室生物安全委員會(huì)文件
- 2025年上海市勞動(dòng)合同范本(年度版)
- 數(shù)據(jù)驅(qū)動(dòng)的工業(yè)設(shè)備故障預(yù)測與診斷-洞察闡釋
- 無責(zé)賠償協(xié)議書
- 國家開放大學(xué)2025年《創(chuàng)業(yè)基礎(chǔ)》形考任務(wù)3答案
- 廚師中級(jí)考試試題及答案
- 2025-2030年中國小肽總體行業(yè)深度調(diào)研及發(fā)展戰(zhàn)略研究報(bào)告
- 橋梁除銹施工方案
- 粒子加速器用30-4000 MHz級(jí)固態(tài)功率源系統(tǒng) 征求意見稿
- GB/T 6418.1-2025銅基釬料第1部分:實(shí)心釬料
- 軟件外包團(tuán)隊(duì)管理制度
評(píng)論
0/150
提交評(píng)論