How to shuffle songs?
We here in Spotify take seriously the feedback from users. Some time ago, we noticed that users complained that when random playlist shuffle is on, the order of songs is actually not random - for example, several songs by the same artist can be played one after another, despite the fact that playlist many songs of different artists. Users asked, are we really not able to do such a simple thing as a random order of playing tracks? We replied, "He is true-true by chance!" We checked! "
So who was right, we or the users? As it turned out - 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 shuffling the playlist. We used the Fisher-Yates algorithm for this — and it gave perfect random mixing. But what is “perfectly random”? This means, for example, that we can get one of the following two orders of songs with the same probability (different colors mean tracks by different artists):
')
By the way, personal opinion: the Fisher-Yates algorithm is one of the most elegant algorithms known to me. It is simply amazing how such a difficult task can be solved in 3 lines of code, to give the correct result and to perform the minimum number of operations.
At first, we did not understand what the users were trying to say to us with their complaints about “not an accident”. But after a thoughtful reading of the comments, we realized that people do not like the situation when several songs of the same artist play in a row. And not even just “in a row”, but when, for example, in 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 sometimes make serious mistakes in the intuitive perception of probabilities. Imagine that every day at work you throw up a coin to decide whether you will eat lunch today - Thai food or Indian. In the first 4 days, the coin chose Thai. And on Friday you are thinking “so, 4 days the coin chose the same thing, well, today there will definitely be Indian food!”. And Thai falls again. The fact is that the coin has no memory, she “does not know” that she chose yesterday and does not take it into account at all in today's “decision”. Millionth throw has the same chances of falling out of an eagle or tails, like the first - 50%.
Or another example: people think that if they played a lot of times in the lottery and did not win, then next time they have a greater chance of winning something. This phenomenon is called a player's delusion, and it is applicable to the lottery, and to the above described case with a coin and a choice of food.
Let's go back to our users, who are also people, which means no less than the others are subject to the player's delusions. If you have just listened to a song of a singer, and there are other of his songs in your playlist, then these songs, if the playlist is randomly mixed, 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” would be good enough not from a mathematical, but from a psychological point of view. Since the ideal mathematical randomness does not look sufficiently random for people.
The task looked like something that should have already been solved by someone earlier. And indeed, we found the article “The Art of Mixing Music, ” written by Martin Fiedler and about the same problem being solved. However, the algorithm described in it was overcomplicated and sometimes worked too slowly, so we modified it according to our tasks:
The main idea is similar to “shaking”. Imagine that we have a picture drawn in shades of gray (there are several hundreds):
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 as follows: if the gray pixel is more than 80% black, it gets a chance to become pure black by 80% and become pure white by 20%. We process the pixels one by one and for each we define a new color according to the above rule. The result, of course, will somewhat resemble the original, but still it is impossible to say that it turned out well:
As you can see, black pixels are clustered together, plus large white gaps between them have formed. 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 :
The clusters, well 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 knocking down 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 this order of the playlist looks ideally random to the human eye (although it is not). Let's take a closer look at how the algorithm works.
Suppose we have 4 songs by The White Stripes (as in the picture above). This means that each of the songs should fall approximately every 25% of the total duration of the playlist. We distribute 4 songs at a distance of 20% to 30% from each other (this is how it looks "random"). 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 into point 0 on the line. You may notice that Britney Spears and Jaga Jazzist have only one song in total, but a random starting bias puts them in a random place in the playlist. We also shuffle the songs of one performer relative to each other (here the old Fisher-Yates algorithm also comes together, although we can recursively apply our new algorithm if we, for example, want to distribute songs from different albums as evenly as we distribute songs of different artists).
Now the algorithm is already used by our players on all platforms. Thanks to all users who are well described their problems concerning the randomness of playlists.
So who was right, we or the users? As it turned out - 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 shuffling the playlist. We used the Fisher-Yates algorithm for this — and it gave perfect random mixing. But what is “perfectly random”? This means, for example, that we can get one of the following two orders of songs with the same probability (different colors mean tracks by different artists):
')
By the way, personal opinion: the Fisher-Yates algorithm is one of the most elegant algorithms known to me. It is simply amazing how such a difficult task can be solved in 3 lines of code, to give the correct result and to perform the minimum number of operations.
Misconception player
At first, we did not understand what the users were trying to say to us with their complaints about “not an accident”. But after a thoughtful reading of the comments, we realized that people do not like the situation when several songs of the same artist play in a row. And not even just “in a row”, but when, for example, in 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 sometimes make serious mistakes in the intuitive perception of probabilities. Imagine that every day at work you throw up a coin to decide whether you will eat lunch today - Thai food or Indian. In the first 4 days, the coin chose Thai. And on Friday you are thinking “so, 4 days the coin chose the same thing, well, today there will definitely be Indian food!”. And Thai falls again. The fact is that the coin has no memory, she “does not know” that she chose yesterday and does not take it into account at all in today's “decision”. Millionth throw has the same chances of falling out of an eagle or tails, like the first - 50%.
Or another example: people think that if they played a lot of times in the lottery and did not win, then next time they have a greater chance of winning something. This phenomenon is called a player's delusion, and it is applicable to the lottery, and to the above described case with a coin and a choice of food.
Let's go back to our users, who are also people, which means no less than the others are subject to the player's delusions. If you have just listened to a song of a singer, and there are other of his songs in your playlist, then these songs, if the playlist is randomly mixed, 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” would be good enough not from a mathematical, but from a psychological point of view. Since the ideal mathematical randomness does not look sufficiently random for people.
Algorithm
The task looked like something that should have already been solved by someone earlier. And indeed, we found the article “The Art of Mixing Music, ” written by Martin Fiedler and about the same problem being solved. However, the algorithm described in it was overcomplicated and sometimes worked too slowly, so we modified it according to our tasks:
The main idea is similar to “shaking”. Imagine that we have a picture drawn in shades of gray (there are several hundreds):
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 as follows: if the gray pixel is more than 80% black, it gets a chance to become pure black by 80% and become pure white by 20%. We process the pixels one by one and for each we define a new color according to the above rule. The result, of course, will somewhat resemble the original, but still it is impossible to say that it turned out well:
As you can see, black pixels are clustered together, plus large white gaps between them have formed. 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 :
The clusters, well 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 knocking down 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 this order of the playlist looks ideally random to the human eye (although it is not). Let's take a closer look at how the algorithm works.
Suppose we have 4 songs by The White Stripes (as in the picture above). This means that each of the songs should fall approximately every 25% of the total duration of the playlist. We distribute 4 songs at a distance of 20% to 30% from each other (this is how it looks "random"). 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 into point 0 on the line. You may notice that Britney Spears and Jaga Jazzist have only one song in total, but a random starting bias puts them in a random place in the playlist. We also shuffle the songs of one performer relative to each other (here the old Fisher-Yates algorithm also comes together, although we can recursively apply our new algorithm if we, for example, want to distribute songs from different albums as evenly as we distribute songs of different artists).
Conclusion
Now the algorithm is already used by our players on all platforms. Thanks to all users who are well described their problems concerning the randomness of playlists.
What else can you read on this topic
Source: https://habr.com/ru/post/343482/
All Articles