16
\$\begingroup\$

I am working on a RPG that I have implemented spells with status effects that can be applied x% of the time. For instance a fire spell has a 25% chance to apply a burning debuff.

Initially I just put it at 0.25 and checked my random roll was less than or equal to the status effect's chance. The problem of course is that it could proc 10 times in a row or go 50 times without.

I decided to swap it over to a shuffle bag to correct the drought issues of it not procing. This gave the opposite problem where now it has become 1 out of 4 with 3 guaranteed failures and at most will hit twice in a row. It was just too predictable.

What I have since come up with is a gate where I leave it fully in the hands of RNG until it surpasses the average number of failures. That's the point I start injecting in extra weight up until a cap where a guaranteed success happens.

public class ChanceGate<TValue> { class ChanceContainer { public TValue Value { get; set; } public float Chance { get; set; } public int MissCount { get; set; } public int IncreaseThreshold => (int)Math.Ceiling(1f / Chance); public int MaxFailures => (int)Math.Ceiling(1f / Chance * 1.5); public void Reset(float chance) { Chance = chance; MissCount = 0; } } readonly Random _random; readonly float _originalChance; readonly float _failuresIncreaseBy; readonly ChanceContainer _chanceItem; public TValue Value => _chanceItem.Value; public ChanceGate(Random random, TValue value, float chance, float failuresIncreaseBy) { _random = random; _originalChance = chance; _failuresIncreaseBy = failuresIncreaseBy; _chanceItem = new ChanceContainer { Chance = chance, Value = value, }; } public bool Roll() { if (_chanceItem.MissCount >= _chanceItem.MaxFailures) { _chanceItem.Reset(_originalChance); return true; } if (_random.NextDouble() <= _chanceItem.Chance) { _chanceItem.Reset(_originalChance); return true; } _chanceItem.MissCount++; if (_chanceItem.MissCount >= _chanceItem.IncreaseThreshold) _chanceItem.Chance += _failuresIncreaseBy; return false; } }

There's a lot of fine tuning I need to do to get it to where I want, but this already has felt better than what was before. The chance of success has obviously increased over 1,000,000 iterations, but the droughts are no longer as severe. As much as I hate to force a failure, I might incorporate my characters' luck stat to determine if a streak ends or use that as the basis around how much weight gets added to try and get a success.

I am sure this concept already exists, but I have no idea what it is called in order to research it. Am I going down the right path? Are there other methodologies I should explore?

\$\endgroup\$
13
  • 5
    \$\begingroup\$ How about enlarging the size of the shuffle bags? just like changing 1/4 to 2/8. \$\endgroup\$ Commented Jul 18, 2022 at 4:20
  • \$\begingroup\$ @Mangata I tried that and all sorts of things today. I just didn't like the numbers I was seeing nor how it was playing out. This is a turn-based RPG and so the streaks are heavily noticeable. I've already changed my example up and it is now increasing chances on failure and diminishing chances on a hot streak. Over a 1,000,000 iterations my 25% is really 29% with my current numbers, but my max drought is 5 and max hit streak is 4. \$\endgroup\$ Commented Jul 18, 2022 at 4:47
  • 3
    \$\begingroup\$ This concept should be PRD(Pseudo Random Distribution). this and this are related. \$\endgroup\$ Commented Jul 18, 2022 at 6:45
  • 6
    \$\begingroup\$ There's a biased generator I designed for use in Far Cry loot drops, which I wrote up in a Twitter thread a few years ago. It works by tracking a "dueness" value for each outcome, so the farther from the expected rate it deviates, the more probability is biased to return it there. And it has a tunable "noise" parameter that lets you increase or decrease the influence of this bias. \$\endgroup\$ Commented Jul 18, 2022 at 13:11
  • 2
    \$\begingroup\$ Related Q&A: How can I make a "random" generator that is biased by prior events? \$\endgroup\$ Commented Jul 18, 2022 at 17:31

5 Answers 5

Reset to default
19
\$\begingroup\$

My first attempt would be to enlarge the shufflebag, as Mangata suggested in a comment. So instead of 3 guaranteed failures every 4 rolls, you now have 6 guaranteed failures every 8 rolls.

If you still find that too predictable, then an extension to this approach is to discard and recreate the shufflebag before it is empty. For example, let's take a 16 entry shufflebag with 4 wins and 12 losses which gets reshuffled after 4 draws. Getting all 4 wins is not impossible, but very, very rare:

  • 1st is a win: 4 in 16 or 25%
  • 2nd after that is also a win: 3 in 15 or 20%
  • 3rd after that is also a win: 2 in 14 or 14%
  • 4th after that is also a win: 1 in 13 or 7.7%

Cumulative chance to get a 4 win streak on a single shufflebag: 0,05%. And after the 4th draw, you get a new shufflebag and everything is open again. So even after this unlikely event there will never be absolute certainty what the next event will be.

Now in reality there is of course a higher chance for a 4 win streak if you consider that one bag might end on two wins and the next start with two wins. But that does not give the player much certainty what will happen next.

Especially when the player does not know on which shufflebag they are. Do not overestimate how much the average player really understands your game mechanics. The average player will probably never realize you are even using shufflebags (that's the whole point, after all). And even those who are aware, will probably not keep count. The only people who will intentionally try to exploit your RNG will be the try-hard challenge gamers who intentionally try to break the game. And those are a very small minority.

Credits for this idea goes to the Las Vegas casinos which introduced it to counter card counting in Black Jack. Instead of playing Black Jack with one deck, they now play it with multiple decks of cards, and reshuffle the shoe long before all of the cards have been dealt.

\$\endgroup\$
5
  • 17
    \$\begingroup\$ By the way, if you are looking for the literal middle-ground between a shufflebag and simple randomness, then consider this: Reshuffling a shufflebag after just 1 draw would be equivalent to simple randomness. So reshuffling it after half the draws would be the literal middle-ground between simple randomness and going through a complete shufflebag. \$\endgroup\$ Commented Jul 18, 2022 at 13:07
  • \$\begingroup\$ A number of board games I've played do something similar by including one or more cards that instructs the player to place the remainder of the draw deck into the discard pile, shuffle the discard pile and then use that as the new draw deck. \$\endgroup\$ Commented Jul 18, 2022 at 16:31
  • \$\begingroup\$ I will try this out and see how it goes. When I played with more pieces in the bag yesterday, the droughts could still be much higher than I wanted. However, I do like the idea of potentially shuffling midway through. Thank you. \$\endgroup\$ Commented Jul 18, 2022 at 16:49
  • 2
    \$\begingroup\$ @TyCobb: Other options (which I discussed in more detail in my answer to an earlier question here) would include refilling (not discarding and recreating!) the bag when it's half full, or even replacing each outcome drawn from the bag immediately with one taken from a deterministic sequence. The potential advantage of those methods is that they give somewhat stronger guarantees of the deviation from the average event rates remaining bounded. \$\endgroup\$ Commented Jul 18, 2022 at 17:36
  • 2
    \$\begingroup\$ This approach is good to limit win streak; but doesn't help as much against a losing streak which is usually the more problematic (most gamers won't quit after getting 10 wins in a row, they might after getting 10 losses). For example, stopping after 4 entries out of 16 makes 4 wins very unlikely (from 0.4% of full random to 0.05% here), but 4 losses drops from 32% to 27% - a minor change you wouldn't notice in ordinary gameplay. \$\endgroup\$ Commented Jul 19, 2022 at 9:47
5
\$\begingroup\$

Stolen blatantly from D_M_Gregory's tweets:

My preferred approach for this kind of selection is to build some Gambler's Fallacy into the generator - adding notion an item can be "overdue" / "used up".

I start with a non-negative weight associated with each item - these don't have to sum to 100% so they're easy to edit. As part of the generator state I track a "dueness" for each item, initialized to that item's weight.

When drawing an item, I form a selection weight for each item as Max(item dueness + item weight * noise, 0) …and select an item with weighted random selection from these weights. After a draw, I increase the dueness of each item (including the selected one) by its original weight, and decrease the dueness of the selected item by the total original weight. If I've overconstrained it so it gets all zero weights, it falls back to the original weights.

The noise parameter lets me control how predictably deck-like (~0) or chaotically dice-like (>>0) the generator behaves. So it's not all or nothing, I can dial in the trade-off I want between consistent guarantees and unpredictability.

This gives me much stronger control over the observed frequencies of each item compared to weighted rolls without memory. I can even add a cooldown between rolls of a single item to avoid back-to-back fails/criticals. And you can even change the source weights on the fly!

So that's how I'm tackling this problem currently, letting me guarantee players don't wait too long for a particular event (droughts), or experience too many back-to-back (streaks), with design parameters I can freely tune to any numbers I want and get the frequencies I expect!

