Optimal Algorithm for 2048: An In-Depth Analysis of the Expectimax Approach

Introduction

2048 is a sliding puzzle game played on a 4x4 grid, where players merge tiles with the same number to create a 2048 tile. The game combines deterministic moves and random tile spawns, making it an ideal testbed for artificial intelligence. While basic greedy algorithms often fail in complex scenarios, the Expectimax algorithm offers a superior solution by evaluating all possible moves and tile spawn probabilities. Based on high-scoring Stack Overflow answers and reference articles, this paper systematically analyzes the application of Expectimax in 2048, covering algorithmic principles, implementation optimizations, and performance results.

Expectimax Algorithm

Expectimax is an extension of the Minimax algorithm, designed for games with uncertainty. In 2048, after each player move, a new tile spawns randomly (90% chance of 2, 10% chance of 4), so Expectimax builds a game tree to compute the expected utility of each move. The algorithm alternates between maximization steps (selecting the best move) and expectation steps (calculating weighted averages for random tile spawns). For instance, starting from the current state, it recursively explores possible moves until a depth limit or repeated state is reached. Unlike Minimax, Expectimax does not assume an optimal opponent but handles probabilistic events, enabling higher scores in random environments.

Implementation Details

Efficient implementation is crucial for Expectimax success. A common approach encodes the entire 4x4 board as a 64-bit integer, with each tile represented by 4 bits (a nybble). This representation allows the board state to be passed in a single machine register and enables fast row and column extraction via bit operations. For example, right-shift operations can isolate specific rows, while precomputed 'move effect tables' define how to transform rows or columns (e.g., converting [2,2,4,4] to [0,0,4,8]). Scoring is also handled through lookup tables that store heuristic-based row and column scores. Here is a simplified code example illustrating board initialization and basic moves:

// Example: Board representation as a 64-bit integer
uint64_t board = 0; // Initial board, all tiles empty (0)
// Function: Apply a move (e.g., right)
void move_right(uint64_t &board) {
    // Use precomputed tables to update rows
    // Assume each row is 16 bits, extracted and updated via bit masks
    for (int i = 0; i < 4; i++) {
        uint16_t row = (board >> (i * 16)) & 0xFFFF;
        row = move_table_right[row]; // Precomputed table lookup
        board = (board & ~(0xFFFFULL << (i * 16))) | ((uint64_t)row << (i * 16));
    }
}

This implementation allows the algorithm to evaluate over 10,000,000 game states per second, significantly improving search efficiency. Additionally, transposition tables cache visited states to avoid recomputation, and depth limits (typically 4-8 plies) balance performance and accuracy.

Heuristic Functions

Heuristic functions assess the 'goodness' of board states, guiding the Expectimax search. Initial heuristics rewarded open spaces and large values on edges but showed limited performance. Enhanced heuristics combine multiple factors: monotonicity penalizes non-monotonic rows and columns (ensuring tile values increase or decrease), merge potential counts adjacent equal values, and open space rewards. These heuristics are weighted and combined, with weights optimized via meta-optimization algorithms like CMA-ES. For example, the monotonicity heuristic can be defined as calculating value changes per row and column, applying penalties based on tile size if non-monotonic. Below is a simplified code for a heuristic scoring function:

// Example: Heuristic scoring function
double evaluate_heuristic(uint64_t board) {
    double score = 0.0;
    // Reward open spaces
    int empty_count = count_empty_tiles(board);
    score += empty_weight * empty_count;
    // Penalize non-monotonicity
    for (int i = 0; i < 4; i++) {
        uint16_t row = extract_row(board, i);
        score -= monotonicity_penalty(row);
    }
    // Reward merge potential
    score += merge_potential(board);
    return score;
}

These heuristics drive the algorithm toward board layouts that are easy to merge, such as monotonic structures, increasing the probability of reaching the 16384 tile from 13% to over 90% in tests and enabling frequent appearances of the 32768 tile.

Performance Results

In 100 game tests, the Expectimax algorithm demonstrated exceptional performance: 100% achieved the 2048 tile, 94% the 16384 tile, and 36% the 32768 tile. Scores ranged from 124,024 to 794,076, with a median of 387,222. The average move rate was 5-10 moves per second, with each move taking 10-200 milliseconds at a search depth of 8. Reducing the depth to 6 increased the move rate to over 20 moves per second but potentially sacrificed score. Through efficient state evaluation and heuristic guidance, the algorithm maintained robust performance in complex board positions, outperforming human players and simple strategies.

Conclusion

The Expectimax algorithm provides an effective AI solution for the 2048 game, achieving high scores and stability by integrating probability handling and heuristic optimization. Although not fully optimal, further refinements in heuristics or integration with reinforcement learning could approach the 65536 tile goal. Future work may explore deep reinforcement learning or hybrid algorithms to address the game's randomness and complexity. This analysis offers practical insights for game AI development, encouraging experimentation and code optimization.