5 ms·
Giving a candidate set of moves that results in a checkmate does not prove that said checkmate was forced. I can provide a candidate set of moves that results i
by Kranar 5y ago
Giving a candidate set of moves that results in a checkmate does not prove that said checkmate was forced. I can provide a candidate set of moves that results in a checkmate after 3 moves (the classic Blitzkrieg), and certainly you can verify that in polynomial time, but that does not mean that it's possible to force a checkmate in 3 moves.
To the best that anyone knows, for a generalized chess board of size WxW, to demonstrate that a checkmate can be forced in at most N moves, you'd need a candidate set of almost every possible sequence of N moves. You can prune some sequences, but not enough to bring the size of the candidate set down to something that can be verified in polynomial time.
Chess, depending on how you generalize it, belongs to EXPTIME.
- aan1092j 5y agoAh my bad. I wrote hastily and did not consider the full implication of the word `forced`, i.e. it would involve proving the opponent has no winning options.
- red_trumpet 5y agoWhere "winning" means "surviving for N+1 moves".
- chaboud 5y agoMate can be forced in N moves. This generally requires involvement of the king (e.g., check, no other pieces, guarding of the king) such that the only legal moves remaining are dictated by the positioning of the attacker.
- SilasX 5y agoGood catch, I was scratching my head at the parent comment since I was pretty sure chess isn't in NP, so thanks for confirming and explaining why it's not.