You're approach seems straight-forward in theory -- just check every possible move and make sure that none lead to a checkmate. The only issue is that "checkin

You're approach seems straight-forward in theory -- just check every possible move and make sure that none lead to a checkmate. The only issue is that "checking every possible move" is a huge state space (way above what is computable). Not only that, but there are cycles (so you need to deduplicate). And if the game is a draw, then that means the number of moves is technically unbounded (since there would always be a move that makes the search tree deeper), as by definition, there is no way to end the game. So the question is 'when do you stop searching?'. It could be that checkmate is possible, but you haven't searched the 1 in 1 billion part of the strategy tree. In practice, its probably down to some heuristics and a reasonable depth search, but its not formally verifiable. Its a variant of the halting program -- prove that there is a stopping point for this game.