2048 Design

Brain dump, to separate later.

2048 Project Description

Goals of the 2048 Project

  • Systematic engineering
  • Testing
  • Scientific investigation (meaningful numbers for performance, comparisons)
  • AI code with cleanup
    • Structured code
    • Localized changes (learn to manage)

Concepts

  • Tree search
  • Designing experiments
  • Sophisticated structure (well, more sophisticated than before, at least)

Outline: Large-Scale Structure

Game

A version of 2048.

  • History mechanism so you can move backwards and forwards in the list of moves already seen.
  • Computer single play using “a”.
  • Computer continuous play (forward/backward) using “f”/“b”.
  • Pause/resume the animation hitting the space bar.
  • You can take over play from the point the animation is stopped. (Is this a useful feature?)

Simulator

  • Constructor accepts a Strategy object. Optional Reporter (later).

  • run_one: should this optionally take in a starting state?

      initialize board with first two tiles?
  report: start
  repeat until game over:
      next move from Strategy object
      spawn new tile
      report: change(move, spawn, current state)
  report: end

  • Should there be a summarize method? Or leave that to the Reporter?

  • run_repeatedly (int ntimes)

    Explain how this is going to work with the reporter if needed. Are we including run number in the list of output.

Reporter

Manages however the programmer wants to produce a trace of the program. The basic one prints id, move, board as (augmented) CSV output.

  • The board should stay the last item on the line even if more is added.
  • The id should be a unique constant for each game. Details: you could use a numbering convention like 1000+n for one Strategy and 2000+n for another. Alternatively, output a lookup table mapping id to Strategy.
  • If you let your Reporter know about the Strategy’s heuristic, it could output that information as well. Strictly speaking, this could be derived from the board state, but it’s more conveient if the info is already available.

The constructor of Reporter can take in a file object.

Speed Test

SpeedTest is built from Simulator by starting a timer before starting the simulation and stopping it afterwards.

Reporting could be augmented by adding a timestamp to every observation.

Trace Generator

  • Constructor takes in a Strategy.
  • generate(Optional[Board]) -> [(Move, Board)] plays out the game and records every move in a trace that the visualizer can use.

Outline: Small-Scale Structure

Move

Everyone agree on numbering: up (1), down (2), left (3), right (4). I will use 0 for the no-op filler for the move spot. (Reporting the board state before the first move can use that.)

Board

Representation

The board is represented by a list of 16 integer.

  • $n=0$ is the empty square
  • $n>0$ is the tile $2^n$

Square numbering:

0  1  2  3
4  5  6  7
8  9  10 11
12 13 14 15

Functions

  • score : Board -> int

  • make_move : Board Move -> Board

  • legal_moves : Board -> [Move]

  • freeze: generate an immutable version of the state

  • unfreeze: is this even necessary?

Notes: the score of a 2048 game is the sum of all of tile merges. Examples:

  • A board that began with 2+2+2+2 and produced an 8 would have the score 4+4+8 = 16.
  • A board that began with 4+4 and produced an 8 would have score 8.

Recommendation: do not look at actual score; instead compute the score from the board by assuming everything began as a 2.

$$ \text{score}(2^n) = 2^n \cdot (n-1)$$

Strategy

An object with a next_move(Board) -> Move method.

Research Questions

How much does luck matter? Does spawning all 2 vs all 4 vs a mix affect the highest score? What if the Strategy knows what will happen and accounts for that in its move planning?