title: How to work out the complexity of the game 2048?
body: <p><strong>Edit:</strong> This question is not a duplicate of <a href="https://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048">What is the optimal algorithm for the game 2048?</a></p>
  
  <ul>
  <li>That question asks 'what is the best way to win the game?'</li>
  <li>This question asks 'how can we work out the complexity of the game?'</li>
  </ul>
  
  <p>They are completely different questions. I'm not interested in which steps are required to move towards a 'win' state - I'm interested in in finding out whether the total number of possible steps can be calculated.</p>
  
  <hr>
  
  <p>I've been reading this <a href="https://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048">question</a> about the game <a href="http://gabrielecirulli.github.io/2048/" rel="nofollow noreferrer">2048</a> which discusses strategies for creating an algorithm that will perform well playing the game.</p>
  
  <p>The accepted answer mentions that:</p>
  
  <blockquote>
    <p>the game is a discrete state space, perfect information, turn-based game like chess</p>
  </blockquote>
  
  <p>which got me thinking about its complexity. For deterministic games like chess, its possible (in theory) to work out all the possible moves that lead to a win state and work backwards, selecting the best moves that keep leading towards that outcome. I know this leads to a large number of possible moves (something in the range of the number of atoms in the universe).. but is 2048 more or less complex?</p>
  
  <p>Psudocode:</p>
  
  <pre><code>for the current arrangement of tiles
      - work out the possible moves
      - work out what the board will look like if the program adds a 2 to the board
      - work out what the board will look like if the program adds a 4 to the board
      - move on to working out the possible moves for the new state
  </code></pre>
  
  <p>At this point I'm thinking I will be here a while waiting on this to run...</p>
  
  <p>So my question is - how would I begin to write this algorithm - what strategy is best for calculating the complexity of the game?</p>
  
  <p>The big difference I see between 2048 and chess is that the program can select randomly between 2 and 4 when adding new tiles - which seems add a massive number of additional possible moves.</p>
  
  <p>Ultimately I'd like the program to output a single figure showing the number of possible permutations in the game. Is this possible?!</p>