高效率電腦象棋停著殺程式之設計與製作

The N-Relaxed Checking-Win Search Problem in Chinese Chess

蔡旭程(Hsu-Cheng Tsai)

指導教授 ： 劉邦鋒

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2005年)

https://doi.org/10.6342/NTU.2005.00492

摘要

停著殺是象棋中一個有趣的問題，在電腦象棋當中，我們也相對應的定義出Ｎ步停著殺的問題。Ｎ步停著殺的問題，就是要找出一個 AND-OR 證明圖，符合從任一個葉節點到根節點的路徑上，先行方至多只有Ｎ個非將軍步。如果找不到證明，那麼自然也能夠得到反證。因為這個問題受到象棋棋規的影響，變得十分困難，因此在此篇論文之前尚無有效率的方法能正確解之，此外，若要加入讓搜尋演算法加速的雜湊表一起考慮的話，問題會變得更加複雜。此篇論文介>紹一個基於搜尋圖歷史交互作用理論（ Graph History Interaction， GHI ）
的搜尋演算法，可找出正確的解答並且效率足以應用於電腦象棋中。本論文的所有討論均根據亞洲棋規的規定。

關鍵字

連將殺 ； 停著殺 ； 電腦象棋

並列摘要

In Chinese chess game, the N-relaxed checking-win problem is to find a proof, in the form of an AND-OR graph, such that any path from the root to the terminal nodes consists of all but at most N non-checking moves for the root player. When a proof cannot be found, then a disproof is sought, This is complicated problem because a correct implementation must
deal with the Chinese chess rules which we are not aware of having any efficient implementation.
The problem becomes more difficult if a hash table is used
to store the previous searched result in order to improve performance.
In this paper, a correct solution with tolerable performance cost based on Graph History Interaction (GHI) proof search is presented. We have chosen to implement the Asia Chinese chess rules in our program.

並列關鍵字

N-relax checking-win ； computer chinese chess

參考文獻

[6] A. Kishimoto and M. Muller. A solution to the GHI problem for depth-first proof-number search. In Proceedings of 2003 Joint Conference on Information Sciences, pages 489-492, 2003.

[7] A. Kishimoto and M. Muller. A general solution to the graph history interaction problem. In Proceedings of Nineteenth National Conference on Arti cial Intelligence, pages 644{649, 2004. 34

[8] C.-C. Liao. A computer chinese chess program and its experimental results (in chinese). Master's thesis, Graduate Institute of Computer Engineering, National Chiao Tung University, Taiwan, 1982.

[12] S.-J. Yen, J.-C. Chen, and S.-C. Hsu. The 2004 world computer Chinesechess championship. International Computer Game Association (ICGA) Journal, 27(3):186-188, 2004.

[1] D. M. Breuker, H. J. van dan Herik, and J. W. H. M. Uiterwijk. A solution to the GHI problem for best-first search. In H.J. van den Herik and H. Iida, editors, Lecture Notes in Computer Science 1558: Proceedings of the 1st International Conference on Computers and Games, pages 25-49. Springer-Verlag, New York, NY, 1998.