基于uct的圍棋引擎的研究與實現(xiàn)（computer go engine research based on uct）

1、<p><b>　　摘 要</b></p><p>　　棋類博弈是人工智能的重要研究主題之一。而在圍棋方面，由于圍棋的搜索空間太大、計算機(jī)難于處理模糊概念且難于設(shè)計學(xué)習(xí)算法，目前最優(yōu)秀的圍棋程序的水平還處于業(yè)余低段水平。計算機(jī)圍棋被認(rèn)為是在繼國際象棋之后人工智能領(lǐng)域中最困難的新挑戰(zhàn)之一。圍棋是檢驗人工智能發(fā)展水平的良好環(huán)境，如何提高圍棋程序的棋力是人工智能領(lǐng)域的一大難題。所以

2、計算機(jī)圍棋研究具有重要的理論意義和實用價值。</p><p>　　本論文將介紹如何基于UCT算法設(shè)計和實現(xiàn)圍棋引擎。第一部分介紹了計算機(jī)圍棋研究背景及意義、研究狀況和關(guān)鍵技術(shù)，包括Monte Carlo方法和UCT算法的理論。第二部分在圍棋引擎總體概述的基礎(chǔ)上說明其總體功能模塊，并對各個子功能模塊進(jìn)行描述，重點講解了交替下子的流程以及棋步產(chǎn)生模塊。第三部分闡明了基于UCT算法的圍棋引擎的設(shè)計，先設(shè)計圍棋引擎的總體

3、流程，再依次說明UCT算法流程、棋步合法性的判斷等模塊的具體設(shè)計流程。第四部分探討了基于UCT算法的圍棋引擎的實現(xiàn)，在分析圍棋引擎核心模塊UCT算法實現(xiàn)的基礎(chǔ)上，詳細(xì)說明了候選步的產(chǎn)生及管理機(jī)制，節(jié)點的UCT選擇，展開節(jié)點和棋局模擬，分析指出不同的因素和策略對計算機(jī)圍棋引擎的影響，其中棋局模擬的著手庫模式匹配和其它圍棋知識對加強(qiáng)程序棋力有至關(guān)重要的作用。最后對主要工作做了總結(jié)，提出進(jìn)一步的發(fā)展目標(biāo)。</p><p&g

4、t;　　基于上述內(nèi)容，實現(xiàn)了一個基于UCT算法的圍棋引擎Tao Go，支持GMP、GTP圍棋協(xié)議，SGF文件調(diào)試輸出和統(tǒng)計UCT模擬棋局的數(shù)據(jù)，目前能正常與圍棋客戶端進(jìn)行通信，實現(xiàn)人機(jī)和機(jī)機(jī)對弈。</p><p>　　關(guān)鍵詞：人工智能 計算機(jī)圍棋 UCT算法 模式匹配</p><p><b>　　目 錄</b></p><p>&l

5、t;b>　　1 緒論1</b></p><p>　　1.1 研究背景及意義1</p><p>　　1.2 研究狀況1</p><p>　　1.3 關(guān)鍵技術(shù)2</p><p>　　1.3.1 Monte Carlo方法2</p><p>　　1.3.2 UCT算法2</p>&

6、lt;p>　　2 基于UCT的圍棋引擎的概述5</p><p>　　2.1 圍棋引擎的總體概述5</p><p>　　2.2 圍棋引擎的總體功能模塊5</p><p>　　2.3 交替下子流程模塊7</p><p>　　2.4 棋步產(chǎn)生(UCT)模塊8</p><p>　　2.5 棋步合法性判斷模塊9

7、</p><p>　　2.6 算氣模塊9</p><p>　　2.7 更新棋盤(提子)模塊10</p><p>　　2.8 勝負(fù)計算模塊10</p><p>　　3 基于UCT的圍棋引擎的設(shè)計11</p><p>　　3.1 圍棋引擎總體流程設(shè)計11</p><p>　　3.2 UCT

8、算法具體流程設(shè)計12</p><p>　　3.3 棋步合法性判斷模塊設(shè)計14</p><p>　　3.4 算氣模塊設(shè)計16</p><p>　　3.5 更新棋盤(提子)模塊設(shè)計17</p><p>　　3.6 勝負(fù)計算模塊設(shè)計18</p><p>　　4 基于UCT的圍棋引擎的實現(xiàn)20</p>

9、<p>　　4.1 軟硬件開發(fā)環(huán)境20</p><p>　　4.2 圍棋引擎的數(shù)據(jù)結(jié)構(gòu)20</p><p>　　4.2.1 棋局?jǐn)?shù)據(jù)20</p><p>　　4.2.2 UCT Tree數(shù)據(jù)21</p><p>　　4.3 圍棋引擎的UCT算法實現(xiàn)21</p><p>　　4.3.1 UCT算法的

10、核心實現(xiàn)21</p><p>　　4.3.2 候選步的產(chǎn)生方式及管理機(jī)制23</p><p>　　4.3.3 選擇節(jié)點(UCT選擇)25</p><p>　　4.3.4 展開節(jié)點27</p><p>　　4.3.5 棋局模擬29</p><p>　　4.4 圍棋引擎運行效果36</p><

11、;p>　　4.4.1 圍棋協(xié)議對弈測試36</p><p>　　4.4.2 調(diào)試模式的SGF文件37</p><p>　　4.4.3 UCT模擬棋局?jǐn)?shù)據(jù)統(tǒng)計38</p><p>　　5 工作總結(jié)及未來展望39</p><p>　　5.1 工作總結(jié)39</p><p>　　5.2 未來展望39</

12、p><p><b>　　致謝40</b></p><p><b>　　參考文獻(xiàn)41</b></p><p><b>　　英文摘要43</b></p><p><b>　　1 緒論</b></p><p>　　1.1 研究背景及意義

13、</p><p>　　博弈是人工智能的重要研究主題，人工智能的發(fā)展在很大程度上得益于博弈研究的發(fā)展。1997年著名的深藍(lán)計算機(jī)戰(zhàn)勝國際象棋世界冠軍卡斯帕羅夫成為轟動一時的新聞事件[l]。可以說，作為博弈研究的主要內(nèi)容之一，棋類博弈得到了滿意的解決，唯一的例外的是圍棋，目前最優(yōu)秀的圍棋程序還處于業(yè)余低段水平。</p><p>　　圍棋是博弈的一種，屬雙人零和博弈[2]。它起源于3000多年前

14、的中國，充分體現(xiàn)了東方人的智慧，盛行于中日韓，逐漸在歐美流行。它比國際象棋復(fù)雜得多，正因為如此，很多人工智能學(xué)家、心理學(xué)家和數(shù)學(xué)家也投入到了計算機(jī)圍棋研究領(lǐng)域。計算機(jī)圍棋這個名稱來自于Computer Go的直譯，略顯生硬。簡單地說，計算機(jī)圍棋就是結(jié)合人工智能技術(shù)教計算機(jī)下圍棋，以達(dá)到與人類棋手相抗衡的目的。</p><p>　　由于圍棋的搜索空間太大、計算機(jī)難于處理模糊概念且難于設(shè)計學(xué)習(xí)算法，造成了計算機(jī)圍棋程

15、序的棋力難于提高。圍棋是檢驗人工智能發(fā)展水平的良好環(huán)境，如何提高圍棋程序的棋力是人工智能領(lǐng)域的一大難題。同時，開發(fā)出與人類棋手水平相當(dāng)?shù)膰宄绦蛞灿兄趯θ祟愓J(rèn)知能力的理解。所以計算機(jī)圍棋研究具有重要的理論意義和實用價值。</p><p><b>　　1.2 研究狀況</b></p><p>　　計算機(jī)圍棋自Zobrist在1970年設(shè)計出第一個可與人對弈的程序以來[

16、3]，至今已有約四十年的歷史。由于圍棋本身的特質(zhì)，使得計算機(jī)圍棋在繼西洋棋、象棋之后，成為人工智能中一個相當(dāng)引人注目的新挑戰(zhàn)。</p><p>　　然而計算機(jī)圍棋的難點之一，便在于缺乏良好的局面評估函數(shù)[4]，使其不能跟國際象棋一樣，運用設(shè)計良好的局面評估函數(shù)、搜尋樹以及優(yōu)秀的剪枝法，即可獲得不錯的棋力；計算機(jī)圍棋大多借鑒一些經(jīng)驗法則，以靜態(tài)的評估為主，而動態(tài)的搜尋則僅用于局部的、目標(biāo)明確的棋串攻殺，較少的全局搜

