> Together we came up with a solution that solves this with O(n) memory usage where n is the number of choices, and O(log n) CPU cost. And it allows you to decide if you want to be more random or more deterministic.
I think you can do the same thing and solve all the same problems in O(1) time per sample using the alias method plus shuffling while blending between regular uniform samples and jittered uniform samples.
- Build your alias map of M buckets, the distribution you want to sample
- Take a set of N uniform samples, and use a knob to blend between regular and jittered. It looks like:
r=lerp(knob, 0.5, rand())/N
For some reason alias sampling is not well known, even though it strictly dominates using a search tree when generating randomness (it's faster, it uses less memory, and IMO it's easier to code). It even works better when generalized to the case of preparing superpositions on quantum computers ( https://algassert.com/post/1805 ).
Thanks for the links. The last one is long, but made it easy to understand how and why alias method works (and it's awesome for providing mathematical proofs along with algorithms).
That said, I'm having trouble understanding the solution you described. I can understand how the alias method can help me efficiently sample an arbitrary discrete probability distribution, but I can't see how adding jitter helps with the problem from TFA - namely, to generate samples that conform to a given distribution long-term, but avoid hitting "annoying" low-probability outcomes like strings of consecutive lower-probability options. Could you please clarify / expand on your explanation?
> I don’t know if this problem has a proper name, but in game development you usually don’t want truly random numbers. I’ve seen the solution named a “pseudo random distribution” but “pseudo random” already has a different meaning outside of game design, so I will just call it controlled randomness for this blog post.
While those are good terms for deterministic uniform random number generators, that is not what the author’s talking about.
He’s referring to how in games, you sometimes don’t want random patterns. But even when you do, you don’t want the pattern to be truly random, because true randomness sometimes feels unfair and sometimes feels un-fun.
It’s a concept with a broader scope than low-discrepancy sequences.
By the time you are tracking misses on each class of event and adjusting the probabilities, you might as well just use random permutations of the desired distribution of outcomes. Like if the sword is supposed to hit 90%, just run through a 10-bit sequence with 9 ones and a zero, and shuffle it after every 10 attempts.
Famously Tetris typically uses this "grab bag randomizer" (or various other controlled forms of randomness). I was surprised Tetris was not mentioned at all in the article.
Are you talking about randomly shuffling the bits or getting a new permutation? Any suggestions on how to quickly randomly shuffle the bits of a number?
The problem: My customer was renting items (to his customers) and wanted those items to be given random, but not too random to avoid giving the same (free to rent) item too many times because it will worn out too fast vs. rest of them. Replacing that item in the overall pool of those items was more expensive than replacing the entire pool (think doors on small lockers, and the entire panel of lockers was cheaper to just get replaced altogether - don't ask me why, modern society is weird)
The solution: Mark each item with a score that goes up each time the item gets rented. And apply random to those that are at bottom. In the beginning all items had zero as score, one gets rented and its score is now 1. I applied random to only those with zero score until all of them were rented once. Of course, renting times were variables so overall the algorithm that I've implemented in the end was more complex, but this was the basic idea.
How is that better than just renting out the next one with the fewest rentals? Maybe it's easier to pick at random than to track an order? But then the randomness is for ease of implementation and not a fundamental part of your solution.
> How do you arrive at that 5% base chance? I actually don’t know an analytic way of arriving there, but you can get there experimentally pretty easily by just writing a loop that runs through this a million times and then tells you how often it succeeded or failed. Then you build a lookup table that contains the percentages.
I'm no stats expert by any means, but couldn't you calculate the percentages of each event occuring (and the amount to increment) using bayesian modeling?
Simply taking the product of a string of actions and calculating those seems like an acceptable solution, however I'm not sure.
The author seems to use a calculation approach, which if I understand correctly is a valid method and is sampling the distribution. But then again, not sure.
An easy way to do the odds analytically is to calculate the average expected number of trials needed for a success, and then note that the overall average success rate is the inverse of that.
E.g. in the author's example, where the rate starts at 5% and increases by 5% with each failure, the expected number of trials needed for a success would be:
sum = 1 * 0.05 + // hit the first trial
2 * 0.95 * 0.10 + // missed first, hit second
3 * (0.95*0.9) * 0.15 + // missed first two, hit third
// ..and so on
Summing up that loop gives 5.29 for the expected number of trials, the inverse of which is 18.9%, matching the author's observed result.
Imagine a binary tree. The root node represents the probability of 5%. If you take the left child to mean a positive result, the probability stays at 5%. If you take the right child to mean a negative result the probability rises to 10%.
Every left child produces a tree from that point which is exactly the same at the root tree.
Every right child produces a probability of +5% until you get to 100% after which the right node is forced back to 5% — meaning it will match the root from that point.
I feel like once you’ve defined the tree to depth 20, you could average all the probabilities and it should equal 19%, because everything from that depth further is just a uniform repetition of the probability tree, but it’s probably slightly more complicated than that.
> I'm no stats expert by any means, but couldn't you calculate the percentages of each event occuring (and the amount to increment) using bayesian modeling?
No. Probability theory is about working forward from a given model to a set of possible observations. And Bayesian statistics is about working backwards from given observations to which model in a set of models produced them (which is why an old name for Bayesian statistics is 'inverse statistics').
In this case, there is no given set of observations; there's not some game out there which has produced a dataset and you're trying to work backwards to figure out what model that game is using. Instead, you have a bunch of models and you're trying to work forwards to figure out which of them will give you the kind of outputs you want. So, that's probability theory.
AFAICT this is what’s called conditional probability in the scientific literature. The algorithms described would probably be called autoregressive samplers.
It all comes down to generating deterministic permutations instead of purely random numbers, since the intent is to avoid bad luck.
The most common permutation used is the AES S-Box, commonly available through various ISA extensions. There are many ways to generate permutations though, and it wouldn’t require a large complex algorithm to avoid a 1 in 10 chance event happening three times in a row or generating the entire permutation to be stored in memory.
S-boxes compute fixed permutations of the bits in a small fixed length buffer, which is entirely inappropriate for accurately picking random permutations of a variable and usually large number of choices.
I dunno, seems silly. I'm sure there are already proven methods, and the mathematical analysis in the article leaves something to be desired. You should probably just lean on whatever is used in Progressive Slot Machines.
Super interesting. It seems to tap into the psychology of some people who gamble... they think the more times they lose, the more likely they win the next time. Why are humans wired this way?
Human brains are optimized for prediction of future events, because this helps with survival (eg: you can predict a winter coming up, so you stock up on food).
Randomness is by (some) definition unpredictable. But humans are so eager for pattern recognition that they will see, or expect, patterns that just are not there.
"Pareidolia is the tendency to interpret a vague stimulus as something known to the observer, such as seeing shapes in clouds, seeing faces in inanimate objects or abstract patterns, or hearing hidden messages in music." and also: https://en.wikipedia.org/wiki/Apophenia#Causes
On a similar note, humans are terrible at coming up with random/unpredictable sequences. If you ask a group of test subjects to pick a random number between 1 and 10, you get a huge edge when you guess 3 or 7.
I suspect it has to do with the same facilities that evoke magical thinking, and other pattern-event associative behavior. And like those pigeons in the famous experiment which were fed randomly and evolved various ritual-like behavior in association, we think we did something to achieve a win condition (or food condition). In the case of gambling, what we 'did' to win was gamble when 'the cards were hot'.
[+] [-] dahart|6 years ago|reply
I think you can do the same thing and solve all the same problems in O(1) time per sample using the alias method plus shuffling while blending between regular uniform samples and jittered uniform samples.
- Build your alias map of M buckets, the distribution you want to sample
- Take a set of N uniform samples, and use a knob to blend between regular and jittered. It looks like: r=lerp(knob, 0.5, rand())/N
- Shuffle the uniform samples, e.g. std::random_shuffle(). This can be done incrementally, per sample (https://en.wikipedia.org/wiki/Fisher–Yates_shuffle).
- Plug the uniform sample into the alias map to find your sampled choice.
- Repeat when you run out of the N uniform samples.
https://en.wikipedia.org/wiki/Alias_method
http://www.keithschwarz.com/darts-dice-coins/
[+] [-] Strilanc|6 years ago|reply
[+] [-] TeMPOraL|6 years ago|reply
That said, I'm having trouble understanding the solution you described. I can understand how the alias method can help me efficiently sample an arbitrary discrete probability distribution, but I can't see how adding jitter helps with the problem from TFA - namely, to generate samples that conform to a given distribution long-term, but avoid hitting "annoying" low-probability outcomes like strings of consecutive lower-probability options. Could you please clarify / expand on your explanation?
[+] [-] ribrars|6 years ago|reply
[+] [-] klipt|6 years ago|reply
The correct term is probably quasirandom or low-discrepancy sequences: https://en.wikipedia.org/wiki/Low-discrepancy_sequence
[+] [-] dahart|6 years ago|reply
He’s referring to how in games, you sometimes don’t want random patterns. But even when you do, you don’t want the pattern to be truly random, because true randomness sometimes feels unfair and sometimes feels un-fun.
It’s a concept with a broader scope than low-discrepancy sequences.
[+] [-] o09rdk|6 years ago|reply
https://www.quantamagazine.org/hyperuniformity-found-in-bird...
[+] [-] richard_todd|6 years ago|reply
[+] [-] 1wd|6 years ago|reply
https://tetris.fandom.com/wiki/Random_Generator
https://katta.mere.st/different-tetris-algorithms/
[+] [-] XCSme|6 years ago|reply
[+] [-] b0blee|6 years ago|reply
[+] [-] unnouinceput|6 years ago|reply
The problem: My customer was renting items (to his customers) and wanted those items to be given random, but not too random to avoid giving the same (free to rent) item too many times because it will worn out too fast vs. rest of them. Replacing that item in the overall pool of those items was more expensive than replacing the entire pool (think doors on small lockers, and the entire panel of lockers was cheaper to just get replaced altogether - don't ask me why, modern society is weird)
The solution: Mark each item with a score that goes up each time the item gets rented. And apply random to those that are at bottom. In the beginning all items had zero as score, one gets rented and its score is now 1. I applied random to only those with zero score until all of them were rented once. Of course, renting times were variables so overall the algorithm that I've implemented in the end was more complex, but this was the basic idea.
[+] [-] bmm6o|6 years ago|reply
[+] [-] ribrars|6 years ago|reply
I'm no stats expert by any means, but couldn't you calculate the percentages of each event occuring (and the amount to increment) using bayesian modeling?
Simply taking the product of a string of actions and calculating those seems like an acceptable solution, however I'm not sure.
The author seems to use a calculation approach, which if I understand correctly is a valid method and is sampling the distribution. But then again, not sure.
[+] [-] fenomas|6 years ago|reply
E.g. in the author's example, where the rate starts at 5% and increases by 5% with each failure, the expected number of trials needed for a success would be:
Summing up that loop gives 5.29 for the expected number of trials, the inverse of which is 18.9%, matching the author's observed result.[+] [-] zaroth|6 years ago|reply
Every left child produces a tree from that point which is exactly the same at the root tree.
Every right child produces a probability of +5% until you get to 100% after which the right node is forced back to 5% — meaning it will match the root from that point.
I feel like once you’ve defined the tree to depth 20, you could average all the probabilities and it should equal 19%, because everything from that depth further is just a uniform repetition of the probability tree, but it’s probably slightly more complicated than that.
[+] [-] gwern|6 years ago|reply
No. Probability theory is about working forward from a given model to a set of possible observations. And Bayesian statistics is about working backwards from given observations to which model in a set of models produced them (which is why an old name for Bayesian statistics is 'inverse statistics').
In this case, there is no given set of observations; there's not some game out there which has produced a dataset and you're trying to work backwards to figure out what model that game is using. Instead, you have a bunch of models and you're trying to work forwards to figure out which of them will give you the kind of outputs you want. So, that's probability theory.
[+] [-] bjornsing|6 years ago|reply
[+] [-] wruza|6 years ago|reply
There is also a good Numberphile video on what we think random really is (it is not) https://youtube.com/watch?v=tP-Ipsat90c
[+] [-] unknown|6 years ago|reply
[deleted]
[+] [-] ryacko|6 years ago|reply
The most common permutation used is the AES S-Box, commonly available through various ISA extensions. There are many ways to generate permutations though, and it wouldn’t require a large complex algorithm to avoid a 1 in 10 chance event happening three times in a row or generating the entire permutation to be stored in memory.
[+] [-] HelloNurse|6 years ago|reply
[+] [-] ggggtez|6 years ago|reply
[+] [-] daenz|6 years ago|reply
[+] [-] throwawaywego|6 years ago|reply
Randomness is by (some) definition unpredictable. But humans are so eager for pattern recognition that they will see, or expect, patterns that just are not there.
"Pareidolia is the tendency to interpret a vague stimulus as something known to the observer, such as seeing shapes in clouds, seeing faces in inanimate objects or abstract patterns, or hearing hidden messages in music." and also: https://en.wikipedia.org/wiki/Apophenia#Causes
On a similar note, humans are terrible at coming up with random/unpredictable sequences. If you ask a group of test subjects to pick a random number between 1 and 10, you get a huge edge when you guess 3 or 7.
[+] [-] neuralzen|6 years ago|reply