工作層級運算系統之研究與設計

On Job-Level Computing

魏廷翰(Ting-Han Wei)

指導教授 ： 吳毅成

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

摘要

工作層級運算模式(job-level computing model)為一種汎用的分散式計算模式。其運作方式將大問題拆解成許多小工作(jobs)，再利用現有的遊戲程式來計算這些工作，進而得到解答。過去，此工作層級運算系統成功證明出許多六子棋開局。本論文在既有的工作層級運算系統上，再提出一系列的改進。首先，本論文提出了一套軟體架構，並介此架構重構原系統的設計，使得開發者能更輕鬆地撰寫新的演算法、遊戲種類，與應用程式。本論文並深入介紹工作層級證明數搜尋法(JL-PNS)及工作層級蒙地卡羅搜尋法(JL-UCT)。
本論文亦提出五個改進工作層級系統的新功能，分別為：工作層級可用的換位表(transposition table)、讓搜尋樹規模可更大的遠端資料庫存取機制、加快運算速度的快取機制、利用BOINC來追加志願型運算資源，以及利用工作層級系統來當人工智慧程式選步，參加線上六子棋比賽。
在實現工作層級應用程式的部份，本論文提出使用前述工作層級蒙地卡羅搜尋法來自動製作六子棋開局庫的應用。新的開局庫在與無開局庫的同版程式對打下，可達到61%的勝率。與先前的工作層級證明數搜尋法生成的開局庫對打下，可達到56%的勝率。
由於分散式計算系統具有一定程度的不穩定性，例如說網路狀況不一定會一直通暢無阻，或是計算資源的網格電腦們可能會有錯誤或回應時間不一，名為「加速指數異常」(speedup anomaly)的現象偶爾會發生。此異常現象的其中一種表徵，是當計算資源增加的同時，加速指數是有可能反而下降的。為了解決此問題，也為了讓工作層級運算系統的實驗，在相同的參數下可保證重現性，本論文提出雙層疊工作層級運算系統(two-tier job-level system)。實驗數據顯示，當問題大小漸大時，此雙層疊功能的運算成本(overhead)增加的速度反而會減緩。換句話說，此功能正適合拿來執行規模大的實驗，可以同時克服加速異常的現象、保證實驗重現性，且同時只須付出較少的運算成本。

關鍵字

分散式計算 ； 志願型計算 ； 電腦遊戲

並列摘要

The job-level (JL) computing model is a generic distributed computing scheme that decomposes a larger problem into smaller jobs, then leverages existing game-playing programs to compute these jobs in parallel. It has been successful in the past in position analysis and opening book construction. This dissertation builds upon prior successes by first redesigning the JL computing system into modularized components, separated based on developer roles. This new software framework enables the search algorithm developer, game type developer, and application developer to work independently. By doing so, new JL applications can be implemented with very little effort, while simultaneously improving code reuse and maintainability. Two best-first JL search algorithms are discussed in detail, the job-level Proof-number search (JL-PNS) algorithm and the job-level upper confidence bound tree (JL-UCT) algorithm.
Five new features are also added to the JL system. First, to implement a transposition table for JL search trees, the search tree is stored in a new unified format. Second, for problem size scalability, JL search trees can be stored in remote databases instead of in local memory. Third, a caching mechanism is designed to speed up the overall computation. The caching mechanism, when enabled, can be up to 18 times faster than when it is not used. Fourth, to leverage more volunteer workers and take advantage of additional computing resources, a method to combine JL systems with BOINC is proposed. Lastly, we demonstrate that the JL system can be used as a game-playing agent. By playing on the website Little Golem, the JL player won 12 of 18 Connect6 tournaments from 2009-2018, for a total of 205 in 228 games (90% win rate). A win/loss database is also proposed so that the JL player can take advantage of previously analyzed winning/losing positions.
A case study of a JL application is the automatic construction of Connect6 opening books using JL-UCT. JL-UCT has the benefit of being designed to choose the best move to play. Using the JL-UCT generated opening book, our Connect6 program NCTU6 can achieve 61% win rate against the same version of itself without an opening book. Comparing between opening books from JL-UCT and JL-PNS, the former can achieve win rates of about 56%.
Finally, the two-tier job-level (2T-JL) system is proposed. 2T-JL contains two separate trees: the kernel tier search tree is a simulation of a JL search, and is guaranteed to be strictly ordered between different trials of the same experiment, whereas the probe tier behaves exactly the same as a normal JL search. The probe tier performs jobs and provides the job results for the kernel tier, so that it may maintain the strict ordering. The purpose of 2T-JL is to alleviate the instability caused by the speedup anomaly phenomenon, where no guarantees can be made that the speedup will improve as more computing units are added to the distributed computing system. The 2T-JL system can achieve reasonable speedups, and the overhead for providing an additional service on top of the normal JL system decreases as the problem size increases, so it is suitable for large and complex problems.

並列關鍵字

Distributed Computing ； Volunteer Computing ； Computer Games

參考文獻

[1] L.V. Allis, Searching for solutions in games and artificial intelligence, Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands, 1994.

[2] L.V. Allis, M. van der Meulen and H.J. van den Herik, “Proof-number Search,” Artificial Intelligence, vol. 66 (1), pp. 91–124, 1994.

[3] D.P. Anderson, “Boinc: A System for Public-resource Computing and Storage,” Proceedings of the Fifth IEEE/ACM International Workshop on Grid Computing (GRID'04), IEEE CS Press, Pittsburgh, USA, pp. 4-10, 2004.

[4] P. Audouard, G. Chaslot, J.-B. Hoock, J. Pérez, A. Rimmel and Teytaud, O, “Grid Coevolution for Adaptive Simulations: Application to the Building of Opening Books in the Game of Go,” Workshops on Applications of Evolutionary Computation, pp. 323-332, Springer, 2009.

[5] P. Auer, N. Cesa-Bianchi and P. Fischer, “Finite-Time Analysis of the Multiarmed Bandit Problem,” Machine Learning, vol. 47(2-3), pp. 235-256, 2002.