2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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. 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, which were specifically designed for this kind of problem. Russell & Norvig have a good set of chapters on both approaches (14-17).

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.