King Chasing Problem in Chinese Chess is NP-hard
This result addresses a theoretical computational complexity problem for researchers in game theory and AI, though it is incremental as it builds on known NP-hardness results for generalized chess.
The authors proved that the king chasing problem in Chinese Chess is NP-hard when generalized to n×n boards, establishing computational complexity for this strategic sub-problem.
We prove that king chasing problem in Chinese Chess is NP-hard when generalized to $n\times n$ boards. `King chasing' is a frequently-used strategy in Chinese Chess, which means that the player has to continuously check the opponent in every move until finally checkmating the opponent's king. The problem is to determine which player has a winning strategy in generalized Chinese Chess, under the constraints of king chasing. Obviously, it is a sub-problem of generalized Chinese Chess problem. We prove that king chasing problem in Chinese Chess is NP-hard by reducing from the classic NP-complete problem 3-SAT.