17、尋。因此，人類的經(jīng)驗如何應(yīng)運用于計算機(jī)圍棋，就成了設(shè)計的重點。</p><p>　　自2003年起，Bouzy試圖打破這種情況[5]。他運用蒙特卡羅(Monte Carlo)方法作為評估函數(shù)，并且試圖運用這一評估函數(shù)，作全局性的搜索，然而在棋力上始終沒有大的突破。直到2006年，同樣使用蒙特卡羅方法的程序Crazy Stone[6~7]，才在杜林舉行的第11屆計算機(jī)奧林匹克的九路圍棋項目中奪得金牌。雖然如此，Cr

18、azy Stone僅在19路圍棋項目中奪得第五名，仍未撼動以人類思維為主的圍棋程序GNU Go在19路圍棋的地位。</p><p>　　然而，隨著基于蒙特卡羅的UCT(Upper Confidence bounds applied to Trees) 搜索方法的出現(xiàn)，以UCT為基礎(chǔ)的圍棋程序MoGo[8~10]也逐漸在一些較非正式的比賽中嶄露頭角。2007年6月，第12屆計算機(jī)奧林匹克于阿姆斯特丹舉行，上屆冠軍G

19、NU Go、亞軍GO Intellect以及前文介紹過的Crazy Stone等程序均有參賽，MoGo在強(qiáng)敵環(huán)伺之下，以全勝戰(zhàn)績奪得了19路圍棋項目的金牌，Crazy Stone也拿到了第二名，GNU Go退居第三。這象征UCT的成功，也代表一個嶄新的局面的到來。</p><p><b>　　1.3 關(guān)鍵技術(shù)</b></p><p>　　1.3.1 Monte Car

20、lo方法</p><p>　　Monte Carlo[11~12]方法主要理論基礎(chǔ)是依據(jù)大數(shù)定理，在隨機(jī)取樣的情況下，可以獲得有誤差的評估值，取樣的數(shù)量越多，誤差將越小，評估值將越準(zhǔn)確。</p><p>　　將Monte Carlo方法應(yīng)用于圍棋[13]，其核心的思想是，在于通過統(tǒng)計許多模擬棋局的結(jié)果，進(jìn)行局面的優(yōu)劣判斷。亦即將蒙特卡羅方法作為局面評估函數(shù)，以決定著手的好壞。</p&

21、gt;<p>　　其中，所謂的模擬棋局，指的是對某一目標(biāo)盤面，由電腦隨機(jī)落子，直到終盤而可以判定勝負(fù)為止。在隨機(jī)落子時，除了基本的圍棋規(guī)則外，只有一個限制：不得自填眼位，這個限制是為了防止棋局無法結(jié)束而設(shè)定的。模擬棋局的結(jié)果，與目前常見的只判斷黑勝或白勝不同，而是會判斷輸贏的目數(shù)，在決定著手優(yōu)劣時，則是統(tǒng)計此著手下所有模擬棋局平均的輸贏目數(shù)來決定的。</p><p>　　1.3.2 UCT算法<

22、;/p><p>　　UCT又名UCB for Tree Search，是UCB(Upper Confidence Bound)在Tree Search上的應(yīng)用。而UCB本來是為了解決吃角子老虎機(jī)問題(Bandit Problem)而產(chǎn)生的。所謂的吃角子老虎機(jī)問題，簡述如下：目前有若干臺吃角子老虎機(jī)，每臺機(jī)器可以投錢并拉動操縱桿，此時會得到收益(reward)，投錢、拉桿、得到收益的過程，稱之為一個Play。每臺吃角子

23、老虎機(jī)有不同的收益率，倘若玩家想要在若干次的Play里獲得最大總收益，那么該怎么做？</p><p>　　一般來說，玩家會開始動手玩，并且依照目前積累的經(jīng)驗來決定下一次的Play要選擇哪一臺機(jī)器，這稱之為開發(fā)(exploitation)。相對地，如果玩家不斷地依照目前所獲得的經(jīng)驗來決定，而不試圖嘗試其它的其他的機(jī)器，則可能會忽略收益率更高的機(jī)器，因此適度地嘗試其他機(jī)器是必須的，這稱之為探險(exploration

24、)。如何在開發(fā)與探險之間保持平衡，就是UCB試圖解決的ExE(exploitation vs. exploration)問題。</p><p>　　UCB根據(jù)目前獲得的信息，配合上一個調(diào)整值，試圖在開發(fā)與探險間保持平衡。大致上來說，每一次Play時，UCB會根據(jù)每一臺機(jī)器目前的平均收益值(亦即其到目前為止的表現(xiàn))，加上一個額外的參數(shù)，得出本次Play此臺機(jī)器的UCB值，然后根據(jù)此值，挑選出擁有最大UCB值的機(jī)器，

25、作為本次Play所要選擇的機(jī)器。其中，所謂額外參數(shù)，會隨每一臺機(jī)器被選擇的次數(shù)增加而相對減少，其目的在于讓選擇機(jī)器時，不過分拘泥于舊有的表現(xiàn)，而可以適度地探索其他機(jī)器。UCB公式表示如下(也稱為UCB1)[14]：</p><p>　　錯誤!未找到引用源。 (3)</p><p>　　錯誤!未找到引用源。是第j臺機(jī)器到目前為止的平均收益， 錯誤!未找到引用源。是第j臺機(jī)器被測試的次數(shù)，n是

26、所有機(jī)器目前被測試的總次數(shù)。讓公式(3)的值最大的機(jī)器將是下一個被選擇的機(jī)器。前項即為此臺機(jī)器的過去表現(xiàn)，后項則是調(diào)整參數(shù)。</p><p>　　而UCB1-TUNED是相對于UCB1實驗較佳的配置策略[14]。UCB1-TUNED的公式如下：</p><p>　　錯誤!未找到引用源。 (4)</p><p>　　錯誤!未找到引用源。 (5)</p

27、><p>　　讓公式(5)的值最大的機(jī)器將是下一個被告選擇來測試的機(jī)器。</p><p>　　UCT(UCB for Tree Search)其實就是把UCB1或UCB1-TUNED(統(tǒng)稱為UCB)等公式運用于Tree Search上的一個方法[14]。以概念而言，UCT把每一個節(jié)點都當(dāng)作是一個吃角子老虎機(jī)問題，而此節(jié)點的每一個分支，都是一臺吃角子老虎的機(jī)器。選擇分支，就會獲得相應(yīng)的收益。&l

28、t;/p><p>　　Tree Search開始時，UCT會建立一棵Tree，然后：</p><p><b>　　從根節(jié)點開始</b></p><p>　　利用UCB公式計算每個子節(jié)點的UCB值，選擇UCB值最高的子節(jié)點</p><p>　　若此子節(jié)點并非葉節(jié)點(從未拜訪過的節(jié)點)，則由此節(jié)點開始，重復(fù)(2)</p&g

29、t;<p>　　直到遇到葉節(jié)點，則計算葉節(jié)點的收益值，并依此更新根節(jié)點到此一節(jié)點路 徑上所有節(jié)點的收益值</p><p>　　由(1)開始重復(fù)，直到時間結(jié)束，或達(dá)到某一預(yù)設(shè)次數(shù)</p><p>　　由根節(jié)點的所有子節(jié)點中，選擇平均收益值最高者，作為最佳節(jié)點</p><p>　　此一節(jié)點，就是UCT的結(jié)果。</p><p&

