2048: betting on the odds, assuming the worst, and a gate that keeps you alive¶

In 2048 you slide numbered tiles and merge equal ones, and after every move a new tile appears where the game decides. A player that plans for the usual tiles plays well when the tiles are random and badly when they are placed to hurt it. This page shows both kinds of player side by side, in worlds that place the tiles randomly, kindly or hostilely, and a gated player whose one promise (it never gives up guaranteed survival) is proved for every world.

This page is for anyone who wants to see what "probabilistic" and "worst-case" mean on a game they know, and for engineers who want a template for a game with a random environment. It assumes only the rules below; the two ideas it builds on are explained on Seeing the future, assuming the worst, or betting on the odds and Who controls the randomness: worlds.

Try it in your browser

The board below plays this game's recorded example with no download; Play live runs this package itself in your browser, in Pyodide (about 7 MB, downloaded once), and the play page has every setting.

2048 runs here when JavaScript is on; the play page has it too, and the commands below run it in a terminal.

Run it¶

uv run grounded-decision examples games_2048   # the report quoted below
make watch-2048                                # the gated agent on 4 x 4, live
make play-2048                                 # you play (w a s d); the gate checks you
make audit-2048                                # every gated move judged by a deeper search

The command line calls the game 2048; the Python module is games/game_2048.py (a module name cannot start with a digit), with the rules in games/game_2048_rules.py. Tests: tests/test_games_2048.py.

The rules, exactly as implemented¶

Rule	What the code does
Board	4 x 4 by default; `--size WxH` from 2 to 8 cells a side.
Move	Up, down, left or right: every tile slides as far as it can. A move must change the board.
Merge	Two equal tiles that meet become one of twice the value; the new value is added to the score. A tile made by a merge does not merge again in the same move (`2 2 2 2` slid left is `4 4 . .`).
New tile	After every move: a 2 with probability 0.9 or a 4 with probability 0.1, on an empty cell chosen uniformly (in the random world). Two such tiles start the game.
End	When no move is legal. The game counts as won if it made a 2048 tile; play continues after 2048, as in the original. `--target TILE` changes the winning tile (a power of two, at least 4) and `--stop-at-target` ends the game, won, as soon as it appears.

The report checks the merge rule on four rows, and the tests compare the fast implementation with a plain one on 1,600 random boards of four sizes:

Sliding a row to the left (a merged tile does not merge again):
  2 2 2 2  ->  4 4 . .   (+8)
  2 2 4 .  ->  4 4 . .   (+4)
  4 . 4 8  ->  8 8 . .   (+8)
  2 . 2 2  ->  4 2 . .   (+4)

How the tiles are drawn. The tile after move \(k\) is decided by a 64-bit number computed from the seed and \(k\) alone (a SplitMix64 hash), never from the moves played: it picks the \(i\)-th empty cell with \(i = \lfloor h \cdot e / 2^{32} \rfloor\) (\(h\) the high 32 bits, \(e\) the number of empty cells) and a 4 when the low 32 bits are below \(2^{32}/10\). Both are uniform up to an error below \(2^{-32}\). So the same seed gives the same sequence of draws whatever the agent does, and a clairvoyant benchmark can be shown them in advance.

Speed. A board is one integer (five bits per cell), and sliding a row is a table look-up that is computed once per distinct row. A 4 x 4 move takes about 1 to 3 microseconds; the expectimax agent decides in about 3 milliseconds.

Who places the tiles: worlds¶

The agent chooses moves; the world chooses the new tiles (--world MODE):

World	Where the new tile goes
`random`	The standard game, from the seed. The only world whose future is fixed in advance.
`kind`	The cell and value that leave the player the best position after its best reply.
`evil`	A fixed adversary: the cell and value that leave the worst position after the player's best reply. It does not look at the agent.
`adversarial`	Adapts to the actual agent: takes the 6 placements `evil` rates worst, asks a private copy of the agent how it would reply to each, and picks the one where that reply ends worst. A placement that leaves no legal move is always taken.
`MODE:p`	Each tile follows `MODE` with probability `p`, else `random` (for example `evil:0.3`).

"Position" is scored by the same heuristic the search agents use (below). Ties between equally bad (or good) placements are broken by the seed, so every world is reproducible.

The agents¶

From weakest to strongest; play 2048 --list prints this table and --explain AGENT the paragraph behind each line.

Agent	Regime	How it moves
`random`	baseline	A uniformly random legal move.
`greedy`	baseline	The move that merges the most points now.
`corner`	baseline	One move ahead: keeps the big tiles in decreasing order along a snake-shaped path from the bottom-left corner (tiles weighted \(4^k\) along the path).
`expectimax`	probabilistic	Searches two moves ahead (three when at most three cells are empty), averaging over every possible new tile with its true probability.
`minimax`	worst-case	The same search, but every new tile is assumed to be the worst one (cell and value).
`gated`	worst-case	`expectimax` proposes; exact survival checks decide (below).
`clairvoyant`	benchmark	Is shown the next four tile draws and tries every sequence of four moves against them. Defined only in the random world.

