「深象」象棋軟體平行化之研究

Research on Parallel Search of Chinese Chess Software “Deep Elephant”

林子哲(Zi-Zhe Lin)

指導教授 ： 林順喜

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2006年)

摘要

在深藍打敗西洋棋棋王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.

並列關鍵字

Chinese chess program ； sequential search ； parallelization ； DTS algorithm

參考文獻

[29] 吳光哲, “電腦象棋搜尋圖歷史交互作用問題之研究”, 國立臺灣大學資訊工程研究所碩士論文, 2005.

[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.

[4] M. G. Brockington,“ A taxonomy of parallel tree search”, ICGA Journal pp. 162-174, 1996.

[6] M. G. Brockington and J. Schaeffer,” APHID game-tree search”, Presented at Advances in Computer Chess 8, Maastricht, 1996.

[12] R. A. Finkel and J. P. Fishburn,“ Parallelism in alpha-beta tearch”, Artificial Intelligence, Vol. 19, No. 1, pp. 89-106, 1982.