30、gt;　　2 基于UCT的圍棋引擎的概述</p><p>　　2.1 圍棋引擎的總體概述</p><p>　　計算機(jī)圍棋程序通常也可稱為計算機(jī)圍棋引擎，具體表現(xiàn)為引擎本身沒有也不需要實現(xiàn)圖形圍棋界面(這通常是交由圍棋客戶端來做的)，而是通過特定的圍棋協(xié)議與引擎外部進(jìn)行通信，如圖2.1所示。這樣的好處是邏輯簡單，功能明確，只需要關(guān)注圍棋引擎的核心部分，即圍棋引擎是如何去思考的，并嘗試產(chǎn)生最優(yōu)

31、棋步。如果不去考慮圍棋引擎具體的思考過程，它表現(xiàn)出來的僅僅是它思考的最終結(jié)果，一個棋步而已。除此之外，圍棋引擎所做的工作就是實現(xiàn)對弈雙方交替落子的過程，同時根據(jù)棋規(guī)進(jìn)行相應(yīng)的更新棋盤處理，并在棋局結(jié)束時計算勝負(fù)。</p><p>　　事實上，圍棋引擎與圍棋客戶端的關(guān)系可以拿IDE和編譯器的關(guān)系來類比。在編譯源文件的時候，首先需要設(shè)置使用哪個編譯器和相應(yīng)的編譯參數(shù)，然后IDE會調(diào)用編譯器去編譯源文件，接著編譯器執(zhí)行

32、編譯過程，最后編譯器返回編譯結(jié)果給IDE，IDE則顯示編譯結(jié)果給用戶查看。而在圍棋對弈的時候，首先需要設(shè)置使用哪個圍棋引擎和圍棋協(xié)議參數(shù)，然后圍棋客戶端會通過圍棋協(xié)議告訴圍棋引擎為黑棋(或白棋)產(chǎn)生一個棋步，接著圍棋引擎進(jìn)行思考，最后圍棋引擎返回思考得到的棋步給圍棋客戶端，圍棋客戶端則在棋盤上顯示該棋步給圍棋用戶查看。</p><p>　　圖2.1 圍棋引擎與圍棋客戶端的通信</p><p&g

33、t;　　2.2 圍棋引擎的總體功能模塊</p><p>　　圍棋引擎Tao Go的總體功能模塊圖如圖2.2所示。其中交替下子流程功能模塊是圍棋引擎的總體流程。如何基于UCT產(chǎn)生棋步是圍棋引擎的核心功能模塊，在棋步產(chǎn)生(UCT)功能模塊下面的五個子功能模塊中除了候選步產(chǎn)生及管理子模塊是起輔助作用以外，其它四個子功能模塊實際上是一個有機(jī)聯(lián)系的整體，構(gòu)成圍棋引擎的UCT算法流程。棋步合法性判斷模塊是根據(jù)圍棋規(guī)則來判斷一

34、個棋步是否合法。更新棋盤(提子)模塊是檢查是否有吃子，有則提掉，并記錄可能的打劫位置。勝負(fù)計算模塊是在棋局結(jié)束時根據(jù)圍棋規(guī)則來計算勝負(fù)。算氣模塊是計算一個棋串的氣數(shù)。</p><p>　　圖2.2 圍棋引擎總體功能模塊</p><p>　　如圖2.3，是圍棋引擎各個模塊之間的關(guān)系?？梢钥吹?，圍棋引擎交替下子流程模塊對外負(fù)責(zé)與圍棋客戶端進(jìn)行通信，然后調(diào)用引擎內(nèi)部其它模塊進(jìn)行處理。例如圍棋客戶

35、端輸入了對手棋步，圍棋引擎交替下子流程模塊會調(diào)用棋步合法性判斷模塊對棋步進(jìn)行判斷，如果合法則更新棋盤，然后調(diào)用棋步產(chǎn)生(UCT)模塊產(chǎn)生棋步，最后輸出棋步返回給圍棋客戶端。圍棋引擎交替下子流程模塊在棋局開始時，還會進(jìn)行一些初始化工作，主要是商定圍棋規(guī)則，在棋局結(jié)束時則計算對弈雙方的勝負(fù)。棋步產(chǎn)生(UCT)模塊在產(chǎn)生棋步過程中會執(zhí)行多次模擬棋局，正式對局中所需要用到的功能模塊同樣會被調(diào)用，包括棋步合法性判斷模塊、更新棋盤(提子)模塊和勝負(fù)

36、計算模塊。 算氣模塊作為最基礎(chǔ)的模塊，為各個模塊提供依據(jù)，服務(wù)的上層的模塊包括棋步產(chǎn)生(UCT)模塊、棋步合法性判斷模塊和更新棋盤(提子)模塊。</p><p>　　圖2.3 圍棋引擎模塊間的關(guān)系</p><p>　　2.3 交替下子流程模塊</p><p>　　交替下子流程模塊展示了圍棋引擎的基本流程活動，如圖2.4是交替下子流程模塊的活動圖?；顒右婚_始是進(jìn)行初始

37、化引擎，主要是商定圍棋規(guī)則和初始化圍棋引擎內(nèi)部的一些參數(shù)和數(shù)據(jù)。然后進(jìn)入對弈雙方交替下子的過程，直到棋局結(jié)束。交替下子時，如果是對手下子，則從圍棋引擎外部得到對手棋步，否則輪到引擎下子，此時引擎的棋步產(chǎn)生模塊會產(chǎn)生合法棋步，然后輸出產(chǎn)生的棋步到圍棋引擎外部。每當(dāng)有下子的動作發(fā)生，則進(jìn)行更新棋盤，對棋局改變的狀態(tài)進(jìn)行相應(yīng)的處理。當(dāng)棋局結(jié)束時，根據(jù)圍棋規(guī)則計算雙方的勝負(fù)，如果對弈雙方對計算勝負(fù)的結(jié)果沒有爭議，棋局正式結(jié)束，否則繼續(xù)對弈。有一

38、點需要指出的是，在這里沒有明顯指出得到對手棋步是否要考慮該棋步的合法性。棋步的合法性通常圍棋引擎外部的圍棋客戶端也會判斷保證，不過在設(shè)計時應(yīng)該考慮加入對對手棋步的合法性判斷和相應(yīng)的錯誤處理，以保證邏輯的完整性，使得棋局能夠順利進(jìn)行。</p><p>　　圖2.4 交替下子流程的活動圖</p><p>　　2.4 棋步產(chǎn)生(UCT)模塊</p><p>　　棋步產(chǎn)生(

39、UCT)模塊使用UCT算法來產(chǎn)生棋步，是整個圍棋引擎的核心功能模塊。前面1.3.2小節(jié)已經(jīng)介紹了UCT算法的理論，下面來說明UCT算法究竟是如何應(yīng)用在圍棋上的。</p><p>　　UCT使用在圍棋上，主要的概念，就是每個節(jié)點代表一個盤面，此節(jié)點的分支代表此盤面下的合法著手，每個分支聯(lián)結(jié)到的子節(jié)點，就是原盤面加上分支代表的著手后，所產(chǎn)生的新盤面。一般而言，目前盤面為根節(jié)點，根節(jié)點的分支代表目前盤面下的合法著手，根

40、節(jié)點的子節(jié)點代表根節(jié)點的盤面加上分支代表的著手后所形成的新盤面，如圖2.5所示。</p><p>　　圖2.5 UCT Tree的概念表示，其中每個節(jié)點均記錄訪問次數(shù)，勝利次數(shù)，形成此節(jié)點的著手，著手顏色等信息</p><p>　　此外，UCB公式的收益值，如前1.3.1小節(jié)所述，就是依照Monte Carlo方法的概念，用模擬棋局的結(jié)果來決定。上面1.3.2小節(jié)中UCT 算法第4個步驟中