The search agents score positions with the row heuristic of Robert Xiao's 2048 AI (nneonneo/2048-ai): bonuses for empty cells and for equal neighbours, penalties for rows and columns that are not monotone and for large tiles, summed over every row and column.

What each regime may claim. minimax's value is a lower bound on the heuristic two moves on, whatever the world does. expectimax's value is an expectation under the random world only; in any other world its notes, compare and audit say "assumption not met". clairvoyant is refused outside the random world, because there the tiles depend on its own moves and there is no fixed future to see:

$ grounded-decision play 2048 --world evil --agents clairvoyant
grounded-decision play: error: the agent clairvoyant is clairvoyant (a benchmark that sees the future), but in the evil world the future depends on the agent's own moves, so there is no fixed future to see; use the random world

The gate: never give up guaranteed survival¶

Call the worst-case survival horizon of a move the largest number of turns \(d\) (up to 3) for which, whatever tiles appear, the player can certainly keep making legal moves after it. The gated agent asks expectimax for a move and checks it:

Check	Passes when
`legal`	The move changes the board.
`survives_any_spawn`	Every possible new tile after the move still leaves a legal move, whenever some legal move achieves that.
`best_survival_horizon`	The move's horizon equals the best horizon of any legal move.

If a check fails, the agent plays a legal move of best horizon, choosing among those by the worst-case search, and the decision says so. The report shows the first override it finds (3 x 3, seed 0):

The gate at work: seed 0, move 35 on a 3 x 3 board
       2      4      8
       8      4      2
      32     16      2
  expectimax proposed down; the gate played up
    [pass] legal: down changes the board
    [pass] survives_any_spawn: down leaves a legal reply after every possible spawn
    [FAIL] best_survival_horizon: down survives 2 turn(s) whatever tiles appear; the best move survives 3 (checked up to 3)
    fallback: up keeps the best worst-case survival horizon (3 of 3 turns) with worst-case value 1,168,188

What is proved. Every move the gated agent plays has the best worst-case survival horizon of any legal move. So in every world, random, kind, evil, adversarial or a mixture: the game never ends at the tile right after a gated move if some move could have survived every possible tile, and if a gated move guarantees \(d \ge 1\) more turns, the next position still has a move guaranteeing \(d - 1\), which the agent will play. Its guaranteed horizon never drops by more than one per turn.

Why it is cheap and exact. A move never reduces the number of empty cells and a new tile fills exactly one; a board with an empty cell and a tile always has a legal move. So a board with at least \(d + 1\) empty cells survives \(d\) turns whatever appears, and the search only has to explore nearly full boards, where there are few tiles to try. The tests compare it with a brute force without that shortcut on hundreds of random positions of 2 x 2, 3 x 2 and 3 x 3 boards.

What is not proved. Scores, game lengths and largest tiles are measured, below. The guarantee is about survival a few turns ahead, not about reaching 2048: the gate gives up expected points to keep its horizon (the audit below prices that).

What happens in each world¶

The report (uv run grounded-decision examples games_2048) plays every agent on 8 seeds of a 3 x 3 board, where games are short. These tables come from the same code on 20 seeds:

uv run grounded-decision compare 2048 --agents random,greedy,corner,expectimax,minimax,gated --size 3x3 --seeds 20 --world random,evil,adversarial

Agent	random: moves	random: score	evil: moves	evil: score	adversarial: moves	adversarial: score
`random`	32.0	193.0	15.7	77.8	12.4	43.2
`greedy`	44.5	311.0	20.8	133.2	14.2	57.0
`corner`	52.0	408.4	15.6	81.6	13.3	51.6
`expectimax`	210.0	2,716.2	34.8	385.2	45.1	529.6
`minimax`	145.9	1,739.8	48.6	634.8	34.5	362.4
`gated`	188.9	2,416.8	60.8	850.6	47.2	563.0

Mean moves and mean score per game; the gate overrode 80, 26 and 22 proposals in the three worlds. With the clairvoyant benchmark in the random world (compare 2048 --agents expectimax,clairvoyant --size 3x3 --seeds 20), seeing the next four tiles takes the mean game from 210.0 to 302.1 moves.

On the standard 4 x 4 board, 10 seeds per agent and world, the largest tile each game ended with:

from grounded_decision.examples.games import game_2048 as g

agents = ("random", "greedy", "corner", "expectimax", "minimax", "gated", "clairvoyant")
for world in ("random", "evil", "adversarial"):
    results = g.measure(agents, world=world, size=(4, 4), seeds=range(10))
    print(*g.distribution_table(results), sep="\n")

