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.

+48  A: 

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.

Adam Wright
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
Eoin Campbell
+1 for seeing the problem behind the request instead of telling the OP he misunderstands random.
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.
Steve Jessop
"will be greater than 1 in 5" - is expected to be in the long run, I mean.
Steve Jessop
You could scale the starting probability down a bit, so that the overall proportion is reduced to 1/5. I haven't worked out how much you have to reduce it by, but everything is continuous so there must be a right answer.
Steve Jessop

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.

Thomas Owens
And why would that make any difference? There is an exactly equal chance of getting a critical for both sets of numbers.
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.
Thomas Owens
The options you're presenting are exactly what he's already doing.
Then he's doing it the right way.
Thomas Owens
Not for what he wants. He wants a non-random number generator, even if he thinks that's called a random number generator.
+7  A: 

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.

he wants game friendly random, if you use strict random generated numbers in some cases you end up having "korean random" results.Those are random results that make players get angry and frustrated way too often (ask any lineage 2 player) ;)
Consequently, if the first hit is a crit, the next four will not be. It does sound like this is what the OP wants, but when you word it like this, it sounds retarded. You get my UV for that.
-1 you appear to be confusing "random" with "memoryless" --
+8  A: 

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.


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)

What was that downvote for?
Weak math - no critical hits in 15 attempts is still a 3.5% chance. Unlikely but "improbable" isn't the word you're looking for.
Wait, an answer suggesting boost::something gets downvoted? I'm shocked!
FYI: This doesn't solve his problem, it just makes it the same problem in a different language.
+6  A: 

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.

Ed Woodcock
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
haha, yeah but the chance is so incredibly low that the laws of maths say you should see an even(ish) distribution.
Ed Woodcock
+7  A: 

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.

Hank Gay
+20  A: 
Colin Pickard
Good one, but will this solve the OPs random number distribution problem? ;-)
Arjan Einbu
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 (
Colin Pickard
I was wondering when this would turn up
Ed Woodcock
@Ed yep, me too
This is more random than the OP wants
-1 because this is just smartassed
+1 because it brings out an insight into randomness.
+90  A: 
Good Numb3rs explanation!
Yeah - Wasn't this explained with raindrops?^^
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.
Dietrich Epp
You can measure the probability that a said distribution is random.
@Dietich: [Of course you can measure randomness](
BlueRaja - Danny Pflughoeft
+4  A: 

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.

Actually, the function he is using is the same as the best RNG in the boost library.
Michael Borgwardt
MT isn't the "best", last I checked. It's nice, simple and fast, but it doesn't produce the best distribution.Anyway, grab a million random numbers and check the distribution. Find out if your random function actually gives you a uniform distribution or not. If it doesn't, find a better generator. If it does, either suck it up and accept the occasional row of crits, or cheat and make results *less* random and more predictable.
+65  A: 

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.

Randomising the number of turns is a good idea!
+1 - great idea!
Eric Petroelje
I think this is great solution, but what about 80% chance?
Matthew Whited
I like this idea, and you're completely correct about the step counter thing, that's been used in final fantasy for a very long time, for example
Ed Woodcock
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?
+1 Very nice, also handles less round to-hit probabilities than 20% very easily.
@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.
+6  A: 

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.

Michael Borgwardt
+3  A: 

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

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

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.
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)
Grant Peters
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.
+23  A: 

Hopefully this article will aid you:
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.

As a poker player, I can assure you that this is more true than anyone appreciates.
+172  A: 

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.

Esko Luontola
+ 1 for good idea without criticism. Scale the bag for a higher degree of randomness, and to handle the variances in critical chance between players (if variable ofc)
The idea is good, but how make it work with bag size 100, 13% critical hit chance, when there would be only 10 turns? Bag won't be emptied and I can still have no critical.
And what if the opponent cast a spell, that lowers chance to critical hit?
You could have a bag size of 10. Put in 1 hit, plus a 30% chance of a second. If critical chance changes, you could just throw away the bag and start a new one. Do note that any such scheme runs the risk that if you (or your opponent) know your critical hit probability and the size of the bag, you can sometimes know for sure that you will not get another critical for a certain number of rolls. This might affect tactics.
Steve Jessop
Yeah... in something like this you run ricks similar to card counting. Do I risk a peon or go in for the big kill... a small fixed set of potential outcomes can decrease the risk of loss and increase the chance of being "gamed"
Matthew Whited
Please see my response-- a generalization of your solution.
Neil G
I like the shuffle bag idea but I don't think this match the game "spirit" because your critical hit probability of 20% (which means you can do none in 10 hits) is not a probability anymore. It becomes exactly 1 hit every 5 hits.Moreover, rerolling the bag if critical hit probability change will cause a glitch in the game. If my critical hit has been done, I'll cast the spell on myself to get next critic earlier :p
The nice things about shuffle bags is that you can refill them. So if you want to implement "lowers chance of critical strike", drop in a few "miss" events. If the user was unlucky in the past, there will still be a bunch of "hit" events remaining.
@Tyalis, if having exactly 4 regular hits and 1 critical hit in the bag, then yes, you're guaranteed 1 in 5. but make the bag larger and keep the ratio the same -- 40 regulars and 10 criticals -- and your keep the initial odds while at the same time increasing the odds for subsequent 'grabs' (after failure). Really a bag of significant size, say 40000 regulars and 10000 criticals, would be sufficiently close to the original, unpredictable, randomness. It's a manageable problem... just a question of how big an impact a success or failure should have on the odds of subsequent grabs from the bag
Jonathan Fingland
Good idea. However,as the other commenters pointed out, you can run into the risk of card-counting. However, how about randomizing the size of the bag also, before each refill, something between size 5 and 10?
@Jonathan: making the bag the large size you give it actually undoes the whole bag-idea: to make sure something happens (the critical that is achieved) within an acceptable amount of throws. Making the bag 50000 large is about just the same as using the random number generator.

Pre-calculate a random critical hit for each player.

// OnAttack()
c_h = c_h -1;
if ( c_h == 0 ) {
 // Yes, critical hit!
 c_h = random(5) + 1 // for the next time
 // ...
Nick D
+2  A: 
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)
+13  A: 

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

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.


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

When you got 3500 players online fighting 10000 battles in a minute, problem that occurs in 3% of battles is very common problem.
Then again, bad luck that occurs in 3% of battles is still just bad luck.

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.

+1  A: 


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.

+5  A: 

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
    if(current_chance > base_chance)
        current_chance = base_chance; // reset the chance.
        current_chance *= 0.8; // decrease the crit chance for the NEXT hit.
    //no crit.
    if(current_chance < base_chance)
        current_chance = base_chance; // reset the chance.
        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...

Paulius Maruška
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.
+18  A: 

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
  elsif @rolls >= @min_rolls && observed_probability < @unfair_low
    rand <= @probability
  @hits += 1 if hit
  @rolls += 1
  return hit

def observed_probability
  @hits.to_f / @rolls

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.

Ian Terrell
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.
+4  A: 

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

Neil G
+1  A: 

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


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

Michael J
Some values in my game like critical hit can't have more than 50% chance, so I'm blocking repeating at all, but this lowers chance of event for some percents.

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.

+2  A: 

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.

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.
Neil G
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.
+1  A: 

I recommend a progressive percentage system like Blizzard uses:

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

if ( randNumber <= .2 ) {
} else {

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

if (randNumber <= .2 + progressiveChance ) {
   progressiveChance = 0;
} 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.


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

Leo Jweda
+1  A: 

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.


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);

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


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 don't use matlab since my studies, some comments to code would be nice :)

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


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

+1  A: 

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)