臺灣博碩士論文加值系統

電腦象棋目前研究主要使用被動式開局庫，其建構方式為收集棋譜並統計整理勝敗等數據。其主要的問題是，使用時若依照統計數據來當作選擇依據，可能選到統計數據顯示為優秀的盤面，但盤面評估程式判斷為不佳。開局庫為保有與評估程式的一致性，避免遭遇上述情況，除了使用統計資料以外，還必須要對開局庫內的葉節點進行盤面評估，然而這是非常大量的計算，因此本論文使用Job Level System來加速運算效率。
一般的Job Level Search是利用平行化發送工作至遠端運算，來加速電腦遊戲程式的運算，因為各個工作能獨立運算，故非常適合分散式運算架構。而本論文提出的方法，是將Job Level Search與AB-DUAL*合併，該演算法由Alpha-Beta Search衍生而來。AB-DUAL*不同於Alpha-Beta Search沒有限制搜尋的分數範圍，其使用了Zero-Window來加速搜尋時的剪裁，因此需要的計算較少，更加適合利用來縮短計算時間。最後在實驗結果中，展示演算法的效能及速率均有大幅改善。

Constructing a passive opening book for Chinese Chess requires the collection of thousands of expert games played on the Internet and filtering and ranking of all positions in the opening book based on factors such as the number of wins/draws/losses. A major issue here is the consistency between the opening book and the game-playing program. That is, the “statistical good” positions could be “weak spots” for game-playing program. In this paper, we evaluate all positions with game-playing program under job-level system to speed up the computation and maintain the consistency for the construction of the Chinese Chess opening book.
Generic job-level search was proposed to solve computer game applications by dispatching jobs to remote workers for parallel processing. This approach leverages game-playing programs and encapsulates them as jobs. Such an approach is well suited for a distributed computing environment, since these jobs can be run independently by remote processors in a job-level system. This paper applies job-level search to AB-DUAL*, which is an extension of Alpha-Beta Search but uses zero-window to increase pruning. In our experiments, the results demonstrate significant performance improvement and speedups.

摘要 i
Abstract ii
目錄 iii
表目錄 iv
圖目錄 v
第一章 緒論 1
1.1. 研究動機 2
1.2. 論文結構 4
第二章 背景 5
2.1. MiniMax Search 5
2.2. Alpha-Beta Search 6
2.3. SSS* 7
2.4. AB-SSS* 7
2.4.1. AB-DUAL* 9
2.5. Job Level System 11
第三章 研究方法 13
3.1. Single Worker Job Level AB-DUAL* 13
3.1.1. 符號定義 13
3.1.2. 演算法 15
3.2. Multi-Worker Job Level AB-DUAL* 17
3.2.1. 符號定義 17
3.2.2. 演算法 17
3.2.3. Abortion 18
3.2.4. Hard Abortion 20
3.2.5. Soft Abortion 20
第四章 實驗及結果 21
第五章 結論與未來展望 23
參考資料 24

[1] Aske Plaat; Jonathan Schaeffer; Wim Pijls; Arie de Bruin; (1994). SSS* = a-b + TT. Technical Report TR-CS-94-17, Department of Computing Science, University of Alberta, Edmonton, AB, Canada.
[2] Aske Plaat; Jonathan Schaeffer; Wim Pijls; Arie de Bruin; (1995). A Minimax Algorithm Better than Alpha-Beta? No and Yes. Technical Report TR-95-15, Department of Computing Science, University of Alberta, Edmonton, AB, Canada.
[3] Aske Plaat; Jonathan Schaeffer; Wim Pijls; Arie de Bruin; (1996). Best-First Fixed-Depth Minimax Algorithms. Artificial Intelligence 87(1-2): 255-293.
[4] Donninger, C. and Lorenz, U., (2006). Innovative Opening-Book Handling. Advances in Computer Games, 11th International Conference (ACG 2005), volume 4250 of Lecture Notes in Computer Science, pp. 1-10. Springer.
[5] George Stockman; (1979). A Minimax Algorithm Better than Alpha-Beta? Artificial Intelligence 12(2):179-196.
[6] Guillaume M.J-B. Chaslot; Jean-Baptiste Hoock; Julien Perez; Arpad Rimmel; Olivier Teytaud; and Mark H.M.Winands; (2009). Meta Monte-Carlo Tree Search for Automatic Opening Book Generation. Proceedings of the IJCAI’09 Workshop on General Intelligence in Game Playing Agents: 7–12.
[7] I-Chen Wu; Hung-Hsuan Lin; Der-Johng Sun; Ping-Hung Lin; Yi-Chih Chan; and Bo-Ting Chen; (2010). Job-Level Proof-Number Search for Connect6. The International Conference on Computers and Games , Kanazawa, Japan, and also the IEEE Transactions on Computational Intelligence and AI in Games, DOI: 10.1109/TCIAIG.2012.2224659.
[8] I-Chen Wu; Hung-Hsuan Lin; Der-Johng Sun; Kuo-Yuan Kao; Ping-Hung Lin; Yi-Chih Chan; Bo-Ting Chen; (2013). Job-Level Proof Number Search. IEEE Trans. Comput. Intellig. and AI in Games 5(1): 44-56
[9] James R. Slagle; John E. Dixon; (1969). Experiments with some programs that search game trees, JACM 16, 2 189-207.
[10] John P. Fishburn (1983). Another optimization of alpha-beta search, SIGART Bulletin, Issue 84.
[11] Jr-Chang Chen (2005). Design and Implemantation of Knowledge-base System for Computer Chinese Chess.
[12] Knuth, D.E., and Moore, R.W. (1975). An Analysis of Alpha-Beta Pruning. Artificial Intelligence 6:293-326.
 
[13] Lung-Ping Chen; I-Chen Wu; Chih-Wei Hsieh; Der-Johng Sun; Hung-Hsuan Lin. (2013). The Development of the Resource Broker of Desktop Grid Federation for Tree Search Applications. Japanese Society for Artificial Intelligence 2013.
[14] Michael Buro; (1999). Toward Opening Book Learning. ICGA Journal 22(2):98-102.
[15] Thomas R. Lincke; (2000). Strategies for the Automatic Construction of Opening Books. International Conference on Computers and Games.