![]() Whenever the game places a random tile on the board, it always follows the same process: pick an available cell uniformly at random, then add a new tile either with value 2, with probability 0.9, or value 4, with probability 0.1.įor 2048 in a bag, we don’t care about finding an available cell, because we haven’t put any capacity constraint on the bag we just care about adding either a 2 or 4 tile with the given probabilities. To represent this in the Markov chain, we need to work out the transition probabilities from the initial state to each of the possible successor states.įortunately, we can look at the game’s source code to find out how the game does this. When we start a new game of 2048, the game places two random tiles on the board (see examples above). ![]() In diagram form, which we’ll add to below, this initial state looks like: Initially, there are no tiles, so our initial state is simply the empty set. We don’t care about the order of the tiles, so we can think of it as a multiset of tiles. ![]() Here we will define each state to encode which tiles are currently in the bag. Each state is like a snapshot of the game at a moment in time, and the transition probabilities specify, for each state, which state is likely to come next. To represent our simplified ‘2048 in a bag’ game as a Markov chain, we need to define the states and the transition probabilities of the chain. The (research quality) code behind this article is open source, in case you’d like to see the code to generate the chain and the plots. ![]() If you’re not familiar with 2048 or with Markov chains, that’s OK - I’ll introduce the necessary ideas as we go. However, by playing many games of 2048 (for science!), I’ll also show that we can often get close to this lower bound in practice. The price we pay for relaxing the geometric constraints is that we can only compute a lower bound on the expected number of moves to win it might be that the geometric constraints make it impossible to attain that bound. This simplification makes our job much easier, because the player no longer has to make any decisions 1, and because we don’t have to keep track of where the tiles are on the board. That is, we’ll ignore the geometric constraints imposed by the board on which tiles can be merged together. To obtain these results, we’ll use a simplified version of 2048: instead of placing the tiles on a board, we’ll… throw them into a bag. The analysis will also show that the distribution for the minimum number of moves to win has a standard deviation of 8.3 moves, and that its overall shape is well-approximated by a mixture of binomial distributions. The number of moves needed to win depends on random chance, because the game adds 2 and 4 tiles at random. This gives us a benchmark - if you can win in around this number of moves, you’re doing pretty well. In this post, we’ll answer that question by modeling the game of 2048 as a Markov chain and analyzing it to show that, no matter how well the player plays, the number of moves required to win the game is at least 938.8 on average. Next: Counting States with Combinatorics.Īs part of a recent revamp, 2048’s “You win!” screen started reporting the number of moves it took to win, which made me wonder: how many moves should it take to win? There was some lively discussion about this series on Hacker News.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |