本論文的目的在於找到一個快速驗證開局庫是否適合AI程式的方式，使得程式編寫者在改變開局庫資料及AI程式時，不用擔心需要花許多時間在銜接開局庫與AI程式的搭配上。我們進一步提出幾種可增進效能的策略，並且實驗比較何種策略在驗證開局庫上能增進較多的效能。
根據我們的實驗顯示，本論文提出的job-level SSS* opening確實能更快速驗證象棋開局庫，且更新所有父節點跟有限度的中止工作能更進一步增進效能，達到本論文的目的。

The main goal of this thesis is to find a quick way to verify if an opening is suitable for an AI program or not. The programmer would spend less time on changing the opening data and the AI program while merging opening into the AI program. Furthermore, we propose some strategies that could enhance the effectiveness and find the one of which benefits much. According to our experiment, this thesis showed that the job-level SSS* opening method performs more quickly than other methods.

第一章 緒論 1
1.1 象棋介紹及規則 1
1.2 電腦象棋的發展 1
1.3 研究動機 2
1.4 主要貢獻 2
1.5 論文大綱 3
第二章 研究背景 4
2.1 開局庫 4
2.1.1 象棋開局 4
2.1.2 電腦象棋開局庫 4
2.2 開局統計與中局審局一致性策略 5
2.3 AB-SSS* 5
2.3.1 Minmax Search 6
2.3.2 Alpha-Beta Search 7
2.3.3 SSS* 8
2.3.4 AB-SSS* 8
2.4 CGDG 12
2.4.1 系統架構 12
2.4.2 工作層級 13
第三章 設計方法 14
3.1 JL-SSS* Opening介紹 14
3.2 使用SSS*的優勢 15
3.2.1 使用SSS*作為選點演算法 15
3.2.2 實作上使用AB-DUAL* 15
3.2.2.1 DUAL*的特性 15
3.2.2.1 AB-DUAL*的好處 16
3.3 平行化的選點方式 16
3.3.1 Virtual Fail 17
3.3.2 SSS* Pass 1的特性 18
3.4 開局樹獨立盤面的問題 19
3.5 修剪的特性 20
3.5.1 Alpha-Beta Search的修剪 20
3.5.2 AB-DUAL*的修剪 21
3.6 執行中止工作的策略探討 23
3.6.1 策略A：發生修剪就中止工作 23
3.6.2 策略B：一律不中止工作 26
3.6.3 策略C：確定不會再被拜訪才中止工作 27
3.6.4 策略D：幾乎不會再被拜訪才中止工作 28
3.7 更新所有父節點 29
第四章 實驗分析與討論 30
4.1 實驗環境 30
4.2 開局樹 30
4.3 實驗結果圖表簡寫說明 31
4.4 DUAL*與Alpha-Beta的比較 32
4.5 DUAL*與增進策略的搭配比較 33
4.6 各核平行化增加效率 36
第五章 結論與未來展望 39
參考資料 41

[1] 陳志昌（2005）。 電腦象棋知識庫系統之研製。
[2] 陳靖平、吳毅成（1999）。適用於六子棋應用的網格計算系統。
[3] 陳昱維、吳毅成（2011）。適用於電腦遊戲之志願型計算系統仲介者。
[4] 許舜欽, 曹國明 （1991）。電腦象棋開局知識庫系統之研製，台灣大學工程學刊，第五十三期，頁75─86。.
[5] 鄒忻芸、吳毅成（2000）。CGDG桌機格網之應用層框架一般化與資源分配管理。
[6] 韓尚餘、吳毅成（2011）。適用於電腦對局遊戲之志願型計算系統工作端。
[7] Bruce Moreland's Programming Topics Site, available at http://brucemo.com/compchess/programming/index.htm
[8] J.P. Fishburn (1980). An optimization of alpha-beta search, SIGART Bulletin, Issue 72.
[9] J.P. Fishburn (1983). Another optimization of alpha-beta search, SIGART Bulletin, Issue 84.
[10] ICGA Tournaments, available at http://www.grappa.univ-lille3.fr/icga/
[11] International Computer Games Association, available at http://ilk.uvt.nl/icga/
[12] D.E. Knuth and R.W. Moore (1975). An analysis of alpha-beta pruning, Artificial Intelligence, 6:293–326.
[13] T. Marsland, A. Reinefeld, and J. Schaeffer (1987). Low Overhead Alternatives to SSS*. Artificial Intelligence, Vol. 31, No. 2, pp. 185-199. ISSN 0004-3702.
[14] J. von Neumann and O. Morgenstern (1944). Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ.
[15] A. Plaat, J. Schaeffer, W. Pijls, and A. de Bruin(1994). SSS* = a-b + TT. Technical Report TR-CS-94-17, Department of Computing Science, University of Alberta, Edmonton, AB, Canada.
[16] A. Plaat, J. Schaeffer, W. Pijls and A. de Bruin (1995). A Minimax Algorithm Better than Alpha-Beta? No and Yes. TR-95-15, Department of Computing Science, University of Alberta, Edmonton, AB, Canada.
[17] A. Plaat, J. Schaeffer, W. Pijls and A. de Bruin (1996). Best-First Fixed-Depth Minimax Algorithms. Artificial Intelligence, Vol. 87, Nos. 1-2, pp. 255-293. ISSN 0004-3702.
[18] A. Plaat, J. Schaeffer, W. Pijls and A. de Bruin (1999). A Minimax Algorithm better than SSS*. Artificial Intelligence, Vol. 87, pp. 255–293. ISSN 0004-3702.
[19] J. Pearl (1980). Scout: A Simple Game-Searching Algorithm with Proven Optimal Properties. Proceedings of the First Annual National Conference on Artificial Intelligence, pp. 143-145.
[20] I. Roizen and J. Pearl (1983). A Minimax Algorithm Better than Alpha-Beta? Yes and No. Artificial Intelligence, Vol. 21, pp. 199-230.
[21] G.C. Stockman (1979). A minimax algorithm better than alpha-beta? Artificial Intelligence, 12(2):179–196.
[22] J.R. Slagle and J.K. Dixon (1969). Experiments with some programs that search game trees, JACM 16, 2 189-207.
[23] I.C. Wu, H.H. Lin, P.H. Lin, D.J. Sun, Y.C. Chan, B.T. Chen. (2010). Job-Level Proof Number Search For Connect6. Computers and Games.
[24] WIKIPEDIA, Chinese Chess, available at http://en.wikipedia.org/wiki/Chinese_Chess
[25] S.J. Yen, J. C. Chen, T. N. Yang and S.C. Hsu (2004). Computer Chinese Chess. ICGA Journal, Vol. 27, No. 1. pp. 3-18.