標題: 平行蒙地卡羅樹狀搜尋之軟體框架
Software Framework for Parallel Monte Carlo Tree Search
作者: 廖挺富
Liao, Ting-Fu
吳毅成
Wu, I-Chen
資訊科學與工程研究所
關鍵字: 蒙地卡羅樹狀搜尋;軟體框架;平行化;電腦對局;Monte Carlo Tree Search;Software Framework;Parallelization;Computer Game
公開日期: 2013
摘要: 在本篇論文中,我們設計出了一個軟體框架,能協助遊戲人工智慧的開發者,快速開發基於平行化蒙地卡羅樹狀搜尋的人工智慧。這個框架實作了與系統相關的細節,能夠使開發者能夠快速地建立起人工智慧,並專注在遊戲相關的專家知識強化上。 這個框架支援在共享記憶體架構以及分散式系統的平行,經測試可在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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT070056001
http://hdl.handle.net/11536/73308
Appears in Collections:Thesis