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

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

鄧涵憶(HAN-I TENG)

指導教授 ： 周信宏

共同指導教授 ： 許舜欽(Shun-Chin Hsu)

長榮大學/資訊暨工程學院/資訊管理學系(所)/碩士(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.

並列關鍵字

Computer Go ； Parallel computing ； Pattern mining ； Go opening database

參考文獻

[5]游明倫（民國 102），「分散式電腦圍棋棋譜搜尋系統之建置」，長榮大學資訊管理學研究所，碩士論文， 2013。

[7]陳勝凱（民國 99），「圍棋棋形擷取、編輯與查詢系統之製作」，長榮大學資訊管理學系研究所，碩士論文，2010。

[9]顏士淨、嚴礽麒、許舜欽(民國105)，「電腦圍棋四十年」，數理人文，第10期，pp.47-53。

[12]嚴礽麒（民國 95），「九路電腦圍棋程式GoKing的設計與製作」，國立臺灣大學資訊工程學研究所，博士論文，2006。

[1]許家平、顏士淨，「從圍棋棋譜擷取棋形之探勘」，2007全國計算機會議，2007。