How AI Solves 2048 - Expectimax Explained
January 22, 2024
The best AI agents for 2048 win over 90% of games - far better than even expert human players. How do they do it? The answer is a technique called expectimax search.
What Is Expectimax?
Expectimax is a variant of minimax search designed for games with randomness. In 2048, after each move a new tile spawns randomly. Minimax assumes an adversary picks the worst possible outcome; expectimax instead computes the expected value over all random outcomes weighted by their probability.
The Search Tree
At each node in the search tree, the AI considers all four possible moves. After each move, it branches on every possible new tile spawn (a 2 in any empty cell, or a 4 in any empty cell). Each spawn branch is weighted by its probability (90% for 2, 10% for 4). The AI recursively evaluates the tree to a certain depth and selects the move with the highest expected heuristic value.
Heuristic Functions
The quality of the heuristic determines how good the AI is. The best heuristics reward:
- More empty cells
- Monotonic rows and columns
- Highest tile in the corner
- Smooth tile values (adjacent tiles close in magnitude)
Watch our 2048 AI Solver to see these principles in action.