41、，計算機(jī)收益值，在此應(yīng)該改為執(zhí)行模擬棋局。所謂的模擬棋局，就是給定一個盤面(在此給的是葉節(jié)點所代表的盤面)，由計算機(jī)接手落子，直到終局，然后判定并回傳勝負(fù)結(jié)果(黑勝或白勝)。在此要注意的是，UCT會據(jù)此結(jié)果，更新葉節(jié)點到根節(jié)點上所有節(jié)點的收益值，也就是說，一個節(jié)點會概括承受所有子節(jié)點模擬棋局的結(jié)果。對于任一節(jié)點，其收益值為：此一節(jié)點的模擬棋局勝利數(shù)/此節(jié)點被訪問的次數(shù)，亦即其勝率。上式中所謂的勝利數(shù)，指的是指向此節(jié)點的分支所代表的顏色(

42、黑棋或白棋)在模擬時的勝利次數(shù)。</p><p>　　UCT Tree搜索流程總結(jié)如下：UCT算法使用極小極大游戲樹(minimax game tree)，搭配節(jié)點選擇公式(UCB公式)，選擇樹節(jié)點，展開要測試的節(jié)點，然后使用Monte Carlo方法執(zhí)行模擬棋局，最后將模擬棋局的結(jié)果回饋更新。流程示意圖如圖2.6所示。</p><p>　　圖2.6 UCT Tree搜索流程示意圖<

43、/p><p>　　2.5 棋步合法性判斷模塊</p><p>　　一個棋步是否合法，是根據(jù)圍棋規(guī)則來確定的，規(guī)則如下：</p><p>　　pass(也稱虛著)是合法的棋步，允許任何一方放棄下子權(quán)而使用虛著。黑白雙方輪流在空點上落子，即不能在非空棋點上落子。</p><p>　　禁著點。棋盤上的任何一點，如某方下子后，該子立即呈無氣狀態(tài)，同時又不

44、能提取對方的棋子。這個點叫做禁著點。</p><p>　　禁止全局同形。著子后不得使對方重復(fù)面臨曾出現(xiàn)過的局面。其中打劫是全局同形最基本的情況。</p><p><b>　　2.6 算氣模塊</b></p><p>　　當(dāng)任何一方落子后，除了虛著以外，都有可能把對方的棋子提掉，這個時候就要計算與所落子相鄰的所有對方棋串的氣數(shù)。事實上，在判斷棋步

45、的合法性時也往往需要計算雙方棋串的氣數(shù)。計算棋串的氣數(shù)主要采用標(biāo)記法，從棋串的某一個棋子開始，先標(biāo)記該棋子已訪問過，然后對于該棋子四個相鄰的棋點，如果相鄰棋點是空點，則棋串氣數(shù)加1；如果相鄰棋點上是對方的棋子，則無需對該方向上的相鄰棋點繼續(xù)進(jìn)行探索；如果相鄰棋點上是己方棋子，則對該相鄰棋點上的己方棋子進(jìn)行同樣的操作，直至計算完整個棋串的氣數(shù)。</p><p>　　2.7 更新棋盤(提子)模塊</p>

46、<p>　　更新棋盤時，主要是利用計算棋串氣數(shù)的功能檢查是否有提子， 有提子時將對方的棋串提掉，即清空對應(yīng)棋串位置，并記錄可能導(dǎo)致劫爭的位置。</p><p>　　2.8 勝負(fù)計算模塊</p><p>　　著子完畢的棋局，采用數(shù)子法計算勝負(fù)。將雙方死子清理出盤外后，對任意一方的活棋和活棋圍住的點以子為單位進(jìn)行計數(shù)。 雙方活棋之間的空點各得一半。 棋盤總點數(shù)的一半點為歸本數(shù)。一方

47、總得點數(shù)超過此數(shù)為勝，等于此數(shù)為和，小于此數(shù)為負(fù)。如果有貼子，則要按照相關(guān)的規(guī)定進(jìn)行計算。</p><p>　　3 基于UCT的圍棋引擎的設(shè)計</p><p>　　3.1 圍棋引擎總體流程設(shè)計</p><p>　　圖3.1 圍棋引擎總體流程</p><p>　　如圖3.1所示，圍棋引擎的總體流程實際就是模擬對弈雙方交替落子的過程。當(dāng)輪到對手落

48、子時，圍棋引擎通過圍棋協(xié)議從引擎外部得到對手的棋步。否則圍棋引擎使用UCT算法產(chǎn)生棋步，并通過圍棋協(xié)議輸出產(chǎn)生的棋步到引擎外部。不管是得到對手棋步之后或者是輸出產(chǎn)生棋步之前，都必須檢查棋步的合法性，如不合法則進(jìn)行相應(yīng)的出錯處理。如果檢查的棋步是合法的，接下來就根據(jù)圍棋規(guī)則做出正確的處理。如果合法棋步是pass時，則將pass數(shù)加1；否則將pass置為0。更新棋盤時，對于非pass合法棋步，則提取可能的死子并記錄可能的打劫位置，對于pas

49、s棋步則不做任何改變。最后，棋步數(shù)加1，然后回去判斷pass是否大于等于2，如果是說明雙方都pass，棋局結(jié)束，否則雙方繼續(xù)落子。</p><p>　　3.2 UCT算法具體流程設(shè)計</p><p>　　UCT算法的流程大致分為四個部分：</p><p>　　第一部分是選擇節(jié)點，在游戲樹中選擇子節(jié)點。</p><p>　　第二部分是展開節(jié)點，

50、產(chǎn)生新的子節(jié)點。</p><p>　　第三部分是棋局模擬，執(zhí)行模擬的棋局。</p><p>　　第四部分是回饋更新，將模擬棋局的結(jié)果以回溯方式更新游戲樹節(jié)點的信息。</p><p>　　在本論文中，將針對該流程前三部分進(jìn)行詳細(xì)說明。</p><p>　　圍棋引擎Tao Go使用的UCT流程如下，其示意圖如圖3.2所示。</p>

51、<p><b>　　選擇節(jié)點</b></p><p>　　若有未被訪問過的子節(jié)點，則優(yōu)先以隨機(jī)方式選擇其中一個子節(jié)點落子然后執(zhí)行模擬棋局(轉(zhuǎn)到(3))，否則繼續(xù)使用節(jié)點選擇公式UCB1或UCB1-TUNED選擇子節(jié)點。當(dāng)被選中的子節(jié)點為葉節(jié)點并且該子節(jié)點被訪問的次數(shù)未達(dá)到指定的次數(shù)時，則選擇該子節(jié)點落子然后執(zhí)行模擬棋局(轉(zhuǎn)到(3))。當(dāng)被選中的子節(jié)點為葉節(jié)點并且該子節(jié)點被訪問的次數(shù)

52、達(dá)到指定的次數(shù)，則需先展開該子節(jié)點(轉(zhuǎn)到(2))。否則重復(fù)此步驟直到找到被訪問的次數(shù)未達(dá)到指定的次數(shù)或未被訪問過的葉節(jié)點為止。</p><p><b>　　展開</b></p><p>　　當(dāng)節(jié)點為葉節(jié)點并且該節(jié)點被訪問的次數(shù)達(dá)到指定的次數(shù)時，進(jìn)行展開子結(jié)點。展開時對候選步作篩選，去除不適合的候選步，再將篩選后的候選步展開成子節(jié)點并隨機(jī)選擇其中一個節(jié)點(轉(zhuǎn)到(1))。

53、</p><p><b>　　棋局模擬</b></p><p>　　當(dāng)被選擇的葉節(jié)點落子后開始執(zhí)行模擬棋局，在模擬棋局中檢查是否有棋串少于四氣，若有則嘗試逃跑；如果有符合簡單的模式庫的棋形，執(zhí)行棋形庫模式匹配；如果沒有符合棋形的空點，則嘗試攻擊對方少于四氣的棋串；如果都沒有合適的棋步，最后使用隨機(jī)方式選擇合法棋步。</p><p><b&

54、gt;　　回饋更新</b></p><p>　　將模擬棋局的結(jié)果回溯更新游戲樹節(jié)點的信息。</p><p>　　圖3.2 Tao Go的UCT具體流程示意圖</p><p>　　在實際上執(zhí)行UCT Search時，其流程可以用圖3.3表示。</p><p>　　在圖3.3中，所謂GetBestSequence，指的是從根節(jié)點開始，

