在深藍打敗西洋棋棋王Kasparov之後，因為象棋的遊戲方式與西洋棋差不多，成為下一個最有可能擊敗人類棋王的棋類，所以電腦象棋成為最熱門的研究領域之一。之前深象使用單一CPU循序的方式搜尋，搜尋的深度大約在10層左右，難以加深，為了增進深象的棋力，我們使用Dynamic Tree Splitting演算法將程式平行化，將其搜尋速度提升。當程式改成使用Dynamic Tree Splitting平行演算法，需要更改其搜尋架構、以及資料結構。經由實驗顯示，當使用四顆CPU，搜尋速度提升為使用單一CPU的3.3倍、搜尋深度平均增加1~2層，對戰的戰績也有相當的提升。

Since Kasparov, the world chess champion, was defeated by "Deep Blue", Chinese chess is expected to be the next chess game in which computer program can defeat any human player. This is due to the fact that the playing rules in chess or Chinese chess are not so much different. Hence, Chinese chess program is one of the most popular research areas nowadays. Previously, our Chinese chess program "Deep Elephant" used sequential Nega_Scout algorithm to search the game tree and its search depth was only about 10. In order to improve the strength of "Deep Elephant", we parallelize the program using the “Dynamic Tree Splitting” algorithm.
Experimental results show that it has a speedup of 3.3 and its search depth increases 1 to 2 ply when using 4 CPUs and it has a better achievement over the previous version.

[1] AI-Master, http://www.ai-master.com/SpecialPage_CaseStudy_ChineseChess_ChineseChessMain.asp
[2] S. G. Akl, D. T. Barnard and R. J. Doran,” Design, analysis and implementation of a parallel tree search algorithm”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-4, No. 2, pp. 192-203, 1982.
[3] G. M. Baudet,“ The design and analysis of algorithms for asynchronous multiprocessors”, Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA. Available as Tech. Rept., 1978.
[4] M. G. Brockington,“ A taxonomy of parallel tree search”, ICGA Journal pp. 162-174, 1996.
[5] A. L. Brudno,” Bounds and valuations for abridging the search of estimates”, Problems of Cybernetics, Vol. 10, pp. 225-241, 1963. Translation of Russian original in Problemy Kibernetiki, 10: 141-150, 1963.
[6] M. G. Brockington and J. Schaeffer,” APHID game-tree search”, Presented at Advances in Computer Chess 8, Maastricht, 1996.
[7] V.-D. Cung,” Contribution à ľ Algorithmique non numérique parallèle: exploration ďEspaces de recherche”, Ph.D. thesis, Université Paris VI, 1994.
[8] V. David,” Algorithmique parallèle sur les arbres de décision et raisonnement en temps contraint-Etude et application au minimax”, Ph.D. thesis, ENSAE, Toulouse, France, 1993.
[9] R. Feldmann,“ Spielbaumsuch e mit massiv parallelen systemen”, Ph.D. thesis, Universität Gesamthochschule Paderborn, Paderborn, Germany, 1993.
[10] E. W. Felten and S. W. Otto,“ Chess on a hypercube”, In G. Fox, editor, Proceedings of The Third Conference on Hypercube Concurrent Computers and Applications, Passadena, CA, Vol. II-Applications, pp. 1329-1341, 1988.
[11] C. Ferguson and R.E. Korf,” Distributed tree search and its application to alpha-beta pruning”, In Proceedings of AAAI-88, pp. 128-132, Saint Paul, MN. , 1988.
[12] R. A. Finkel and J. P. Fishburn,“ Parallelism in alpha-beta tearch”, Artificial Intelligence, Vol. 19, No. 1, pp. 89-106, 1982.
[13] F. Hsu,” Large scale parallelization of alpha-beta search: an algorithmic and architectural study”, Ph.D. thesis, Carnegie Mellon University, Pittsburgh, U.S.A., Also Tech. Rept. CMU-CS-90-108, Carnegie Mellon University, 1990.
[14] R. M. Hyatt,” A high-performance parallel algorithm to search depth-first game trees”, Ph.D. thesis, University of Alabama, Birmingham, U.S.A., 1988.
[15] R. M. Hyatt, B. W. Suter, and H. L. Nelson,” A parallel alpha/beta tree searching algorithm”, Parallel Computing, Vol. 10, No. 3, pp. 299-308, 1989.
[16] R. M. Hyatt, Crafty Source code, V.20.14.
[17] B. C. Kuszmaul,” Synchronized MIND computing”, Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts, U.S.A., 1994.
[18] G. Lindstorm,“ The key node method: a highly-parallel alpha-beta algorithm”, Technical Report UUCS 83-101, University of Utah, Department of Computer Science, Salt Lake City, Utah, U.S.A., 1983.
[19] C. -P. P. Lu,” Parallel search of narrow game trees”, M.Sc. thesis, Department of Computing Science, University of Alberta, Edmonton, Canada, 1993.
[20] T. A. Marsland and Y. Gao,” Speculative parallelism improves search?”, Tech. Rept., Department of Computing Science, University of Alberta, Edmonton, Canada, 1995.
[21] T. A. Marsland, M. Olafsson, and J. Schaeffer,“ Multiprocessor tree-search experiments”, In D. Beal, editor, Advances in Computer Chess 4, pp. 37-51, 1985.
[22] M. M. Newborn,“ Unsynchronized iterative deepening parallel alpha-beta search”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-10, No. 5, pp. 687-694, 1988.
[23] A. Reinefeld,“ An improvement of the scout tree-search algorithm”, ICCA Journal, Vol. 6, No. 4, pp. 4 –14, 1983.
[24] J. Schaeffer,“ Distributed game-tree searching”, Journal of Parallel and Distributed Computing, Vol. 6, No. 2, pp. 90-114, 1989.
[25] J.-C Weill,” Programmes d’échecs de championnat: architecture logicielle synthèse de functions d’évaluations, parallélisme de recherche”, Ph.D. thesis, Université Paris 8, 1995.
[26] 近十年電腦象棋的發展, 人工智慧學會通訊, 中華民國人工智慧學會, p8-p10, 2007.
[27] 王驕, 王濤, 羅豔江, 徐心和, “中國象棋電腦博弈系統評估函數的自適應遺傳演算法實現”, 東北大學學報(自然科學版), Vol. 26, No. 10, 2005.
[28] 李任軒, “電腦象棋知識庫切捨技術”, 國立臺灣師範大學資訊工程研究所碩士論文, 2006.
[29] 吳光哲, “電腦象棋搜尋圖歷史交互作用問題之研究”, 國立臺灣大學資訊工程研究所碩士論文, 2005.
[30] 曹國明, “智慧型中國象棋程式的設計與實作”, 國立台灣大學資訊工程所碩士論文, 1988.
[31] 陳志昌, “電腦象棋開局知識庫系統之設計與實作”, 國立台灣大學資訊工程研究所碩士論文, 1998.
[32] 張耀騰, “人造智慧在電腦象棋的應用”, 國立臺灣大學電機工程研究所碩士論文, 1981.
[33] 黃文樟, “電腦象棋深象中局程式的設計與實作”, 國立臺灣師範大學資訊工程研究所碩士論文, 2006.