Columns: mean moves, mean score, then how many of the 10 games ended with each largest tile (. for none).

World random (4 x 4, seeds 0-9)
  agent          moves    score     32    64   128   256   512  1024  2048  4096  8192 16384
  random         112.1    986.4      2     3     5     .     .     .     .     .     .     .
  greedy         258.6   3109.2      .     .     2     7     1     .     .     .     .     .
  corner         238.3   2886.8      .     .     5     4     1     .     .     .     .     .
  expectimax    2749.7  58446.0      .     .     .     .     .     1     4     4     1     .
  minimax       1474.5  29089.2      .     .     .     .     1     2     5     2     .     .
  gated         2629.8  57661.2      .     .     .     .     1     2     2     3     2     .
  clairvoyant   7873.9 198551.2      .     .     .     .     .     .     .     1     5     4

World evil
  agent          moves    score     16    32    64   128   256   512
  random          51.6    430.4      1     4     4     1     .     .
  greedy          47.8    391.2      1     4     4     1     .     .
  corner          63.8    608.8      .     4     5     1     .     .
  expectimax     110.2   1541.6      .     .     2     5     3     .
  minimax        165.6   2777.6      .     .     1     3     4     2
  gated          131.6   1945.6      .     .     .     5     5     .

World adversarial
  agent          moves    score      8    16    32    64   128   256   512  1024
  random          28.6    134.4      2     5     3     .     .     .     .     .
  greedy          35.5    208.8      .     3     7     .     .     .     .     .
  corner          37.9    245.2      .     2     7     1     .     .     .     .
  expectimax     124.7   1739.6      .     .     .     2     5     3     .     .
  minimax        257.7   4924.4      .     .     .     .     1     4     4     1
  gated          167.0   2751.2      .     .     .     .     5     2     3     .

In the random world the gated agent made 2048 or more in 7 of 10 games (81 overrides in all), expectimax in 9, minimax in 7 and the clairvoyant benchmark in all 10 (it ends the longest games, up to 13,717 moves).

What the numbers say:

In the random world, betting on the odds pays. expectimax beats minimax clearly: assuming the worst tile every time makes it play too cautiously.
Against hostile tiles, the bet collapses. In the evil and the adaptive adversarial worlds on 4 x 4, minimax lasts 1.5 and 2.1 times as long as expectimax (165.6 against 110.2 moves, 257.7 against 124.7) and makes larger tiles. On 3 x 3 the adaptive adversary, which tests each agent's actual reply, hurts minimax more than expectimax: assuming the worst one move ahead is not the same as surviving an opponent that searches against you.
The gate helps most where survival is tight. On 3 x 3 under evil the gated agent lasts longest (60.8 moves against 34.8 for the expectimax it gates); on 4 x 4 it sits between expectimax and minimax. In the random world it gives up a little score for its guarantee.
None of these agents makes 2048 against hostile tiles (the best 4 x 4 game under adversarial ended at 1024). That is measured on these seeds, not proved for every player.

Audit: what the guarantee costs¶

make audit-2048 plays the gated agent on 3 x 3 and judges every decision with a depth-3 expectimax (regret is in the heuristic's points):

== Audit: gated [worst-case] playing player in 2048, seed 0 ==
Line-up: player (gated). Result: no move left: largest tile 128, score 1,288 after 123 moves.
Oracle: expectimax depth 3. Regret unit: expected heuristic points (nneonneo line heuristic) 3 moves ahead.

Decisions audited: 123
  total regret 1.884e+05, mean 1531 per decision
  agreed with the oracle: 112/123 (P(agrees with the oracle) ∈ [0.85, 0.95] (95%, 123 trials))
  gate overrides: 7

Most of the regret comes from the 7 overrides: the deeper search would have taken the higher expected value and accepted a shorter guaranteed horizon. The survival oracle (--oracle survival) measures the other side: by construction the gated agent has zero regret against it.

The audit also prints the regime table: on 3 x 3 with 20 seeds, the chance of making a 256 tile in the random world is 1.00 for the clairvoyant benchmark, 0.80 for expectimax, 0.45 for minimax and 0.70 for the gated agent; under evil, the chance of making 128 is 0.15 for expectimax, 0.45 for minimax and 0.80 for the gated agent, each with an exact 95% interval in the output.

Limits¶

The survival guarantee looks 3 turns ahead (SURVIVAL_HORIZON); a longer horizon is exact too but costs more on full boards.
The adversarial world simulates only the agent's next reply to at most 6 candidate placements, so it is a bounded adversary, not an optimal one.
The heuristic, search depths and every comparison above are measured on few seeds; the intervals in compare and the regime table say how little 10 or 20 games can show.