They could have simply adopted blitz chess rules, where the goal is to capture the opponent king, and leaving your king in check is not illegal, to avoid all this extra computation...
I wonder if it's cheaper to verify a proof of checkmate that someone else computes. I'm not sure exactly what such a proof would look like, but there are lots of problems where finding a proof is hard, but verifying one is easy. Then you could make the checkmating player prove that it's checkmate and provide that proof along with their final move, and the contract could just verify it.
The problem here is that there is a cap of how much gas[1] a block may consume which is the moving average of consumed gas plus some extra.
A few contracts got stuck that way; by getting to a point where they could no longer use that much gas.
[1]: Gas in Ethereum refers to the amount of value paid for computation, once gas runs out the execution is terminated and the gas subtracted from the senders account.
When the transaction runs, gas is consumed. If the transaction finished or there is no more gas, computation stops.
Now, transactions have no limit but blocks of transactions have. This is to prevent a single person creating and mining gigantic transaction to stall the network.
This limit is dynamic and you can raise it by having the network use more gas until the moving average climbs high enough.
I was going to make a counter-argument but then I realized that this system doesn't normally enumerate legal moves, simply verify legality of moves that are actually played, which is a crucial distinction here.
Thanks for making this observation; I found it a pretty subtle point!
Those are not blitz chess rules. The goal of blitz is still checkmate, not capturing the opponent's king. USCF, FIDE, WBCA all agree, leaving a king in check is an illegal move and loses the game as soon as it is pointed out.
Edit: there is a relevant distinction like this according to FIDE!
http://www.fide.com/component/handbook/?id=171&view=article
In normal play, when "it is found that an illegal move has been completed, the position immediately before the irregularity shall be reinstated." (7.5a)
But in rapidplay (including blitz), "[i]f the opponent does not claim and the arbiter does not intervene, the illegal move shall stand and the game shall continue." (A.4)
The FIDE laws still seem to assume the presence of an arbiter, which wouldn't always be the case for blitz games outside of a tournament or other formal event. But I guess there is an official notion even according to FIDE that illegal moves (including moving into check!) can be allowed in a blitz game if nobody notices them, which is not the case in a standard game.
Nonetheless, for all types of games, "[l]eaving one’s own king under attack, exposing one’s own king to attack and also ’capturing’ the opponent’s king are not allowed." (1.2)
And stalemate is huge, e.g. many K+pawn vs K endgames are drawn because of stalemate, without stalemate a one pawn advantage would be much more significant.
Isn't checkmate a very constrained 2-ply search? If you have a 1-ply search that suffices to check that kings are not left in check, isn't the checkmate simply using that search for each of the maximum 9 board positions (including current one) that the king can occupy? I must be missing something about blockchain computation because the article says this:
"In order to verify a checkmate, Grau wrote, all possible moves must be calculated and verified, which he and his peers found was not feasible on the blockchain."
https://en.wikipedia.org/wiki/Check_(chess)#Getting_out_of_c...
While your analysis is right, you don't really need the "etc." at the end!
Even easier in case of double checks, since you exclude captures.
Verifying a tie or mate due to repetition is more tricky for a usual test, but not if you hash the whole board state.
This could allow for player error, but to prevent that you simply have client-side code perform the steps.