運用平行化探勘技術萃取圍棋棋形之研究

A Study on Extraction of Computer Go Patterns by Using Parallel Exploration Technology

鄧涵憶

電腦圍棋 ； 平行化運算 ； 棋形探勘 ； 開局知識庫 ； Computer Go ； Parallel computing ； Pattern mining ； Go opening database

長榮大學資訊管理學系(所)學位論文

2016年

碩士

周信宏

繁體中文

目前世界頂尖的電腦圍棋程式大多以蒙地卡羅演算法為發展基礎，蒙地卡羅搜尋樹是一個全域搜尋的演算法，主要概念是透過隨機落子來模擬棋局，根據大量的模擬棋局結果，評估著手的好壞。由於電腦圍棋比賽有時間的限制，因此模擬的棋局數量無法太多，導致棋局模擬結果無法很精確，為了使蒙地卡羅樹搜尋演算法能更精確且快速的判斷棋局盤勢，棋形扮演相當關鍵的角色。 本論文收集二十幾萬九路圍棋高手的對弈棋譜，建置Hadoop雲端平台，運用平行化運算的技術，從棋譜中探勘出重要的棋形，並決定棋形在不同位置的權重，再將棋形加入到使用蒙地卡羅演算法的Wingo電腦圍棋程式，進而建立九路圍棋開局知識庫，從實驗結果證明，將收集的棋形和開局庫結合加入到Wingo電腦圍棋程式可以大幅提升圍棋程式的棋力。

Currently the world's top computer Go programs are mostly based on Monte Carlo algorithm which is a global search algorithm. The Monte Carlo tree search in computer Go is based on many playouts in which the game is played out to the end by selecting moves at random. Since there has time limitation in the tournament, the simulation result of MCTS cannot be very precisely due to lack of a large amount of simulation playouts. In order to make the simulation result more precisely, patterns play an important role. In this research, we use parallel computing technology to mining crucial patterns from a large number of Go game records, and to determine the weight of these patterns at different locations. Finally we build a 9x9 Go opening database by reinforcing learning using the patterns. Results indicate that using patterns and opening database in simulations can greatly enhance the strength of the Go program.

1. [1]許家平、顏士淨，「從圍棋棋譜擷取棋形之探勘」，2007全國計算機會議，2007。
   連結：
2. [5]游明倫（民國 102），「分散式電腦圍棋棋譜搜尋系統之建置」，長榮大學資訊管理學研究所，碩士論文， 2013。
   連結：
3. [7]陳勝凱（民國 99），「圍棋棋形擷取、編輯與查詢系統之製作」，長榮大學資訊管理學系研究所，碩士論文，2010。
   連結：
4. [8]賴柔羽（民國 101），「棋形導向的蒙地卡羅電腦圍棋程式之設計與製作」，長榮大學資訊管理研究所，碩士論文，2012。
   連結：
5. [9]顏士淨、嚴礽麒、許舜欽(民國105)，「電腦圍棋四十年」，數理人文，第10期，pp.47-53。
   連結：
6. [11]嚴礽麒（民國 92），「棋形知識庫之設計與製作」，國立台灣大學資訊工程研究所，2003。
   連結：
7. [12]嚴礽麒（民國 95），「九路電腦圍棋程式GoKing的設計與製作」，國立臺灣大學資訊工程學研究所，博士論文，2006。
   連結：
8. [13]Berliner, H.J. (1980), “Computer Backgammon,” Scientific American, Vol. 242, No. 6, pp. 64-72.
   連結：
9. [18]Ghemawat, S., Gobioff, H., and Leung, S.T. (2003), “The Google file system,” Proceedings of the nineteenth ACM symposium on Operating systems principles, Bolton Landing, NY, USA.
   連結：
10. [22]Mueller, M. (2002), “Computer Go,” Artificial Intelligence, No.134, pp.145-179.
    連結：
11. [24]N.Metropolis, S.Ulam (1949), “The Monte Carlo Method”,Journal of the American Statistical Association, Vol.44, No.247, pp.335-341.
    連結：
12. [25]Pratx, G., and Xing, L. (2011), “Monte Carlo simulation of photon migration in a cloud computing environment with MapReduce.” Journal of Biomedical Optics, Vol.16(12): 125003-1250039.
    連結：
13. [27]Remi Coulom (2007), “Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search” , Lecture Notes in Computer Science 4630, pp. 72 – 83.
    連結：
14. [31]Walter Reitman and Bruce Wilcox (1978), “Pattern recognition and pattern-directed inference in a program for playing Go”, Pattern-Directed Inference Systems, pp. 503—523.
    連結：
15. [32]Zobrist, A. L. (1970), “Feature Extraction and Representation for Pattern Recognition and the Game of Go”, Ph.D. Dissertation, University of Wisconsin.
    連結：
16. [2]許家平(民國98)，「電腦圍棋對局策略研究與分析」，國立東華大學資訊工程研究所，碩士論文，2009。
17. [3]深度學習維基百科，http://zh.wikipedia.org/wiki/深度學習
18. [4]圍棋維基百科，http://zh.wikipedia.org/wiki/圍棋
19. [6]劉東岳（民國 78），「電腦圍棋程式之設計與製作」，國立臺灣大學資訊工程學研究所，碩士論文，1989。
20. [10]嚴礽麒，許舜欽，「Killer Moves Generator之研究與設計」，第六屆人工智慧與應用研討會，2001年11月，pp.162~168。
21. [14]Brugmann, B.(1993),“Monte Carlo Go,” Unpublished teczhnical report.
22. [15]D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot(2016), “ Mastering the game of go with deep neural networks and tree search.” Nature, vol. 529, no. 7587, pp. 484–489.
23. [16]Dean, J. and Ghemawat, S. (2008), “MapReduce: simplified data processing on large clusters,” Communications of the ACM,51, pp. 107-113.
24. [17]Gelly, S. ,Wang, Y. , Munos, R. and Teytaud, O. (2006),“Modification of UCT with patterns in Monte-Carlo Go.” Technical Report 6062, INRIA, France, November.
25. [19]Keh-Hsun Chen, Dawei Du, Peigang Zhang (2008), "A Fast Indexing Method for Monte-Carlo Go", Computers and Games,pp 92-101.
26. [20]Kocsis and C. Szepesvari. (2006),“Bandit based monte-carlo planning.” In 15th European Conference on Machine Learning (ECML), pp. 282–293.
27. [21]MapReduce Tutorial，https://hadoop.apache.org/docs/r2.6.0/hadoop-mapreduce-client/hadoop-mapreduce-client-core/MapReduceTutorial.html#Example:_WordCount_v1.0
28. [23]Newell, A., Shaw, J.C. and Simon, H.A. (1958), “Chess playing programs and the problem of complexity,” IBM Journal of Research and Development, Vol. 4, No. 2. pp. 320-335.
29. [26]Remi Coulom (2007), "Computing Elo Ratings of Move Patterns in the Game of Go", ICGA Journal, Vol. 30.
30. [28]SGF格式，http://www.red-bean.com/sgf/user_guide/index.html
31. [29]Tanguy Urvoy and gnugo team(2002), Pattern Matching in Go with DFA, http://www.irisa.fr/galion/turvoy/papers/dfabstract.ps
32. [30]Tom White, “Hadoop: The Definitive Guide, 4th Edition”, O’Reilly Media Inc.