Research on the Computational Complexity of n x n Chinese Chess 1

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 G₃ 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 G₃ game is simulated on the position, and it is proved that G₃ 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.