平行化蒙地卡羅圍棋程式之研究

A Study on Parallelizing MCTS Go Program

陳文誠(Wen-Cheng Chen)

指導教授 ： 周信宏

長榮大學/資訊暨工程學院/資訊管理學系(所)/碩士(2014年)

https://doi.org/10.6833/CJCU.2014.00055

摘要

以Monte Carlo Tree Search 演算法實作的電腦圍棋近年來開始嶄露頭角，然而在時間的限制下，模擬結果的精確度往往不佳。因此，如何使該方法在短時間內有較高的勝率便成了重要的研究方向。
本論文對於上述問題提出兩種解決方式：以多執行緒的GPU架構為基礎實作CUDA平行化的專家知識庫搜尋系統，藉由降低專家知識庫的比對時間，提供後續有更充足的時間模擬棋局。另一方面，本文運用Hadoop容易建置平行化系統的特性，透過Hadoop Streaming工具將UCT程式分散到此平行環境底下的電腦節點，並使用主從式架構的設計方式，讓現有的圍棋程式Wingo立即地接收並統整各個機器上的模擬結果，從中找出最佳的一手。
實驗結果顯示，若專家知識庫規模持續成長，相較於單機搜尋CUDA平行搜尋系統能省下更多時間。而Wingo圍棋程式導入Hadoop平行化系統後，對抗單機版Wingo時，模擬次數雖然減少卻還能保持壓倒性的優勢。

關鍵字

蒙地卡羅搜尋樹 ； 統一計算架構 ； Hadoop ； Hadoop Streaming ； 主從式架構

並列摘要

The Monte Carlo Tree Search algorithm for implementing computer Go program became popular in recent years. The success of the algorithm is relied on the number of simulations. However, because of the time limitation, it is an important issue to generate a large amount of simulations in a short time.
In order to enhance the power of the computer Go program, we study the parallelization of our computer Go program- Wingo. We implement two parts of Wingo with parallelization. One is the parallel query system for the Go book, which is implemented by CUDA. The other is the parallelization of UCT tree search. We use Hadoop Streaming tools, which is presented by Apache, to parallelize the UCT tree search.
Experimental results show that the parallelized Wingo program behaves much better than the sequential Wingo.

並列關鍵字

Monte-Carlo tree search ； CUDA ； Hadoop ； Hadoop Streaming ； Client-Server model

參考文獻

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

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

[6] 賴柔羽（民國 101），「棋形導向的蒙地卡羅電腦圍棋程式之設計與製作」，長榮大學資訊管理研究所，碩士論文。

[9] 龔建銓（民國 88），「使用 GPU 平行運算加速電腦象棋之走子產生器」，國立成功大學工程科學研究所，碩士論文。

[12] Berliner, H.J. (1980), “Computer Backgammon,” Scientific American, Vol. 242, No. 6, pp. 64-72.