\$\endgroup\$
2
  • \$\begingroup\$ (He linked them in the comments above, so I'm taking that as consent for it to be an answer, and I have marked it as community wiki) \$\endgroup\$ Commented Jul 18, 2022 at 20:24
  • 6
    \$\begingroup\$ Generally, you should ask for consent, not assume it. \$\endgroup\$ Commented Jul 18, 2022 at 20:34
4
\$\begingroup\$

One very simple way is to continuously tweak probabilities instead of after some fixed point.

There is base probability pb (0.25 in the example). We have another parameter I am calling "stiffness" - s that influences how the current probability p changes with wins and losses. Our random generator output r is in range of 0 to 1 and is compared to the current probability p. Current probability p changes according to a simple formula (starting with p=pb):

if r<=p p=p-(1-pb)*s //If we win, we make it less likely to win again. else p=p+pb*s //If we lose, we make it more likely to win next time. end

So, let's see what this simple formula gives us. Pluses are for wins (above 0); circles are for losses (below 0).

win/loss streak image

s=0 is fully random. Few cases have extremely long win or loss streaks. s=0.5 is somewhat in-between, showing shorter tail of at most 10 losses or 3 wins in a row. s=1 is equivalent to a shuffle bag size 4 (the basic shuffle bag size). Then we have s=2 where we get at most 1 win in a row, but losing streak is also fairly likely to be 3 and is at most 5. Increasing s further makes losses even closer to always 3 in a row, in limit s->inf we would get 2.5e4 cases of that (note that we get 3 losses in a streak, so end probability of a win is the base 0.25 one)

Tweak the s to obtain the curve most suitable for your purposes. s can be lower if pb is higher - the long losing streaks are problematic, not the long winning ones. I suggest something like s=1/8pb. This makes results more random when base probability is high, but more deterministic when base probability is low.

The nice bit about this approach is that it is very simple to understand what is happening and fairly trivial to implement. The possibly problematic aspect is that once people know this is the approach, they might intentionally try getting many misses in a row to "prime" the probability before their big fight. But this can be also desirable - if you want to give a little benefit to the most dedicated players.

\$\endgroup\$
2
  • \$\begingroup\$ Upvoting because it's a clean, simple approach - I feel this is an area that needs a quick fix (to address frustrating runs) but otherwise, imperfect randomness isn't too much of an issue. I guess a sole question would be about persisting this "stiffness" between save reloads - I can see a good arguement for it, in games where you die a lot \$\endgroup\$ Commented Jul 20, 2022 at 10:47
  • 1
    \$\begingroup\$ I can attest that the general approach outlined here works well for dealing with the issues inherent in true randomness for RPG type games. I have actually used an almost identical mechanism with percentile dice for years now when running in-person tabletop RPG games to influence the probability of random encounters and ensure that players are not likely to get swamped with them but will still see them with some regularity. \$\endgroup\$ Commented Jul 20, 2022 at 17:59
2
\$\begingroup\$

A shufflebag that is kept at a constant size and refilled using a predictable series could remedy this.

The algorithm

I'm using the 25% proc rate as an example.

Setup
Create a refill list with the correct amount of procs and fails: [proc, fail, fail, fail].
Fill the shufflebag by adding items from the refill list in order, cycling back to the first item after the end. Add a proc, fail, fail, fail, proc, fail etc until the bag is full.
Drawing
Pull a random result from the bag as normal.
Refill the bag using the next item from the list.

Interesting aspects of constant refilling shuffle bags

Because results are pulled from a bag randomly there is a random chance for every event. Only in very specific cases (only procs or fails in the bag) the result can be predicted. This is different from a regular shuffle bag, where at least every last draw before refill can be known in advance.

Because the refilling bag is fed from a list where every fourth result procs in the long run this will tend to exactly 25% procs. This is very artificial, but similar to a regular shuffle bag.

The bag size for refilling bags doesn't need to be related to the proc chance like regular shuffle bags. Regular shuffle bags for a 25% chance can have size n*4, while 31% only works with bag size n*100. Using a custom filling algorithm where not all bags are the same could fix this but adds another layer of complexity.

Tweaking this algorithm

  • An increase in bag size will cause an increase in randomness. At size 1, exactly every 4th result will proc. Changing the size to 2 will allow a maximum of 2 procs to occur consecutively. Increasing it even further would allow longer chains of procs, even though they become very improbable.
  • The proc chance is controlled by the refill list. For 25% every fourth item should be a proc, for 20% every fifth. For other percentages it may not be as easy. If you want you can pre-calculate a table for every percentage you'll be using.

Just like the simulations

Running 1M simulations for various bag sizes and counting proc streak lengths gives the following results. Also shown is the 'naive' implementation where every draw is a simple 25% chance. Note that the count axis is logarithmic. Streak length counts for various bag sizes As expected bigger bags allows longer streaks. For the naive case there is an inverse exponential relationship: the chance of a streak having length n is 0.25^n. Eyeballing it there seems to be an inverse exponential relationship for the refilling bags as well, but it drops off more steeply.

Truncation is visible in bag sizes 2 and 3, this is due to the fill list containing 3 consecutive fails.

\$\endgroup\$
0
0
\$\begingroup\$

Adapted from Steve Rabin article on filtered randomness from AI Programming Wisdom 2.

As you identified in the question, a truly random sequence allows for rare anomalies that are perceived as random. Instead, people expect random results to have an average distribution & avoid certain characteristics. In particular, research by Falk has identified certain things that cause people to perceive things as less random:

  • long runs of outcomes
  • lack of alternations
  • repeated patterns
  • symmetric patterns

To counter these problems we can keep a short history of results and apply a series of rules:

  • force alternation when needed
  • restrict long runs
  • eliminate unwanted patterns

My personal take is that tuning unwanted runs is more important that filtering out patterns. But since it's relatively easy to comment out that section of code if desired, so I'm presenting the material in its original form.

Here's a rough C# adaptation from the original C++ companion code along with a basic tester / demo:

class Program { const int FR_CHANCE_HISTORY_LENGTH = 20; int[] m_hist = new int[FR_CHANCE_HISTORY_LENGTH]; const float FLOATING_POINT_ROUNDOFF_ERROR = 0.000001f; static void Main(string[] args) { int count = 0; float odds = 0.25f; for(int a=0; a<1000; a++) { if (RandChance(odds)) { count++; } } Console.WriteLine("count for " + (int)(odds * 100) + "% out of 1000 trials = " + count + " or " + count/10.0 + "%"); Console.WriteLine("example output: "); for (int a = 0; a < 50; a++) { int i = RandChance(odds) ? 1 : 0; Console.Write(i); } } public static bool RandChance(float a) { Random rng = new Random(); return ((((float)rng.Next()) + 0.5) * (1.0 / (float)Int32.MaxValue) <= a); } // These tables were carefully hand-tuned to ensure that random chances were within 1% of requested chance. int[] MaxAlternations = { 2, 4, 4, 4, 4, 4, 4, 4, 4, 6, //0.01 through 0.10 6, 6, 6, 6, 6, 8, 8, 8, 8, 8, //0.11 through 0.20 10,10,10,10,10,12,12,12,12,12, //0.21 through 0.30 12,12,12,12,12,12,12,12,12,12, //0.31 through 0.40 12,12,12,12,12,14,14,14,14,14 };//0.41 through 0.50 int[] MinAlternations = { 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, //0.01 through 0.10 1, 1, 1, 4, 4, 4, 4, 4, 4, 4, //0.11 through 0.20 4, 4, 4, 6, 6, 6, 6, 6, 6, 6, //0.21 through 0.30 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, //0.31 through 0.40 8, 8,10,10,10,12,12,12,12,12 };//0.41 through 0.50 int[] MaxTrueRun = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, //0.01 through 0.10 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, //0.11 through 0.20 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, //0.21 through 0.30 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, //0.31 through 0.40 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 };//0.41 through 0.50 int[] MaxFalseRun = {25,25,25,25,25,25,25,15,15,15, //0.01 through 0.10 14,14,14,12,12,12,12,10,10,10, //0.11 through 0.20 10,10,10,10,10,10,10, 7, 7, 7, //0.21 through 0.30 7, 7, 7, 7, 7, 6, 6, 5, 5, 5, //0.31 through 0.40 5, 5, 4, 4, 4, 4, 4, 3, 3, 3 };//0.41 through 0.50 int[] InitialHistoryChance = { 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0 }; bool GenRand(float chance) { int i, alternations = 0; float adjchance = chance; int adjchance_int = (int)((chance * 100.0f) + 0.5f) - 1; bool flip = false; for (i = 0; i < FR_CHANCE_HISTORY_LENGTH - 1; i++) { // move history down m_hist[i] = m_hist[i + 1]; } if (chance > 0.5f) { adjchance = 1.0f - chance - FLOATING_POINT_ROUNDOFF_ERROR; adjchance_int = (int)(((1.0f - chance) * 100.0f) + 0.5f) - 1; flip = true; } if (adjchance_int < 0) { adjchance_int = 0; } // Get random value based on chance m_hist[FR_CHANCE_HISTORY_LENGTH - 1] = RandChance(adjchance) ? 1 : 0; // force desired alterations int max, min; for (i = 0; i < FR_CHANCE_HISTORY_LENGTH - 1; i++) { // count alternations if (m_hist[i] != m_hist[i + 1]) { alternations++; } } max = MaxAlternations[adjchance_int]; min = MinAlternations[adjchance_int]; if (alternations > max) { // if too many alternations, make the new value the same as the last m_hist[FR_CHANCE_HISTORY_LENGTH - 1] = m_hist[FR_CHANCE_HISTORY_LENGTH - 2]; } else if (alternations < min) { // if not enough alternations, make the new value the opposite fo the last m_hist[FR_CHANCE_HISTORY_LENGTH - 1] = (m_hist[FR_CHANCE_HISTORY_LENGTH - 2]+1)%2; } // eliminate implausible runs int run = 1; //the first element starts as a run of 1 for (i = FR_CHANCE_HISTORY_LENGTH - 2; i >= 0; i--) { // count size of the most recent run if (m_hist[i] == m_hist[i + 1]) { run++; } else { break; } } if (m_hist[FR_CHANCE_HISTORY_LENGTH - 1]==1 && run > MaxTrueRun[adjchance_int]) { m_hist[FR_CHANCE_HISTORY_LENGTH - 1] = 0; } else if (!(m_hist[FR_CHANCE_HISTORY_LENGTH - 1]==1) && run > MaxFalseRun[adjchance_int]) { m_hist[FR_CHANCE_HISTORY_LENGTH - 1] = 1; } // eliminate repeating motifs of size 4, like 01110111 where 0111 is the motif if (chance >= 0.4f && chance <= 0.6f) { // enforce for around the 50% chance case if (m_hist[FR_CHANCE_HISTORY_LENGTH - 1] == m_hist[FR_CHANCE_HISTORY_LENGTH - 5] && m_hist[FR_CHANCE_HISTORY_LENGTH - 2] == m_hist[FR_CHANCE_HISTORY_LENGTH - 6] && m_hist[FR_CHANCE_HISTORY_LENGTH - 3] == m_hist[FR_CHANCE_HISTORY_LENGTH - 7] && m_hist[FR_CHANCE_HISTORY_LENGTH - 4] == m_hist[FR_CHANCE_HISTORY_LENGTH - 8]) { if (m_hist[FR_CHANCE_HISTORY_LENGTH - 1] == 0) { m_hist[FR_CHANCE_HISTORY_LENGTH - 1] = 1; } else { m_hist[FR_CHANCE_HISTORY_LENGTH - 1] = 0; } } } // eliminate 111000 and 000111 pattern if (chance >= 0.4f && chance <= 0.6f) { // enforce for around the 50% chance case if ((m_hist[FR_CHANCE_HISTORY_LENGTH - 1] == 0 && m_hist[FR_CHANCE_HISTORY_LENGTH - 4] == 1 && m_hist[FR_CHANCE_HISTORY_LENGTH - 2] == 0 && m_hist[FR_CHANCE_HISTORY_LENGTH - 5] == 1 && m_hist[FR_CHANCE_HISTORY_LENGTH - 3] == 0 && m_hist[FR_CHANCE_HISTORY_LENGTH - 6] == 1) || (m_hist[FR_CHANCE_HISTORY_LENGTH - 1] == 1 && m_hist[FR_CHANCE_HISTORY_LENGTH - 4] == 0 && m_hist[FR_CHANCE_HISTORY_LENGTH - 2] == 1 && m_hist[FR_CHANCE_HISTORY_LENGTH - 5] == 0 && m_hist[FR_CHANCE_HISTORY_LENGTH - 3] == 1 && m_hist[FR_CHANCE_HISTORY_LENGTH - 6] == 0)) { if (m_hist[FR_CHANCE_HISTORY_LENGTH - 1] == 0) { m_hist[FR_CHANCE_HISTORY_LENGTH - 1] = 1; } else { m_hist[FR_CHANCE_HISTORY_LENGTH - 1] = 0; } } } if (flip) { // requested percentage (chance) is above 0.50, so flip result return (!(m_hist[FR_CHANCE_HISTORY_LENGTH - 1]==1)); } else { return (m_hist[FR_CHANCE_HISTORY_LENGTH - 1]==1); } } }

Result:

count for 25% out of 1000 trials = 253 or 25.3% example output: 10000001000000100000001000010011000000001001000010

As indicated in the comments, the tables were hand tuned for the corresponding percentages. As such if experiment with other values you should make sure to thoroughly test the result to avoid unpleasant surprises.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.