The third approach to building Valhello will be by using Parity's Substrate, a framework for building custom blockchains with custom logic.
It's made by Parity, and theoretically uses Polkadot to communicate with other blockchains. In theory, Valhello should be able to run on a custom substrate blockchain with each node verifying game logic, and then communicate game state across to Ethereum for some NFT goodness.
This would, however, require a proof-of-authority-style blockchain to exist which means we'd need some kind of incentive for players or third parties to run the nodes validating and building the blockchain. This makes the game far less decentralized as it requires a permissioned layer to accept new validators into the blockchain's consensus.
This post will be updated as research progresses, but feel free to chime in on Github.