55、根據(jù)UCB公式向下搜索，直到找到被訪問次數(shù)不超過指定次數(shù)的葉節(jié)點為止的過程。當(dāng)搜索時，若被訪問的節(jié)點達(dá)到指定的次數(shù)，則會產(chǎn)生子節(jié)點，子節(jié)點的多寡，直接影響到搜索的深度與棋力的高低，因此對于產(chǎn)生出來的子節(jié)點，必須加以裁減。</p><p>　　第三個步驟是模擬棋局。所謂模擬棋局，就是由上一個步驟所找到的葉節(jié)點開始，由計算機(jī)接手下完，并回傳勝負(fù)結(jié)果，以更新UCT Tree。模擬棋局的核心就是其決定著手的方法。最簡單的

56、方法，就是純粹隨機(jī)落子（除了非法著手或自填眼位以外），這種方法的好處就是快速、簡單，且符合Monte Carlo的精神。但缺點則是用這種方法做出來的圍棋程序，棋力低落。要使棋力進(jìn)步的重點，在于棋局的手順要有意義，而不是隨機(jī)落子，天南地北地亂下。Tao Go建立了一個著手庫對常見棋形進(jìn)行模式匹配，如果沒有棋形可以匹配則對少于四氣的己方棋串進(jìn)行長氣或叫吃對方少于四氣的棋串，如果以上都不成功，則隨機(jī)落子[15-24]。</p>

57、<p>　　有了模擬棋局的結(jié)果，就要依此更新UCT Tree。所謂更新，指的是把從根節(jié)點到第二步驟中所找到的葉節(jié)點所形成的路徑上的所有點，依照模擬棋局的結(jié)果來更新勝場數(shù)和訪問次數(shù)，亦即若此點為黑，且模擬棋局之結(jié)果為黑勝，則此節(jié)點的勝利次數(shù)加一，反之亦然。訪問次數(shù)則是此路徑上的所有節(jié)點都加一。</p><p>　　若總模擬次數(shù)達(dá)到所設(shè)定的次數(shù)，或限制時間已用完，則結(jié)束UCT Search，并且挑出根節(jié)點下

58、被訪問次數(shù)最多的子節(jié)點，作為此次搜索的最佳著手。</p><p>　　圖3.3 UCT Search的流程圖</p><p>　　3.3 棋步合法性判斷模塊設(shè)計</p><p>　　棋步的合法性是根據(jù)圍棋規(guī)則來判斷，如圖3.4所示。分別檢查是否是虛著，是否在棋盤內(nèi)，是否是打劫以及是否是自殺(禁著點)。虛著，通常采用特殊的棋盤坐標(biāo)來表示，正常棋步跟特殊棋盤坐標(biāo)比較即可

59、知道知道是虛著。有時候產(chǎn)生的棋步的坐標(biāo)值是不合法的，此時棋步不在棋盤內(nèi)，跟正常棋盤坐標(biāo)范圍比較即可。而打劫可借助記錄可能造成打劫的位置，只要比較棋步的坐標(biāo)和造成打劫的位置即可。至于自殺棋步的判斷，如圖3.5所示。棋子自殺顧名思義是使得下子后棋子所在的棋串沒有氣數(shù)，但同時必須沒有殺死對方的任何棋串。先計算下子后棋子所在的棋串的氣數(shù)，如果棋串氣數(shù)不為0則說明肯定不是自殺棋步。如果棋串氣數(shù)為0，則需要考慮有沒有可能殺死對方棋子。可通過計算與該

60、棋串相鄰的對方棋串的氣數(shù)來判斷，如果沒有相鄰對方棋串氣數(shù)為0，即提取死子數(shù)為0，屬于自殺，是不合法棋步。如果有提取對方死子，此時也有可能是打劫，不過打劫的情況已經(jīng)在前面被排除了，說明盡管有提取死子，但肯定不是由于打劫造成的。這也是打劫要先進(jìn)行判斷的原因。</p><p>　　圖3.4 棋步合法性判斷流程圖</p><p>　　圖3.5 自殺棋步判斷</p><p>

61、　　3.4 算氣模塊設(shè)計</p><p>　　算氣模塊用來計算一個棋串的氣數(shù)。通常是已知棋串的某一個棋子，計算該棋串的氣數(shù)。使用如下步驟進(jìn)行計算：</p><p>　　將當(dāng)前棋子標(biāo)記為已訪問。</p><p>　　對當(dāng)前棋子的四個相鄰棋點進(jìn)行如下操作：</p><p>　　如果相鄰棋點是空點并且該空點未被訪問過，則氣數(shù)加一，然后將空點標(biāo)記為已

62、訪問。</p><p>　　如果相鄰棋點是己方棋子并且該己方棋子未被訪問過，則對相鄰的己方棋子按照(1)~(4)的步驟進(jìn)行同樣的操作。</p><p>　　當(dāng)對整個棋串所有的棋子進(jìn)行上述步驟的操作后，整個棋串的棋子和棋串相鄰的所有空點都會被標(biāo)記為已訪問，此時的氣數(shù)和即是要計算的棋串的氣數(shù)。算氣模塊四個相鄰棋點操作轉(zhuǎn)換的示意圖如圖3.6所示。</p><p>　　圖3

63、.6 算氣轉(zhuǎn)換示意圖</p><p>　　3.5 更新棋盤(提子)模塊設(shè)計</p><p>　　如圖3.7，是更新棋盤的具體流程。更新棋盤時，首先將產(chǎn)生的棋步下在棋盤上，將對應(yīng)的棋盤坐標(biāo)標(biāo)為棋步的顏色。然后計算相鄰的對方棋串的氣數(shù)和棋串的棋子個數(shù)。接著判斷計算出來的棋串的氣數(shù)是否為0并且棋串的棋子數(shù)為1，有可能出現(xiàn)會造成打劫的情況，所以需要判斷下子后周圍的棋形是不是會造成打劫的棋形，如果是

64、會造成打劫的棋形則記錄會造成打劫的位置。不管是否有會造成打劫的情況出現(xiàn)，只要有對方的棋串的氣數(shù)為0，則將對方的棋串的所有棋子的清空，即提掉對方死子，同時增加相應(yīng)的擔(dān)子數(shù)。最后，當(dāng)一方的棋步處理完畢后，則交換對方下子?？梢钥吹?，更新棋盤時總共有兩個功能，即是提取對方的死子和記錄打劫的位置，如果上述情況存在。</p><p>　　圖3.7 更新棋盤(提子)流程圖</p><p>　　3.6 勝

65、負(fù)計算模塊設(shè)計</p><p>　　計算勝負(fù)時，對棋盤上的每一個棋點，進(jìn)行如圖3.8的數(shù)子流程判斷。一個棋點，無非是被黑棋或白棋占據(jù)，要不然則為空點。當(dāng)被白棋占據(jù)時，白棋子數(shù)加一。當(dāng)被黑棋占據(jù)時，黑棋子數(shù)加一。而空點在棋局結(jié)束時，無非是被白棋或黑棋占據(jù)(雙活除外)，所以如果空點被白棋圍住，白棋子數(shù)加一，否則空點被黑棋圍住，黑棋子數(shù)加一。當(dāng)棋盤所有的棋點計算完畢后，白棋和黑棋的子數(shù)都已經(jīng)知道，只需比較雙方的子數(shù)即可

66、知道勝負(fù)結(jié)果。</p><p>　　圖3.8 數(shù)子流程圖</p><p>　　4 基于UCT的圍棋引擎的實現(xiàn)</p><p>　　4.1 軟硬件開發(fā)環(huán)境</p><p>　　硬件平臺：AMD Athlon(tm) 64 X2 Dual Core Processor 4000+, 1G內(nèi)存</p><p>　　軟件平臺：

67、Slackware Linux 13.0和Windows XP</p><p><b>　　開發(fā)語言：C語言</b></p><p>　　開發(fā)工具：采用(g)Vim-7.2+Makefile+gcc-4.3.3的方式，前期代碼的編寫和測試主要</p><p>　　是在Linux環(huán)境下完成，后期代碼移植通過MinGW-5.1.6編譯出可運行<

