Boardgame.io: Allow simultaneous moves

[evandroabukamel]

Well, I participated in a conversation about this in Gitter and just read an old one. The thing is:

Two or more players make a move "in the same time" but just one is executed, the others throws an "Invalid stateID" error on the server.

Now that my card game, "cards against humanity"-ish, is in beta test we saw this problem occurring a lot of times and it's hard to handle it on the client since the server does not return the error. I think one way to handle this is to return the error, there is an issue open about that. Although, I believe that is not the best way to solve that as the clients will receive errors, that may cause a bad experience, so I believe making the server handle moves with the same stateID is a good approach, of course checking if the move is still allowed. Maybe we could make this optional.

What do you think? I will look the the code and test some implementations.

Follows the talks from Gitter that I found about this issue:

Chris Swithinbank @delucis out 03 2019 07:47
Nice!
Question: I’ve been wondering about race conditions on the server now that players can be active simultaneously. What happens if two players make a move “at the same time”? Does the server know how to handle that or could this be a source for bugs? Are there good strategies for dealing with this given that bg.io is deterministic and dependent on order of execution.

Nicolo John Davis @nicolodavis out 03 2019 08:09
There is a stateID that is passed along with each action.
The server will only accept an action from a client that provides it the correct stateId, which it subsequently increments once the move is applied.
If two moves happen simultaneously (i.e. they're both on the wire at the same time without one client seeing the update from the other) then the server will reject the move that arrives second.
This is an exceedingly rare possibility and I don't think it's worth building any intelligent reconciliation logic.
However, I think we should surface the error on the client. I don't think we do currently.

Chris Swithinbank @delucis out 03 2019 08:42
OK — I wondered whether one approach would be to declare that moves were not order/state dependent and allow just those to be processed “late”. (Similar to declaring if a move can be undone or should be redacted.)
As an example: The project I’m working on includes a messaging interface that needs to be in game state, because other players can play “spy” cards and read their opponents’ discussions. The sendMessage move is enabled most of the time, but it doesn’t really matter if it happens before or after other moves (or other sendMessage calls for that matter), so could safely be made “late” as I describe.
This is probably a really really uncommon use-case, so I wouldn’t propose implementing something like this, but I was curious what the current behaviour was.
(In simple terms: two moves that don’t touch the same state — including the PRNG — can be safely made in any order.)

Nicolo John Davis @nicolodavis out 03 2019 09:00
Yeah, I'm definitely open to marking moves that can be safely made out of order.
And have the server ignore the stateID for those cases.

Chris Swithinbank @delucis out 03 2019 09:16
Cool — like I said, definitely not a priority. Surfacing a client error for rejected moves would be helpful (in general). Is there an open issue for that? I thought there was but I can’t seem to find it.

Another talk:

Ruslan Hydra
@HydraOrc
jul 28 14:09
Guys, how do you ensure that you do not run into race conditions when you allow both players to do moves simultaniously at the same turn or also if one player issues a couple moves at the same time (ERROR: invalid stateID, was=[11], expected=[13])?

Chris Swithinbank
@delucis
jul 29 06:25
This is an area where the framework still needs some work. Regarding the first issue, the logic for this was written before Stages allowed simultaneous actions and it hasn’t been updated to handle that scenario (it simply blocks the action it sees second as you probably experienced). With the invalid stateID error, I think we could improve that too by queueing player actions on the server or something.

Ruslan Hydra
@HydraOrc
jul 29 18:03
Maybe make server master sync instead of async? Is that a possible try to solve?

Chris Swithinbank
@delucis
jul 29 19:01
I would have to dive into the implementation to check the options. Keeping it async would probably be best (to handle multiple matches in parallel), but probably use a per-match queue, so if an action arrives while another is already being processed we can wait and then check if the second action is still valid.

Evandro Abu Kamel
@evandroabukamel
jul 29 20:19
That's a problem I'm going to have soon. The game we're developing allows players to make moves simultaneously. The idea of a move queue is excellent.

[larry801]

Do you really need simultaneous move on framework level in a card game?
May be you can check implementation in this repo, though it is too simple to cope with your issue.
https://github.com/wsun/multibuzzer
They changed the framework to allow simultaneous moves.

[larry801]

https://github.com/wsun/boardgame.io/commit/408a242bbc38670a3958a71245f09073036e0b95

[larry801]

I am still wondering why a predetermined move order cannot handle your game. Why not specify turn order in rules?

[evandroabukamel]

Nice, I will give a look into that project. The reason I need this is because game rule: all players can send their cards at the same time, there is no order, and one player should not wait for the others because it would take too long.

[evandroabukamel]

That's a simple implementation, but I liked this library and I would like to help to improve it and follow the updates.

[vdfdev]

This out-of-sync issues are a can of worms, might sound simple to accept moves simultaneously, but to make it "feel" right and meet users expectations for real-time collaboration is really hard.

I would avoid going to this route and just re-issuing the new state and asking users to try again. Yes, it is annoying, but it less annoying than corrupted states and bad stuff that can happen of a bad real-time implementation.

[nicolodavis]

It is feasible to explore some sort of phase option where out of order moves are acceptable (basically have the framework stop incrementing stateID during that phase and ensure that clients are at the very least inside that phase in order to make a move).

There is the other question of serializing these moves at the infrastructure level so that there is no race condition on the server (like having the second move undo the state of the first). Some sort of per-match queuing mechanism like @delucis suggests will be helpful.

[nicolodavis]

This is a low priority item, but we will be happy to look at a PR if someone is keen to work on this.

[delucis]

My personal leaning would be something like the following:

1. Add an option to the long-form move interface rather than a phase option. _stateID is also used to process and accept updates on the client, so not updating it is likely to have side effects that might be hard to handle.

   That said, I’m not quite sure what this option might be called, which could be a sign this is a conceptually muddy approach (especially because these checks are generally invisible to developers, they “just work” so it’s strange to surface them in this one obscure way). processIfStale (if what is stale?)… acceptStaleStateID (the move accepts it?)… allowOutOfOrder (out of turn order?)… Names are hard…

   moves: {
     simultaneousMove: {
       move: (G, ctx) => {},
       processIfStale: true,
     },
   }
   

2. In the master, if the move has this new option enabled it gets processed even if the _stateID checks fail. (Developers could still include more specific validity checks in the move function and return INVALID_MOVE if necessary.)

This approach keeps the current behaviour and only allows out-of-sync processing when specifically enabled. I agree with @flamecoals that this can actually cause all kinds of UX issues — for example, a player makes a move, but the first update they see is someone else’s move, then their own move arrives, potentially in quick succession, potentially cancelling or overwriting transitions or UI updates in confusing ways. There are definitely moves that can work fine like this though, like a discard stage where order is irrelevant.

@evandroabukamel points out that the flip-side of this problem is that there’s no way to handle client errors (see #723), which could be the alternative fix for this. Instead of implementing something server-side like the above, if the client received errors, developers could decide to handle that error in an appropriate way there. For example, if a move is rejected because it lost a race condition, they could display a message to the player to try again, or automatically dispatch a retry for cases where they know that’s acceptable. (Not that #723 is any simpler to implement 😅, but it might address a range of more generic scenarios rather than just this specific one.)

[evandroabukamel]

Good point, @delucis . I was thinking about a queue implementation, where moves are enqueued and at some point they are processed and, only after that, the stateID is incremented. But I'm not sure what would trigger the queue processing, queue length, time or some event.

I'll give a look at #723 . That could be some way to solve the problem.

[evandroabukamel]

Well, #723 is a lot of work. I'm doing @delucis suggestion, it seems more simple to implement and the developers should be aware to check their game state to use the option to ignore stateID checking. What about "ignoreStateState", @delucis ?

[delucis]

@evandroabukamel Yes, #723 would be quite a bit of work! How about ignoreStaleStateID?

[evandroabukamel]

@delucis , I'm testing it right now.

[evandroabukamel]

It seemed to work pretty well for me. I'll make more tests on other environments to be sure.