The second-generation Worms games (2, Armageddon, WWP) use the same approach (here called "Deterministic action propagation method"). It was implemented by Karl Morton, and we also use it for replay files (which is why the game logic is meticulously versioned).
The solution we used for managing secret state, when the state is from a random source, is to delay generating the secret information for as long as possible (so, e.g., if a card is drawn, the drawn card is decided at that moment, as opposed to pre-shuffling the deck at the start of the game). We experimented with some designs in which the secret is revealed only to the player who owns it, and the rest only see a verifiable hash of the secret until the player performs an action which reveals the secret; however, it doesn't solve the general problem that any time the game must immediately (without network latency) make a random choice, the design must compromise between either allowing a hacked client to predict the result (when the RNG output is stable) or manipulate it (when the RNG output changes very often, e.g. every frame).
Sadly, the newer games went for a simpler synchronization algorithm, in which if a discrepancy is detected, the entire state is simply copied over from one player's game to another. This does allow blatant cheating; I'm guessing it was a concession due to the new engine lacking in robustness or portability.
This is a really interesting approach for managing secret state. Another life ago I implemented a rule-based version of everyone's favorite collectible card game, and it was P2P (so each client ran the full rules engine and synchronized the initial random seed and the each player's actions). I could never figure out a good way of limiting cheating by peaking at either your own deck or the opponents. I looked into commutative encryption and mental poker, but at that point my interest in the project fizzled and I stopped working on it. This approach would work for keeping randomness in the game, and homomorphic encryption could be used to hide the contents of the opponent's deck.
There's a third way of thinking, best exemplified by Agar.io and things like that which basically asserts that any network latency is the player's problem. There's a deterministic state on the server, and the UI doesn't bother to try to sugarcoat it to make it feel any more instantaneous than it is. IMHO this is the only way most games will be written down the line. I'm an old casino coder, so the "tricks" were things like, slow the card deal animation; keep the roulette wheel animation going longer; etc. But where money's concerned you can't take shortcuts, and in the end a player with a faster connection has a better experience, and (in casino land) those are the players with money anyway. I'm not sure I understand why there'd ever need to be an instant result (sans network latency) in a turn-based game. If the player has a visual indication that the server is waiting for their command, then any jumpy movement on the part of other players is strictly down to their own bad connection as long as the server is running well. If players understand that the alternative would be the ability to cheat, they'll generally accept that and upgrade their network connection.
> I'm not sure I understand why there'd ever need to be an instant result (sans network latency) in a turn-based game. If the player has a visual indication that the server is waiting for their command, then any jumpy movement on the part of other players is strictly down to their own bad connection as long as the server is running well.
Although the Worms games are turn-based, gameplay typically involves performing a lot of actions within one turn. Walking, jumping, using utilities (which don't end your turn), and finally firing a weapon. Many of these actions can trigger an event with a random outcome, which should ideally be unpredictable and un-manipulatable, such as which weapon will be found in a weapon crate, or how long the fuse of a mine with a random fuse will be.
In a peer-to-peer game, the server is just another player, and should not be considered intrinsically more trustworthy. Ignoring latency, it's possible to implement a scheme of securely generating random data, in which everyone produces a verifiable hash (commitment) of a random number, and after everyone announced their hash everyone announces their random number, which is then XORed together to produce the outcome (see e.g. Keybase's "Cryptographic coin flipping"). The problem with this approach is that the latency to obtain the result becomes the roundtrip to the player with the slowest connection and back.
In a case like Worms where there are concurrent actions and random reveal choices inside each turn... If some deterministic state and random number is created for each player at the start of the turn, then their inputs can be reproducibly mapped to the results of all the random choices. In that case you can just upload the inputs and let the server work out what happened based on the hash the player was given (i.e., let the server replay each player's inputs against that hash and figure out the result).
But the server is not another player. It's not a player at all. It's the arbiter of truth. So as you said:
>> The problem with this approach is that the latency to obtain the result becomes the roundtrip to the player with the slowest connection and back.
This is what I'm saying above. At some point games will just accept this and allow the player with too slow of a connection to be disadvantaged. To the extent that a server should tolerate slow connections, it is a handicap given by the game to players with slow connections.
> In a case like Worms where there are concurrent actions and random reveal choices inside each turn... If some deterministic state and random number is created for each player at the start of the turn, then their inputs can be reproducibly mapped to the results of all the random choices. In that case you can just upload the inputs and let the server work out what happened based on the hash the player was given (i.e., let the server replay each player's inputs against that hash and figure out the result).
No, this is the worst of the two cases: it allows predicting all outcomes at the start of the turn AND allows manipulating the outcome. So, in a territory control scheme like Team17, you can choose whether to pick up that crate now, or wait a turn or two until picking it up will result in a better outcome.
> But the server is not another player. It's not a player at all. It's the arbiter of truth.
No, that's not how peer-to-peer games work. In the current implementation, it is the "arbiter of truth" because it's the "server" in the TCP/IP sense, but it is still run and controlled by a player, and should not have any intrinsic advantage.
> At some point games will just accept this and allow the player with too slow of a connection to be disadvantaged.
Maybe games with a centralized networking model. We deliberately avoided doing anything in this direction for Worms Armageddon because it puts a death clock on the game and the community - see all games which are no longer playable because the developer/publisher decided that keeping the servers online was no longer profitable.
> To the extent that a server should tolerate slow connections, it is a handicap given by the game to players with slow connections.
In the hypothetical secure scheme I described above, ALL players are affected, not just the slowest one.
> [the server] is still run and controlled by a player
Just to drive this point home for anyone who hasn't played Worms: the developer (Team17) doesn't operate game servers. One of the players hosts a game on their PC, and other players connect either through the WormNET listing service, or by punching in their friend's IP address and connecting directly to their PC. Players can even operate their own WormNET-compatible listing servers if they wish.
This means there's no trustworthy source of truth to settle disputes or cheating, since whichever player's PC acted as the arbiter could simply dictate in-game reality to their opponent(s).
So players' PCs need to be able to validate that competitors' randomized events are legal, but without generating the randomness early enough that a player could use a hacked game client to peek into the randomness future before taking actions.
I wonder if speculative calculation on the clients could be used.
For example let's say we're at frame 999 and have 2 players and 10 deterministic NPCs. And each player has 4 possible moves 2 of which have results depending on a random number being <= X or > X.
So each client calculates the next possible frame states knowing its user input (so it only has max 2 options depending on the random generator) * possible inputs from the other player (2 + 2*2 = 6 options), so there's 12 possible game states for frame 1000 from this client POV.
NPCs are deterministic so they can react to the player moves in each branch.
The other client does the same but has different variables missing and different state tree (with small overlap that only depends on random generator).
Then both clients send their player inputs to the server and wait for the missing variables to choose which branch of the state tree they both go. Depending on the game we may not wait just show the most likely branch and if we mispredicted we switch to the right branch after we get missing data.
This state tree could be several levels deep if there's enough computing power, and it could also be used by AI to choose best moves assuming what player can do (but then it gets complicated).
Advantages:
- server needs much less computing power than clients
- server can still verify the state
- clients don't have information they shouldn't have
- network latency is mostly hidden
Disadvantages:
- more computing power needed on the clients
- can get impractical quickly with more possible moves on each turn
You don’t need to simulate multiple futures just keep going with the most likely (continue doing what you’re already doing is a common heuristic) and correct when you get the missing info. This is the basis of deterministic rollback networking popular in fighting games.
The solution we used for managing secret state, when the state is from a random source, is to delay generating the secret information for as long as possible (so, e.g., if a card is drawn, the drawn card is decided at that moment, as opposed to pre-shuffling the deck at the start of the game). We experimented with some designs in which the secret is revealed only to the player who owns it, and the rest only see a verifiable hash of the secret until the player performs an action which reveals the secret; however, it doesn't solve the general problem that any time the game must immediately (without network latency) make a random choice, the design must compromise between either allowing a hacked client to predict the result (when the RNG output is stable) or manipulate it (when the RNG output changes very often, e.g. every frame).
Sadly, the newer games went for a simpler synchronization algorithm, in which if a discrepancy is detected, the entire state is simply copied over from one player's game to another. This does allow blatant cheating; I'm guessing it was a concession due to the new engine lacking in robustness or portability.