68、;/p><p>　　在Windows環(huán)境下的圍棋程序。</p><p>　　其它工具：cgoban-1.9.14和gogui-1.1.10分別支持GMP和GTP圍棋協(xié)議，用于測試圍棋引擎的協(xié)議接口，并提供良好的人機(jī)、機(jī)機(jī)對弈界面。另外，也可以使用引擎的控制臺字符界面進(jìn)行操作和測試。StoneBase 4.6.1.2147用來查看與編輯引擎調(diào)試輸出的SGF文件。</p><p

69、>　　4.2 圍棋引擎的數(shù)據(jù)結(jié)構(gòu)</p><p>　　在程序中主要有兩類數(shù)據(jù)結(jié)構(gòu)：一是與棋局相關(guān)數(shù)據(jù)，用于記錄棋盤信息和保證棋局的正常進(jìn)行；二是與UCT算法相關(guān)數(shù)據(jù)，里面保存了創(chuàng)建UCT Tree的節(jié)點信息及模擬棋局相關(guān)參數(shù)和數(shù)據(jù)。</p><p>　　4.2.1 棋局?jǐn)?shù)據(jù)</p><p>　　以下是正式棋局?jǐn)?shù)據(jù)的拷貝，因為進(jìn)行UCT模擬棋局時會改變相關(guān)棋局信

70、息，必須另外復(fù)制一份數(shù)據(jù)，以便于操作和防止錯誤修改原有的數(shù)據(jù)。棋局?jǐn)?shù)據(jù)包括了棋盤，棋盤大小，當(dāng)前下棋的顏色，貼目，劫爭位置等。這些數(shù)據(jù)有的可能在初始化后在棋局中沒有任何改變(如貼目)，有的可能會時刻變化(如當(dāng)前下棋的顏色)，全部進(jìn)行復(fù)制是為了保持一致性，即正式棋局的數(shù)據(jù)和模擬棋局的數(shù)據(jù)是一致的，只是在名稱上不同。</p><p>　　4.2.2 UCT Tree數(shù)據(jù)</p><p>　　這

71、里包含了UCB公式參數(shù)和UCT Tree結(jié)點的結(jié)構(gòu)，說明了結(jié)點代表的著手，勝利的次數(shù)，被訪問的次數(shù)，以及結(jié)點之間的關(guān)系。</p><p>　　4.3 圍棋引擎的UCT算法實現(xiàn)</p><p>　　4.3.1 UCT算法的核心實現(xiàn)</p><p>　　這一小節(jié)給出Tao Go的UCT算法的核心代碼，并對代碼中各個變量和函數(shù)的意義及作用進(jìn)行分析說明。</p>

72、<p>　　UCT算法流程實現(xiàn)主要在play_simulation函數(shù)，而uct_search是調(diào)用play_simulation函數(shù)來提供產(chǎn)生棋步著手的接口函數(shù)。</p><p>　　uct_search函數(shù)的功能是在進(jìn)行UCT搜索之前進(jìn)行初始化工作，包括創(chuàng)建和初始化根節(jié)點，首次展開節(jié)點。主體是進(jìn)行numsim次UCT搜索，并在調(diào)用play_simulation之前復(fù)制棋局信息。進(jìn)行完numsim

73、次UCT搜索后，從根節(jié)點下面找到最佳子節(jié)點并返回該節(jié)點代表的著手和釋放UCT樹。</p><p>　　在uct_search函數(shù)中變量numsim用于控制模擬次數(shù)，在其他條件不變的情況下，通常認(rèn)為模擬次數(shù)越多，程序能搜索的棋步越多越深，棋力也會越強(qiáng)。當(dāng)然也有賴于模擬質(zhì)量的好壞。</p><p>　　在uct_search函數(shù)中根節(jié)點初始化時子節(jié)點為空，被訪問次數(shù)為0，進(jìn)行模擬之前必須對其展

74、開子節(jié)點(create_children)，才能在play_simulation函數(shù)中選擇子節(jié)點。展開子節(jié)點時包含了對子節(jié)點裁減的判斷，控制搜索棋步的廣度。</p><p>　　在uct_search函數(shù)中copy_state函數(shù)的功能就是復(fù)制在4.2小節(jié)中提到的有關(guān)棋局?jǐn)?shù)據(jù)的信息，防止錯誤修改棋局信息，同時為下一次模擬恢復(fù)數(shù)據(jù)。</p><p>　　在uct_search函數(shù)中g(shù)et_b

75、est_child函數(shù)是獲得根節(jié)點下面被訪問次數(shù)最多的子節(jié)點，此節(jié)點代表的著手被認(rèn)為是UCT算法產(chǎn)生的最佳著手，也是圍棋引擎思考的結(jié)果，并最終被輸出到引擎外部。</p><p>　　play_simulation函數(shù)功能是實現(xiàn)了UCT算法的流程，表現(xiàn)為遞歸選擇子節(jié)點直到選中符合要求的葉節(jié)點(在必要時進(jìn)行展開節(jié)點)，然后進(jìn)行模擬棋局，最后將棋局勝負(fù)結(jié)果回饋更新。</p><p>　　在pla

76、y_simulation函數(shù)中變量num_visits控制節(jié)點被擴(kuò)展時的次數(shù)，能降低UCT Tree節(jié)點在內(nèi)存的增長速率，在相同模擬次數(shù)的情況下，增加對節(jié)點搜索模擬的次數(shù)，在一定程度上增加程序搜索的有效程度，負(fù)面影響是會減少棋步搜索的深度。</p><p>　　在play_simulation函數(shù)中play_random_game函數(shù)包含了模擬棋局的功能：棋形模式匹配、長氣逃子和吃子。uct_select函數(shù)中要

77、優(yōu)先選擇未被訪問過的子節(jié)點，這也是一個策略問題。關(guān)于play_random_game和uct_select函數(shù)的功能分別在4.3.5小節(jié)和4.3.4小節(jié)會有詳細(xì)說明。</p><p>　　至于make_move函數(shù)則是根據(jù)圍棋規(guī)則對落子進(jìn)行更新棋盤處理，關(guān)于基本圍棋規(guī)則會在討論play_random_grame函數(shù)模擬棋局功能時進(jìn)行介紹。而update_node函數(shù)是當(dāng)模擬棋局勝利時將勝率加1，被訪問次數(shù)不管勝利

78、與否都加1。注意update_node更新節(jié)點信息時，模擬棋局勝負(fù)的結(jié)果對于不同深度的節(jié)點是相反的。某一深度的節(jié)點的父節(jié)點和子節(jié)點代表對方著手的節(jié)點，如果模擬棋局結(jié)果對該節(jié)點來說是勝利著手，則模擬棋局對于對方而言就是失敗的，所以更新到該節(jié)點的父節(jié)點和子節(jié)點的勝負(fù)結(jié)果是相反的。實際上也就是說，UCT樹本質(zhì)是一棵極小極大(minimax)樹，對于己方有利的棋步對對方則是不利的，反之亦然。</p><p>　　4.3.

79、2 候選步的產(chǎn)生方式及管理機(jī)制</p><p>　　棋局一開始時，雖然棋盤上有八十一個空點，黑棋可以任意選擇其一，也就是說有八十一個候選步。如此一來，游戲樹的樹支將緩慢遞減，但是，并不時每個候選步都是合適的，根據(jù)圍棋知識，選擇如圖4.1中的二十五個候選步為棋局開始的候選步。</p><p>　　圖4.1 二十五個候選步</p><p>　　如果一開始只有十五個空戰(zhàn)成

80、為候選步，必須要在適當(dāng)時機(jī)，把其它空點也加入候選步中，否則，有些空點將就永遠(yuǎn)不會被選擇，而造成錯誤。因此，需要一個候選步的產(chǎn)生方式及管理機(jī)制。</p><p>　　由于每下一子(稱為著手)，就會讓周圍附近的空點成為下一步合適的候選步。因此，產(chǎn)生候選步的方式就是對于每一個空點，檢查其周圍是否有下子，看是否將其納入候選步。而檢查的方式是根據(jù)空點所在線，周圍棋子與空點之間的距離和已下棋子的步數(shù)來判斷的。其中兩個棋子的距

