工作層級應用之軟體開發框架

在電腦遊戲的領域中，有許多平行化運算的方法被提出，其中的工作層級演算法已被成功用來建構開局庫以及解出部分六子棋的開局。目前已被提出的工作層級應用有工作層級證明數搜尋演算法用於六子棋、工作層級上界信賴樹演算法用於六子棋、Hex及工作層級alpha-beta搜尋演算法用於象棋，這些應用被獨立開發，卻有許多行為相似可以被共享，例如和工作層級系統的溝通以及最佳優先搜尋演算法(BFS)的通用行為等等。在本論文中，我們提出了一個工作層級應用的軟體開發框架，該框架實作了底層的溝通行為，並開放介面讓開發人員發展其應用，我們的框架更進一步提供BFS的基本模組，並成功分離出演算法相關部分及遊戲相關部分，讓不同的開發者得以獨立實作其演算法或遊戲。在案例研究中，我們的框架撰寫了一萬多行的程式碼，透過充分的共享，讓開發者只需要數百行的程式碼便能輕易開發出新的工作層級應用，由此可見透過我們的框架可以讓工作層級應用的開發更有效率。

關鍵字

工作層級運算；電腦對局；軟體框架

並列摘要

In computer games, many parallelization techniques of game-playing programs are proposed. Job-Level (JL) Computing is one of the techniques which is based on distributed computing, and was successfully used to construct the opening books of game-playing programs. It was also used to solve several Connect6 opening positions. Recently, various JL applications such as JL proof number search for Connect6, JL upper confidence tree for Connect6 and Hex, and JL alpha-beta search for Chinese chess were proposed. While these JL applications were developed independently, the communication with JL systems and the procedures of best-first search (BFS) are common and can be shared. In this thesis, we design a software framework for JL applications. This framework implements the low-level behaviors of the communication to JL systems and provides an interface for JL application developers to develop their applications easily. Furthermore, this framework provides some common modules for BFS and separates the algorithm-specific and game-specific behaviors of best-first JL applications. With this JL framework, JL algorithm developers and game developers can focus on their parts independently. Consequently, JL application developers can easily combine different algorithms and games together as a new JL application. In our case studies, only hundreds of lines of code are required for developments of JL applications, while the code for JL framework requires more than ten thousand of lines of code. This demonstrates that efforts were greatly reduced by using this framework.

並列關鍵字

job-level computing ； computer games ； software framework

參考文獻

[2] Allis, L.V., van der Meulen, M., and Van Den Herik, H.J.: ‘Proof-number search’, Artificial Intelligence, 1994, 66, (1), pp. 91-124

[11] Chaslot, G.M.-B., Winands, M.H., and van Den Herik, H.J.: ‘Parallel monte-carlo tree search’: ‘Computers and Games’ (Springer, 2008), pp. 60-71

[29] Saito, J.-T., Winands, M.H., and van den Herik, H.J.: ‘Randomized parallel proof-number search’: ‘Advances in Computer Games’ (Springer, 2010), pp. 75-87

[36] Winands, M.H., Uiterwijk, J.W., and van den Herik, J.: ‘PDS-PN: A new proof-number search algorithm’: ‘Computers and Games’ (Springer, 2003), pp. 61-74

[3] Alus, L., and Huntjens, M.: ‘GO‐MOKU SOLVED BY NEW SEARCH TECHNIQUES’, Computational Intelligence, 1996, 12, (1), pp. 7-23

國際替代計量

工作層級應用之軟體開發框架

全文下載

主題瀏覽