電腦象棋搜尋圖歷史交互作用問題之研究

Graph History Interaction Problem in Computer Chinese Chess

吳光哲(Kuang-che Wu)

指導教授 ： 劉邦鋒

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

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

摘要

電腦象棋發展至今，已有相當於象棋高段棋手的棋力。高手對局，象棋棋規的正確判斷與運用愈顯重要。然而至今未曾有公開的文獻提出完整且有效率的象棋棋規實作。本文實作完整的象棋棋規，並針對中局搜尋的循環局面歷史交互作用問題提出部份解決的策略。此處的象棋棋規採用亞洲象棋聯合會的象棋比賽規則。象棋棋規較西洋棋困難處在於循環局面的判決結果勝、負、和都有可能；而且得造成三次相同的循環條件才會輸棋，譬如一將一捉作和。西洋棋則一律視循環為和棋。

關鍵字

搜尋圖歷史交互作用問題 ； 電腦象棋 ； 亞洲棋規

並列摘要

The importance of mastering Chinese chess rules to improve the skills of Computer Chinese chess players is recognized by experts. However, we are not aware of any published results of a full implementation of Chinese chess rules with reasonable performance degradation. This paper reposts such an implementation and proposes some heuristics to deal the cyclic rules during search. The Chinese chess rules used to decide the outcome of a game when it falls into loops are those proposed by the Asia Chinese Chess Association. The Chinese chess rules for cyclic moves differ from Western chess rules in two regards. First the outcome of a cyclic game can either be win, loss or draw. Second, the same type of rule has to be violated three times in a row to lose the game. In other words, a player can violate different rules in three cycles to achieve a draw. In comparison, Western chess rules define a cyclic game as a draw.

並列關鍵字

Graph History Interaction ； Computer Chinese Chess ； Asia Chinese Chess rule

參考文獻

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

[4] M.-C. Cheng. Private communication on design and implementation of the Chinese chess program ShiGa, 2004.

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

[10] A. J. Palay. Searching with Probabilities. PhD thesis, Carnegie Mellon University, 1983.

[11] A. Reinefeld. An improvement of the scout tree search algorithm. Inter- national Computer Chess Association (ICCA) Journal, 6(4):4--14, 1983.