81、離是指兩個棋子橫坐標(biāo)差的絕對值和縱坐標(biāo)差的絕對值之和，即有P1(X1, Y1)和P2(X2, Y2)，則兩個棋子距離為</p><p>　　|P1P2| = |X1-X2| + |Y1-Y2|</p><p><b>　　一線空點</b></p><p>　　已下棋子的步數(shù)不超過預(yù)定的步數(shù)(如10)時，不考慮一線空點作為候選步。達(dá)到預(yù)定的步數(shù)后

82、，對于一線的空點，當(dāng)周圍有棋子在一線或二線上而且和該空點的距離小于3時，將該空點納入候選步。如圖4.2中，交叉點代表空點，其陰影部分代表如果這些地方有棋子，則說明該空點適合作為候選步。</p><p>　　圖4.2 一線空點候選步范圍</p><p><b>　　二線空點</b></p><p>　　已下棋子的步數(shù)不超過預(yù)定的步數(shù)(如5)時，不

83、考慮一線空點作為候選步。達(dá)到預(yù)定的步數(shù)后，對于二線的空點，當(dāng)周圍縱橫坐標(biāo)都不超過兩線所構(gòu)成的矩形范圍內(nèi)，如果有棋子距離該空點小于4時，即類似于中國象眼的位置不考慮，則將空點納入候選步。如圖4.3所示，用三角形標(biāo)記的地方即為象眼位置，不考慮該位置是否有棋子。</p><p>　　圖4.3 二線空點候選步范圍</p><p><b>　　三線及三線以上空點</b><

84、/p><p>　　三線及三線以上空點，考慮到九路棋盤的特殊性，無條件納入候選步。</p><p>　　由于圍棋棋盤上的空點數(shù)目是固定的，九路棋盤只有八十一個棋點，可以成為候選步的空點最多也只有八十一個，所有使用candidate_move數(shù)組來保存是適合的。根據(jù)“敵之要點即我之要點”的指導(dǎo)思想，這里不考慮空點是由于黑棋或白棋而納入候選步的，簡化了產(chǎn)生候選步操作，同時也避免錯失好點。當(dāng)然有時某些

85、空點并非是要點或好點，將其納入候選步，在展開子節(jié)點時不僅浪費了游戲樹內(nèi)存空間，而且增加了搜索空間，減少有效搜索次數(shù)，搜索到不好的著手的幾率也會增大。這就體現(xiàn)了計算機(jī)圍棋中不同的策略對圍棋程序的影響。</p><p>　　候選步的產(chǎn)生與管理是在每次落子時執(zhí)行，也就是在程序的流程中只要有下子的動作，不論是展開節(jié)點還是棋局模擬時隨機(jī)下子，都會使用候選步的產(chǎn)生與管理。</p><p>　　4.3.

86、3 選擇節(jié)點(UCT選擇)</p><p>　　上文中提到過的uct_select函數(shù)是從父節(jié)點中選擇uct值最大的節(jié)點進(jìn)行搜索，其中uct值的計算如下簡略代碼所示：</p><p>　　可變參數(shù)對uct值的影響</p><p>　　首先來關(guān)注子節(jié)點被訪問過的情況時，uct值的計算用以下公式計算：</p><p>　　uctvalue = w

87、inrate + UCTK * sqrt(log(parent->visits) / child->visits)</p><p>　　要注意到UCTK的值是可變的，不同的值對程序的影響也不同。在CGOS上運行許多實現(xiàn)了基礎(chǔ)UCT算法，使用不同參數(shù)值的圍棋機(jī)器人找到最優(yōu)參數(shù)值。它們使用如下方法</p><p>　　UCB1 = avgScore + c * sqrt(log(n

88、) / m)</p><p>　　其中上一行的公式和uct_select函數(shù)中的計算公式實際上等價的。要注意K和c都是在根號sqrt外面的。不同參數(shù)對圍棋機(jī)器人的影響如圖4.4所示。圖中Nick代表圍棋機(jī)器人的名稱。ELO代表等級分排行，Plts代表圍棋機(jī)器人的實力，10k表示10級。c為可變參數(shù)。</p><p>　　圖4.4 可變參數(shù)對圍棋機(jī)器人的影響</p><p

89、>　　FPU(First-play urgency)</p><p>　　當(dāng)子節(jié)點從未被訪問過時，使用下面的公式計算uct值：</p><p>　　uctvalue = 10000 + 1000 * rand(); (1)</p><p>　　子節(jié)點被創(chuàng)建時，其被訪問數(shù)和勝利數(shù)都為0。而更新節(jié)點信息時，即便模擬棋局返回勝利結(jié)果，勝利數(shù)僅加1，被訪問數(shù)加1。也

90、就是說當(dāng)節(jié)點被訪問的次數(shù)很少時，用公式</p><p>　　uctvalue = winrate + UCTK * sqrt(log(parent->visits) / child->visits)(2)</p><p>　　計算出來的uct值實際很小，遠(yuǎn)遠(yuǎn)小于用公式(1)計算出來的uct值，這就確保了能夠優(yōu)先隨機(jī)未被訪問過的子節(jié)點。用公式(1)計算出來的uct值，稱為FP

91、U[8]。</p><p>　　將FPU值賦給未被訪問過的節(jié)點。任意節(jié)點，至少被訪問過一次之后，它的uct值是根據(jù)公式(2)來計算。選擇最高uct值的節(jié)點來落子。因此FPU很大時能保證在開發(fā)已訪問過的子節(jié)點之前探索未被訪問過的節(jié)點一次。</p><p>　　如果總是至少訪問一次所有的子節(jié)點，有時這樣會導(dǎo)致搜索的低效，尤其是搜索的次數(shù)的次數(shù)相對于游戲樹的節(jié)點數(shù)目不大的時候。例如一個節(jié)點如果持

92、續(xù)返回勝利的結(jié)果，沒有好的理由需要去探索其它的節(jié)點。從另一方面來說，取較小的FPU值同樣可以使得不去搜索其它一些未被訪問過的節(jié)點。</p><p>　　4.3.4 展開節(jié)點</p><p>　　當(dāng)節(jié)點要展開時，并不是每個候選步都是合適的。如4.2.1小節(jié)提到的，九路棋局一開始雖然有八十一個空點可以選擇，但是依據(jù)圍棋知識，并非八十一個空點都是合適的。因此，對于候選步有篩選的必要。將不合理的候

93、選步予以去除，篩選的作用可以樹的分支，在相同的時間或相同的模擬棋局次數(shù)，可以增加搜索的深度。</p><p>　　每一個節(jié)點代表一個盤面，對于一個特定的盤面其候選步也是固定的。當(dāng)一個節(jié)點要展開產(chǎn)生子節(jié)點時，先對所有候選步進(jìn)行篩選，將篩選后的候選步分別記錄在子節(jié)點中，子節(jié)點之間以伙伴關(guān)系(鏈接形式)鏈接起來，將該節(jié)點的子節(jié)點指針指向鏈頭子關(guān)點。</p><p>　　棋局開始時，節(jié)點只有根節(jié)點

94、，盤面上有八十一個空點可供選擇，但是只有二十五個空點為合適的候選步(圖4.1)，此為第一步粗略的篩選。再更進(jìn)一步，由于對稱的點可以視為同一個，所以，僅六個候選步需要測試。如此一來，樹分支由原來的八十一縮減成六。</p><p>　　圖4.5 六個需要測試的候選步</p><p>　　同樣地，對于開局時，棋局可能會對稱，篩選候選步時還可以進(jìn)行簡單的篩選，直到發(fā)現(xiàn)棋局不對稱為止。例如圖4.6所

95、示，只需要考慮陰影部分即可。</p><p>　　圖4.6 對稱棋局候選步</p><p>　　對于任何樹節(jié)點，在展開子節(jié)點之前，都執(zhí)行候選步篩選，去除不合理的候選步，能減少樹分支，增加搜索深度，進(jìn)而提高搜索結(jié)果的準(zhǔn)確性。但是，篩選的進(jìn)行需要圍棋知識的輔助，而且，不當(dāng)?shù)暮Y選有可能把合適的甚至是最佳的候選步予以去除，造成無法挽救的錯誤。因此，對于候選步的篩選必須謹(jǐn)慎地進(jìn)行，不僅篩選的條件必須

