There's a probability model called the Pólya urn where you imagine an urns containing numbered balls (colored balls in a typical example, but to draw the comparison with dice we can say they're numbered 1-6), and every time you draw a ball of a certain color, you put back more balls according to some rule. A few probability distributions can be expressed in terms of a Pólya urn, see https://en.wikipedia.org/wiki/P%C3%B3lya_urn_model.
A fair 6-sided die would be an equal number of balls numbered 1-6 and a rule that you simply return the ball you drew. You can get a gambler's fallacy distribution by, say, adding one of every ball that you didn't draw. I read the code as a Pólya urn starting with 1 ball 1-N and doing that on each draw plus reducing the number of balls of the drawn number to 1.
Also related, in 2d space, is the idea of randomly covering the plane in points but getting a spread-out distribution, since uniformity will result in clusters. (If you're moving a small window in any direction and you haven't seen a point in a while, you're "due" to see another one, and vice versa if you just saw a point.) Mike Bostock did a very nice visualization of that here: https://bost.ocks.org/mike/algorithms/
In the 1960s, the biostatistician Marvin Zelen proposed using something very much like the Pólya urn for clinical trials, calling it the "play the winner" rule [1]. This has had a major effect in causing a rethinking of the traditional randomized controlled trial, and these ideas are still making their way through the medical community today [2].
Interesting - just perusing those links, it sounds like a multi-armed bandit problem, in which you reason that if something has worked out before, you should tilt your bets more in that direction. In the context of the urn model, you'd return more balls of the same color for every successful draw. In the context of medicine, you can balance between proving or disproving a treatment effect and actually supplying that treatment to the test subjects who need them.
Relatedly, there's a Bayesian interpretation to overweighting successful past draws. A model where you return one extra ball of the same color to the urn gets you a Dirichlet-multinomial distribution, which is a die-roll distribution where the weights to each face are not known for sure, but are given a probability distribution and revised with observed evidence. In other words: here's an n-sided die, I don't know its weightings, but as I observe outcomes I'll update my beliefs that the sides that come up are more favorably weighted. The number of balls in the urn you start with correspond to your priors; only 1 ball of each color means a very weak belief that it's a fair die, 1000 balls of each color means a strong belief, unequal numbers mean that you start off believing it's weighted.
Covering the plane randomly but without clusters is actually quite useful in simulations. The "random" numbers that do that are often call "low-discrepancy sequence".
Also called "quasirandom" numbers, as I learned it from wikipedia years ago. ("Quasirandom" and "quasirandom numbers" today redirect to "low-discrepancy sequence".)
A great application for this is in randomizing playlists. My friends, who are also CS grads and should know better, have often complained that their MP3 players, CD carousels, etc play the same music too often claiming that the random is broken, when a song repeating in a short period of time or other songs never playing is what you would expect from a truly random selection. Using this algorithm, you'd be sure to hear all of your songs. I'm guessing most music services already do something like this.
A simpler way that's guaranteed to not repeat a song till the entire set has been played is: Assuming you have N songs, pick a prime P such that N is not divisible by P. Then pick a random index I (0 <= I < N) to start from. The index of the next song is I' = MOD(I + P, N). This method has the advantage of being O(1) regardless of the size of the playlist.
Another method is to pick a random key K and sort the entries of the playlist based on HMAC(SONG, K) (where SONG is the name or other identifier of the song). This has a number of interesting properties. For starters the playlist will be randomized (that's good). It will also keep it's overall order if a new song is added. The new song will get inserted based upon its HMAC. You can switch things up a bit by having K be a based on the current date. That way new songs will maintain their order and jumping to a track on a given day will continue the chain as before, but day to day you won't always hear the same tracks back to back.
I think you're solving the wrong problem here. The goal is not to take a list and shuffle it once. That's trivial. The goal is: given a set of N songs, sample an arbitrarily long sequence of songs with replacement from this set such that the sequence "feels" random. Things that are random but don't "feel random" include: playing the same song too often, not playing a song often enough, and repeating the same sub-sequence of songs too often. The "shuffle the list once and repeat forever" approach fails hard on the last criterion. Generating a new shuffle every time through the list solves that issue but fails on the first two criteria, since a song could appear at the end of one shuffle and at the beginning of the next, resulting in repeating the same song twice in a row (or vice versa, resulting in the song not playing for 2N-2 songs).
This - and possibly also a reminder that the same words may mean different things for people with different backgrounds.
If someone with no specialized knowledge about math and probability requests their songs in a "random" order, I don't think one should assume they are insisting on an order sampled from a uniform distribution.
Shuffle and weighted random both give a better chance of variety than truly random. Shuffle is cheaper to calculate in terms of storage space.
The article is about weighting randomness based on past distribution. In a music playlist that may be enough. Some user might also want a term in the equation that weights songs they've rated highly to be favored over lower-rated or unrated songs.
Because the casual definition of "random" means "without a discernible pattern", which multiple artists in a row doesn't handle. Music shuffle algorithms sometimes go lengths to avoid patterns and duplicate artists.
Many music players have done this for a long time. In fact I believe that's part of the reason why they refer to that function as "shuffle" rather than "random"
Several years ago I used to use a music service that had a bunch of sliders, something like:
Favorites: Normal <----------> Very Frequently
Artist: Liked only <-----------> Wide variety
Prefer: Old <----Balanced----> New
Popularity: Hits only <--------> Fringe
It was great to be able to customize stations. I don't remember what service it was, but I think it did get purchased and folded into something else.
This was a great way of tweaking the "randomization", and really gets into understanding what people want to hear. In my case, I had different stations/playlists customized in different ways.
> My friends, who are also CS grads and should know better...
I know this is about being "technically correct" but I'd argue that even if you're pedantic and know the behavior of true randomness, the complaints are justified.
First, "pick a song from a uniform distribution" is an implementation detail, not the use case. The use case is "pick songs in a pleasant, novel order". If the implementer chose to do this using uniform randomness, that's their descision. If that implementation does not fulfill the use case, it's a bug and also their responsibility.
Second, the function is frequently called "shuffle" - so it even gives some hints about the implementation expected. No shuffling algorithm should ever result in duplicates. (except at the beginning and end of playlists)
Oh, I really like this idea. I might go with a number greater than two though for the aesthetic reason that 25% of the time, you will select a song that has been played more recently than half of the playlist. With four, you'd be selecting something from the back half of the playlist more than 90% of the time.
I have a theory that Spotify doesn't do random shuffling, but weighted shuffling, so that new items are more likely to be at the top of a shuffle (or maybe even popular items). I also believe that this will satisfy users better than true random shuffling.
About your linked post: You don't test the randomness of the shuffling, you only test if a shuffled list contain one and only of each original item.
Spotify's shuffling is most certainly not random. Every once in a while I get a bug where it simply shuffles through various songs from 4-5 albums and will never pick songs outside that set. Restarting the app corrects the behaviour. To me that's some level of proof, because the songs are all there. So what's the algorithm really doing?
On your website you put a source mark on the statement 'This is the same reason the Brits mistakenly assumed
that the Germans had an exceptionally good aim with their V-1 flying
bombs during World War II '
I'd like to read about this, do you still have the intended link?
This is called "sampling without replacement" and lines up with the physical intuition users have for taking a playlist where each song appears once, randomly reordering it, and then playing the entire playlist.
Good implementations actually don't make a random choice, but do a random sort and then play the whole list, then random sort again, then play again the whole list, etc. The only possible problem here is when the last song in one playthrough is the same as the first song in the next playthrough. But even that can be overcome by re-random-sorting the follow-up.
I had a few issues with Spotify doing this. I even saw a post where an engineer claimed it was all psychological, but I was definitely getting repeats when I had queued up a large amount of music (e.g. over 40 hours.) I think they only shuffle a certain percentage of the playlist and forget which songs have already been played after a while.
I manually shuffle some playlists now. One nice thing about the desktop client is the clipboard integration. You can press cmd+a to highlight all the songs, cmd+c to copy, and then paste all the song URLs into a text editor. Then I used "permute lines" in Sublime Text to shuffle them, then cmd+c and cmd+v to paste the songs back into Spotify.
I probably have some details wrong, but
according to Spotify's customer feedback site, there at least used to be a couple of issues with their shuffle.
One, if I remember somewhat correctly, was that if the player was stopped/shutdown, it forgot the shuffle seed. This would essentially lead to a reshuffle, which would cause duplicate songs for songs played before the unintended reseeding.
back when I used Winamp as my daily player, I was getting annoyed that its "shuffle" kept playing the same songs. and it would play the same songs in a row. so I would hear the songs C,A,F play. then the next day again the sequence would be C,A,F. over time, I would start hearing the melody of the next song before it even started playing.
when I finally noticed this and realized that could only mean it's not actually random, I researched it, and found out that once you hit shuffle/random on Winamp, it shuffled the songs once and kept the sequence forever.
and then as it turned out, Winamp actually had a setting to select a truly random song each time. all I needed to cure my madness was a checkbox!
You can take it too far, though. When I listen to Venetian Snares on Spotify, they only play some songs off of 3 albums, despite the fact that have about a dozen albums. If you're going to do that, tell people it's not actually random.
Interesting, and at first I was excited about the possibilities in something like D&D, where a series of bad rolls can have you feeling down. "I'm due for a critical hit any swing now..."
Players would love that! Make my hero feel more heroic! The inevitable comeback!
But then I thought about the inverse case -- you are doing really well, and now you are due for a failure. Or series of failures. That would feel awful.
We have a lot of emotions around dice rolling. I wonder if players really want from their dice. Would players prefer dice that are secretly unevenly weighted towards good rolls? Would they still want those dice if they knew they were weighted?
I made this specifically for my online D&D sessions. I can tell you that nobody was suspicious when I replaced the standard Math.random() with this version, and all of the "I think your dice function is broken" statements all the sudden stopped happening.
As a D&D player I can see how this might be nice, but at the same time it would be frustrating to get a 20 for something stupid (passing a DC5 check) and know that it had a real effect on my chances for getting a 20 when I could actually use it (a critical attack roll).
In some competitive games like Dota and LoL, the random distribution for critical hits is weighted so that it ramps up over time, resetting after a successful crit.
(http://dota2.gamepedia.com/Random_distribution) This both reduces the chance of two high rolls coming up twice in a row as well as long periods of low rolls.
It doesn't have the "you are doing really well, and now you are due for a failure" since "not a critical" isn't really that negative of an outcome.
For something like D&D, the same kind of "better-than-random" distribution just comes from adding dice. 4d6 is much more consistent than 1d21+3.
Dota was my first thought when I read the article. Good Dota players pay attention to their crits, and if they haven't had one in a few hits they adjust strategy with the expectation of higher damage, something you would never do if it was truly random.
Fascinating! I wonder if the distribution is engineered like that to avoid specious cheating claims. E.g. Player:"Look at this video of Famous_Player getting 3 crits in a row! They're probably cheating!" So much potential for fallacies; Gambler's Fallacy, Silent Evidence Fallacy..
Interesting, when I used to play League of Legends I was sure that the crit chance wasn't random at all. In my experience, at 25% crit precisely every 4th strike would crit, at 50% precisely half, and at 75% every 4th strike I'd do wouldn't be a crit. It seemed fully deterministic which I thought was an interesting way to make the mechanic more skillful as you could count in your head when you'll get a damage spike; you could fire some useless shots on minions then dive in for a trade on your enemy laner knowing that you'd win because of your guaranteed crit.
I've heard Blizzard does the same thing for valuable random drops (like legendary drops in Hearthstone and Diablo 3): instead of being random, there's a proc rate so you can't get screwed by chance.
In hobby time I have been exploring the storytelling possibility space of RPGs using card decks. I love playing cards and I love custom playing card designs and I wish there was more impetus for players to bring decks with interesting designs to an RPG table in the same way that dice are so varied and fun to see what people bring to a table.
I think there are interesting stories to tell in an RPG where you know the "weight" of your rolls, approximately how many "success" cards you have left, some choice in what you play from your hand.
«But then I thought about the inverse case -- you are doing really well, and now you are due for a failure. Or series of failures. That would feel awful.»
It depends on how personal you take it in how awful it feels. If the goal is to create an interesting story, a grand sequence of failures can be a very interesting story. Look at Fiasco, for instance, where some of the fun can be very explicitly "how do I make my character more miserable?" In those cases where you know you are about to hit a lot of failures in die rolls/card draws you can lean in to it. Try to explain why your character is having such awful luck, for instance. Maybe try to set up an elaborate Rube Goldberg design of failures that eventually cascade into the weirdest, grandest success, like a "drunken master" kung fu ballet.
Randomness is what makes a game more realistic but true randomness will not make it more likable. True randomness dictates that in half of your games, your players will have a harder time achieving anything.
It is not uniformity of results that the players are looking for, it is uniformity of successes weighted by the importance of the rolls. Failing a perception check in an empty room is less important than failing a dodge roll in the final fight on your last health point.
Many games suggest that the gamemaster cheats on some crucial rolls. More games propose an alternate system that biases rolls based on points systems. Some others even replace totally the dices with a points system.
I really prefer those. A very simple biased rolls system I often use (Dk2) is that GM can emphasize the action of dangerous NPCs by adding special D6 dices to a D20 roll (they are special as they only give +3 or +6 on 3 and 6 and +0 on other results). Once used, these dices are added to a pool that the players can use for their actions.
Anyway, my favorite system is Amber Diceless RPG. It trades randomness for secrets. Every player is a bit of a backstabing asshole who does not show all their skills on any action. If someone has 30 in strength, they may just announce 10 if they think it is enough for the action.
The winner in a fight is the one with the bigger score. Add bonus if they use some kind of trick or ambushes (recommended). It is surprisingly interesting for such a simple system.
EVE Online has a really interesting approach to this balance as well.
In general, things are heavily weighted towards actual player skill and also character skills accrued over time for the important interactive elements.
For things like loot drops, it's strictly random from a chart per enemy type, but they monitor the overall economy and use that to set the weights for the various items. If one group of people has figured out some trick to farming an extremely valuable item, they will nerf it to keep the economy where they want it. For a number of years, the company actually kept a professional economist on full-time to keep track of these things. I think that got eliminated when CCP was having a rough financial time several years ago. And I think that game has gotten a bit worse as a result.
But in terms of stuff that counts RNGs are a fairly small part of the action, and in some cases not at all, so you can pick your poison: lower overall damage to a target but more consistent, allowing for one kind of play style. Or you can have more variable damage with higher potential if you're willing to take risks. And there are a couple of flavors along the spectrum.
It's a pretty interesting game design. And, of course, tons of people complain about it. Loot drops really are pretty damn random (with between 30-40 thousand people online at any given time, there's a lot of entropy to seed the PRNG). And you get the clusters you would expect from random data. But everyone really hates random outcomes. People want uniform outcomes. It's baked into our psychology.
But in terms of things that determine who lives and who dies in a fight. The random element is really downplayed, and it boils down to player skill more than anything.
There's a whole thing where people who have been playing for a long time will start brand new accounts with low skill levels and shitty equipment and still be able to blow people out of the water because they have a superior understanding of the game mechanics. In fact, there are entire "corporations" who really do nothing but this. Fine people who have been around for long enough to make some money and buy some expensive things and then lure them into fights and slaughter their bling-bling.
It's an interesting approach to game balance, and one I quite admire. It does keep me coming back, and paying that sweet, sweet monthly sub.
EVE is also one of the games that really capitalizes on the technology component. As much as I love Skyrim, for example, I don't think there's anything going on with the actual game interaction mechanics that couldn't be easily replicated on a table with some dice. I'm also willing to eat my words if I'm completely wrong about that.
EVE Online has the luxury of hammering out fairly complicated formulas based on the current state of things, and it does so very well. It does it for every ship in space (again, typically 30-40k), once each server tick (usually a tick is 1 second, but for really huge fights, they dilate time and slow the ticks down).
So they can make things like damage calculated for each gun or missile or drone on each ship based on every relevant ship's current speed and direction relative to every other ship, etc.
It's an impressive use of technology for an RPG, and I find it especially cool that you are your own gamemaster. The only story is the one you make for yourself.
But now I sound like a fucking fanboi, so I'll shut up.
I've never heard of Amber Diceless before. I'm curious and will check it out. Thanks for mentioning.
Maybe a hybrid mode, where too many bad rolls bias the dice towards a more "true uniform" - lol - distribution while a series of good rolls just keep it actually fair.
Better have games without dice rolls. Unexpected events could come from other non-random sources (like the combination of a lot of factors involving other players actions).
> I made a chatbot that rolled dice, and it was constantly criticized for being "broken" because four 3's would come up in a row.
> These accusations would come up even though they (all being computer science majors) know it's possible (although unlikely) for these events to happen. They just don't trust the black box.
> As I promised earlier, if you donate to the site and are unhappy about the rolls, let me know and I will pull a die out of the machine, melt it flat and mail it to you, as an object lesson to the other dice. Tangible revenge.
Hah! That might be the best donation "gift" I've ever heard of!
I had the privilege of studying probability from G-C. Rota. One of my favorite quotes from him was "Randomness is not what we expect", which he used to describe the phenomenon of people disbelieving that random data was actually random. Another great was "This will become intuitive to you, once you adjust your intuition to the facts."
True But I would like to show you an interesting counterexample which requires changing the rules slightly. If we toss a coin and keep tossing until one of the below sequences turn up then which sequence is more likely?
HHHHHH THHHHH
Answer: THHHHH. Only 1/(2^6) of the time it will be HHHHHH. The only way to get HHHHHH will be if the first 6 flips are heads. If you don't flip a head you must have got a tail which means THHHHH will always appear before HHHHHH.
There was an old flash video game I worked on a long time ago where I did exactly this. I had a boss with two main attacks, and I didn't want it to be super predictable A/B/A/B, so I had it pick between A and B randomly, then reweight the probabilities, so if it picked A, instead of 50% A, 50% B it'd now be 25% A, 75% B. If it picked A again it'd be down to like 12.5% A, 87.5% B. If B then got chosen, it'd flip flop to 75% A, 25% B, etc. The result was it mostly went back and forth between the two, but would do some attacks 2 or 3 times in a row before switching back to the other.
Hmm, but by the algorithm you describe you are MORE likely to get a "super predictable" a/b/a/b than you would with just an independently random coin flip each time. That is, strings of multiple As or Bs in a row is less likely with your algorithm, but you make it sound like that's what you wanted.
No, you misunderstand. I didn't want it to be always A,B,A,B, but I also didn't want it to be an even coin flip and risk an A,A,A,A,A,A,A or whatever (like in the play Rosencrantz and Guildenstern are Dead).
With my method, it was possible for the same move to be picked 2 or 3 times in a row, but it mostly went back and forth, so the player was definitely going to encounter both moves, but they couldn't know for absolute certain which move the next one would be (and they both needed you to kind of quickly get into different positions before getting hit).
The type of pattern you'd usually get with mine was more like A,B,B,A,A,B,A,B,A,A,A,B,B,A.
A similar, simpler idea is sometimes used in games: you put all choices in a "bag", then draw from the bag until it's empty, then put everything back.
Tetris is the go-to example. Tetris has seven tetronimos, and in most modern implementations you're guaranteed to see them in sets of seven in random order.
This is pretty essential to make competitive play err on the side of skill rather than randomness: pro-players can anticipate and plan for this. For fun, here's a recent Tetris head-to-head speed-run from Awesome Games Done Quick, with pretty good narration about the tactics involved:
You could just use a deck of cards with numbers on them. That's the simplest way to do "Gambler's Fallacy Dice" IRL. For example, there's a popular Catan expansion pack that replaces the dice with a deck of cards with numbers on them for just this reason, because in Catan each roll of 2D6 represents different regions of the map paying out so if a number never comes up it never pays out.
One of our first house rules for Catan was to introduce a deck. Not quite sure why they went with dice for that game; the deck eliminates a lot of boring games.
Some purists insist that they role dice, so we just let 'em and the resulting game feels quite like you're using gambler's dice.
The thing about rolling 2D6, is the distribution isn't even.
I'm not sure that factors into the game (have played but its been a while). Cards seem like a more controlled way to distribute the results with some randomness.
only one way to get a 12 (6+6)
but 7 much more likely.. (6+1, 5+2, 4+3, 3+4, 2+5, 1+6)
as someone who played a bit of online backgammon back in the day, We always suspected the random dice rolls behaved differently in the game than playing in real life...
There's a little randomness in the Catan deck of cards: the bottom 5 cards of every shuffle are not used. Not as much as dice, but also not a guarantee for certain numbers to come up a certain amount.
I've never played in real life with the deck, but I first came across this version on a software version of Catan I had (I think Xbox?). I really enjoyed it and my guess is that in real life it adds a substantial angle to negotiating placement of the robber. In particular, bribing people to put/not put the robber in a given location - if the deck is 7-heavy or your good squares are already drawn, no big deal.
I was a little disappointed when I clicked, too. I can't think of a way you could make physical dice like that, unless maybe the faces were LEDs? That might be too fragile.
Apple has a patent[0] for a fall-protection system that will rotate the phone while it's in the air. If something like that could be made small enough to fit into a die, that would work.
The biggest challenge will probably be the power supply. I'm sure that a processor, accelerometer, and the Taptic Engine (the thing that provides vibration and haptic feedback in Apple devices) are all small enough to fit in a typical die. Of course, something like this could easily be built into a larger novelty die.
Bonus points should be awarded if the die is perfectly balanced when it's not actively adjusting itself in mid-air.
Put 6 weights in the die, one per face. A mechanism controls each weight individually, moving it from near the face (likely to land down) to near the center (likely to land up). Combine it with something that can detect roll outcomes.
This would probably cost a lot of money to fit in a normal sized die.
Well, a little micro mechanical device offsetting the internal balance could work, though the balance change would have to be pretty large to bump the probability of any one face up significantly.
Make them from a substance that leaves a tiny amount of residue on any surface it's left on for more than a small amount of time. Any time a die is rolled (and then left unperturbed for a short amount of time), that face becomes lighter.
Wouldn't this be the opposite of what you want? You'd weigh down the current bottom face, making that face more likely to be on the bottom for future rolls.
Readit News
A fair 6-sided die would be an equal number of balls numbered 1-6 and a rule that you simply return the ball you drew. You can get a gambler's fallacy distribution by, say, adding one of every ball that you didn't draw. I read the code as a Pólya urn starting with 1 ball 1-N and doing that on each draw plus reducing the number of balls of the drawn number to 1.
Also related, in 2d space, is the idea of randomly covering the plane in points but getting a spread-out distribution, since uniformity will result in clusters. (If you're moving a small window in any direction and you haven't seen a point in a while, you're "due" to see another one, and vice versa if you just saw a point.) Mike Bostock did a very nice visualization of that here: https://bost.ocks.org/mike/algorithms/
[1] https://www.jstor.org/stable/2283724
[2] https://www.fda.gov/downloads/MedicalDevices/DeviceRegulatio...
Relatedly, there's a Bayesian interpretation to overweighting successful past draws. A model where you return one extra ball of the same color to the urn gets you a Dirichlet-multinomial distribution, which is a die-roll distribution where the weights to each face are not known for sure, but are given a probability distribution and revised with observed evidence. In other words: here's an n-sided die, I don't know its weightings, but as I observe outcomes I'll update my beliefs that the sides that come up are more favorably weighted. The number of balls in the urn you start with correspond to your priors; only 1 ball of each color means a very weak belief that it's a fair die, 1000 balls of each color means a strong belief, unequal numbers mean that you start off believing it's weighted.
Then months later by accident while looking at a completely different topic: "OMG there it is, the thing!"
Thank you for that link - a great read!
Another method is to pick a random key K and sort the entries of the playlist based on HMAC(SONG, K) (where SONG is the name or other identifier of the song). This has a number of interesting properties. For starters the playlist will be randomized (that's good). It will also keep it's overall order if a new song is added. The new song will get inserted based upon its HMAC. You can switch things up a bit by having K be a based on the current date. That way new songs will maintain their order and jumping to a track on a given day will continue the chain as before, but day to day you won't always hear the same tracks back to back.
If someone with no specialized knowledge about math and probability requests their songs in a "random" order, I don't think one should assume they are insisting on an order sampled from a uniform distribution.
The article is about weighting randomness based on past distribution. In a music playlist that may be enough. Some user might also want a term in the equation that weights songs they've rated highly to be favored over lower-rated or unrated songs.
'Random' was better, especially when there were players that would play "random album" which was great.
You're right that shuffle has been the standard for a long time, the last actual "random" for singles I remember was napster back when it was popular.
This was a great way of tweaking the "randomization", and really gets into understanding what people want to hear. In my case, I had different stations/playlists customized in different ways.
Deleted Comment
I know this is about being "technically correct" but I'd argue that even if you're pedantic and know the behavior of true randomness, the complaints are justified.
First, "pick a song from a uniform distribution" is an implementation detail, not the use case. The use case is "pick songs in a pleasant, novel order". If the implementer chose to do this using uniform randomness, that's their descision. If that implementation does not fulfill the use case, it's a bug and also their responsibility.
Second, the function is frequently called "shuffle" - so it even gives some hints about the implementation expected. No shuffling algorithm should ever result in duplicates. (except at the beginning and end of playlists)
https://labs.spotify.com/2014/02/28/how-to-shuffle-songs/
About your linked post: You don't test the randomness of the shuffling, you only test if a shuffled list contain one and only of each original item.
I'd like to read about this, do you still have the intended link?
https://en.wikipedia.org/wiki/Simple_random_sample
Whether this was because they had a botched 'smart' randomizer or because they in fact used true random to shuffle, I may never know.
Supposedly Jobs specifically “fixed” this behavior and it’s why there used to be (still is?) a slider that allowed you to customize that behavior.
I manually shuffle some playlists now. One nice thing about the desktop client is the clipboard integration. You can press cmd+a to highlight all the songs, cmd+c to copy, and then paste all the song URLs into a text editor. Then I used "permute lines" in Sublime Text to shuffle them, then cmd+c and cmd+v to paste the songs back into Spotify.
One, if I remember somewhat correctly, was that if the player was stopped/shutdown, it forgot the shuffle seed. This would essentially lead to a reshuffle, which would cause duplicate songs for songs played before the unintended reseeding.
Long ago I asked this related question on stackoverflow: https://stackoverflow.com/questions/5467174/how-to-implement... - it surprises me still that nobody has identified a classic algorithm for solving exactly this problem.
when I finally noticed this and realized that could only mean it's not actually random, I researched it, and found out that once you hit shuffle/random on Winamp, it shuffled the songs once and kept the sequence forever.
and then as it turned out, Winamp actually had a setting to select a truly random song each time. all I needed to cure my madness was a checkbox!
A simpler system is picking a random song, but excluding the last 20 songs played.
Deleted Comment
Players would love that! Make my hero feel more heroic! The inevitable comeback!
But then I thought about the inverse case -- you are doing really well, and now you are due for a failure. Or series of failures. That would feel awful.
We have a lot of emotions around dice rolling. I wonder if players really want from their dice. Would players prefer dice that are secretly unevenly weighted towards good rolls? Would they still want those dice if they knew they were weighted?
It doesn't have the "you are doing really well, and now you are due for a failure" since "not a critical" isn't really that negative of an outcome.
For something like D&D, the same kind of "better-than-random" distribution just comes from adding dice. 4d6 is much more consistent than 1d21+3.
I think there are interesting stories to tell in an RPG where you know the "weight" of your rolls, approximately how many "success" cards you have left, some choice in what you play from your hand.
«But then I thought about the inverse case -- you are doing really well, and now you are due for a failure. Or series of failures. That would feel awful.»
It depends on how personal you take it in how awful it feels. If the goal is to create an interesting story, a grand sequence of failures can be a very interesting story. Look at Fiasco, for instance, where some of the fun can be very explicitly "how do I make my character more miserable?" In those cases where you know you are about to hit a lot of failures in die rolls/card draws you can lean in to it. Try to explain why your character is having such awful luck, for instance. Maybe try to set up an elaborate Rube Goldberg design of failures that eventually cascade into the weirdest, grandest success, like a "drunken master" kung fu ballet.
Randomness is what makes a game more realistic but true randomness will not make it more likable. True randomness dictates that in half of your games, your players will have a harder time achieving anything.
It is not uniformity of results that the players are looking for, it is uniformity of successes weighted by the importance of the rolls. Failing a perception check in an empty room is less important than failing a dodge roll in the final fight on your last health point.
Many games suggest that the gamemaster cheats on some crucial rolls. More games propose an alternate system that biases rolls based on points systems. Some others even replace totally the dices with a points system.
I really prefer those. A very simple biased rolls system I often use (Dk2) is that GM can emphasize the action of dangerous NPCs by adding special D6 dices to a D20 roll (they are special as they only give +3 or +6 on 3 and 6 and +0 on other results). Once used, these dices are added to a pool that the players can use for their actions.
Anyway, my favorite system is Amber Diceless RPG. It trades randomness for secrets. Every player is a bit of a backstabing asshole who does not show all their skills on any action. If someone has 30 in strength, they may just announce 10 if they think it is enough for the action.
The winner in a fight is the one with the bigger score. Add bonus if they use some kind of trick or ambushes (recommended). It is surprisingly interesting for such a simple system.
In general, things are heavily weighted towards actual player skill and also character skills accrued over time for the important interactive elements.
For things like loot drops, it's strictly random from a chart per enemy type, but they monitor the overall economy and use that to set the weights for the various items. If one group of people has figured out some trick to farming an extremely valuable item, they will nerf it to keep the economy where they want it. For a number of years, the company actually kept a professional economist on full-time to keep track of these things. I think that got eliminated when CCP was having a rough financial time several years ago. And I think that game has gotten a bit worse as a result.
But in terms of stuff that counts RNGs are a fairly small part of the action, and in some cases not at all, so you can pick your poison: lower overall damage to a target but more consistent, allowing for one kind of play style. Or you can have more variable damage with higher potential if you're willing to take risks. And there are a couple of flavors along the spectrum.
It's a pretty interesting game design. And, of course, tons of people complain about it. Loot drops really are pretty damn random (with between 30-40 thousand people online at any given time, there's a lot of entropy to seed the PRNG). And you get the clusters you would expect from random data. But everyone really hates random outcomes. People want uniform outcomes. It's baked into our psychology.
But in terms of things that determine who lives and who dies in a fight. The random element is really downplayed, and it boils down to player skill more than anything.
There's a whole thing where people who have been playing for a long time will start brand new accounts with low skill levels and shitty equipment and still be able to blow people out of the water because they have a superior understanding of the game mechanics. In fact, there are entire "corporations" who really do nothing but this. Fine people who have been around for long enough to make some money and buy some expensive things and then lure them into fights and slaughter their bling-bling.
It's an interesting approach to game balance, and one I quite admire. It does keep me coming back, and paying that sweet, sweet monthly sub.
EVE is also one of the games that really capitalizes on the technology component. As much as I love Skyrim, for example, I don't think there's anything going on with the actual game interaction mechanics that couldn't be easily replicated on a table with some dice. I'm also willing to eat my words if I'm completely wrong about that.
EVE Online has the luxury of hammering out fairly complicated formulas based on the current state of things, and it does so very well. It does it for every ship in space (again, typically 30-40k), once each server tick (usually a tick is 1 second, but for really huge fights, they dilate time and slow the ticks down).
So they can make things like damage calculated for each gun or missile or drone on each ship based on every relevant ship's current speed and direction relative to every other ship, etc.
It's an impressive use of technology for an RPG, and I find it especially cool that you are your own gamemaster. The only story is the one you make for yourself.
But now I sound like a fucking fanboi, so I'll shut up.
I've never heard of Amber Diceless before. I'm curious and will check it out. Thanks for mentioning.
Anyway, nice work!
Deleted Comment
> These accusations would come up even though they (all being computer science majors) know it's possible (although unlikely) for these events to happen. They just don't trust the black box.
I am reminded of the approach that GamesByEmail.com used to address this criticism: http://www.gamesbyemail.com/News/DiceOMatic
Hah! That might be the best donation "gift" I've ever heard of!
Given a fair coin that outputs Heads (H) or Tails (T), which of the following sequences is more or less probable
HHTHTT or HHHHHH
Answer: Both are equally probable strings to be generated by the fair coin and each should occur once in every 64 sequences (~1.56%)
HHHHHH THHHHH
Answer: THHHHH. Only 1/(2^6) of the time it will be HHHHHH. The only way to get HHHHHH will be if the first 6 flips are heads. If you don't flip a head you must have got a tail which means THHHHH will always appear before HHHHHH.
You can actually play it right here and go direct to the Boss Fight if you wanted to: http://briancable.com/clock-legends/
With my method, it was possible for the same move to be picked 2 or 3 times in a row, but it mostly went back and forth, so the player was definitely going to encounter both moves, but they couldn't know for absolute certain which move the next one would be (and they both needed you to kind of quickly get into different positions before getting hit).
The type of pattern you'd usually get with mine was more like A,B,B,A,A,B,A,B,A,A,A,B,B,A.
Tetris is the go-to example. Tetris has seven tetronimos, and in most modern implementations you're guaranteed to see them in sets of seven in random order.
http://tetris.wikia.com/wiki/Random_Generator
This is pretty essential to make competitive play err on the side of skill rather than randomness: pro-players can anticipate and plan for this. For fun, here's a recent Tetris head-to-head speed-run from Awesome Games Done Quick, with pretty good narration about the tactics involved:
https://www.youtube.com/watch?v=PeNB4w99FiY&t=1h21m15s
Some purists insist that they role dice, so we just let 'em and the resulting game feels quite like you're using gambler's dice.
I'm not sure that factors into the game (have played but its been a while). Cards seem like a more controlled way to distribute the results with some randomness.
only one way to get a 12 (6+6) but 7 much more likely.. (6+1, 5+2, 4+3, 3+4, 2+5, 1+6)
as someone who played a bit of online backgammon back in the day, We always suspected the random dice rolls behaved differently in the game than playing in real life...
The biggest challenge will probably be the power supply. I'm sure that a processor, accelerometer, and the Taptic Engine (the thing that provides vibration and haptic feedback in Apple devices) are all small enough to fit in a typical die. Of course, something like this could easily be built into a larger novelty die.
Bonus points should be awarded if the die is perfectly balanced when it's not actively adjusting itself in mid-air.
[0] http://appleinsider.com/articles/14/12/02/apple-patents-acti...
This would probably cost a lot of money to fit in a normal sized die.