Need for predictable random generator

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.

> 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.

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.

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.

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.

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.

How about replacing mt_rand() with something like this?

(RFC 1149.5 specifies 4 as the standard IEEE-vetted random number.)

From XKCD.

Hopefully this article will aid you: http://web.archive.org/web/20090103063439/http://www.gamedev.net:80/reference/design/features/randomness/

This method of generating 'random numbers' is common in rpg/mmorpg games.

The problem it solves is this (extract): >A blade spider is at your throat. It hits and you miss. It hits again and you miss again. And again and again, until there's nothing left of you to hit. You're dead and there's a two-ton arachnid gloating over your corpse. Impossible? No. Improbable? Yes. But given enough players and given enough time, the improbable becomes almost certain. It wasn't that the blade spider was hard, it was just bad luck. How frustrating. It's enough to make a player want to quit.

What you want are not random numbers, but numbers which seem random to a human. Other have already suggested individual algorithms, which can help you, like Shuffle Bag.

For a good detailed and extensive analysis of this domain see AI Game Programming Wisdom 2. The whole book is worth reading for any game developer, the idea of "seemingly random numbers" is handled in chapter:

Filtered Randomness for AI Decisions and Game Logic:

> Abstract: Conventional wisdom suggests that the better the random number generator, the more unpredictable your game will be. However, according to psychology studies, true randomness over the short term often looks decidedly unrandom to humans. This article shows how to make random AI decisions and game logic look more random to players, while still maintaining strong statistical randomness.

You may also find another chapter interesting:

The Statistics of Random Numbers

> Abstract: Random numbers are used most heavily by Artificial Intelligence and games in general. To ignore their potential is to make the game predictable and boring. Using them incorrectly can be just as bad as ignoring them outright. Understanding how random numbers are generated, their limitations and their capabilities, can remove many difficulties of using them in your game. This article offers insight into random numbers, their generation, and methods to separate good ones from bad.

Surely any random number generation has the chance of producing such runs? You're not going to get a big enough sample set in 3-10 rolls to see appropriate percentages.

Maybe what you want is a mercy threshold ... remember the last 10 rolls, and if they haven't had a critical hit, give them a freebie. Smooth out the slings and arrows of randomness.

Your best solution might be play-testing with multiple different nonrandom schemes and pick the one that makes players happiest.

You might also try a back-off policy for the same number in a given encounter, e.g., if a player rolls a 1 on their first turn accept it. To get another 1 they need to roll 2 1s in a row. To get a third 1 they need 3 in a row, ad infinitum.

Unfortunately what you are asking for is effectively an non-random number generator - because you want previous results to be taken into account when determining the next number. This isn't how random number generators work I'm afraid.

If you want 1 out of every 5 hits to be a critical then simply pick a number between 1 and 5 and say that that hit will be a critical.

mt_rand() is based on a Mersenne Twister implementation, which means it yields one of the best random distributions you can get.

Apparently what you want is not randomness at all, so you should start out specifying exactly what you want. You'll probably realize you have conflicting expectations - that the results should be truely random and not predictable, yet at the same time they should not exhibit local variations from the stated probability - but then it becomes predictable. If you set a maximum of 10 non-crits in a row, then you've just told players "if you've had 9 non-crits in a row, the next one will be critical with 100% certainty" - you might as well not bother with randomness at all.

Over such a small number of tests you should expect results like that:

True randomness is only predictable over a huge set size, such that it's quite possible to flip a coin and get heads 3 times in a row first time, however over a few million flips you will end up with apporximately 50-50.

I see a lot of answers suggesting to keep track of the previously generated numbers or to shuffle the all possible values.

Personally, I do not agree, that 3 crits in a row is bad. Nor I agree that 15 non-crits in a row is bad.

I would solve the problem, by modifying the crit chance it self, after each number. Example (to demonstrate the idea):

int base_chance = 20;
int current_chance = base_chance;

