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

Abstract

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