<commit_before>---
layout: post
title: "The Mathematics of 2048: Minimum Moves to Win with Markov Chains"
date: 2017-08-05 09:00:00 +0000
categories: articles
image: /assets/2048/markov_chain_weighted_mixture.png
description: How many moves does it take to win a game of 2048? Find out using Markov chains!
---

<img src="/assets/2048/2048.png" alt="Screenshot of 2048" style="width: 40%; float: right; margin-left: 10pt; border: 6pt solid #eee;"/>

As part of a recent revamp, [2048](http://gabrielecirulli.github.io/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?

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**. This gives us a benchmark --- if you can win in around this number of moves, you're doing pretty well.

The number of moves needed to win depends on random chance, because the game adds `2` and `4` tiles at random. 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.

To obtain these results, we'll use a simplified version of 2048: instead of placing the tiles on a board, we'll&hellip; throw them into a bag. That is, we'll ignore the geometric constraints imposed by the board on which tiles can be merged together. This simplification makes our job much easier, because the player no longer has to make any decisions [^mdp], and because we don't have to keep track of where the tiles are on the board.

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. 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.

If you're not familiar with 2048 or with Markov chains, that's OK --- I'll introduce the necessary ideas as we go. The (research quality) code behind this article is [open source](https://github.com/jdleesmiller/twenty_48), in case you'd like to see the code to generate [the chain](https://github.com/jdleesmiller/twenty48/blob/27c30f5e42861c87a2162efed38003a9db9e8b29/bin/markov_chain) and [the plots](https://github.com/jdleesmiller/twenty48/blob/27c30f5e42861c87a2162efed38003a9db9e8b29/data/markov_chain/plot.R).
<commit_msg>Use new repo URL<commit_after>---
layout: post
title: "The Mathematics of 2048: Minimum Moves to Win with Markov Chains"
date: 2017-08-05 09:00:00 +0000
categories: articles
image: /assets/2048/markov_chain_weighted_mixture.png
description: How many moves does it take to win a game of 2048? Find out using Markov chains!
---

<img src="/assets/2048/2048.png" alt="Screenshot of 2048" style="width: 40%; float: right; margin-left: 10pt; border: 6pt solid #eee;"/>

As part of a recent revamp, [2048](http://gabrielecirulli.github.io/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?

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**. This gives us a benchmark --- if you can win in around this number of moves, you're doing pretty well.

The number of moves needed to win depends on random chance, because the game adds `2` and `4` tiles at random. 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.

To obtain these results, we'll use a simplified version of 2048: instead of placing the tiles on a board, we'll&hellip; throw them into a bag. That is, we'll ignore the geometric constraints imposed by the board on which tiles can be merged together. This simplification makes our job much easier, because the player no longer has to make any decisions [^mdp], and because we don't have to keep track of where the tiles are on the board.

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. 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.

If you're not familiar with 2048 or with Markov chains, that's OK --- I'll introduce the necessary ideas as we go. The (research quality) code behind this article is [open source](https://github.com/jdleesmiller/twenty48), in case you'd like to see the code to generate [the chain](https://github.com/jdleesmiller/twenty48/blob/27c30f5e42861c87a2162efed38003a9db9e8b29/bin/markov_chain) and [the plots](https://github.com/jdleesmiller/twenty48/blob/27c30f5e42861c87a2162efed38003a9db9e8b29/data/markov_chain/plot.R).

{'fraction_non_alphanumeric': 0.06792452830188679, 'fraction_numerical': 0.05169811320754717, 'mean_word_length': 4.58, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 6, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1680490', 'n_tokens_mistral': 1671, 'n_tokens_neox': 1452, 'n_words': 793}