平行蒙地卡羅樹狀搜尋之軟體框架

Software Framework for Parallel Monte Carlo Tree Search

廖挺富(Ting-Fu Liao)

指導教授 ： 吳毅成

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2013年)

https://doi.org/10.6842/NCTU.2013.00600

摘要

在本篇論文中，我們設計出了一個軟體框架，能協助遊戲人工智慧的開發者，快速開發基於平行化蒙地卡羅樹狀搜尋的人工智慧。這個框架實作了與系統相關的細節，能夠使開發者能夠快速地建立起人工智慧，並專注在遊戲相關的專家知識強化上。
這個框架支援在共享記憶體架構以及分散式系統的平行，經測試可在Windows系統以及Linux系統執行，並且已套用至雙人完整資訊(perfect information)遊戲、雙人不完整資訊(imperfect information)遊戲以及單人遊戲上。我們的實驗使用圍棋版本的實作；在共享記憶體平行化中，使用48核心可以達到36.08倍的模擬次數，與單核心版本對戰，使用12核心可以達到90%以上勝率。在分散式平行化下，我們比較單一台機器與8台機器各使用36核心，分別與Fuego對戰，勝率從23%提升至68%。除圍棋外，亦套用至禁圍棋、暗棋等遊戲上；其中圍棋利用此平行框架，同時使用576核心進行運算，在十七屆電腦奧林匹亞電腦對局競賽中，獲得第四名。

關鍵字

蒙地卡羅樹狀搜尋 ； 軟體框架 ； 平行化 ； 電腦對局

並列摘要

In this thesis, we design a software framework for developing computer games based on parallel Monte-Carlo tree search. This framework hides the game-independent details from developers, so that developers can concentrate on improving heuristics related to game-specific knowledge.
This framework supports parallelization in both shared-memory and distributed systems, and cross-platform in both Windows and Linux operating systems. In our experiments, we use the implementation of Go. In shared-memory parallelization, the speedup is 36.08 for 48 cores, and the winning rate against the single core version is more than 90% for 12 cores. In distributed-memory system, the winning rate for one machine with 36 cores against Fuego is 23%, while that for 8 machines each with 36 cores is 68%, about 45% higher. In addition to Go, we also applied this framework to another two-player perfect-information games, NoGo, a two-player imperfect-information game, Dark chess, and a single player game, 8 puzzle. The one for Go using a total of 576 cores won the 4th place in the 17th Computer Olympiad, held in Yokohama, Japan, 2013.

並列關鍵字

Monte Carlo Tree Search ； Software Framework ； Parallelization ； Computer Game

參考文獻

[4] Browne, C., Monte Carlo Tree Search, http://mcts.ai/.

[5] Bruegmann B., Monte Carlo Go. White paper, 1993.

[6] Chaslot G.M.J.B., Winands M.H.M., and H.J. van den Herik. Parallel monte-carlo tree search. Proceedings of the Conference on Computers and Games 2008.

[9] Coulom, R., Monte Carlo tree search in crazy stone. Game Programming Workshop, pp. 74–75, Tokyo, Japan, 2007.

[11] Enzenberger M., Muller M., Fuego - An Open-source Framework for Board Games and Go Engine Based on Monte-Carlo Tree Search, IEEE Transactions Computational Intelligence and AI in Games, 2009.