8 ms·
A New Algorithm for Controlled Randomness
- deleted 7y ago[deleted]
- klipt 7y ago> 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. The correct term is probably quasirandom or low-discrepancy sequences: https://en.wikipedia.org/wiki/Low-discrepancy_sequence https://en.wikipedia.org/wiki/Low-discrepancy_sequence
- dahart 7y agoWhile 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.
- klipt 7y agoThey don't have to be deterministic, the wiki article has a section on constructing low-discrepancy sequences from independent random numbers by imposing negative correlation between subsequent numbers: https://en.wikipedia.org/wiki/Low-discrepancy_sequence#Random_numbers https://en.wikipedia.org/wiki/Low-discrepancy_sequence#Rando... Which sounds pretty similar to what the author is doing - removing some of the independence from a sequence of independent random numbers to make them feel "fairer" (basically making them more in line with misconceptions people have about truly independent random sequences https://en.wikipedia.org/wiki/Randomness#Misconceptions_and_logical_fallacies https://en.wikipedia.org/wiki/Randomness#Misconceptions_and_...)
- kzrdude 7y agoMaybe they have misconceptions about randomness, but are they wrong about their expectations for something that models the real world? I'm thinking the space of possible random events might be too big, or the distribution is wrong.
- dahart 7y ago> They don’t have to be deterministic. Right. Agreed. Still, the idea here is about the perception of randomness at the expense of actual randomness, it’s related to but different from quasi-random ideas. Edit: Actually I don’t know, maybe you’re totally right about this article, maybe quasi-random is the same thing in this case. I was projecting a broader idea based on having worked on games and run into this problem... my philosophy on it is that often you don’t want any randomness, but sequences that are random seeming at first but are predictable and learnable by the player. Depending on the game feature, that’s sometimes more fun. In this particular case, they are trying to preserve the intended distribution, and sample a given distribution without shuffling. A low discrepancy sequence does do that, so I’m changing my mind here.
- o09rdk 7y agoAlso hyperuniformity? https://www.quantamagazine.org/hyperuniformity-found-in-birds-math-and-physics-20160712/ https://www.quantamagazine.org/hyperuniformity-found-in-bird...
- gwern 7y agoPoisson disc sampling! https://www.jasondavies.com/poisson-disc/ https://www.jasondavies.com/poisson-disc/
- dahart 7y ago> 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 - Shuffle the uniform samples, e.g. std::random_shuffle(). This can be done incrementally, per sample (https://en.wikipedia.org/wiki/Fisher–Yates_shuffle 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 https://en.wikipedia.org/wiki/Alias_method http://www.keithschwarz.com/darts-dice-coins/ http://www.keithschwarz.com/darts-dice-coins/
- ribrars 7y agoNice, seems like a great solution especially in the use case where this service is needed by a game server and good performance is a requirement.
- Strilanc 7y agoFor 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 https://algassert.com/post/1805 ).
- ur-whale 7y agoAlias sampling is a really beautiful algorithm, but implementing it correctly and efficiently isn't as easy as you seem to imply. I would also very much like to know what a generalization of this algorithm to continuous distribution would look like.
- ribrars 7y ago> 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.
- gwern 7y ago> 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.
- zaroth 7y agoImagine 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.
- unnouinceput 7y agoAt one of my projects I had a similar problem. 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 7y agoHow 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.
- TeMPOraL 7y agoI'd guess the scoring was not linear with number of rentals, because wear isn't. E.g. 2 long rentals will generate more wear than 2 short rentals; probably even more than 3, depending on how much wear is caused by shipping & handling. I wonder why not derive the score from human input? I assume someone is handling returns; that someone could be trained to eyeball the condition of the item and input that into a database.
- unnouinceput 7y agoNo human to oversee this, was the goal. The only human was cleaning lady that was cleaning them at the closing time, and she definitely was not trained to do anything else, hence everything algorithm driven. When something was broken a technician was send to repair, or replace, but no person to stay onsite.
- daenz 7y agoSuper 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?
- neuralzen 7y agoI 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'.
- throwawaywego 7y agoHuman 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 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.
- richard_todd 7y agoBy 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.
- b0blee 7y agoThat sounds a lot easier to me.
- deleted 7y ago[deleted]
- 1wd 7y agoFamously 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. https://tetris.fandom.com/wiki/Random_Generator https://tetris.fandom.com/wiki/Random_Generator https://katta.mere.st/different-tetris-algorithms/ https://katta.mere.st/different-tetris-algorithms/
- XCSme 7y agoAre 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?
- richard_todd 7y agoRandomly shuffling the bits _is_ a new permutation (of those bits). There may be a faster way to shuffle the bits of whole bytes/words on some architectures, but for the general case I suspect a normal shuffling algorithm (like Fisher-Yates) and shifts+and+xor swapping is best.
- XCSme 7y agoOh, sorry for not making it clear, when I meant permutation I was referring to the the immediately next permutation. I guess after current set is over you could also take the Xth permutation of the current state, where X is a random integer. (so you randomly skip some permutations to not make it predictable).
- ryacko 7y agoIt 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.
- HelloNurse 7y agoS-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.
- ryacko 7y agoFor a RNG, the maximum run length of same values would be the period length divided by the output size (in general). The blog post is horrifying, it feeds the output of the Mersenne Twister into another function to reduce the run length of seemingly biased outcomes. I think to generate a single value the whole CPU’s cache is cleared from the size and complexity of the code. The AES S-box, with the seed XORed before and after, would still be a better solution (especially since the probably of certain runs of similar values should be somewhat low). The theory behind LCGs is a lot simpler, and using a suitably small prime, I think, one could have an appropriately short period without excessive predictability.
- bjornsing 7y agoAFAICT this is what’s called conditional probability in the scientific literature. The algorithms described would probably be called autoregressive samplers.
- wruza 7y agoOh, I remember good old fallout 1-2 when you have 42% hit chance but still miss 7 times in a row. There is also a good Numberphile video on what we think random really is (it is not) https://youtube.com/watch?v=tP-Ipsat90c https://youtube.com/watch?v=tP-Ipsat90c
- ggggtez 7y agoI 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.