<commit_before>---
layout: post
title: "The Mathematics of 2048: Counting States with Combinatorics"
date: 2017-09-17 01:00:00 +0000
categories: articles
image: /assets/2048/2048_infeasible.png
description: How many board configurations are there in the game of 2048? Let's estimate using combinatorics.
---

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

In [my last 2048 post](/articles/2017/08/05/markov-chain-2048.html), I found that it takes at least 938.8 moves on average to win a game of [2048](http://gabrielecirulli.github.io/2048). The main simplification that enabled that calculation was to ignore the structure of the board --- essentially to throw the tiles into a bag instead of placing them on a board. With the 'bag' simplification, we were able to model the game as a Markov chain with only 3486 distinct states.

In this post, we'll make a first cut at counting the number of states without the bag simplification. That is, in this post a *state* captures the complete configuration of the board by specifying which tile, if any, is in each of the board's cells. We would therefore expect there to be a lot more states of this kind, now that the positions of the tiles (and cells without tiles) are included, and we will see that this is indeed the case.

To do so, we will use some (simple) techniques from enumerative combinatorics to exclude some states that we can write down but which can't actually occur in the game. The results will also apply to 2048-like games played on different boards (not just 4x4) and up to different tiles (not just the `2048` tile). We'll see that such games on smaller boards and/or to smaller tiles have far fewer states than the full 4x4 game to 2048, and that the techniques used here are relatively much more effective at reducing the estimated number of states when the board size is small. As a bonus, we'll also see that the 4x4 board is the smallest square board on which it is possible to reach the `2048` tile.

The (research quality) code behind this article is [open source](https://github.com/jdleesmiller/twenty48), in case you would like to see the [implementation](https://github.com/jdleesmiller/twenty48/blob/4337c357f2cc14bdc3e14ddaa5207ad2a6a972e6/bin/combinatorics) or [code for the plots](https://github.com/jdleesmiller/twenty48/tree/4337c357f2cc14bdc3e14ddaa5207ad2a6a972e6/data/combinatorics).<commit_msg>Mention the cover image<commit_after>---
layout: post
title: "The Mathematics of 2048: Counting States with Combinatorics"
date: 2017-09-17 01:00:00 +0000
categories: articles
image: /assets/2048/2048_infeasible.png
description: How many board configurations are there in the game of 2048? Let's estimate using combinatorics.
---

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

In [my last 2048 post](/articles/2017/08/05/markov-chain-2048.html), I found that it takes at least 938.8 moves on average to win a game of [2048](http://gabrielecirulli.github.io/2048). The main simplification that enabled that calculation was to ignore the structure of the board --- essentially to throw the tiles into a bag instead of placing them on a board. With the 'bag' simplification, we were able to model the game as a Markov chain with only 3486 distinct states.

In this post, we'll make a first cut at counting the number of states without the bag simplification. That is, in this post a *state* captures the complete configuration of the board by specifying which tile, if any, is in each of the board's cells. We would therefore expect there to be a lot more states of this kind, now that the positions of the tiles (and cells without tiles) are included, and we will see that this is indeed the case.

To do so, we will use some (simple) techniques from enumerative combinatorics to exclude some states that we can write down but which can't actually occur in the game, such as the one above. The results will also apply to 2048-like games played on different boards (not just 4x4) and up to different tiles (not just the `2048` tile). We'll see that such games on smaller boards and/or to smaller tiles have far fewer states than the full 4x4 game to 2048, and that the techniques used here are relatively much more effective at reducing the estimated number of states when the board size is small. As a bonus, we'll also see that the 4x4 board is the smallest square board on which it is possible to reach the `2048` tile.

The (research quality) code behind this article is [open source](https://github.com/jdleesmiller/twenty48), in case you would like to see the [implementation](https://github.com/jdleesmiller/twenty48/blob/4337c357f2cc14bdc3e14ddaa5207ad2a6a972e6/bin/combinatorics) or [code for the plots](https://github.com/jdleesmiller/twenty48/tree/4337c357f2cc14bdc3e14ddaa5207ad2a6a972e6/data/combinatorics).
{'fraction_non_alphanumeric': 0.06666666666666667, 'fraction_numerical': 0.06175024582104228, 'mean_word_length': 4.7468926553672315, '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': '5147056', 'n_tokens_mistral': 1629, 'n_tokens_neox': 1412, 'n_words': 727}