Boardgame.io: Random API

[nicolodavis]

Dice, shuffling etc. all require randomness, but having impure reducers (using Math.random(), for example) breaks the ability to view earlier game states (and is an anti-pattern in Redux). We should use a seed in ctx (that's stripped away before sending it to the client) that is used to predictably generate random numbers.

Plan:

• [x] API to generate random numbers.
• [x] API for various die rolls.
• [x] API to shuffle an array.
• [x] Allow calling the Random API in flow code (only really supported in moves at the moment).

[scheijan]

I've used https://github.com/davidbau/seedrandom before to solve a similar problem. If you think that could be a solution here as well, I could take a stab...

[nicolodavis]

Using seedrandom sounds good! Go ahead.

[vdfdev]

I just want to note that this will also be a problem for when developing a generic AI, as the algorithm will need to know what is the probability of each state happening for maximizing the expected value of each action.

If we just use Math.random() or any similar approach, it can lead to almost infinite amount of distinct states. Maybe we need to develop an API that will allow us to tell how many possible states it can happen from there -- ie throw a 6-sided dice API.
But to be completely honest I still don't have a good solution for this. I want to focus on having a simple AI for deterministic games first, and then maybe we can revisit this.

[philihp]

I think keeping a seed in the ctx is the best way to make sure the reducers stay deterministic.

If a bot/AI were to search the state tree with random elements would probably want an MCTS, since something like a draw from a 6-deck shoe in blackjack can have 300+ branches per level of depth.

There will need to be a way to tell Game to use a new seed, though, because the bot will want to sample what “could” happen, but if it knows what “will” happen with the actual seed, that wouldn’t be fair to the humans.

[vdfdev]

Yes, again, I think keeping the seed is a good solution, I just wanted to start thinking about how to solve this for AI as it is related. We are going to need to have more information for sure, after all we are going to need to generate a graph to run Markov decision process algorithms...

[scheijan]

@nicolodavis where would like to you see functions like shuffle() or random()? Directly on ctx? As methods of the GameBoard? A new module?

[nicolodavis]

ctx should be a plain object, so let's put them in a separate module?

[nicolodavis]

@scheijan Haven't heard from you in a while. Are you still working on this?

[scheijan]

I started to look into it, but I'm pretty busy right now and can't promise I'll get to it any time soon. So if anyone else wants to give it a try please feel free...

[Stefan-Hanke]

I'll give this a shot.

[Stefan-Hanke]

Regarding stripping secrets: Currently the STRIP_SECRETS method gets G, ctx, and the playerID, but is written to just return G.

I don't know whether modifying ctx in-place is the way to go, I'd prefer to have it return a new ctx instead. But this means we'd need to first adapt existing usages of _playerView_ to allow it to return an object with G and the new ctx object. Thoughts?

[nicolodavis]

Ah, good point.

playerView strictly deals with state in G (and isn't meant to modify any internals in ctx), so let's not change it. One option would be to just strip ctx of seed where playerView is called here and here.

Both these locations create a new state object, so you wouldn't be modifying ctx in-place.

[Stefan-Hanke]

I'm ok with this. Unfortunately, there is no obvious way in JavaScript to somehow _functionally_ strip an object from a key - the code is now using Reflect.deleteProperty (could as well use delete also, I don't care). There already was a deepCopy function, so I've copied it to have the duplication stand out.

Currently, the code allows to pass an initial seed from the setup method. I'm unsure whether this is the way things should be. Since the seed shall be on the ctx object, it is copied there. And from there, it trickled down the initial state object.

One thing that I think I'm missing - the seed is used to start off the pseudo random number chain. When calls to random have been made, the internal state of the prng changed. Somehow, this state needs to be stored. Currently, the code attaches a function to the ctx object, however I think ctx (as part of state) needs to be serializable. So, we'd need to create the pnrg with {state: true} (reference) s.t. it allows to access its internal state. The prng state would be part of ctx also, and would need to be stripped, too.

[nicolodavis]

You don't need to delete a key anywhere really. You can just set it to undefined | null, or use the object spread syntax to achieve a delete.

Don't attach functions to ctx (it should be a plain serializable object). Sounds like you've already taken this into consideration. About the PRNG internal state, sure, let's put it in ctx along with seed. Maybe put everything inside a key called random (or something similar).

[Stefan-Hanke]

Setting to undefined looks quite good. I've tinkered with the object rest spread operator (SO); the post does not mention just setting a key to undefined.

The code now stores the seed and another variable called prngstate. Now, how is this supposed to work at all? The problem is that just calling Math.random() updates hidden state. Currently, this is reflected in updating the given ctx - a call to random(ctx) calls into the PRNG, updates prngstate, and returns the random number. Either modifying ctx is OK, or the functions would need to return a new ctx object.

[Stefan-Hanke]

Let's say we don't care about single player. Here, the reducer fully processes the move.

So we're left with the multiplayer case. For sake of having a concrete example, let's say there is an implementation of Yahtzee, where the player is allowed to click a button to roll the dice.

Currently, the client-side reducer would process the move, but not events that eventually pop up (see reducer, l.79). The attached middleware pushes the move to the server, where the server-side reducer fully processes the move (including events) (because here, multiplayer=false (reference) - even for a mulitplayer game. Poor server must play alone always), and afterwards syncs the clients.

This also means that the same move is done twice - on the client and on the server. This will not work in presence of randomness where only one side is allowed to know the PRNG state.

Now, the Yahtzee move must utilize randomness. So, we need to process the full move on the server only and not on the client. I wonder what happens when the reducer would just do the complete move always (that is, move the multiplayer check above processing the move here). Currently, all tests stay green. I've not checked the example games.

The hypothetical Yahtzee rollDice move function itself needs to call into random. This would modify ctx. I could dream up two solutions:

1. have the move return the ctx also
2. allow modification of ctx and take care about this inside the framework.

[nicolodavis]

About PNRG issues:
Maybe use something like https://gist.github.com/blixt/f17b47c62508be59987b instead of seedrandom so that you don't have any hidden internal state that can't be persisted in ctx easily.

About client vs. server:
The library neatly demarcates these zones into moves and flow. Anything inside flow is only ever run on the server in multiplayer mode. This is by design. In order to simulate something like a die-roll, you can do:

moves: {
  RollDie(G, ctx) {
    return { ...G, _roll: true };
  }
}

flow: {
  onMove(G, ctx) {
    if (G._roll) {
      // 1. delete _roll from G
      // 2. Call PNRG
      // 3. Put result in G
    }
  }
}

Our API could provide a bundled RollDie move like this that merely sets a boolean in the move, and then processes it in a trigger (in the real implementation you probably won't use onMove, but write some custom code in flow.js because you want to modify ctx as well).

It could look something like:

import { RollDie } from 'boardgame.io/core';

moves: {
  moveName(G, ctx) {
    G = RollDie(G, 'name of field in which die result is recorded');

    // The die result is available in G right after the server processes
    // the triggers for this move (i.e. you can't depend on its result within
    // the same move).
  }
}

[Stefan-Hanke]

Getting the PRNG state is not an issue - sorry if I confused you.

I'm not sure how such API will work out. It looks like an action/command that is transported via G since this is what moves return. I'm kind of intrigued by this approach.

In your first example, the // 2. Call PNRG code would modify ctx. As of now, I think the intention is having code inside moves and flow to not modify ctx at all. So I'll modify the code to _just_ record random operations, have special code to interpret it, and inject it back into G as per your suggestion.

• [x] Modify API to only record intended random operation + tests
• [x] Embed random ops into existing framework + tests
• [x] Write explanatory article
• [x] Create PR

[Stefan-Hanke]

https://github.com/google/boardgame.io/pull/103

Hmm - I'd expected that the PR reference gets automatically expanded.

[nicolodavis]

The server is the authoritative source of truth, so everything needs to run there. We also want reducers to be pure (not rely on any data outside their inputs). The complication arises from the fact that moves are run on both server and client (to update state locally without network lag). This state is still overridden by an eventual server update.

When you have some secret state like seed, you cannot reliably run code that depends on it on the client (because it is not available there). So, the the two approaches are:

1. Resolve a move in two steps: "throw the die" in moves and "let it fall" in flow.
2. Only allow calls that use random inside flow (throw an error if used in moves).

Also note that seed can be kept entirely inside G if you want to avoid writing custom code and just use existing mechanisms like onMove to keep the PRNG state.

[Stefan-Hanke]

While coding along I've noticed that there are two APIs that are currently inside one module

1. The public-facing API that is to be used by games
2. The internal-facing API that is used to make it work.

I've split these apart into separate modules. Part 1 could be added to packages/core.js, Part 2 is only used directly inside the module that performs evaluating the requested random operations.

What do you think?

[Stefan-Hanke]

When embedding runrandom inside processMove, the _Gamelog rewind_ (inside _log.test.js_) breaks. Something looks fishy here, I can't imagine how it can monitor that operation other than fiddling with the objects. I need to take a look later.

[Stefan-Hanke]

OK. Turns out that test used plain numbers for G. I hope you don't mind that I changed it to be an object with one key arg.

I'm royally unsure about my changes in the rollup config.

[weatherfordmat]

I think it's easier to just wait on this PR to go through before fixing the rollDice (onClick) function in the UI package.

[nicolodavis]

Yep, sounds good. I'm happy to make the necessary changes to your PR before merging it in too.

[Stefan-Hanke]

It's unfortunate that Math.seedrandom() was dropped. It looks like we could have saved all hassle by just avoiding seedrandom altogether and inline the alea code, which is comprised of some ten lines of code. I don't know whether the seedrandom library itself does not behave like a typical npm module would, or whether it was its usage...

[nicolodavis]

The problem is that it relies on a global this (see issue here), which does not play well with Rollup. Yeah, let's consider inlining the PRNG code. I think that would be good.

[Stefan-Hanke]

I think, now that the functions to generate random numbers are readily usable (without really thinking about how they work), there's no urgent need to add more expresiveness. One can always write a rollDice function that does want is needed.

Some small changes would make the API more usable, though.

• We could allow to throw more than one die: Random.D6(5) would return an array of D6 values. However, then the return value would be either a number or an array, which I particularly dislike. But perhaps this is ok in JavaScript?
• We could add a function to evaluate strings like 5D6 4D8 10D20. I'm unsure about what to return from that function, but I think it could make that code very expressive.

[nicolodavis]

The first idea sounds good to me. Having return values that depend on the inputs shouldn't be alien to JS developers.

I'm not sure we should be in the business of parsing string expressions to generate Random calls though. Feels more like an add-on that could live in a separate library and be optionally merged here if it becomes popular.

[Stefan-Hanke]

Well, the function could return a straight number when just calling Random.D6(), and always an array when a number argument is provided, even when calling Random.D6(1).

[nicolodavis]

Yes, that's what I was thinking too.