Replacing "chance per tick"

[actual-nh]

This is inspired by something @kevingranade wrote in #47186:

I'm moving everything possible away from the "chance to happen per tick" model. It's a very attractive concept and I've used it extensively in the past, but once you start adding in testing it turns out that we are not performing enough iterations of these actions to make the "law of large numbers" kick in, so instead of being a nice way to handle sub-unit probabilities, it instead injects a significant degree of randomness into the system.

If there are instances when "chance to happen per tick" looks to be, aside from the over-dispersion, the best model, I can see a few ways to regulate this. Most are based around having something be sampling without replacement instead of sampling with replacement:

• The crudest way to do this is to, for instance, have a population of 0s and 1s for whether something happens on a tick (proportion of 1s = likelihood per tick; size of population vs number of draws determines variance) and each tick draw a sample from this population without replacing it. For better performance, this can be simulated using a negative hypergeometric distribution - this will determine the number of ticks between samples of 1 for a hypothetical population size and proportion. (It may be easier to do via simulating a hypergeometric distribution.) As it is, you're doing a poisson or related distribution, and you can't control the variance/SD separately from the mean.
• If you're needing something more continuous happening each tick, then you either need to decrease the variance of the random distribution, or transform it to have a negative correlation (quasirandom sequence, error correction, or whatever) - if it's averaging too high, reduce it, and vice-versa. This can be thought of as sampling from a continuous distribution without replacement (for instance, you figured up a series of changes that add up to what you want, then scrambled what order they happen in).
• If the likelihood of something happening may be variable (e.g., affected by a field's intensity), then one could do somewhat of a combination of the above - generate a set of quasirandom numbers, scramble the order, and compare them to the desired probability.

I'm tired and probably not explaining the above terribly clearly (plus got slightly mixed up on the first one)... This is also relevant to, for instance, some of the work @Venera3 has been doing, both on venoms/effects and on maps - with the latter, the question of how different generated overmaps should be from each other.

[kevingranade]

The alternative is to remove the randomness entirely. If you aren't trying to inject randomness for some reason, you shouldn't invoke randomness.
When there is randomness needed, for example the probability of a contested combat action succeeding, or random placement of entities during mapgen, of course you want randomness of some kind.
But in general we should be looking at most uses of randomness in the game and asking ourselves whether the randomness is providing a tangible benefit.

[actual-nh]

Agreed re not using randomness where it isn't needed (if it's present due to roundoff, have the underlying value use a double and/or change the scale, for instance). But quite frequently one wants a controlled amount of randomness to keep everything from always proceeding the exact same way (same number of hours for an illness to develop, say).

Randomness can also be useful in avoiding synchronies between regular events creating problems - the temporal equivalent of a moire effect. (Another way, when applicable, is to have prime number time periods - avoiding synchronization with predators gets you thirteen-year cicadas, etc.)

[Venera3]

In the current effect system per tick chance is useful for two things:

• It allows for nonlinear scaling of effect averages, with only changing X_chance allowing for exponential and concurrently changing X_chance_bot allowing for logarithmic scaling (thanks again for fixing that, I'll swing back to using it one of these days). This I could see replaced with a more deterministic approach, potentially defining a starting value, an endpoint, a desired scaling form and maybe an inflection point. Good candidates for this would be continous low-impact effects, like thirst, stamina drain or damage.
• It enables stochastic symptoms, like "you will probably throw up once a day, but no telling when". Turning those deterministic is also doable, but it would open the way to gaming the system ( "I got food poisoning at 08:17, I should not eat until after my 10:37 vomit session is over").

[actual-nh]

I note frequent fails in the fields tests (see #47512 and #46256 - the latter reduced by @Aivean's helpful PR) due to, for instance, random failures to spread. To what degree could/should the variance-control techniques I discussed above be used to help this?

[kevingranade]

One thing I've been considering for field spread to both reduce calculation overhead and to make it more deterministic is to adopt the https://en.wikipedia.org/wiki/Gillespie_algorithm , which means when we have a field with a chance to spread (or split, or mutate in any way), we instead determine when the event will occur and record it, then we only check whether that threshold has been reached each turn. There are additional complications, such as the need to reset field state if something else modifies the field or its surroundings (with the caveat that processes that are highly reactive to their surroundings can't benefit from this algorithm in the same way since they would be constantly invalidated).

As for determinism, this means we can put an upper bound on how long it takes for a field spread event to occur in some nominal scenario based on the parameters we feed to the algorithm.

[actual-nh]

Nice! This could be put together with the "draw without replacement" idea above - Monte-Carlo methods frequently use quasirandom distributions - or the time taken for an event can be more-directly simulated with a negative binomial distribution, with the ability to choose a lower standard deviation than the effectively-fixed one for a Poisson distribution. (This can be substituted for the Poisson distribution in a boosted-performance version of the Gillespie algorithm - tau-leaping.)