Decentralized game of Battleships

[A example of battleships on pen and paper]

Decentralization is a solution sought after for many things related to inter computer communication. It helps alleviate threats that centralized systems commonly face, such as having a single point of failure (technical, financial, legal). So it's interesting to see how decentralization could be applied to multiplayer computer games.

Outside of the computer there is a game called battleships, which could be played on pen and paper, or could be played with plastic board and pegs. Each player sets up his board by placing ships in a 10x10 grid, hidden to the other player. The game progresses by players alternately calling out coordinates with a response that the shot hit or missed. The game ends when the all of the ships of a player are sunk.

There are hidden elements in this game, but it isn't necessary to have an arbiter to play. As long as the ships were actually placed at start, the marks themselves are sufficient to verify the result of the game. So why is it that every networked computer implementation I know of requires a server computer to handle the whole game session? All that is required is establishing the initial configuration without divulging to the other player, and with a bit of cryptography that is easy to do.

Let's assume there are two players, each with a computer, and a reliable message based link between the two computers. While the link resists outside influence, the player's computers are free to say anything to each other. First each player places ships on his own virtual board, then those boards are encrypted with a good symmetric cypher and a random password. Next the conputer sends the encrypted board while withholding the password. After both players receive each other's encrypted board they can play though the game as normal. At the end of the game the computers send the passwords to the encrypted board, so that the whole game can then be verified.

The act of sending a encrypted board ensures that the players can't change it mid-course, because then the board configuration would clearly mismatch when passwords are finally sent. With that there is no need for a third arbiter computer.

This could be applied to not only turn based virtual board games, but any game that requires chosen but hidden elements, regardless of the rate of those elements. D&D like RPGs could also benefit from this. All the maps, event triggers, item and monster locations could be loaded to all the players computers and be progressively revealed by the Dungeon Master. RTS games could possibly use this kind of system. Every command that players issue could be broadcast encrypted to all players, and when there's a situation where the list of commands must be known, the passwords would automatically be sent. This would completely decentralize the game, yet not allow cheating.