A problem I've been thinking about recently is how it might be possible to create a multiplayer game without a centralised game server.
Is it possible to distribute "server" responsibilities across players? I feel like it would be too easy for modified/hacked clients to change the multiplayer experience, are there any ways around this?
For some games it is possible. Take chess, for example. Can you cheat at online chess without the opponent noticing? Cheating at chess is hard, because the game:
When your opponent says they just moved their king from a3 to f1, your game client can recognize that this is an illegal move and reject it. The only possible cheat left is AI assistance (which actually is a serious issue for competitive chess, by the way). But there is really no workaround for that unless you force players into a controlled environment. A while ago I asked a question about how to design a game as AI-unfriendly as possible, but didn't get really good answers. So I am not going to cover this issue.
While there is no good way to get around the third requirement, you can get around the first and second by using some applied cryptography.
Take battleship, for example. How can you verify that your opponent didn't cheat by lying about their fleet layout? Have each player calculate a cryptographic hash of their layout at the start of the game and send it to the opponent. At the end of the game when the complete layout of the enemy is revealed, you can verify if the hash matches the layout. You might want to add some bytes of random data to the data from which the hashes are calculated (also to be revealed at the end of the game) to prevent the opponent from brute-forcing your fleet layout when you've reached the endgame and the number of possible positions is low enough to allow that.
The same method can also be used if you want some randomness in your game, because randomness is essentially hiding of information from all players.
Before you start the game, have both players create a long list of random bits (more than you will need for the complete game). Use a cryptographically secure RNG seeded from an unpredictable entropy source. Again, have the player hash their lists and exchange the hashes for post-game verification. During the game, use these two lists as one-time pads for each other. When you need a random bit, have each player reveal the next bit from their list, XOR the bits with each other, and use the result. This gets you a random number which both players contributed to but none could predict. Again, at the end of the game, send your complete list to the opponent so they can verify the hash and confirm you didn't lie during the game.
But how do you deal with players you catch cheating?
In a game with more than two players which follows above guidelines, everyone knows when a player cheated. So they can simply all disconnect from that player and continue the game without them. There is no practical difference between someone ragequitting because they can't stand losing or being kicked for cheating.
But what about a two-player game where the clients can't agree on who cheated? This is actually not unlikely to happen if both clients aren't aware that they are playing different versions of the game. This is essentially equivalent to a rule dispute in a tabletop game. If you can't come to an agreement, the only solution is to abort the game and call it inconclusive. Again, equivalent to a ragequit. Who is the quitter from your perspective depends on how guilty you feel.
