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

Abstract

在本篇論文中，我們設計出了一個軟體框架，能協助遊戲人工智慧的開發者，快速開發基於平行化蒙地卡羅樹狀搜尋的人工智慧。這個框架實作了與系統相關的細節，能夠使開發者能夠快速地建立起人工智慧，並專注在遊戲相關的專家知識強化上。 這個框架支援在共享記憶體架構以及分散式系統的平行，經測試可在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.