int hit = generate_random_number(0, 100) + 1; // anything from 1 to 100
if(hit < current_chance)//Or whatever method you use to check
{
    //crit!
    if(current_chance > base_chance)
        current_chance = base_chance; // reset the chance.
    else
        current_chance *= 0.8; // decrease the crit chance for the NEXT hit.
}
else
{
    //no crit.
    if(current_chance < base_chance)
        current_chance = base_chance; // reset the chance.
    else
        current_chance *= 1.1; // increase the crit chance for the NEXT hit.
    //raise the current_chance
}

The longer you don't get a crit - the higher chance you have for your next action to crit. The reset I included is entirely optional and it would need testing to tell if it's needed or not. It may or may not be desirable to give a higher probability of a crit for more than one action in a row, after a long non-crit action chain.

Just throwing in my 2 cents...

The top few answers are great explanations, so I'll just focus on an algorithm that gives you control over the probability of "bad streaks" while never becoming deterministic. Here's what I think you should do:

Instead of specifying p, the parameter of a Bernoulli distribution, which is your probability of a critical hit, specify a and b, the parameters of the beta distribution, the "conjugate prior" of the Bernoulli distribution. You need to keep track of A and B, the number of critical and non-critical hits so far.

Now, to specify a and b, ensure that a/(a+b) = p, the chance of a critical hit. The neat thing is that (a+b) quantifies how close you want the A/(A+B) to be to p in general.

You do your sampling like this:

let p(x) be the probability density function of the beta distribution. It is available in many places, but you can find it in the GSL as gsl_ran_beta_pdf.

S = A+B+1
p_1 = p((A+1)/S)
p_2 = p(A/S)

Choose a critical hit by sampling from a bernoulli distribution with probability p_1 / (p_1 + p_2)

If you find that the random numbers have too many "bad streaks", scale up a and b, but in the limit, as a and b go to infinity, you will have the shuffle bag approach previously described.

If you implement this, please let me know how it goes!

If you want a distribution that discourages repeat values, you could use a simple repeat rejection algorithm.

e.g.

int GetRand(int nSize)
{
    return 1 + (::rand() % nSize);
}
int GetDice()
{
    static int nPrevious=-1;
    while (1) {
        int nValue = GetRand(6);
        // only allow repeat 5% of the time
        if (nValue==nPrevious && GetRand(100)<95)
            continue;
        nPrevious = nValue;
        return nValue;
    }
}

This code rejects repeat values 95% of the time, making repeats unlikely but not impossible. Statistically it is a bit ugly, but it will probably produce the results you want. Of course, it won't prevent a distribution like "5 4 5 4 5". You could get fancier and reject the second last (say) 60% of the time and third last (say) 30%.

I'm not recommending this as good game design. Simply suggesting how to achieve what you want.

It's not really clear what you want. It is possible to create a function such that the first 5 times you call it, it returns the numberes 1-5 in a random order.

But that's not really random. The player will know that he's going to get exactly one 5 in the next 5 attacks. It might be what you want though, and in that case, you simply have to code it yourself. (create an array containing the numbers and then shuffle them)

Alternatively, you could keep using your current approach, and assume that your current results are due to a bad random generator. Note that nothing may be wrong with your current numbers. Random values are random. sometimes you get 2, 3 or 8 of the same value in a row. Because they're random. A good random generator just guarantees that on average, all the numbers will be returned equally often.

Of course if you've been using a bad random generator, that might have skewed your results, and if so, simply switching to a better random generator should fix the problem. (Check out the Boost.Random library for better generators)

