Need for predictable random generator


Question

I'm a web-game developer and I got a problem with random numbers. Let's say that a player has 20% chance to get a critical hit with his sword. That means, 1 out of 5 hits should be critical. The problem is I got very bad real life results — sometimes players get 3 crits in 5 hits, sometimes none in 15 hits. Battles are rather short (3-10 hits) so it's important to get good random distribution.

Currently I use PHP mt_rand(), but we are just moving our code to C++, so I want to solve this problem in our game's new engine.

I don't know if the solution is some uniform random generator, or maybe to remember previous random states to force proper distribution.

1
151
4/9/2016 6:25:34 PM

Accepted Answer

I agree with the earlier answers that real randomness in small runs of some games is undesirable -- it does seem too unfair for some use cases.

I wrote a simple Shuffle Bag like implementation in Ruby and did some testing. The implementation did this:

  • If it still seems fair or we haven't reached a threshold of minimum rolls, it returns a fair hit based on the normal probability.
  • If the observed probability from past rolls makes it seem unfair, it returns a "fair-ifying" hit.

It is deemed unfair based on boundary probabilities. For instance, for a probability of 20%, you could set 10% as a lower bound and 40% as an upper bound.

Using those bounds, I found that with runs of 10 hits, 14.2% of the time the true pseudorandom implementation produced results that were out of those bounds. About 11% of the time, 0 critical hits were scored in 10 tries. 3.3% of the time, 5 or more critical hits were landed out of 10. Naturally, using this algorithm (with a minimum roll count of 5), a much smaller amount (0.03%) of the "Fairish" runs were out of bounds. Even if the below implementation is unsuitable (more clever things can be done, certainly), it is worth noting that noticably often your users will feel that it's unfair with a real pseudorandom solution.

Here is the meat of my FairishBag written in Ruby. The whole implementation and quick Monte Carlo simulation is available here (gist).

def fire!
  hit = if @rolls >= @min_rolls && observed_probability > @unfair_high
    false
  elsif @rolls >= @min_rolls && observed_probability < @unfair_low
    true
  else
    rand <= @probability
  end
  @hits += 1 if hit
  @rolls += 1
  return hit
end

def observed_probability
  @hits.to_f / @rolls
end

Update: Using this method does increase the overall probability of getting a critical hit, to about 22% using the bounds above. You can offset this by setting its "real" probability a little bit lower. A probability of 17.5% with the fairish modification yields an observed long term probability of about 20%, and keeps the short term runs feeling fair.

39
10/30/2012 9:40:46 PM

That means, 1 out of 5 hits should be critical. The problem is I got very bad real life results - sometimes players get 3 crits in 5 hits, sometimes none in 15 hits.

What you need is a shuffle bag. It solves the problem of true random being too random for games.

The algorithm is about like this: You put 1 critical and 4 non-critical hits in a bag. Then you randomize their order in the bag and pick them out one at a time. When the bag is empty, you fill it again with the same values and randomize it. That way you will get in average 1 critical hit per 5 hits, and at most 2 critical and 8 non-critical hits in a row. Increase the number of items in the bag for more randomness.

Here is an example of an implementation (in Java) and its test cases that I wrote some time ago.


Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon