臺灣博碩士論文加值系統

本篇論文闡述電腦圍棋程式發展所需具備的基本審局知識，結合過去古典方法和當今火紅的演算法"蒙地卡羅信賴上界樹搜尋"進行類似於人類假想落子的模擬賽局。一開始介紹如何透過勢力評估影響值和空點價值分數融入棋型探勘，而且使用地域處理系統和邊界着手加成等盤面偵測來量化排序候選點棋步，並利用博弈樹和模擬棋局來尋找棋步後續衍生的最佳路徑。在兼具隨機與策略性著手應對的模擬賽局過程中，自行落子直到盤面結束，之後立即計算勝負並隨那些曾拜訪過的路徑節點，一個接一個將結果往前疊代至博弈樹的第一層為止，爾後反覆同樣動作統計各個節點的勝率，最終在大量模擬次數下可歸納找出最佳候選棋步。

實驗證實對一顆博弈樹進行一定程度精簡降低複雜度，有助於在固定模擬次數情況下增加搜尋的效率提升程式棋力。另外提出候選點排序準確率等評估方式來視為評量棋步產生的優劣好壞。還有實驗比較模擬過程當中使用到各項策略的實用價值。實驗心得論述每當替程式加入新的演算策略時，可透過空盤面模擬規律來提早預知該戰術是否有用。最後說明未來在19路電腦圍棋發展上所會遭遇到的難處與尚待解決的問題。

This paper described a basic knowledge on computer go, combining the past research and "MC-UCT Search" algorithm. Firstly, it introduces how to merge the influence into the explorative pattern through the domain weights and domain scores, and then applying the analytic systems to quantify and sort the candidate moves. Followed by using the method of the game tree and simulation of go game, finally in large number of simulation games that could be summarize to identify the best candidate move.

Experiment proved that appropriately pruning the branch of a game tree, it can conduce to the efficiency of search. Besides, this paper makes a description of evaluation for measuring the accuracy of candidate moves. Furthermore, it also compared the merits and demerits with various strategies in the simulation process. By experimental result, as soon as merging a new strategy to program, making use of a law of simulation on opening can predict the usefulness of the strategy in advance. Finally, we expound the difficulties that the development of the computer 19x19 go will encounter in the future as well as the outstanding issues that need to be developed.

摘要 I
Abstract II
致謝 III
目錄 IV
表目錄 VII
圖目錄 VIII
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機與目的 2
1.3 論文概述 2
第二章 基礎理論與相關文獻 3
2.1 開局設計 3
2.2 定式設計 3
2.3 棋串表示法 4
2.4 棋塊表示法 5
2.5 蒙地卡羅演算法 6
2.6 樹狀結構信賴上界演算法 8
2.7 蒙地卡羅信賴上界樹搜尋的平行化 11
第三章 對局策略 13
3.1 著手產生 13
3.1.1 評估函數 13
3.1.2 棋型比對 20
3.1.3 單官搜尋 24
3.1.4 棋塊潛在的眼位 24
3.1.5 地域處理系統 25
3.1.6 基本死活型 26
3.1.7 棋塊交界著手加成 26
3.2 改進蒙地卡羅信賴上界樹演算策略 27
3.2.1 信賴上界樹的分支裁減 28
3.2.2 利用專家知識改善模擬品質 29
3.2.3 Rapid Action Value Estimation 30
3.2.4 漸進化加速模擬 32
第四章 對局實驗與各類方法比較測試 33
4.1 實驗用程式介紹 33
4.2 實驗方法與數據 33
4.2.1 候選點裁減排序準確率 33
4.2.2 從棋譜探勘棋型出現頻率與領域分數範圍 35
4.2.3 信賴上界樹節點裁減與否 38
4.2.4 蒙地卡羅模擬過程中的各類策略獨立測試 38
4.2.5 綜合測試 39
4.3 實驗結果探討與心得分享 40
4.3.1 實驗結果分析 40
4.3.2 空盤面測試法 41
4.3.3 成果簡介 41
第五章 結論與未來發展 43
5.1 結論 43
5.2 未來發展 43
參考文獻 45

【1】P. Audouard, G. Chaslot, J.-B. Hoock, J. Perez, A. Rimmel, O.Teytaud, "Grid coevolution for adaptive simulations; application to the building of opening books in the game of Go", 2009.
【2】Bruno Bouzy, Tristan Cazenave, "Computer Go: an AI Oriented Survey".
【3】Guillaume M.J-B. Chaslot, Mark H.M. Winands and JOS W.H.M. UITERWIJK MICC-IKAT, "Progressive Strategies For Monte-Carlo Tree Search", 2007-8-30.
【4】Guillaume M.J-B. Chaslot, Mark H.M. Winands, and H. Jaap van den Herik, "Parallel Monte-Carlo Tree Search", 2008-11-07.
【5】Guillaume M.J-B. Chaslot, Louis Chatriot, C. Fite, Sylvain Gelly, and Jean-Baptiste, "Combining expert, offline, transient and online knowledge in Monte-Carlo exploration", 2008-12-03.
【6】Keh-Hsun Chen, Dawei Du, and Peigang Zhang, "A Fast Indexing Method for Monte-Carlo Go", Computers and Games 2008，pages 92-101, 2008.
【7】Rémi Coulom, "Computing “Elo Ratings” of Move Patterns in the Game of Go.", ICGA Journal, Vol. 30, No. 4, pp. 198-208, December 2007.
【8】Sylvain Gelly and David Silver, "Achieving Master Level Play in 9 × 9 Computer Go", AAAI 2008, p. 1537-1540, July 13-17, 2008.
【9】Sylvain Gelly, Yizao Wang, R´emi Munos, and Olivier Teytaud, "Modification of UCT with Patterns in Monte-Carlo Go", Technical Report 6062, INRIA, 2006.
【10】Zhiqing Liu, Qing Dou, and Benjie Lu, "Frequency Distribution of Contextual Patterns in the Game of Go", Computers and Games 2008，pages 125-134, 2008.
【11】Ling Zhao and Martin M¨uller, "Using Artificial Boundaries in the Game of Go", Computers and Games 2008, pages 81-91, 2008.
【12】佛蘭克(Karen A. Frenkel) 撰文、王怡文 翻譯，"電腦進軍圍棋界"，科學人雜誌2007年7月號。
【13】許家平、陳擎文，"電腦圍棋製作與棋型勢力分析之研究"，2006全國數位內容學術研討會，2006。
【14】許家平、陳擎文，"電腦圍棋棋串表示法及其應用"，第11屆人工智慧與應用研討會，2006。
【15】許家平、顏士淨，"從圍棋棋譜擷取棋型之探勘技術"，2007全國計算機會議，2007。
【16】顏士淨，"電腦圍棋程式Jimmy 5.0 之設計與製作"，國立台灣大學資訊工程研究所，博士論文，1999。
【17】顏士淨、嚴礽麒、許舜欽，"電腦圍棋中盤著手策略"，國立東華大學資訊工程研究所、國立台灣大學資訊工程研究所，2002。