Alternatively, you could remember the last N values returned by your random function, and weigh the result by those. (a simple example would be, "for each occurrence of the new result, there's a 50% chance we should discard the value and get a new one"

If I had to guess, I'd say sticking with "actual" randomness is your best bet. Make sure you use a good random generator, and then keep going the way you're doing it now.

You could create a list containing the numbers from 1 to 5, and have them sorted by randomness. Then just go through the list you created. You have a guarantee of running into every number at least once... When you're through with the first 5, just create another 5 numbers...

Well, if you are into math a little, you can probably try Exponential distribution

For example, if lambda = 0.5, expected value is 2 (go read that article!), means you will most probably hit/crit/whatever every 2nd turn (like 50%, huh?). But with such probability distribution, you will definetevely miss (or do opposite to whatever) at 0th turn (the one, in which event had already occured and turn_counter had been reseted), have like 40% chance to hit next turn, about 65% chance to do it 2nd (next after next) turn, about 80% to hit 3rd and so on.

The whole purpose of that distribution is if one has 50% hit chance and he misses 3 times in a row, he wil shurely (well, over 80% chance, and it increases every next turn) hit. It leads to more "fair" results, keeping overal 50% chance unchanged.

Taking your 20% chance of crit, you have

• 17% to crit 1st turn
• 32% to crit 2nd turn, if no crit occures in all previous ones.
• 45% to crit 3rd turn, if no crit occures in all previous ones.
• 54% to crit 4th turn, if no crit occures in all previous ones.
• ...
• 80% to crit 8th turn, if no crit occures in all previous ones.

Its still about 0.2% (vs those 5%) chance of 3 crits + 2 non-crits in 5 consequent turns. And there is 14% chance of 4 consequent non-crits, 5% of 5, 1.5% for 6, 0.3% for 7, 0.07% for 8 consequent non-crits. I bet its "more fair" than 41%, 32%, 26%,21% and 16%.

Hope you still don't bored to death.

I recommend a progressive percentage system like Blizzard uses: http://www.shacknews.com/onearticle.x/57886

Generally you roll a RNG then compare it to a value to determine if succeed or not. That may look like:

if ( randNumber <= .2 ) {
   //Critical
} else {
   //Normal
}

All you need to do is add in a progressive increase in base chance...

if (randNumber <= .2 + progressiveChance ) {
   progressiveChance = 0;
   //Critical
} else {
   progressiveChance += CHANCE_MODIFIER;
   //Normal hit
}

If you need it to be more fancy it's pretty easy to add in more. You can cap the amount that progressiveChance can get to avoid a 100% critical chance or reset it on certain events. You can also have progressiveChance increase in smaller amounts each boost with something like progressiveChance += (1 - progressiveChance) * SCALE where SCALE < 1.

What about making the chance of critical depend on the last N attacks. One simple scheme is some kind of markov chain: <http://en.wikipedia.org/wiki/Markov_chain> but the code is very simple anyway.

IF turns_since_last_critical < M THEN
critial = false
turns_since_last_critical++;
ELSE
critial = IsCritical(chance);
IF Critial THEN
turns_since_last_critica = 0;
ELSE
turns_since_last_critica++;
END IF;
END IF;

Of course you must make your maths because the chance of a critical is lower than the chance of a critical once you know that it has been enough turns since the last one

OP,

Pretty much, if you want it to be fair, its not going to be random.

The problem of your game is the actual match length. The longer the match is, the less randomness you are going to see(crits will tend to be 20%) and its going to approach your intended values.

You got two options, pre-calculate the attacks based on previous rolls. Which will you get one crit every 5 attacks(based on yours 20%), but you can make the order it occurs random.

listOfFollowingAttacks = {Hit,Hit,Hit,Miss,Crit};

That's the pattern you want. So make it choose randomly from that list, until its empty, them re-create it.

That's a pattern I created for my game, it works quite well, for what I want it to do.

your second option, would be, increase the chance to crit, you are probably going to see a more even number in the end of all attacks(presuming that your matches ends rather quickly). The less % chance, the more RNG'd you get.

You are looking at a linear distribution, when you probably want a normal distribution.

If you remember back in your youth playing D&D, you were asked to roll multiple n-sided die, then sum the results.

For instance, rolling 4 x 6-sided die is different than rolling 1 x 24-sided dice.

this one is really predictable... but you can never be sure.

City of Heroes actually has a mechanic called the "streakbreaker" that solves exactly this problem. The way it works is that after a string of misses of a length related to the lowest to-hit probability in the string, the next attack is guaranteed to be a hit. For example if you miss an attack with over 90% to hit chance then your next attack will auto hit, but if your hit chance is lower like 60% then you'll need to have several consecutive misses to trigger the "streakbreaker" (I don't know the exact numbers)

How about weighting the value?

