臺灣博碩士論文加值系統

電腦西洋棋在近年來已經大量使用平行搜尋演算法，目前表現最好的是使用DTS（Dynamic Tree Splitting）搜尋演算法，該演算法的作者Robert M. Hyatt所設計出來的電腦西洋棋程式Crafty也在2004年第12屆World Computer Speed Chess Championship比賽獲得第二名。
本篇論文主要研究DTS（Dynamic Tree Splitting）搜尋演算法，發現使用一些改良技巧，如改良方法一的控制CPU分配量與改良方法二的控制允許使用DTS搜尋演算法的最低層數，能將DTS（Dynamic Tree Splitting）搜尋演算法在電腦西洋棋程式中獲得更好的效能。我們也使用開放程式碼的Crafty20.14版做實驗，目前研究結果發現改良方法一能提升20％左右的效能，而改良方法二能提升35％左右的效能。

摘 要 ii
ABSTRACT iii
目錄 vi
附表目錄 vii
附圖目錄 viii
第一章 緒論 1
第一節 前言 1
第二節 研究動機及目的 2
第三節 論文架構 3
第二章 平行Alpha-Beta搜尋演算法 4
第一節 前言與Alpha-Beta搜尋演算法 4
第二節 三種節點分類 6
第三節 PVS搜尋演算法 7
第四節 EPVS搜尋演算法 9
第五節 DTS搜尋演算法 10
第三章 DTS搜尋演算法效能改良 13
第一節 過去的效能與實驗數據發現 13
第二節 改良方法一：橫向思考 15
第三節 改良方法二：縱向思考 18
第四章 效能分析 21
第一節 改良方法一的實驗結果 21
第二節 改良方法一簡易的分析及驗證方法 25
第三節 改良方法二的實驗結果 28
第五章 結論與未來研究方向 33
第一節 結論 33
第二節 未來研究方向 35
附錄 36
附錄A Crafty測試的12個盤面資訊 36
附錄B 深象測試的10個盤面資訊 32
參考文獻 47

【1】Beal, D. F.,“Experiments with the Null-Move”, Advances in Computer Chess ,Vol. 5, pp.65-79, 1989.
【2】Brudno, A. L., “Bounds and Valuations for Abridging the Search of Estimates”, Problems of Cybernetics, Vol. 10, pp.255-241, 1963.
【3】Donninger, C.,“Null Move and Deep Search : Selective Search Heuristics for Obtuse Chess Programs”, ICCA Journal, Vol. 16, No. 3, pp.137-143, 1993.
【4】Goetsch, G., and Campbell, M. S.,“Experiments with the Null-Move Heuristic”, Computers, Chess, and Cognition, pp. 159-168, 1988.
【5】Greenblatt, R. D., Eastlake, D. E., and Crocker, S. D.,“The Greenblatt Chess Program”, Fall Joint Computing Conf. Procs. Vol. 31, pp.801-810, 1967.
【6】Hyatt, R. M., Suter, B. W., and Nelson, H. L., “A Parallel Alpha/Beta Tree Searching Algorithm”, Parallel Computing , Vol. 10, No.3 , pp.299-308, 1989.
【7】Hyatt, R. M., “The DTS High-Performance Parallel Tree Search Algorithm”, ICCA Journal , Vol. 20, No. 1, pp.3-19, 1997.
【8】Kaindl, H.,“Dynamic Control of the Quiescence Search in Computer Chess”, Cybernetics and Systems Research, pp.973-977, 1982.
【9】Knuth, D. E. and Moore, R. W., “An Analysis of Alpha-beta Pruning”, Artificial Intelligence, Vol. 6, No. 4, pp.293-326, 1975.
【10】Marsland , T. A. and Campbell, M. S., “Parallel Search of Strongly Ordered Game Tree”, ACM Computing Surveys, Vol. 14, No. 4, pp.533-551, 1982.
【11】Plaat, A., Schaeffer, J., Pijls, W., and Bruin, A. de,“Nearly Optimal Minimax Tree Search”, Technical Report ,Vol. 19, 1994.
【12】 李任軒,“電腦象棋知識庫切捨技術”, 國立台灣師範大學資訊工程研究所碩士論文, 2006.
【13】許舜欽,黃東輝,“中國象棋知識庫之設計與製作”, 全國計算機會議論文集, 頁505-509, 1985.
【14】張躍騰,“人造智慧在電腦象棋的應用”,國立台灣大學電機工程研究所,碩士論文, 1981.
【15】 黃文樟,“電腦象棋深象中局程式的設計與實作”, 國立台灣師範大學資訊工程研究所碩士論文, 2006.
【16】 陳志昌,“電腦象棋開局知識庫系統之設計與製作”, 國立台灣大學資訊工程研究所碩士論文, 1998.