電腦博奕在人工智慧領域中，一直是引人關注的，在深藍打敗西洋棋棋王Karsparov之後，象棋由於複雜度與西洋棋接近，在資料結構與搜尋演算法方面與西洋棋有許多相似或共通之處，成為下一個最有可能打敗人類棋王的棋類遊戲，近年來也吸引了許多人投入研究。
本論文介紹電腦象棋程式“深象”(取得了在義大利杜林舉辦之第十一屆Computer Olympiad象棋比賽銅牌)的基本資料結構、搜尋演算法與審局函數的設計，以及對所使用的資料結構與搜尋演算法進行測試與分析，並針對提高棋力的核心－審局函數，提出我們的改進方案。

關鍵字:電腦象棋、搜尋演算法、審局函數、人工智慧。

Computer chess is always deeply concerned in the field of artificial intelligence. Computer Chinese chess is most possibly the next game to defeat the top human player after DeepBlue defeated the best human chess player Kasparov. Many researchers started studying computer Chinese chess since the complexity of Chinese chess is a little higher than that of chess and both the data structure and search algorithms are similar with each other.
This thesis introduces the basic data structures, search algorithms, and evaluation function of computer Chinese chess “Deep Elephant” (won the bronze medal of 11th Computer Olympiad hold in Turin, Italy) and gives the experimental results and analyses of the data structures and search algorithms it used. Finally, we propose some improvements aimed at the evaluation function－the core of strengthening the ability of the program.

Keywords : artificial intelligence, computer Chinese chess, search algorithm, evaluation function.

[1] A. L. Brudno,“Bounds and Valuations for Abridging the Search of Estimates”, Problems of Cybernetics 10 (1963), 255-241. Translation of Russian original in Problemy Kibernetiki 10, 141-150, May 1963.
[2] A. Reinefeld,“An Improvement of the Scout Tree-Search Algorithm”, Int. Computer Chess Assoc. J. 6, 4, 4-14, 1983.
[3] Aske Plaat, Jonathan Schaeffer, Wim Pijls and Arie de Bruin,“Nearly Optimal Minimax Tree Search”, Technical Report 94-19, Department of Computing Science, University of Alberta, December 1994.
[4] Beal, D.F.,“Experiments with the Null-Move”, Advances in Computer Chess 5, p.65-79.Elsevier Science Publishers, Amsterdam, The Netherlands.
[5] Christian Donninger,“Null Move and Deep Search : Selective Search Heuristics for Obtuse Chess Programs”, ICCA Journal, 16(3):137-143, Sep. 1993.
[6] Claude E. Shannon,“Programming a Computer for Playing Chess”, Philosophical Magazine, Ser. 7, Vol. 41, No. 314, Mar. 1950.
[7] D. E. Knuth and R. W. Moore,“An Analysis of Alpha-beta Pruning”, Artificial Intelligence 6, 4, 293-326, 1975.
[8] D. J. Slate and L. R. Atkin,“CHESS 4.5 – The Northwestern University Chess Program”, Chess Skill in Man and Machine, P. Frey(ed.) Springer-Verlag, 226-324, 1988.
[9] Goetsch G. and Campbell M. S.“Experiments with the Null-Move Heuristic”, Computers, Chess, and Cognition, pp. 159-168. Springer-Verlag, New York.
[10] H. Kaindl,“Dynamic Control of the Quiescence Search in Computer Chess”, Cybernetics and Systems Research, R. Trappl (ed.), North-Holland, Amsterdam, 973-977, 1982.
[11] J. Gillogly,“The technology Chess Program”, Artificial Intelligence 3, 1-4, 1972.
[12] K. Thompson,“Advances in Computer Chess”, volume 3, p. 55-56, Oxford,1982.

[13] Murray Campbell, A. Joseph Hoane Jr., Feng-hsiung Hsu,“Deep Blue”, Artificial Intelligence, Volume 134 , Issue 1-2, Jan. 2002.
[14] R. D. Greenblatt , D. E. Eastlake and S. D. Crocker,“The Greenblatt Chess Program”, Fall Joint Computing Conf. Procs. Vol. 31, (San Francisco, 1967) 801-810. Also in D. Levy (ed.), Computer Chess Compendium, Springer-Verlag, 56-66, 1988.
[15] 王驕, 王濤, 羅豔紅, 徐心和,“中國象棋電腦博弈系統評估函數的自適應遺傳演算法實現”, 東北大學學報(自然科學版) Vol. 26, No. 10, Oct. 2005.
[16] 涂志堅,“電腦象棋的設計與實現”, 中山大學碩士論文, 2004.
[17] 許舜欽, 黃東輝,“中國象棋知識庫之設計與製作”, 全國計算機會議論文集, 頁505-509,1985.
[18] 許舜欽,“電腦西洋棋和電腦象棋的回顧與前瞻”, 電腦學刊, 第二卷, 第二期,頁1-8,1990.
[19] 曹國明,“智慧型中國象棋程式的設計和製作”, 國立台灣大學資訊工程研究所碩士論文, 1988.
[20] 陳志昌,“電腦象棋開局知識庫系統之設計與製作”, 國立台灣大學資訊工程研究所碩士論文, 1998.
[21] 張躍騰,“人造智慧在電腦象棋的應用”,國立台灣大學電機工程研究所碩士論文,1981.
[22] 黃少龍, “象棋教材”, 第四卷, 蜀蓉棋藝出版社, 1995年三月初版.
[23] 董昱驣,“電腦象棋程式達奕設計與製作”,國立東華大學資訊工程研究所碩士論文,1992.
[24] 廖嘉誠,“利用計算機下象棋之實驗”,國立交通大學計算機工程研究所碩士論文,1982.
[25] 範德軍, http://bbs.elephantbase.net/viewthread.php?tid=640&fpage=3.