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.

Solution 1

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.

Solution 2

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.

Solution 3

You've got a misunderstanding of what random means.

Which of these is more random?

While the second plot looks more evenly distributed, the more random is actually the first plot. The human mind often sees patterns in randomness, so we see the clumps in the first plot as patterns, but they're not - they're just part of a randomly selected sample.

Solution 4

Given the behavior you're asking for, I think you're randomizing the wrong variable.

Rather than randomizing whether this hit will be critical, try randomizing the number of turns until the next critical hit occurs. For example, just pick a number between 2 & 9 every time the player gets a critical, and then give them their next critical after that many rounds have passed. You can also use dice methods to get closer to a normal distribution -- for example, you will get your next critical in 2D4 turns.

I believe this technique gets used in RPGs that have random encounters in the overworld as well -- you randomize a step counter, and after that many steps, you get hit again. It feels a lot more fair because you almost never get hit by two encounters in a row -- if that happens even once, the players get irritable.

Solution 5

First, define "proper" distribution. Random numbers are, well, random - the results you're seeing are entirely consistent with (pseudo) randomness.

Expanding on this, I assume what you want is some feeling of "fairness", so the user can't go 100 turns without a success. If so, I'd keep track of the number of failures since the last success, and weight the generated result. Let's assume you want 1 in 5 rolls to "succeed". So you randomly generate a number from 1 to 5, and if it's 5, great.

If not, record the failure, and next time, generate a number from 1 to 5, but add on say, floor(numFailures / 2). So this time, again, they have a 1 in 5 chance. If they fail, next time the winning interval is 4 and 5; a 2 in 5 chance of success. With these choices, after 8 failures, they are certain to succeed.

View more solutions

Comments

[Fidor]

There is about a 0.5% chance of exactly 3 critical hits and 2 non-critical ones and a 3.5% chance of 15 non-critical hits in a row, assuming true random numbers.

[ConcernedOfTunbridgeWells]

+1 to above. One characteristic of random numbers is that you get outliers.

[erikkallen]

@Nixus: No, it's approx 5% chance of 3 critical hits and 2 non-critical ones, you are forgetting to multiply with (5! / (3!*2!)) = 10. With 95% confidence level, it is not statistically unlikely for 3 critical hits to happen in 5 strikes.

[SergioL]

At first I thought this was a silly question...once again, I'm humbled by SO.

[andriy]

dilbert.com/strips/comic/2001-10-25

[samjudson]

And why would that make any difference? There is an exactly equal chance of getting a critical for both sets of numbers.

[Eoin Campbell]

On that note... would teh range of random numbers affect the distribution... e.g. choosing a Random r = new Random(); r.Next(1,5) vs. r.Next(1, 1000000) % 200000

[Thomas Owens]

Exactly. I'm just presenting two options for him for his 20% example. Although 100 would probably work better if you are dealing with whole number percentages, as you would only need to simulate one "die", if you want to think of it like that.

[Arjan Einbu]

Good one, but will this solve the OPs random number distribution problem? ;-)

[ceejayoz]

The options you're presenting are exactly what he's already doing.

[Steve Jessop]

Note that if you do this, then their overall proportion of successes will be greater than 1 in 5. A way around that is to (for example) choose 20 different numbers at random from the range 1..100, and predetermine that those will be their criticals. It's a bunch more bookkeeping, though.

[Michael Borgwardt]

Actually, the function he is using is the same as the best RNG in the boost library.

[Colin Pickard]

Not really; He's asking for a non-random RNG, for which he could use this function; but what he really wants is better explained by the current top answer (stackoverflow.com/questions/910215/910224#910224)

[ceejayoz]

Not for what he wants. He wants a non-random number generator, even if he thinks that's called a random number generator.

[ceejayoz]

The OP already is doing that sort of thing. He misunderstands 'random' and actually wants a non-random generator that takes into account past rolls.

[Grant Peters]

Though there is still a chance that after a few million flips, you still will have only seen one side of the coin. Though if this ever happens, you're probably sitting too close to an infinite improbability drive :P

[Grant Peters]