96、嚴(yán)謹(jǐn)，更需要經(jīng)過測試驗證以確認(rèn)不會造成不必要的副作用。目前Tao Go中所使用的候選步篩選僅依據(jù)圍棋基本規(guī)則，將不合法及不適合的候選步予以去除。</p><p>　　目前歸納共有三種棋步，第一種如圖4.7的A1，A9等棋點對黑棋而言是自殺的著手，由于使用中國圍棋規(guī)則，因此自殺著手是禁著的一種。第二種是劫，如圖4.7的H1，由于上一步黑棋下G2吃掉H2，白棋不能下，這稱為打劫立即反提著手，也是禁著的一種，打劫立即反

97、提著手是圍棋規(guī)則中避免棋局無法結(jié)束的一項規(guī)定，如果沒有這項規(guī)定，黑白雙方將會因為互相吃掉對方的子而不斷地循環(huán)而讓棋局無法結(jié)束。第三種是真眼，如圖4.7中的A6，C9，D8等為白棋的真眼，是棋串死活重要的部分，白棋沒有理由把自己的真眼填掉，對白棋而言是不合適的著手，對黑棋而言則是禁著。</p><p>　　圖4.7 禁著與打劫</p><p>　　4.3.5 棋局模擬</p>

98、<p>　　模擬棋局的好壞是決定節(jié)點(著手)好壞的一個重要依據(jù)，因此，模擬棋局的合理性與正確性是相當(dāng)重要的，雖然在大量的隨機(jī)取樣下，可以得到誤差小到忽略的結(jié)果，但是，一盤棋局的比賽時間是有限的，每一個著手更需要在更短的時間內(nèi)獲得結(jié)果，所以，執(zhí)行合理而正確的模擬棋局是有其必要性的。</p><p>　　另外，對于一些常見的棋形，人類棋手總結(jié)出其特定的比較好的著手，雖然在某些盤面下可能不是最佳的著手，但通常

99、來說都不會太壞，對于這部分的加強(qiáng)就需要圍棋的知識。當(dāng)愈多的檢查與處理被加入，模擬棋局的合理性與正確性也隨之增加，但是模擬棋局的所需時間也隨之增加，在相同時間內(nèi)可以執(zhí)行的模擬棋局的數(shù)量也就相對減少。</p><p>　　因此，如何讓模擬棋局足夠合理與正確，同時不會讓一盤模擬棋局的所需時間太長，將是一項困難的挑戰(zhàn)。對此，采取的策略是先確認(rèn)在相同的模擬棋局次數(shù)情況下，棋力是否有提升，再確認(rèn)能在限定內(nèi)時間內(nèi)完成棋局比賽。

100、</p><p>　　在此對模擬棋局的加強(qiáng)方法分別說明如下：</p><p><b>　　棋局結(jié)束的判斷</b></p><p>　　無論一盤棋局下得好壞，總得知道如何判斷棋局是否結(jié)束。前文中曾提到過在蒙特卡羅方法中模擬棋局用不自填眼位來確保棋局正常結(jié)束。自填眼位通常是指如圖4.8中第一行最左邊圖所示，E5位置的空點相鄰的四個棋點都是是同色(圖

101、中為黑棋)的棋子，而不考慮其周圍四個對角點(用交叉標(biāo)記)的顏色。</p><p>　　圖4.8 中央自填眼位的判斷</p><p>　　在中央一個空點如果周圍四個對角點至少有兩個被敵方棋子占據(jù)時，而不能將對方棋子殺死，該空點將成為假眼，最終會被對方打吃而自己自填眼位。即如圖4.8第一行中，如果圖中交叉點被白棋占據(jù)，E5點將成為假眼而最終自填眼位。而圖4.8第二行則是真眼。如圖4.9，在邊、

102、角一個空點周圍的對角點如果有一個被敵方棋子占據(jù)，則該空點也會自填眼位。</p><p>　　圖4.9 邊、角自填眼位的判斷</p><p>　　從上面的分析中要明確的是不自填眼位確切來說應(yīng)該是不自填真眼。注意，這里的真假眼是從形狀上來簡單判斷的，并不考慮棋串的氣數(shù)和死活，因此有一些比較少見的棋形是假眼成真眼活棋的，如果把假眼填掉，會導(dǎo)致棋子被殺，模擬棋局失真。如圖4.10，黑棋兩個都是假眼

103、，都因為不入氣而活棋。</p><p>　　圖4.10 雙假眼成活棋</p><p>　　除了不自填眼位外，還涉及到公氣(黑棋和白棋共同擁有的氣點)的填充，在中國圍棋規(guī)則數(shù)子法里要求填公氣。圍棋顧名思義就是圍地，當(dāng)棋子占據(jù)的地盤比較大時，難以判斷一個空點是否是公氣。在棋局結(jié)束時，如果有不能活棋的又沒有馬上被提掉的棋子，稱為俘虜，也是要提掉的。另外，一塊地被圍起來，也很難檢查是屬于哪方棋子的

104、地盤。當(dāng)然，還有更多的情況，可以說棋局的結(jié)束情況是相當(dāng)復(fù)雜的。</p><p>　　對此，Tao Go采取以實戰(zhàn)為最高原則，基本的圍棋規(guī)則和不自填眼位，一直下到將棋盤上所有的公氣填完，提盡俘虜，活棋下成兩個或兩個以上真眼的棋形。這樣做的好處是在結(jié)束棋局時只要黑白雙方都發(fā)現(xiàn)沒有地方可下，雙方都pass棋局即可宣告結(jié)束，而且在計算勝負(fù)時也是和中國圍棋規(guī)則的數(shù)子法的精神是一致的，計算簡單。不過這樣下也會對模擬棋局效率有

105、一定的影響，因為填充公氣，提取俘虜，作真眼等并不會對勝負(fù)的結(jié)果有影響，如果這類棋步步數(shù)太多會浪費時間。如圖4.11，是棋局結(jié)束時的盤面圖。</p><p>　　圖4.11 棋局結(jié)束盤面</p><p>　　還有一個會對判斷棋局結(jié)束有影響的是雙活的情形。雙活時如果強(qiáng)制要求填公氣，將導(dǎo)致被吃，對棋局的勝負(fù)可能會造成影響。如圖4.12，E9，E8為黑白兩個棋串共有，誰都不能下，強(qiáng)制要求填公氣時填

106、公氣的一方會被吃。由于雙活的情形比較少見，而判斷是否雙活又非常困難，簡單忽略雙活是可行的。</p><p><b>　　圖4.12 雙活</b></p><p><b>　　圍棋基本規(guī)則處理</b></p><p>　　在模擬棋局中，有可能會選擇到非法或不合理的棋步，非法的棋步因為地攤圍棋的基本規(guī)則，是一定要去除的，但是不

107、合理的棋步，如果不去除，則會造成不合理的模擬棋局。</p><p>　　這部分使用候選步篩選方式處理，不再贅述，但是對于假眼，則是必須確認(rèn)是否能成為真眼，也就是檢查其斜角四個相鄰的棋點是否為空點，如果是空點，表示有機(jī)會形成真眼，此時就以斜角的相鄰空點任選其一為棋步，如果無空點，表示此假眼已成為劫，填此假眼只是粘劫，不屬于眼位。如果選擇到的是對方的假眼，則要檢查是否此棋步會吃掉對方棋串，也就是對方的棋串只剩一氣，且

108、其最后一氣就是此假眼。如果不是，則此對方的假眼是己方的禁著。</p><p><b>　　模式匹配</b></p><p>　　對于常見的棋形，人類棋士通過長期經(jīng)驗積累，總結(jié)出一些著手比較合理，得失大致均等，雙方都能接受的定型，就是在圍棋上稱為“定式”。由于定式的數(shù)量很多，棋步較復(fù)雜，要想在快速的模擬棋局中構(gòu)建一個高效的定式庫，實現(xiàn)起來非常復(fù)雜，對于模擬次數(shù)很大的模擬