2048 solver
2048 solver finds the best move in the game 2048, on the standard 4×4 board or a larger 5×5 one. It is a single file of C with no dependencies. Given a board, it prints the expected value of each of the four moves and picks the best.
./solve4 best "0 0 2 2 / 0 4 8 16 / 2 2 32 64 / 4 8 128 256"
Best move: up (depth 6, 3117348 leaves, 242.4 ms)How it works
- Bitboards. Each cell is stored as a 4-bit exponent (1 means 2, 2 means 4, up to 15 for 32768). A 4×4 board fits in one 64-bit integer, and a 5×5 board in a 128-bit one.
- Row tables. Every possible row is computed once at start-up: 65,536 rows for 4×4 and 1,048,576 for 5×5. Each entry stores the result of sliding left and right, the points scored, and a heuristic score. Vertical moves transpose the board, apply the row move and transpose back.
- Expectimax search. The solver alternates two kinds of step:
- your move: it takes the best of the four directions;
- the game's move: it averages over every empty cell receiving a 2 (90% chance) or a 4 (10% chance).
Search depth adapts to how many different tiles are on the board. Unlikely branches (below 0.01%) are cut, a table caches positions already seen, and the four first moves are searched in parallel threads.
- Heuristic. It rewards empty cells and neighbouring equal tiles, and penalises rows that don't rise or fall steadily. The weights come from a well-known open-source 2048 AI by nneonneo, generalised to rows of any length.
A built-in self-test checks the precomputed tables against a straightforward implementation. A JSON output mode makes it easy to drive from other programs, and an index.html provides a page for entering boards.
Limits
The largest tile is 32768, so two of them can't merge. The 5×5 board uses weights tuned for 4×4: they play well but aren't tuned for the larger board.