If a chess game was integrated into the protocol, such that two players play against each other, and moves are signed with private keys, then I think the winner could be verified automatically. Beating a highly rated player would count more than beating a lowly rated player.
...
I hope I'm on the right track here.
Computers play chess better than humans now. Much better. No human player has won a tournament against a top computer program since the mid-2000s. If you buy any of the top-rated chess programs for PCs such as Fritz or Houdini and run them in full-power mode, you're going to get trounced. There are now chess programs playing at grandmaster level that run on
smartphones. If you've been on the cover of Chess Life, you might win against one of them once in a while.
Yes, that was just an example of something that could be automatically verified. Go would be a more appropriate choice of games. And that would only work if: only beating players rated higher than some threshold counted as PoW (otherwise computers could compete), and enough appropriately skilled players participated.