For example, if you have a 20% chance to critical hit, generate a number between 1 and 5 with one number representing a critical hit, or a number between 1 and 100 with 20 numbers being a critical hit.

But as long as you are working with random or pseudorandom numbers, there's no way to potentially avoid the results you are currently seeing. It's the nature of randomness.

Pre-calculate a random critical hit for each player.

// OBJECT
//...
// OnAttack()
//...
c_h = c_h -1;
if ( c_h == 0 ) {
 // Yes, critical hit!
 c_h = random(5) + 1 // for the next time
 // ...
}

Reaction on: "The problem is I got very bad real life results -- sometimes players get 3 crits in 5 hits, sometimes none in 15 hits."

You have a chance of somewhere between 3 and 4 % of getting nothing in 15 hits...

I would propose the following "randomly delayed putback die":

• Maintain two arrays, one (in-array) initially filled with the values from 0 to n-1, the other (out-array) empty
• When a result is requested:
• return a random value from all defined values in in-array
• move this value from in-array to out-array
• move one random (over all elements, including the undefined!) element from out-array back into in-array

This has the property that it will "react" more slowly the bigger n is. For example, if you want a 20% chance, setting n to 5 and hitting on a 0 is "less random" than setting n to 10 and hitting on a 0 or 1, and making it 0 to 199 out of 1000 will be almost indistinguishable from true randomness over a small sample. You will have to adjust n to your sample size.

I think perhaps you are using the wrong random distribution function. You probably don't want an even distribution over the numbers. Try a normal distribution instead so that the critical hits become more uncommon than the 'regular' hits.

I work with Java so I'm not sure where you can find something for C++ that gives you random numbers with a normal distribution but there has to be something out there.

As many say, it's really a problem with what's 'random'. The results you're getting are random, and no matter how you make the game, some players will feel your counter isn't fair and isn't random. ;)

One possible option might be to guarantee a hit every n times, and have n generated randomly, within certain boundaries, after each hit. It's all a question of what 'feels' right in playtesting.

That IS how it should be, it's probability, you shouldn't expect a critical hit 1ce every 5 battles.. try it with a coin or a dice and see for yourself. But that's just me. GB

I've also tried to solve this problem. The best I could come up with was dynamically changing the probabilities if the numbers based on how often they have come up in the immediate past. Something like (for a dice, in matlab):

probabilities = [1 1 1 1 1 1];
unrandomness = 1;
while true
    cumprob = cumsum(probabilities) ./ sum(probabilities);
    roll = find(cumprob >= rand, 1)
    probabilities = probabilities + unrandomness;
    probabilities(roll) = probabilities(roll) - 6*unrandomness;
    if min(probabilities) < 0
        probabilities = probabilities - min(probabilities);
    end
end

Sorry for lack of indentation. The unrandomness parameter can be adjusted as desired. True random output (unrandomness=0):

2 3 1 1 4 1 3 3 4 5 1 5 5 2 6 1 1 1 6 1 1 3 5 6 6 1 4 2 4 6 3 6 5 1 1 6 2 5 6 4 3 5 2 4 6 5 5 5 4 4 3 4 1 2

unrandomness=1:

3 2 4 5 6 2 6 2 4 1 5 5 1 6 4 3 1 4 2 1 3 2 6 5 3 6 5 3 1 4 1 6 5 3 4 2 1 6 5 4 1 4 3 1 6 6 5 4 3 1 5 2 3 2

Looks better I think. Especially if you plot the gaps between numbers.

I think you need to generate random numbers out of a Poisson Distribution.

The problem with bozo sort, it that it has the potential to take forever.

For C++ random-number generators, use rand or boost::random

Whenever a player is hit, you just check whether a random number in [0; 1] is less than 0.2. This implies that someone can get no critical hits in 15, but that's improbable.

This will give you natural random numbers according to the laws of a binomial distribution (p = 0.2)

static int crit = 0;

public bool isCritical()
{
   crit = crit++ % 5;
   return (crit==0);
} 

if you still want some randomness, alter the modulus using another static variable each time a crit is performed. varying it will equal probability from 3 to 7 should keep the average time between crits at 1 in 5, but never less than 3 or more than 7 hits between them.