this is not random at all, its just every 5th hit is a critical, he still wants some randomness, he justs wants it to be "fair" to the player (i.e. doesn't want the player getting annoyed that they haven't got a hit in over 50 attacks, or something like that, which is entirely possible when using a standard PRNG)

[tstenner]

Wait, an answer suggesting boost::something gets downvoted? I'm shocked!

[Ed James]

haha, yeah but the chance is so incredibly low that the laws of maths say you should see an even(ish) distribution.

[Çağdaş Tekin]

This is more random than the OP wants

[Thinker]

I think this is great solution, but what about 80% chance?

[Raquel]

I like to use multi-dimensional random generators at times as well. Chance to hit + Chance to power + Chance to critical. Just like rolling several different dice in D&D

[Thinker]

When you got 3500 players online fighting 10000 battles in a minute, problem that occurs in 3% of battles is very common problem.

[MSalters]

Then again, bad luck that occurs in 3% of battles is still just bad luck.

[MSalters]

You get most of the effect by just taking the last attack in account. Let P be the observed hit rate, R the hit rate after a miss and R/2 the hit rate after a hit. By definition, at any point you then have a chance to hit of P = P*R+(1-P)*(R/2). This means P = R / (2-R)

[Stephan]

Not sure what language you were aiming for but in C# and I believe C++ your method always returns true because crit always equals 0. You need to change it to ++crit instead.

[Matthew]

I like this sort of approach. I would probably do it the other way. Start with a lower chance and build up to the maximum of 20%+some added percentage until it hits and reset again to some low amount.

[Neil G]

this is pretty similar to my solution, except that it only "remembers" the time since the last critical hit. Under this solution, a string of 4 critical hits is the same as a string of 1 critical hit as far as probabilities about the future. So, if critical hits are good, this solution limits your downside risk, but not your upside. My solution affects both.

[Dietrich Epp]

Technically speaking, you can't measure randomness. Both distributions look fairly arbitrary to me, although my guess is both were algorithmically generated. You can perform a number of tests on the first plot and determine that it's likely to come from a process that places points according to a uniform distribution, but you won't be able to conclude that it's more random. As a counterexample, you could make a plot like the first using a linear congruential generator, then make a plot like the second using amplified noise from a zener diode. Try the word uncorrelated instead of random.

[ceejayoz]

You can measure the probability that a said distribution is random.

[Dark]

It's obvious that different solutions have their own benefits. This one focuses on keeping randomness clean from science point of view. It doesn't mean, that its somehow better, than shuffle bag or anything else. It's just a solution that seems worth of trying.

[Thinker]

I think this is best solution that suits my needs. Shuffle bag mentioned in best pointed answer is not bad, but needs lots of calculation, and I like simplest solution that leads to the target.

[Alex319]

One problem with this is that it only works if the probability of a critical is roughly constant between hits. Suppose that mid-battle the player casts a spell that doubles their likelihood of a critical hit. Then how do you adjust the number of turns?

[BlueRaja - Danny Pflughoeft]

@Dietich: Of course you can measure randomness

[Alice Purcell]

+1 Very nice, also handles less round to-hit probabilities than 20% very easily.

[Alice Purcell]

@Alex319 Treat a double-likelihood spell as two chances at a critical hit -- so casting it continuously would effectively just halve the number of turns to the next critical. This should be easy to generalize.

[greyfade]

-1 because RFC1149 has no section 5 (and alternately, there is no 1149.5); +1 for fair randomness.

[Danger Code master]

@Thinker For an 80% average, you should get a critical 4/5 hits. So roll 1d4; on a 1, skip 1 turn before giving them a critical; and on a 2-4, you'll get a critical on the following turn. This should generate a non-critical approximately one turn in five, or critical 4/5 times. There are other ways to distribute it, but IMO that's the simplest.

[ceejayoz]

I've heard a variant on this - "a one in a million event happens 6,000 times in the world's population".

[Kip]

To be fair, while OP may not be using the correct terms, he understands that random number generator is giving him something more like the first graph, when he wants something more like the second graph because it feels more "fair" to the user.

[Admin]

This should be my desktop wallpaper!!