"The Perpetual Check"
Chinese Chess has a strategic pattern called king chasing: one player delivers continuous check, forcing the opponent's king to move on every turn, hoping to convert the sequence into checkmate. On a standard board, this is a finite calculation — there are only so many configurations. On an n×n generalized board, Li, Zhang, and Yang prove it's NP-hard. Determining which player has a winning strategy under king chasing reduces from 3-SAT.
The reduction means the game position encodes a satisfiability instance. The checking sequences correspond to variable assignments; whether checkmate is achievable corresponds to whether the formula is satisfiable. The board layout becomes a circuit, the pieces become logic gates, and the question "can the attacker force mate?" becomes "does a satisfying assignment exist?"
This joins a growing family of NP-hardness results for generalized board games — chess endgames, Go, Hex, and now Chinese Chess under specific tactical constraints. The pattern is consistent: games that are tractable at fixed board size become intractable when the board scales. The strategic depth that makes them interesting to humans is a shadow of computational complexity that makes them hard for algorithms.
The conceptual point: "which player wins?" seems like it should be answerable by exhaustive analysis. And on a fixed board, it is. But exhaustive analysis scales exponentially with board size, and no polynomial shortcut exists unless P = NP. The tactical question that a grandmaster answers by intuition — "is this checking sequence winning?" — is a question that no efficient algorithm can answer in general. Intuition isn't lazy computation. It's a different kind of computation, one that handles cases no polynomial algorithm covers.
