The smart contract would not be generating moves. Just officiating a human vs. human match. I have in mind something like in the article I linked to. Checking whether a move is valid is far easier than generating good moves.
I'm sorry, I misunderstood your intentions.
Timing moves is tricky, however it may be possible to play long games where the time per move is measured in blocks. If the time is long enough (for instance, 100 blocks per move), the variance of block creation may not be an issue. However since the goal is not to post every move on the chain (as mentioned in the original post, this is super inefficient), there may be some way to play with faster time controls with all verification done off-chain or over a Lightning channel.
But judging the game isn't just verification of the moves. Most of the effort in judging actually goes to verifying the fairness, meaning that any of the sides isn't using any disallowed resources. So it would not be "human vs. human" but more like "correspondence game with unlimited computing resources and unlimited consultation".
I mention zero knowledge proofs because those are solutions that Greg mentioned already exist (ZKCP) or are eventually coming (SNARKS). You're right that it seems like zero knowledge shouldn't be needed for this. If anyone knows how to trustlessly verify an arbitrary computation without it, I'm interested to know how.
Is that a trick question? If you know the computation program and the input state then just rerun that computation as many times as you want until the you are convinced. Do you have some strange definition of "trustlessness" in your mind? Something like "left hand doesn't trust right hand?"
I think chess programming is just a nice way to really learn a new programming languages. It is non-trivial yet small enough that interesting and sensible programs can be written by a single programmer. Other than that what is the point? It really is "play to play" not "play to win".