A Song Shuffling Algorithm Proposal
Real music shuffling never feels random enough. We have a biased view of what randomness is. If we shuffle a playlist and the same song plays twice in a row, we think the shuffling algorithm is broken. In reality, the song that just played had as much chance as any other song to be selected.
Shuffling a small set (like most of your playlists) is not an unknown concept for Tetris. Tetris only has 7 pieces. In versions of the game that implement real randomness (such as Sega Tetris) to select the next piece, it often feels like the game favors certain pieces. A good example is known as the drought.
Many versions of the game try to mitigate the problem by implementing algorithms that are not 100% random. In my opinion, one of the best algorithm in any Tetris game to select a piece is the one found in the Tetris: The Grand Master series.
“The system involves keeping a history of the four most recent tetrominoes and trying to choose a random tetromino not in the history. Each time a piece is generated, the game will try a certain number of times to generate a tetromino that doesn’t match any in the history; if all tries fail and generate a recent piece, the game will settle with that recent piece. The overall effect is to minimize several of the same tetromino showing up in succession, while maintaining a certain amount of unpredictability. TGM1 uses 4 tries, while subsequent games using the TGM randomizer use 6 tries.” Tetris Wikia
Applying this algorithm to music, we might get something like what is described below.
- The last n songs are kept in memory.
- The history depth (n) depends on the size of the song library.
- A random song is selected.
- If the artist of the randomly selected song is the artist of one of the last n songs. A new song is randomly selected.
- If after 4 tries, a song from an artist not in the history couldn’t be selected, stop trying to select a new song and select the current one.
I’ve implemented this algorithm in Java. The code can be found on Github.Posted on 2018-01-15 #tetris #java