Is it possible to implement a completely-stateless multiplayer game?

It's not state what causes problems in scalability but keeping up with state.

I don't know if you are to design a REST interface, which is about state transfer, not statelesness. Statelesness would mean, that doing the same action twice has the same result.

This doesn't even apply to HTTP. If you do a DELETE request twice, the second one is pretty much supposed to fail.

In case you're developing an HTML-based game, nothing stops you to maintain state on the client in JavaScript.

In servers, the problem with state is usually its mutability:

• getting half-changed data (eg, if a Knight in chess moves, both coordinates change. If part of the system would get data with only one of the coordinates changed, there'd be potential trouble)
• data changing between transfer: suppose A calls B, and both use C. A is assuming C has a certain state, and expects B to behave accordingly. Yet in the meanwhile, C has changed, and B is acting differently. Bugs happen.

Also, there's a problem with concurrency:

• parallel components getting different state and thinking theirs is right: this is called conflict. An example would be, when in a realtime game, you hit an opponent, an opponent also hits you, and both shots are fatal. Each of them would think the other one is dead and they've won

And finally, there's a problem with storage&retrieval and failure:

• dying components: suppose there's a webshop, and the user has a basket. If the basket is maintained by a single compoennt, it could die if there are too many customers. If it is managed by 10 components, each of them managing a subset of customers, what happens if the component which was managing the current user's state dies?

So, state is normal. It's part of life. Computers are about interactions: a non-interactive computer is called book or newspaper, or rather, a poster (as a book has both open and closed states). Interaction changes state. While we try to minimize maintenance of state, we can't avoid it by nature.

A single player game can be completely stateless if the entire description of the game is transmitted on each request. A chess game against a computer program implemented by your server could just send the complete position after each move.

It's hard to see how a multiplayer game can be completely stateless - someone has to keep track of who the players are and who needs to be informed of state changes, and at least remember the state "in transit" long enough for all the players to receive it.

In any case, the primary role of the server can be just to relay bags of bits among the clients, and only need to keep track of where the bits are supposed to go. Depending on the nature of the game, the bits may need to be authenticated in some way to prevent cheating, for example by adding a checksum to the parts the clients aren't supposed to be able to change.