隨著圖形處理器(GPU)的快速發展，以往許多運算需求量很大的問題，都可嘗試將其轉移到GPU上來處理。電腦象棋本身就是以硬體的運算速度以及其演算法來決定棋力，傳統的發展趨勢是使用平行系統，或是特殊設計的硬體以提升棋力。雖然GPU擁有強大的運算能力，但在架構上也有特殊性，在移植個人電腦上的應用程式到GPU時，需要詳加考慮配合GPU的平行化方式，才能發揮更好的效能。
在本篇論文中，我們分析電腦象棋的搜尋演算法，依照GPU在平行處理上的特性，提出一個方式讓GPU來處理此搜尋演算法。並分析此方式下GPU能達到的運算能力，並將之與僅使用個人電腦的方式做比較。
實驗的結果中，我們以定量深度5層啓動搜尋演算法，在執行時間的比較中，GPU版本走訪的節點數目為CPU版本走訪的2.06倍，處理時間為CPU之0.38倍。而在每秒可分析棋步(NPS, Nodes per second)的比較中，GPU版本由於平行化的提升而得到81萬之NPS，而相同情形下CPU的NPS為15萬。因此，我們可以預期往後能在GPU核心數目會再提升的情形下，能得到更高的NPS及執行效能。本實驗之實作及量測是在個人電腦上執行，使用的設備為CPU Intel Core 2 Quad Q6600 2.4GHz與4G RAM，以及GPU NVIDIA GeForce 9800GTX+ 738MHz搭載512M DDR3 RAM。

Nowadays, with the fast development of GPU(Graphic Processing Unit), more and more studies are on how to accelerate specific computing problems by utilizing the GPU’s rich computing resources. This thesis focuses on how to improve a Chinese Chess program by exploiting the GPU’s computing power.
The strength of a Chinese Chess program depends on the underlying hardware ability and the searching algorithm. One trend to enhance the Chinese Chess programs is to port them to parallel computers or some systems with custom-designed chess accelerating chips. With the large number of computing units on GPU, it seems a promising way to use GPU on Chinese Chess computing.
In this thesis, we analyze the search algorithm of a Chinese Chess program, in compliance with the characteristics in parallel computing on GPU, and port the search algorithm to the GPU working on a graphic card of a personal computer.
In our experiment, the computing ability of GPU is compared with that using general-purpose 80X86 CPU. The experiments are executing the search program, fixed on a 5-layer depth search, on GPU and PC, respectively. The results show that our approach traverses 2.06 times nodes compared with the CPU, and the execution time is 0.38 times compared with the CPU. We obtain 0.81 million NPS (Nodes per second) by parallelizing the algorithm with GPU support while the NPS acquired by executing the program on PC, without GPU support, is 0.15 million. Therefore, it can be expected to improve the completeness of the searching algorithm with GPU support in the future, and we can obtain more NPS and execution performance with more cores. The implementation and measurements is on a personal computer, equipped with Intel Core 2 Quad Q6600 2.4GHz CPU, with 4G RAM, and the GPU is NVIDIA GeForce 9800GTX+ 738MHz equipped with 512M RAM.

[1]. M.G. Brockington, “A Taxonomy of Parallel Game-Tree Search Algorithms”, International Congress and Convention Association Journal, vol. 19, no.3, pp. 162-174, 1996.
[2]. CUDA Zone, available from http://www.nvidia.com/cuda, (accessed 04.06.10)
[3]. C. Donninger, “Null Move and Deep Search: Selective-Search Heuristics for Obtuse Chess Programs”, International Congress and Convention Association Journal, vol. 16, no.3, pp. 137-143, 1993.
[4]. A. Grama, and V. Kumar, “A Survey of Parallel Search Algorithms for Discrete Optimization Problems”, ORSA Journal on Computing, vol. 7, 1993.
[5]. A. Grama, and V. Kumar, “State-of-the-Art in Parallel Search Techniques for Discrete Optimization Problems”, IEEE Transactions on Knowledge and Data Engineering, vol. 11, no. 1, pp. 28-35, 1999.
[6]. G. Karypis, and V. Kumar, “Unstructured Tree Search on SIMD Parallel Computers”, IEEE Transactions on Parallel and Distributed Systems, vol. 5, pp. 453-462, 1994.
[7]. T.A. Marsland, and F. Popowich, “Parallel Game-Tree Search”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 7, pp.442-452, 1985.
[8]. Strategy Game Programming, available from http://www.fierz.ch/strategy5.htm (accessed June 28, 2010)
[9]. Shi-Jim Yen, Jr-Chang Chen, Tai-Ning Yang, and Shun-Chin Hsu, “Computer Chinese Chess”, International Computer Games Association Journal, vol. 27, no.1, pp. 3-18, 2004.
[10]. 中華民國象棋文化協會, available from http://www.oasis-open.org/specs/, (accessed June 4, 2010)
[11]. 曹任明, 電腦象棋分散式搜尋技術之研究, 國立台灣大學資訊工程研究所, 碩士論文, 1998.
[12]. 鄭明政, 電腦象棋程式位置評分表之研究, 國立成功大學工程學所, 碩士論文, 2006.
[13]. 顏士淨, 楊泰寧, 董昱騰, “電腦象棋程式達奕之設計與製作”, 第八屆人工智慧與應用研討會, 2003.
[14]. 龔建銓, 使用GPU平行運算加速電腦象棋之走子產生器, 國立成功大學工程學所, 碩士論文, 2009.