基於UCT的围棋引擎的研究与实现.doc

摘 要棋類博弈是人工智慧的重要研究主題之一。而在圍棋方面，由於圍棋的搜索空間太大、電腦難於處理模糊概念且難於設計學習演算法，目前最優秀的圍棋程式的水準還處於業餘低段水準。電腦圍棋被認為是在繼國際象棋之後人工智慧領域中最困難的新挑戰之一。圍棋是檢驗人工智慧發展水準的良好環境，如何提高圍棋程式的棋力是人工智慧領域的一大難題。所以電腦圍棋研究具有重要的理論意義和實用價值。本論文將介紹如何基於UCT演算法設計和實現圍棋引擎。第一部分介紹了電腦圍棋研究背景及意義、研究狀況和關鍵技術，包括Monte Carlo方法和UCT演算法的理論。第二部分在圍棋引擎總體概述的基礎上說明其總體功能模組，並對各個子功能模組進行描述，重點講解了交替下子的流程以及棋步產生模組。第三部分闡明了基於UCT演算法的圍棋引擎的設計，先設計圍棋引擎的總體流程，再依次說明UCT演算法流程、棋步合法性的判斷等模組的具體設計流程。第四部分探討了基於UCT演算法的圍棋引擎的實現，在分析圍棋引擎核心模組UCT演算法實現的基礎上，詳細說明了候選步的產生及管理機制，節點的UCT選擇，展開節點和棋局模擬，分析指出不同的因素和策略對電腦圍棋引擎的影響，其中棋局類比的著手庫模式匹配和其它圍棋知識對加強程式棋力有至關重要的作用。最後對主要工作做了總結，提出進一步的發展目標。基於上述內容，實現了一個基於UCT演算法的圍棋引擎Tao Go，支援GMP、GTP圍棋協定，SGF檔調試輸出和統計UCT類比棋局的資料，目前能正常與圍棋用戶端進行通信，實現人機和機機對弈。關鍵字：人工智慧 電腦圍棋 UCT演算法 模式匹配目 錄1 緒論11.1 研究背景及意義11.2 研究狀況11.3 關鍵技術21.3.1 Monte Carlo方法21.3.2 UCT演算法32 基於UCT的圍棋引擎的概述52.1 圍棋引擎的總體概述52.2 圍棋引擎的總體功能模組52.3 交替下子流程模組72.4 棋步產生(UCT)模組82.5 棋步合法性判斷模組102.6 算氣模組102.7 更新棋盤(提子)模組112.8 勝負計算模組113 基於UCT的圍棋引擎的設計123.1 圍棋引擎總體流程設計123.2 UCT演算法具體流程設計133.3 棋步合法性判斷模組設計163.4 算氣模組設計183.5 更新棋盤(提子)模組設計193.6 勝負計算模組設計204 基於UCT的圍棋引擎的實現224.1 軟硬體開發環境224.2 圍棋引擎的資料結構224.2.1 棋局數據224.2.2 UCT Tree數據234.3 圍棋引擎的UCT演算法實現234.3.1 UCT演算法的核心實現234.3.2 候選步的產生方式及管理機制264.3.3 選擇節點(UCT選擇)284.3.4 展開節點314.3.5 棋局模擬334.4 圍棋引擎運行效果414.4.1 圍棋協議對弈測試414.4.2 調試模式的SGF檔434.4.3 UCT類比棋局資料統計445 工作總結及未來展望455.1 工作總結455.2 未來展望45致 謝46參 考 文 獻47英 文 摘 要49 1 緒論1.1 研究背景及意義博弈是人工智慧的重要研究主題，人工智慧的發展在很大程度上得益於博弈研究的發展。1997年著名的深藍電腦戰勝國際象棋世界冠軍卡斯帕羅夫成為轟動一時的新聞事件l。可以說，作為博弈研究的主要內容之一，棋類博弈得到了滿意的解決，唯一的例外的是圍棋，目前最優秀的圍棋程式還處於業餘低段水準。圍棋是博弈的一種，屬雙人零和博弈2。它起源於3000多年前的中國，充分體現了東方人的智慧，盛行于中日韓，逐漸在歐美流行。它比國際象棋複雜得多，正因為如此，很多人工智慧學家、心理學家和數學家也投入到了電腦圍棋研究領域。電腦圍棋這個名稱來自於Computer Go的直譯，略顯生硬。簡單地說，電腦圍棋就是結合人工智慧技術教電腦下圍棋，以達到與人類棋手相抗衡的目的。由於圍棋的搜索空間太大、電腦難於處理模糊概念且難於設計學習演算法，造成了電腦圍棋程式的棋力難於提高。圍棋是檢驗人工智慧發展水準的良好環境，如何提高圍棋程式的棋力是人工智慧領域的一大難題。同時，開發出與人類棋手水準相當的圍棋程式也有助於對人類認知能力的理解。所以電腦圍棋研究具有重要的理論意義和實用價值。1.2 研究狀況電腦圍棋自Zobrist在1970年設計出第一個可與人對弈的程式以來3，至今已有約四十年的歷史。由於圍棋本身的特質，使得電腦圍棋在繼西洋棋、象棋之後，成為人工智慧中一個相當引人注目的新挑戰。然而電腦圍棋的難點之一，便在於缺乏良好的局面評估函數4，使其不能跟國際象棋一樣，運用設計良好的局面評估函數、搜尋樹以及優秀的剪枝法，即可獲得不錯的棋力；電腦圍棋大多借鑒一些經驗法則，以靜態的評估為主，而動態的搜尋則僅用於局部的、目標明確的棋串攻殺，較少的全域搜尋。因此，人類的經驗如何應運用於電腦圍棋，就成了設計的重點。自2003年起，Bouzy試圖打破這種情況5。他運用蒙特卡羅(Monte Carlo)方法作為評估函數，並且試圖運用這一評估函數，作全域性的搜索，然而在棋力上始終沒有大的突破。直到2006年，同樣使用蒙特卡羅方法的程式Crazy Stone67，才在杜林舉行的第11屆電腦奧林匹克的九路圍棋項目中奪得金牌。雖然如此，Crazy Stone僅在19路圍棋項目中奪得第五名，仍未撼動以人類思維為主的圍棋程式GNU Go在19路圍棋的地位。然而，隨著基於蒙特卡羅的UCT(Upper Confidence bounds applied to Trees) 搜索方法的出現，以UCT為基礎的圍棋程式MoGo810也逐漸在一些較非正式的比賽中嶄露頭角。2007年6月，第12屆電腦奧林匹克於阿姆斯特丹舉行，上屆冠軍GNU Go、亞軍GO Intellect以及前文介紹過的Crazy Stone等程式均有參賽，MoGo在強敵環伺之下，以全勝戰績奪得了19路圍棋項目的金牌，Crazy Stone也拿到了第二名，GNU Go退居第三。這象徵UCT的成功，也代表一個嶄新的局面的到來。1.3 關鍵技術1.3.1 Monte Carlo方法Monte Carlo1112方法主要理論基礎是依據大數定理，在隨機取樣的情況下，可以獲得有誤差的評估值，取樣的數量越多，誤差將越小，評估值將越準確。將Monte Carlo方法應用於圍棋13，其核心的思想是，在於通過統計許多模擬棋局的結果，進行局面的優劣判斷。亦即將蒙特卡羅方法作為局面評估函數，以決定著手的好壞。其中，所謂的模擬棋局，指的是對某一目標盤面，由電腦隨機落子，直到終盤而可以判定勝負為止。在隨機落子時，除了基本的圍棋規則外，只有一個限制：不得自填眼位，這個限制是為了防止棋局無法結束而設定的。模擬棋局的結果，與目前常見的只判斷黑勝或白勝不同，而是會判斷輸贏的目數，在決定著手優劣時，則是統計此著手下所有模擬棋局平均的輸贏目數來決定的。1.3.2 UCT演算法UCT又名UCB for Tree Search，是UCB(Upper Confidence Bound)在Tree Search上的應用。而UCB本來是為了解決吃角子老虎機問題(Bandit Problem)而產生的。所謂的吃角子老虎機問題，簡述如下：目前有若干台吃角子老虎機，每台機器可以投錢並拉動操縱杆，此時會得到收益(reward)，投錢、拉杆、得到收益的過程，稱之為一個Play。每台吃角子老虎機有不同的收益率，倘若玩家想要在若干次的Play裡獲得最大總收益，那麼該怎麼做？一般來說，玩家會開始動手玩，並且依照目前積累的經驗來決定下一次的Play要選擇哪一台機器，這稱之為開發(exploitation)。相對地，如果玩家不斷地依照目前所獲得的經驗來決定，而不試圖嘗試其它的其他的機器，則可能會忽略收益率更高的機器，因此適度地嘗試其他機器是必須的，這稱之為探險(exploration)。如何在開發與探險之間保持平衡，就是UCB試圖解決的ExE(exploitation vs. exploration)問題。UCB根據目前獲得的資訊，配合上一個調整值，試圖在開發與探險間保持平衡。大致上來說，每一次Play時，UCB會根據每一台機器目前的平均收益值(亦即其到目前為止的表現)，加上一個額外的參數，得出本次Play此台機器的UCB值，然後根據此值，挑選出擁有最大UCB值的機器，作為本次Play所要選擇的機器。其中，所謂額外參數，會隨每一台機器被選擇的次數增加而相對減少，其目的在於讓選擇機器時，不過分拘泥於舊有的表現，而可以適度地探索其他機器。UCB公式表示如下(也稱為UCB1)14：Xj+2lognTj(n) (3)Xj是第j台機器到目前為止的平均收益，Tjn是第j台機器被測試的次數，n是所有機器目前被測試的總次數。讓公式(3)的值最大的機器將是下一個被選擇的機器。前項即為此台機器的過去表現，後項則是調整參數。而UCB1-TUNED是相對於UCB1實驗較佳的配置策略14。UCB1-TUNED的公式如下：Vjs=1s=1sXj,2-Xj,s2+2logns (4)Xj+lognTj(n)min14,VjTj(n) (5)讓公式(5)的值最大的機器將是下一個被告選擇來測試的機器。UCT(UCB for Tree Search)其實就是把UCB1或UCB1-TUNED(統稱為UCB)等公式運用於Tree Search上的一個方法14。以概念而言，UCT把每一個節點都當作是一個吃角子老虎機問題，而此節點的每一個分支，都是一台吃角子老虎的機器。選擇分支，就會獲得相應的收益。Tree Search開始時，UCT會建立一棵Tree，然後：(1) 從根節點開始(2) 利用UCB公式計算每個子節點的UCB值，選擇UCB值最高的子節點(3) 若此子節點並非葉節點(從未拜訪過的節點)，則由此節點開始，重複(2)(4) 直到遇到葉節點，則計算葉節點的收益值，並依此更新根節點到此一節點路 徑上所有節點的收益值(5) 由(1)開始重複，直到時間結束，或達到某一預設次數(6) 由根節點的所有子節點中，選擇平均收益值最高者，作為最佳節點此一節點，就是UCT的結果。2 基於UCT的圍棋引擎的概述2.1 圍棋引擎的總體概述電腦圍棋程式通常也可稱為電腦圍棋引擎，具體表現為引擎本身沒有也不需要實現圖形圍棋介面(這通常是交由圍棋用戶端來做的)，而是通過特定的圍棋協定與引擎外部進行通信，如圖2.1所示。這樣的好處是邏輯簡單，功能明確，只需要關注圍棋引擎的核心部分，即圍棋引擎是如何去思考的，並嘗試產生最優棋步。如果不去考慮圍棋引擎具體的思考過程，它表現出來的僅僅是它思考的最終結果，一個棋步而已。除此之外，圍棋引擎所做的工作就是實現對弈雙方交替落子的過程，同時根據棋規進行相應的更新棋盤處理，並在棋局結束時計算勝負。事實上，圍棋引擎與圍棋用戶端的關係可以拿IDE和編譯器的關係來類比。在編譯原始檔案的時候，首先需要設置使用哪個編譯器和相應的編譯參數，然後IDE會調用編譯器去編譯原始檔案，接著編譯器執行編譯過程，最後編譯器返回編譯結果給IDE，IDE則顯示編譯結果給使用者查看。而在圍棋對弈的時候，首先需要設置使用哪個圍棋引擎和圍棋協定參數，然後圍棋用戶端會通過圍棋協定告訴圍棋引擎為黑棋(或白棋)產生一個棋步，接著圍棋引擎進行思考，最後圍棋引擎返回思考得到的棋步給圍棋用戶端，圍棋用戶端則在棋盤上顯示該棋步給圍棋用戶查看。圖2.1 圍棋引擎與圍棋用戶端的通信2.2 圍棋引擎的總體功能模組圍棋引擎Tao Go的總體功能模組圖如圖2.2所示。其中交替下子流程功能模組是圍棋引擎的總體流程。如何基於UCT產生棋步是圍棋引擎的核心功能模組，在棋步產生(UCT)功能模組下面的五個子功能模組中除了候選步產生及管理子模組是起輔助作用以外，其它四個子功能模組實際上是一個有機聯繫的整體，構成圍棋引擎的UCT演算法流程。棋步合法性判斷模組是根據圍棋規則來判斷一個棋步是否合法。更新棋盤(提子)模組是檢查是否有吃子，有則提掉，並記錄可能的打劫位置。勝負計算模組是在棋局結束時根據圍棋規則來計算勝負。算氣模組是計算一個棋串的氣數。圖2.2 圍棋引擎總體功能模組如圖2.3，是圍棋引擎各個模組之間的關係。可以看到，圍棋引擎交替下子流程模組對外負責與圍棋用戶端進行通信，然後調用引擎內部其它模組進行處理。例如圍棋用戶端輸入了對手棋步，圍棋引擎交替下子流程模組會調用棋步合法性判斷模組對棋步進行判斷，如果合法則更新棋盤，然後調用棋步產生(UCT)模組產生棋步，最後輸出棋步返回給圍棋用戶端。圍棋引擎交替下子流程模組在棋局開始時，還會進行一些初始化工作，主要是商定圍棋規則，在棋局結束時則計算對弈雙方的勝負。棋步產生(UCT)模組在產生棋步過程中會執行多次模擬棋局，正式對局中所需要用到的功能模組同樣會被調用，包括棋步合法性判斷模組、更新棋盤(提子)模組和勝負計算模組。 算氣模組作為最基礎的模組，為各個模組提供依據，服務的上層的模組包括棋步產生(UCT)模組、棋步合法性判斷模組和更新棋盤(提子)模組。圖2.3 圍棋引擎模組間的關係2.3 交替下子流程模組交替下子流程模組展示了圍棋引擎的基本流程活動，如圖2.4是交替下子流程模組的活動圖。活動一開始是進行初始化引擎，主要是商定圍棋規則和初始化圍棋引擎內部的一些參數和資料。然後進入對弈雙方交替下子的過程，直到棋局結束。交替下子時，如果是對手下子，則從圍棋引擎外部得到對手棋步，否則輪到引擎下子，此時引擎的棋步產生模組會產生合法棋步，然後輸出產生的棋步到圍棋引擎外部。每當有下子的動作發生，則進行更新棋盤，對棋局改變的狀態進行相應的處理。當棋局結束時，根據圍棋規則計算雙方的勝負，如果對弈雙方對計算勝負的結果沒有爭議，棋局正式結束，否則繼續對弈。有一點需要指出的是，在這裡沒有明顯指出得到對手棋步是否要考慮該棋步的合法性。棋步的合法性通常圍棋引擎外部的圍棋用戶端也會判斷保證，不過在設計時應該考慮加入對對手棋步的合法性判斷和相應的錯誤處理，以保證邏輯的完整性，使得棋局能夠順利進行。圖2.4 交替下子流程的活動圖2.4 棋步產生(UCT)模組棋步產生(UCT)模組使用UCT演算法來產生棋步，是整個圍棋引擎的核心功能模組。前面1.3.2小節已經介紹了UCT演算法的理論，下面來說明UCT演算法究竟是如何應用在圍棋上的。UCT使用在圍棋上，主要的概念，就是每個節點代表一個盤面，此節點的分支代表此盤面下的合法著手，每個分支聯結到的子節點，就是原盤面加上分支代表的著手後，所產生的新盤面。一般而言，目前盤面為根節點，根節點的分支代表目前盤面下的合法著手，根節點的子節點代表根節點的盤面加上分支代表的著手後所形成的新盤面，如圖2.5所示。圖2.5 UCT Tree的概念表示，其中每個節點均記錄訪問次數，勝利次數，形成此節點的著手，著手顏色等資訊此外，UCB公式的收益值，如前1.3.1小節所述，就是依照Monte Carlo方法的概念，用模擬棋局的結果來決定。上面1.3.2小節中UCT 演算法第4個步驟中，電腦收益值，在此應該改為執行模擬棋局。所謂的模擬棋局，就是給定一個盤面(在此給的是葉節點所代表的盤面)，由電腦接手落子，直到終局，然後判定並回傳勝負結果(黑勝或白勝)。在此要注意的是，UCT會據此結果，更新葉節點到根節點上所有節點的收益值，也就是說，一個節點會概括承受所有子節點模擬棋局的結果。對於任一節點，其收益值為：此一節點的模擬棋局勝利數/此節點被訪問的次數，亦即其勝率。上式中所謂的勝利數，指的是指向此節點的分支所代表的顏色(黑棋或白棋)在模擬時的勝利次數。UCT Tree搜索流程總結如下：UCT演算法使用極小極大遊戲樹(minimax game tree)，搭配節點選擇公式(UCB公式)，選擇樹節點，展開要測試的節點，然後使用Monte Carlo方法執行模擬棋局，最後將模擬棋局的結果回饋更新。流程示意圖如圖2.6所示。圖2.6 UCT Tree搜索流程示意圖2.5 棋步合法性判斷模組一個棋步是否合法，是根據圍棋規則來確定的，規則如下：(1) pass(也稱虛著)是合法的棋步，允許任何一方放棄下子權而使用虛著。黑白雙方輪流在空點上落子，即不能在非空棋點上落子。(2) 禁著點。棋盤上的任何一點，如某方下子後，該子立即呈無氣狀態，同時又不能提取對方的棋子。這個點叫做禁著點。(3) 禁止全域同形。著子後不得使對方重複面臨曾出現過的局面。其中打劫是全域同形最基本的情況。2.6 算氣模組當任何一方落子後，除了虛著以外，都有可能把對方的棋子提掉，這個時候就要計算與所落子相鄰的所有對方棋串的氣數。事實上，在判斷棋步的合法性時也往往需要計算雙方棋串的氣數。計算棋串的氣數主要採用標記法，從棋串的某一個棋子開始，先標記該棋子已訪問過，然後對於該棋子四個相鄰的棋點，如果相鄰棋點是空點，則棋串氣數加1；如果相鄰棋點上是對方的棋子，則無需對該方向上的相鄰棋點繼續進行探索；如果相鄰棋點上是己方棋子，則對該相鄰棋點上的己方棋子進行同樣的操作，直至計算完整個棋串的氣數。2.7 更新棋盤(提子)模組更新棋盤時，主要是利用計算棋串氣數的功能檢查是否有提子， 有提子時將對方的棋串提掉，即清空對應棋串位置，並記錄可能導致劫爭的位置。2.8 勝負計算模組著子完畢的棋局，採用數子法計算勝負。將雙方死子清理出盤外後，對任意一方的活棋和活棋圍住的點以子為單位進行計數。 雙方活棋之間的空點各得一半。 棋盤總點數的一半點為歸本數。一方總得點數超過此數為勝，等於此數為和，小於此數為負。如果有貼子，則要按照相關的規定進行計算。3 基於UCT的圍棋引擎的設計3.1 圍棋引擎總體流程設計圖3.1 圍棋引擎總體流程如圖3.1所示，圍棋引擎的總體流程實際就是類比對弈雙方交替落子的過程。當輪到對手落子時，圍棋引擎通過圍棋協定從引擎外部得到對手的棋步。否則圍棋引擎使用UCT演算法產生棋步，並通過圍棋協議輸出產生的棋步到引擎外部。不管是得到對手棋步之後或者是輸出產生棋步之前，都必須檢查棋步的合法性，如不合法則進行相應的出錯處理。如果檢查的棋步是合法的，接下來就根據圍棋規則做出正確的處理。如果合法棋步是pass時，則將pass數加1；否則將pass置為0。更新棋盤時，對於非pass合法棋步，則提取可能的死子並記錄可能的打劫位置，對於pass棋步則不做任何改變。最後，棋步數加1，然後回去判斷pass是否大於等於2，如果是說明雙方都pass，棋局結束，否則雙方繼續落子。3.2 UCT演算法具體流程設計UCT演算法的流程大致分為四個部分：第一部分是選擇節點，在遊戲樹中選擇子節點。第二部分是展開節點，產生新的子節點。第三部分是棋局類比，執行模擬的棋局。第四部分是回饋更新，將模擬棋局的結果以回溯方式更新遊戲樹節點的資訊。在本論文中，將針對該流程前三部分進行詳細說明。圍棋引擎Tao Go使用的UCT流程如下，其示意圖如圖3.2所示。(1) 選擇節點若有未被訪問過的子節點，則優先以隨機方式選擇其中一個子節點落子然後執行模擬棋局(轉到(3)，否則繼續使用節點選擇公式UCB1或UCB1-TUNED選擇子節點。當被選中的子節點為葉節點並且該子節點被訪問的次數未達到指定的次數時，則選擇該子節點落子然後執行模擬棋局(轉到(3)。當被選中的子節點為葉節點並且該子節點被訪問的次數達到指定的次數，則需先展開該子節點(轉到(2)。否則重複此步驟直到找到被訪問的次數未達到指定的次數或未被訪問過的葉節點為止。(2) 展開當節點為葉節點並且該節點被訪問的次數達到指定的次數時，進行展開子結點。展開時對候選步作篩選，去除不適合的候選步，再將篩選後的候選步展開成子節點並隨機選擇其中一個節點(轉到(1)。(3) 棋局模擬當被選擇的葉節點落子後開始執行模擬棋局，在模擬棋局中檢查是否有棋串少於四氣，若有則嘗試逃跑；如果有符合簡單的模式庫的棋形，執行棋形庫模式匹配；如果沒有符合棋形的空點，則嘗試攻擊對方少於四氣的棋串；如果都沒有合適的棋步，最後使用隨機方式選擇合法棋步。(4) 回饋更新將模擬棋局的結果回溯更新遊戲樹節點的資訊。圖3.2 Tao Go的UCT具體流程示意圖在實際上執行UCT Search時，其流程可以用圖3.3表示。在圖3.3中，所謂GetBestSequence，指的是從根節點開始，根據UCB公式向下搜索，直到找到被訪問次數不超過指定次數的葉節點為止的過程。當搜索時，若被訪問的節點達到指定的次數，則會產生子節點，子節點的多寡，直接影響到搜索的深度與棋力的高低，因此對於產生出來的子節點，必須加以裁減。第三個步驟是類比棋局。所謂類比棋局，就是由上一個步驟所找到的葉節點開始，由電腦接手下完，並回傳勝負結果，以更新UCT Tree。模擬棋局的核心就是其決定著手的方法。最簡單的方法，就是純粹隨機落子（除了非法著手或自填眼位以外），這種方法的好處就是快速、簡單，且符合Monte Carlo的精神。但缺點則是用這種方法做出來的圍棋程式，棋力低落。要使棋力進步的重點，在於棋局的手順要有意義，而不是隨機落子，天南地北地亂下。Tao Go建立了一個著手庫對常見棋形進行模式匹配，如果沒有棋形可以匹配則對少於四氣的己方棋串進行長氣或叫吃對方少於四氣的棋串，如果以上都不成功，則隨機落子15-24。有了模擬棋局的結果，就要依此更新UCT Tree。所謂更新，指的是把從根節點到第二步驟中所找到的葉節點所形成的路徑上的所有點，依照模擬棋局的結果來更新勝場數和訪問次數，亦即若此點為黑，且模擬棋局之結果為黑勝，則此節點的勝利次數加一，反之亦然。訪問次數則是此路徑上的所有節點都加一。若總模擬次數達到所設定的次數，或限制時間已用完，則結束UCT Search，並且挑出根節點下被訪問次數最多的子節點，作為此次搜索的最佳著手。是以當前盤面建立root node由root開始，GetBestSequence執行模擬棋局更新UCT Tree類比次數加一,判斷是否達到目標類比次數回傳root底下被訪問次數最多的子節點作為UCT Search的結果否圖3.3 UCT Search的流程圖3.3 棋步合法性判斷模組設計棋步的合法性是根據圍棋規則來判斷，如圖3.4所示。分別檢查是否是虛著，是否在棋盤內，是否是打劫以及是否是自殺(禁著點)。虛著，通常採用特殊的棋盤座標來表示，正常棋步跟特殊棋盤座標比較即可知道知道是虛著。有時候產生的棋步的座標值是不合法的，此時棋步不在棋盤內，跟正常棋盤座標範圍比較即可。而打劫可借助記錄可能造成打劫的位置，只要比較棋步的座標和造成打劫的位置即可。至於自殺棋步的判斷，如圖3.5所示。棋子自殺顧名思義是使得下子後棋子所在的棋串沒有氣數，但同時必須沒有殺死對方的任何棋串。先計算下子後棋子所在的棋串的氣數，如果棋串氣數不為0則說明肯定不是自殺棋步。如果棋串氣數為0，則需要考慮有沒有可能殺死對方棋子。可通過計算與該棋串相鄰的對方棋串的氣數來判斷，如果沒有相鄰對方棋串氣數為0，即提取死子數為0，屬於自殺，是不合法棋步。如果有提取對方死子，此時也有可能是打劫，不過打劫的情況已經在前面被排除了，說明儘管有提取死子，但肯定不是由於打劫造成的。這也是打劫要先進行判斷的原因。圖3.4 棋步合法性判斷流程圖圖3.5 自殺棋步判斷3.4 算氣模組設計算氣模組用來計算一個棋串的氣數。通常是已知棋串的某一個棋子，計算該棋串的氣數。使用如下步驟進行計算：(1) 將當前棋子標記為已訪問。(2) 對當前棋子的四個相鄰棋點進行如下操作：(3) 如果相鄰棋點是空點並且該空點未被訪問過，則氣數加一，然後將空點標記為已訪問。(4) 如果相鄰棋點是己方棋子並且該己方棋子未被訪問過，則對相鄰的己方棋子按照(1)(4)的步驟進行同樣的操作。當對整個棋串所有的棋子進行上述步驟的操作後，整個棋串的棋子和棋串相鄰的所有空點都會被標記為已訪問，此時的氣數和即是要計算的棋串的氣數。算氣模組四個相鄰棋點操作轉換的示意圖如圖3.6所示。圖3.6 算氣轉換示意圖3.5 更新棋盤(提子)模組設計如圖3.7，是更新棋盤的具體流程。更新棋盤時，首先將產生的棋步下在棋盤上，將對應的棋盤座標標為棋步的顏色。然後計算相鄰的對方棋串的氣數和棋串的棋子個數。接著判斷計算出來的棋串的氣數是否為0並且棋串的棋子數為1，有可能出現會造成打劫的情況，所以需要判斷下子後周圍的棋形是不是會造成打劫的棋形，如果是會造成打劫的棋形則記錄會造成打劫的位置。不管是否有會造成打劫的情況出現，只要有對方的棋串的氣數為0，則將對方的棋串的所有棋子的清空，即提掉對方死子，同時增加相應的擔子數。最後，當一方的棋步處理完畢後，則交換對方下子。可以看到，更新棋盤時總共有兩個功能，即是提取對方的死子和記錄打劫的位置，如果上述情況存在。圖3.7 更新棋盤(提子)流程圖3.6 勝負計算模組設計計算勝負時，對棋盤上的每一個棋點，進行如圖3.8的數子流程判斷。一個棋點，無非是被黑棋或白棋佔據，要不然則為空點。當被白棋佔據時，白棋子數加一。當被黑棋佔據時，黑棋子數加一。而空點在棋局結束時，無非是被白棋或黑棋佔據(雙活除外)，所以如果空點被白棋圍住，白棋子數加一，否則空點被黑棋圍住，黑棋子數加一。當棋盤所有的棋點計算完畢後，白棋和黑棋的子數都已經知道，只需比較雙方的子數即可知道勝負結果。圖3.8 數子流程圖4 基於UCT的圍棋引擎的實現4.1 軟硬體開發環境硬體平臺：AMD Athlon(tm) 64 X2 Dual Core Processor 4000+, 1G記憶體軟體平臺：Slackware Linux 13.0和Windows XP開發語言：C語言開發工具：採用(g)Vim-7.2+Makefile+gcc-4.3.3的方式，前期代碼的編寫和測試主要是在Linux環境下完成，後期代碼移植通過MinGW-5.1.6編譯出可運行在Windows環境下的圍棋程式。其它工具：cgoban-1.9.14和gogui-1.1.10分別支援GMP和GTP圍棋協定，用於測試圍棋引擎的協定介面，並提供良好的人機、機機對弈介面。另外，也可以使用引擎的控制台字元介面進行操作和測試。StoneBase 4.6.1.2147用來查看與編輯引擎調試輸出的SGF檔。4.2 圍棋引擎的資料結構在程式中主要有兩類資料結構：一是與棋局相關資料，用於記錄棋盤資訊和保證棋局的正常進行；二是與UCT演算法相關資料，裡面保存了創建UCT Tree的節點資訊及類比棋局相關參數和資料。4.2.1 棋局數據以下是正式棋局資料的拷貝，因為進行UCT類比棋局時會改變相關棋局資訊，必須另外複製一份資料，以便於操作和防止錯誤修改原有的資料。棋局資料包括了棋盤，棋盤大小，當前下棋的顏色，貼目，劫爭位置等。這些資料有的可能在初始化後在棋局中沒有任何改變(如貼目)，有的可能會時刻變化(如當前下棋的顏色)，全部進行複製是為了保持一致性，即正式棋局的資料和類比棋局的資料是一致的，只是在名稱上不同。typedef unsigned char board_t;board_t boardMAX_BOARDMAX_BOARD; /* 棋盤9x9, 最大19x19 */board_t libertyMAX_BOARDMAX_BOARD;/* 所有棋串的氣數 */board_t maMAX_BOARDMAX_BOARD; /* 通用輔助標記陣列 */board_t mlMAX_BOARDMAX_BOARD; /* 計算氣數標記陣列 */board_t candidate_moveMAX_BOARDMAX_BOARD;/* 候選著法標記陣列 */board_t move_listMAX_BOARD*MAX_BOARD; /* 隨機候選著法 */int cur_player; /* 當前下棋的顏色，黑或白 */int num_move=0; /* 當前已下棋子的步數 */int board_size; /* 棋盤大小 */int pass=0; /* 虛著, 雙方連續使用虛著, 視為終局 */int lib=0; /* 當前座標棋子所在棋串的氣數 */int ko_i; /* 劫爭位置的橫坐標 */int ko_j; /* 劫爭位置的縱坐標 */int last_move_i; /* 最後下的棋子位置的橫坐標 */int last_move_j; /* 最後下的棋子位置的縱坐標 */int black_captured; /* 已被提取的黑棋個數 */int white_captured; /* 已被提取的白棋個數 */float komi; /* 貼目 */4.2.2 UCT Tree數據這裡包含了UCB公式參數和UCT Tree結點的結構，說明了結點代表的著手，勝利的次數，被訪問的次數，以及結點之間的關係。static const double UCTK = 0.44;/* UCB公式中的0.44 = sqrt(1/5) */static const int num_visits = 10;/* 直到子節點被創建時節點被訪問的次數 */typedef struct Node int wins; /* 勝利的次數 */ int visits; /* 被訪問的次數 */ int x, y; /* 該節點代表的著手 */ struct Node *child, *sibling; /* 節點的子節點和夥伴節點 */ Node; /* UCT Tree的節點 */4.3 圍棋引擎的UCT演算法實現4.3.1 UCT演算法的核心實現這一小節給出Tao Go的UCT演算法的核心代碼，並對代碼中各個變數和函數的意義及作用進行分析說明。UCT演算法流程實現主要在play_simulation函數，而uct_search是調用play_simulation函數來提供產生棋步著手的介面函數。uct_search函數的功能是在進行UCT搜索之前進行初始化工作，包括創建和初始化根節點，首次展開節點。主體是進行numsim次UCT搜索，並在調用play_simulation之前複製棋局資訊。進行完numsim次UCT搜索後，從根節點下面找到最佳子節點並返回該節點代表的著手和釋放UCT樹。在uct_search函數中變數numsim用於控制類比次數，在其他條件不變的情況下，通常認為類比次數越多，程式能搜索的棋步越多越深，棋力也會越強。當然也有賴於模擬品質的好壞。在uct_search函數中根節點初始化時子節點為空，被訪問次數為0，進行模擬之前必須對其展開子節點(create_children)，才能在play_simulation函數中選擇子節點。展開子節點時包含了對子節點裁減的判斷，控制搜索棋步的廣度。在uct_search函數中copy_state函數的功能就是複製在4.2小節中提到的有關棋局資料的資訊，防止錯誤修改棋局資訊，同時為下一次類比恢復資料。在uct_search函數中get_best_child函數是獲得根節點下面被訪問次數最多的子節點，此節點代表的著手被認為是UCT演算法產生的最佳著手，也是圍棋引擎思考的結果，並最終被輸出到引擎外部。void uct_search(int *x, int *y, int color, int numsim)Node *root = (Node *) malloc(sizeof(Node); init_node(-1, -1, root); /* 初始化根節點 */ create_children(root); /* 展開子節點 */ for (int i = 0; i x;*y=n-y; /* 返回節點著手 */ free_tree(root); /* 釋放UCT Tree */play_simulation函數功能是實現了UCT演算法的流程，表現為遞迴選擇子節點直到選中符合要求的葉節點(在必要時進行展開節點)，然後進行模擬棋局，最後將棋局勝負結果回饋更新。在play_simulation函數中變數num_visits控制節點被擴展時的次數，能降低UCT Tree節點在記憶體的增長速率，在相同類比次數的情況下，增加對節點搜索模擬的次數，在一定程度上增加程式搜索的有效程度，負面影響是會減少棋步搜索的深度。在play_simulation函數中play_random_game函數包含了類比棋局的功能：棋形模式匹配、長氣逃子和吃子。uct_select函數中要優先選擇未被訪問過的子節點，這也是一個策略問題。關於play_random_game和uct_select函數的功能分別在4.3.5小節和4.3.4小節會有詳細說明。至於make_move函數則是根據圍棋規則對落子進行更新棋盤處理，關於基本圍棋規則會在討論play_random_grame函數類比棋局功能時進行介紹。而update_node函數是當類比棋局勝利時將勝率加1，被訪問次數不管勝利與否都加1。注意update_node更新節點資訊時，類比棋局勝負的結果對於不同深度的節點是相反的。某一深度的節點的父節點和子節點代表對方著手的節點，如果模擬棋局結果對該節點來說是勝利著手，則模擬棋局對於對方而言就是失敗的，所以更新到該節點的父節點和子節點的勝負結果是相反的。實際上也就是說，UCT樹本質是一棵極小極大(minimax)樹，對於己方有利的棋步對對方則是不利的，反之亦然。/* 返回 0代表輸，1代表贏 */int play_simulation(Node *n)int randomresult=0; /* num_visits次類比直到子節點被擴展(節省記憶體) */ if (n-child = NULL & n-visits child = NULL) create_children(n); /* 展開子節點 */ Node *next = uct_select(n); /* 選擇uct值最大子節點 */ if (next = NULL) /* ERROR */ make_move(next-x, next-y); /* 落子 */ int res = play_simulation(next); /* 遞迴選擇節點 */ randomresult = 1 - res; update_node(1-randomresult, n); /* 更新節點資訊 */ return randomresult;/* 返回模擬結果 */4.3.2 候選步的產生方式及管理機制棋局一開始時，雖然棋盤上有八十一個空點，黑棋可以任意選擇其一，也就是說有八十一個候選步。如此一來，遊戲樹的樹支將緩慢遞減，但是，並不時每個候選步都是合適的，根據圍棋知識，選擇如圖4.1中的二十五個候選步為棋局開始的候選步。圖4.1 二十五個候選步如果一開始只有十五個空戰成為候選步，必須要在適當時機，把其它空點也加入候選步中，否則，有些空點將就永遠不會被選擇，而造成錯誤。因此，需要一個候選步的產生方式及管理機制。由於每下一子(稱為著手)，就會讓周圍附近的空點成為下一步合適的候選步。因此，產生候選步的方式就是對於每一個空點，檢查其周圍是否有下子，看是否將其納入候選步。而檢查的方式是根據空點所線上，周圍棋子與空點之間的距離和已下棋子的步數來判斷的。其中兩個棋子的距離是指兩個棋子橫坐標差的絕對值和縱坐標差的絕對值之和，即有P1(X1, Y1)和P2(X2, Y2)，則兩個棋子距離為|P1P2| = |X1-X2| + |Y1-Y2|(1) 一線空點已下棋子的步數不超過預定的步數(如10)時，不考慮一線空點作為候選步。達到預定的步數後，對於一線的空點，當周圍有棋子在一線或二線上而且和該空點的距離小於3時，將該空點納入候選步。如圖4.2中，交叉點代表空點，其陰影部分代表如果這些地方有棋子，則說明該空點適合作為候選步。 圖4.2 一線空點候選步範圍(2) 二線空點已下棋子的步數不超過預定的步數(如5)時，不考慮一線空點作為候選步。達到預定的步數後，對於二線的空點，當周圍縱橫坐標都不超過兩線所構成的矩形範圍內，如果有棋子距離該空點小於4時，即類似於中國象眼的位置不考慮，則將空點納入候選步。如圖4.3所示，用三角形標記的地方即為象眼位置，不考慮該位置是否有棋子。 圖4.3 二線空點候選步範圍(3) 三線及三線以上空點三線及三線以上空點，考慮到九路棋盤的特殊性，無條件納入候選步。由於圍棋棋盤上的空點數目是固定的，九路棋盤只有八十一個棋點，可以成為候選步的空點最多也只有八十一個，所有使用candidate_move陣列來保存是適合的。根據“敵之要點即我之要點”的指導思想，這裡不考慮空點是由於黑棋或白棋而納入候選步的，簡化了產生候選步操作，同時也避免錯失好點。當然有時某些空點並非是要點或好點，將其納入候選步，在展開子節點時不僅浪費了遊戲樹記憶體空間，而且增加了搜索空間，減少有效搜索次數，搜索到不好的著手的幾率也會增大。這就體現了電腦圍棋中不同的策略對圍棋程式的影響。候選步的產生與管理是在每次落子時執行，也就是在程式的流程中只要有下子的動作，不論是展開節點還是棋局類比時隨機下子，都會使用候選步的產生與管理。4.3.3 選擇節點(UCT選擇)上文中提到過的uct_select函數是從父節點中選擇uct值最大的節點進行搜索，其中uct值的計算如下簡略代碼所示：if (child-visits 0)/* 勝率, UCB公式的過去表現 */ winrate = get_winrate(child);/* UCB公式 = 過去表現 + 調整參數 */ uctvalue = winrate + UCTK * sqrt(log(parent-visits) / child-visits);else /* 總是優先隨機選擇一個未訪問過的子節點 */uctvalue = 10000 + 1000 * rand();(1) 可變參數對uct值的影響首先來關注子節點被訪問過的情況時，uct值的計算用以下公式計算：uctvalue = winrate + UCTK * sqrt(log(parent-visits) / child-visits)要注意到UCTK的值是可變的，不同的值對程式的影響也不同。在CGOS上運行許多實現了基礎UCT演算法，使用不同參數值的圍棋機器人找到最優參數值。它們使用如下方法UCB1 = avgScore + c * sqrt(log(n) / m)其中上一行的公式和uct_select函數中的計算公式實際上等價的。要注意K和c都是在根號sqrt外面的。不同參數對圍棋機器人的影響如圖4.4所示。圖中Nick代表圍棋機器人的名稱。ELO代表等級分排行，Plts代表圍棋機器人的實力，10k表示10級。c為可變參數。圖4.4 可變參數對圍棋機器人的影響(2) FPU(First-play urgency)當子節點從未被訪問過時，使用下面的公式計算uct值：uctvalue = 10000 + 1000 * rand(); (1)子節點被創建時，其被訪問數和勝利數都為0。而更新節點資訊時，即便類比棋局返回勝利結果，勝利數僅加1，被訪問數加1。也就是說當節點被訪問的次數很少時，用公式uctvalue = winrate + UCTK * sqrt(log(parent-visits) / child-visits)(2)計算出來的uct值實際很小，遠遠小於用公式(1)計算出來的uct值，這就確保了能夠優先隨機未被訪問過的子節點。用公式(1)計算出來的uct值，稱為FPU8。將FPU值賦給未被