Research on the Computational Complexity of n x n Chinese Chess1

Article type: Research Article

Authors: Gao, Qiang² | Xu, Xinhe³

Affiliations: Shenyang, 110004, China

Note: [1] Supported by National Natural Science Foundation of China, ID61370153

Note: [2] College of Information Science and Engineering, Northeastern University, email: [email protected]

Note: [3] College of Information Science and Engineering, Northeastern University, email: [email protected]

Abstract: Computational complexity of a computer game is an almost insurmountable obstacle in the process of looking for an ideal solution. Nevertheless researchers in the field of computer games aim to find such solutions, which may range from tractable to intractable. From the perspective of computational complexity, this article illustrates that n × n Chinese chess is intractable. The article starts to introduce the notion of an EXPTIME-complete problem of computational complexity and give as an example the G3 game. Then an n × n Chinese chess position (one rook and two queens) is constructed, which consists of three essential components, viz. Boolean controller, switch, and the crossing of clause-channel. The G3 game is simulated on the position, and it is proved that G3 is reducible to the n × n Chinese chess position in polynomial time. From this result it is implied that n × n Chinese chess is EXPTIME-complete.

DOI: 10.3233/ICG-2015-38106

Journal: ICGA Journal, vol. 38, no. 1, pp. 47-53, 2015