November 29, 2017 at 14:09How to shuffle songs?
- Transfer
We here at Spotify take user feedback seriously. Some time ago, we noticed that users complain that when the random playlist shuffle mode is on, the order of the songs is actually not random - for example, several songs of the same artist can be played one by one, despite the fact that playlist many songs of different artists. Users asked, are we really not able to do such a simple thing as randomly playing tracks? We replied, “He is really, really random! We checked! ”
So who was right - us or the users? As it turned out, both we and they. Well, in general, the situation was much more serious than it seemed at first glance.
Even in the very first release of our player, it had the function of randomly mixing the playlist. We used the Fisher-Yates algorithm for this - and it gave perfectly random mixing. But what is “perfectly random”? This means, for example, that we can get one of the following song orders with the same probability (different colors mean tracks of different artists):
By the way, personal opinion: the Fisher-Yates algorithm is one of the most elegant of the algorithms I know. It is simply amazing how such a difficult task can be solved in 3 lines of code, at the same time give the correct result and perform the minimum required number of operations.
At first, we did not understand what users were trying to tell us with their complaints about “not an accident”. But after thoughtfully reading the comments, we realized that people don’t like the situation when several songs of the same artist are played in a row. And not even just “in a row”, but when, for example, for 5 songs played, 3 belong to one author (even if other songs were played between them). People considered this a clear violation of chance.
It is well known that people are sometimes seriously mistaken in the intuitive perception of probabilities. Imagine that every day at work you toss a coin to decide what you will eat for lunch today - Thai or Indian food. In the first 4 days, the coin chose Thai. And on Friday you think, “so, for 4 days the coin chose the same thing, well, today there will definitely be Indian food!”. And again, Thai falls out. The fact is that the coin has no memory, it “does not know” what it chose yesterday and completely does not take this into account in its “decision” today. A millionth roll has the same chance of losing an eagle or tails as the first - 50%.
Or another example: people think that if they played the lottery several times and did not win, then the next time they have a greater chance to win something. This phenomenon is called the delusion of the player, and it is applicable for the lottery, and for the above case with a coin and a choice of food.
Let's get back to our users, who are also people, which means that no less than the rest are subject to the player’s error. If you just listened to a song of some artist, and there are other songs in your playlist, then these songs, with random mixing of the playlist, have every right to get to the next position in the playlist. They are no worse than other songs.
But, as they say - "the client is always right." And we decided to think about how to change our mixing algorithm so that its "randomness" was good enough not from a mathematical, but from a psychological point of view. Since ideal mathematical randomness does not look random enough for people.
The task looked like something that should have already been solved by someone before. Indeed, we found an article entitled “The Art of Mixing Music, ” written by Martin Fiedler, and which solves roughly the same problem. However, the algorithm described in it was overcomplicated and sometimes worked too slowly, so we modified it in accordance with our tasks: The
main idea is similar to “shaking”. Imagine that we have a picture drawn in shades of gray (there are several hundred of them):
We want to simplify the image by converting it to a black and white spectrum (use only pure black and pure white pixels). This can be done like this: if the gray pixel has more than 80% black, it gets a 80% chance to become pure black and 20% to become pure white. We process the pixels one at a time and for each we define a new color according to the above rule. The result, of course, will be somewhat reminiscent of the original, but nevertheless it cannot be said that it turned out well:
As you can see, the black pixels are clustered in clusters, plus large white gaps are formed between them. It would be better if the groups of black and white pixels were smaller and more evenly distributed. To do this, you can use another algorithm, for example, Floyd-Steinberg :
Clusters, clearly visible in the previous picture, are gone. We can use the ideas of this algorithm in our task of mixing songs. This will allow us to avoid dropping songs of one artist into clusters - we will try to distribute them throughout the playlist. Let's imagine that we have a playlist consisting of songs by artists such as The White Stripes (red in the picture), The xx (black), Bonobo (green), Britney Spears (pink) and Jaga Jazzist (orange). We will take the songs of each of the performers and try to “smear” them on the playlist. A picture is better than a thousand words:
As you can see, the songs of each artist are distributed far enough from each other and to the human eye this order of the playlist looks perfectly random (although it is not). Let's take a closer look at how the algorithm works.
Let us have 4 songs by The White Stripes (as in the picture above). This means that each of the songs should fall into approximately every 25% of the total duration of the playlist. We distribute 4 songs at a distance of 20% to 30% from each other (it looks “random"). You see, the distances between the red circles on the line are not the same. At the beginning we add a random indent, otherwise the first songs of each artist will fall to point 0 on the line. You may notice that Britney Spears and Jaga Jazzist have just one song each, but a random starting bias puts them in a random place in the playlist. We also shuffle the songs of one artist relative to each other (the old Fisher-Yates algorithm will come down here, although we can recursively apply our new algorithm if we, for example,
Now the algorithm is already used by our players on all platforms. Thanks to all users who have well described their problems regarding playlist randomness.
So who was right - us or the users? As it turned out, both we and they. Well, in general, the situation was much more serious than it seemed at first glance.
Our point of view
Even in the very first release of our player, it had the function of randomly mixing the playlist. We used the Fisher-Yates algorithm for this - and it gave perfectly random mixing. But what is “perfectly random”? This means, for example, that we can get one of the following song orders with the same probability (different colors mean tracks of different artists):
By the way, personal opinion: the Fisher-Yates algorithm is one of the most elegant of the algorithms I know. It is simply amazing how such a difficult task can be solved in 3 lines of code, at the same time give the correct result and perform the minimum required number of operations.
Player misconception
At first, we did not understand what users were trying to tell us with their complaints about “not an accident”. But after thoughtfully reading the comments, we realized that people don’t like the situation when several songs of the same artist are played in a row. And not even just “in a row”, but when, for example, for 5 songs played, 3 belong to one author (even if other songs were played between them). People considered this a clear violation of chance.
It is well known that people are sometimes seriously mistaken in the intuitive perception of probabilities. Imagine that every day at work you toss a coin to decide what you will eat for lunch today - Thai or Indian food. In the first 4 days, the coin chose Thai. And on Friday you think, “so, for 4 days the coin chose the same thing, well, today there will definitely be Indian food!”. And again, Thai falls out. The fact is that the coin has no memory, it “does not know” what it chose yesterday and completely does not take this into account in its “decision” today. A millionth roll has the same chance of losing an eagle or tails as the first - 50%.
Or another example: people think that if they played the lottery several times and did not win, then the next time they have a greater chance to win something. This phenomenon is called the delusion of the player, and it is applicable for the lottery, and for the above case with a coin and a choice of food.
Let's get back to our users, who are also people, which means that no less than the rest are subject to the player’s error. If you just listened to a song of some artist, and there are other songs in your playlist, then these songs, with random mixing of the playlist, have every right to get to the next position in the playlist. They are no worse than other songs.
But, as they say - "the client is always right." And we decided to think about how to change our mixing algorithm so that its "randomness" was good enough not from a mathematical, but from a psychological point of view. Since ideal mathematical randomness does not look random enough for people.
Algorithm
The task looked like something that should have already been solved by someone before. Indeed, we found an article entitled “The Art of Mixing Music, ” written by Martin Fiedler, and which solves roughly the same problem. However, the algorithm described in it was overcomplicated and sometimes worked too slowly, so we modified it in accordance with our tasks: The
main idea is similar to “shaking”. Imagine that we have a picture drawn in shades of gray (there are several hundred of them):
We want to simplify the image by converting it to a black and white spectrum (use only pure black and pure white pixels). This can be done like this: if the gray pixel has more than 80% black, it gets a 80% chance to become pure black and 20% to become pure white. We process the pixels one at a time and for each we define a new color according to the above rule. The result, of course, will be somewhat reminiscent of the original, but nevertheless it cannot be said that it turned out well:
As you can see, the black pixels are clustered in clusters, plus large white gaps are formed between them. It would be better if the groups of black and white pixels were smaller and more evenly distributed. To do this, you can use another algorithm, for example, Floyd-Steinberg :
Clusters, clearly visible in the previous picture, are gone. We can use the ideas of this algorithm in our task of mixing songs. This will allow us to avoid dropping songs of one artist into clusters - we will try to distribute them throughout the playlist. Let's imagine that we have a playlist consisting of songs by artists such as The White Stripes (red in the picture), The xx (black), Bonobo (green), Britney Spears (pink) and Jaga Jazzist (orange). We will take the songs of each of the performers and try to “smear” them on the playlist. A picture is better than a thousand words:
As you can see, the songs of each artist are distributed far enough from each other and to the human eye this order of the playlist looks perfectly random (although it is not). Let's take a closer look at how the algorithm works.
Let us have 4 songs by The White Stripes (as in the picture above). This means that each of the songs should fall into approximately every 25% of the total duration of the playlist. We distribute 4 songs at a distance of 20% to 30% from each other (it looks “random"). You see, the distances between the red circles on the line are not the same. At the beginning we add a random indent, otherwise the first songs of each artist will fall to point 0 on the line. You may notice that Britney Spears and Jaga Jazzist have just one song each, but a random starting bias puts them in a random place in the playlist. We also shuffle the songs of one artist relative to each other (the old Fisher-Yates algorithm will come down here, although we can recursively apply our new algorithm if we, for example,
Conclusion
Now the algorithm is already used by our players on all platforms. Thanks to all users who have well described their problems regarding playlist randomness.