Answers.Body: <p>To model 2048 (or any problem) for search, you need a only a few pieces of information.</p>
  
  <p>Note first though, that 2048 is not suitable for minimax, because there's only one player! Instead, you can treat this as a <a href="https://en.wikipedia.org/wiki/Markov_decision_process" rel="nofollow noreferrer">Markov decision process</a>. The techniques to solve it are pretty similar though. Basically, you'll do search for one player, and insert "chance" nodes at each ply of the search. The value of a chance node is the expected value of its children. Note that this will reduce the effectiveness of pruning, so it might mean the problem is not tractable for search-based approaches.</p>
  
  <ol>
  <li>What does an <em>end state</em> look like? Usually you have some function <em>G(s)</em> that accepts a state s, and produces true if and only if it's an end state. In 2048, end states would be states where the player loses (no moves possible), or where the player wins (a 131072 tile is present), so this should be fairly easy to write.</li>
  <li>What are the <em>payoffs</em>? This is usually given by a utility function <em>U(e)</em> that accepts an end-state e, and produces a numeric value indicating the utility the player will receive.</li>
  <li>What actions can the player take in each state? In 2048, these are always the same (up, down, left and right)</li>
  <li>How are new states generated from old states and player actions (in this case, the tiles slide according to the rules of the game, and then a new tile is inserted at a random empty location.</li>
  </ol>
  
  <p>Although search <em>might</em> work here, since 2048 is a relatively simple MDP, you might be happier using techniques from <a href="https://en.wikipedia.org/wiki/Reinforcement_learning" rel="nofollow noreferrer">reinforcement learning</a>, which were specifically designed for this kind of problem. <a href="https://rads.stackoverflow.com/amzn/click/0136042597" rel="nofollow noreferrer">Russell &amp; Norvig</a> have a good set of chapters on both approaches (14-17).  </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-03-14T23:18:02.617Z
Answers.Text: You can model 2048 as a two player game, just with a random opponent (how the game chooses new tiles) instead of one playing adversarially.
Answers.UserDisplayName: qwr
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-08T15:22:47.210Z
Answers.LastActivityDate: 2018-08-08T15:22:47.210Z
Answers.UserDisplayName: John Doucette
Answers.Body: <p>2048 is still a two player game, just not in the minimax sense. The computer of the original game just plays moves randomly rather than adversarially (it is possible to program a much harder variant of 2048 that does play adversarially).</p>
  <p>We can therefore use a variant of minimax called exptectimax that considers expected value of all possible computer random moves instead of minimizing the score in adversarial play. Since we cannot evaluate the entire state space, we must limit the depth of our search and estimate expected value using heuristics described below instead of computing it exactly.</p>
  <p><a href="http://azaky.github.io/2048-AI/paper.pdf" rel="nofollow noreferrer">http://azaky.github.io/2048-AI/paper.pdf</a> for more explanations and experiments results</p>
  <p><a href="https://stackoverflow.com/a/22498940/3163618">https://stackoverflow.com/a/22498940/3163618</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-03-14T23:14:37.800Z
Answers.LastActivityDate: 2022-03-14T23:14:37.800Z
Answers.UserDisplayName: qwr
Body: <p>If we model the game '2048' using a max-min game tree, what is the maximal path from a start state to a terminal state? (Assume the game ends only when the board is full.)</p>
  <p>This is one of the sub-questions that should prepare us to actually modeling the game as a max-min game tree. However, I'm failing to understand the question.</p>
  <p>Is it actually the path to receiving 131072 as an endgame?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-03-15T16:43:16.317Z
Comments.Text: This is an old question, but you should specify why you fail to understand the question. What is "131072" here? What do you know about minimax? Is this a homework? If yes, you should add the tag [tag:homework]. These are questions that people reading your post (like me) might have.
Comments.UserDisplayName: nbro
Tags: <search><minimax>
Title: If we model the game "2048" using a max-min game tree, what is the maximal path from a start state to a terminal state?
UserDisplayName: Bar
ThreadText: # If we model the game "2048" using a max-min game tree, what is the maximal path from a start state to a terminal state?
  
  (Asked by: username_0 on 2018-04-13)
  
  If we model the game '2048' using a max-min game tree, what is the maximal path from a start state to a terminal state? (Assume the game ends only when the board is full.)
  
  This is one of the sub-questions that should prepare us to actually modeling the game as a max-min game tree. However, I'm failing to understand the question.
  
  Is it actually the path to receiving 131072 as an endgame?
  
  **Tags:** search, minimax
  > **Comments:**
  > **username_1**: This is an old question, but you should specify why you fail to understand the question. What is "131072" here? What do you know about minimax? Is this a homework? If yes, you should add the tag [tag:homework]. These are questions that people reading your post (like me) might have.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2018-08-08. Score: 1
  
  To model 2048 (or any problem) for search, you need a only a few pieces of information.
  
  Note first though, that 2048 is not suitable for minimax, because there's only one player! Instead, you can treat this as a [Markov decision process](https://en.wikipedia.org/wiki/Markov_decision_process). The techniques to solve it are pretty similar though. Basically, you'll do search for one player, and insert "chance" nodes at each ply of the search. The value of a chance node is the expected value of its children. Note that this will reduce the effectiveness of pruning, so it might mean the problem is not tractable for search-based approaches.
  
  1. What does an *end state* look like? Usually you have some function *G(s)* that accepts a state s, and produces true if and only if it's an end state. In 2048, end states would be states where the player loses (no moves possible), or where the player wins (a 131072 tile is present), so this should be fairly easy to write.
  2. What are the *payoffs*? This is usually given by a utility function *U(e)* that accepts an end-state e, and produces a numeric value indicating the utility the player will receive.
  3. What actions can the player take in each state? In 2048, these are always the same (up, down, left and right)
  4. How are new states generated from old states and player actions (in this case, the tiles slide according to the rules of the game, and then a new tile is inserted at a random empty location.
  
  Although search *might* work here, since 2048 is a relatively simple MDP, you might be happier using techniques from [reinforcement learning](https://en.wikipedia.org/wiki/Reinforcement_learning), which were specifically designed for this kind of problem. [Russell & Norvig](https://rads.stackoverflow.com/amzn/click/0136042597) have a good set of chapters on both approaches (14-17).
  
  > **Comments:**
  > **username_3**: You can model 2048 as a two player game, just with a random opponent (how the game chooses new tiles) instead of one playing adversarially.  
  
  ---
  
  ### Answer by username_3 on 2022-03-14. Score: 0
  
  2048 is still a two player game, just not in the minimax sense. The computer of the original game just plays moves randomly rather than adversarially (it is possible to program a much harder variant of 2048 that does play adversarially).
  
  We can therefore use a variant of minimax called exptectimax that considers expected value of all possible computer random moves instead of minimizing the score in adversarial play. Since we cannot evaluate the entire state space, we must limit the depth of our search and estimate expected value using heuristics described below instead of computing it exactly.
  
  <http://azaky.github.io/2048-AI/paper.pdf> for more explanations and experiments results
  
  <https://stackoverflow.com/a/22498940/3163618>
  
  
  ---
  
  