Automatic 2048-Solving Algorithm: From Human Strategy to Expectimax AI

1. Understanding the core nature of the 2048 problem

A quick summary of the 2048 rules:

• A 4×4 grid board.
• Each turn:
  • The player chooses one of four directions: up, down, left, right.
  • Tiles slide as far as possible in that direction, and tiles of the same value merge: 2+2, 4+4, 8+8, …
  • The system spawns a new tile: 90% chance of a 2, 10% chance of a 4, placed at a random empty cell.
• You lose when no valid moves remain.
• The usual goal is to reach the 2048 tile or higher.

From an algorithmic viewpoint:

• The player is an agent.
• Each move is an action from the set {Up, Right, Down, Left}.
• The generation of the random 2/4 tile is the environment (a stochastic process).
• The goal is to find a strategy (policy) that:
  • Maximizes the score, or
  • Maximizes the probability of reaching the highest tile (2048, 4096, …), or
  • Maximizes the expected largest tile on the board.

This is essentially a search problem in a stochastic state space. Expectimax is the suitable algorithm, instead of traditional minimax.

2. Basic strategies used by skilled human players

Before introducing complex AI, it’s essential to understand how an experienced human player typically approaches the game. These principles will later be translated into the bot’s evaluation function:

• Keep the highest tile in one fixed corner (usually bottom-left or bottom-right).
• Prioritize two main directions (e.g. left + down) and only use the other two when necessary.
• Avoid creating “zigzag” rows/columns where large tiles get stuck between small ones.
• Prefer states with many empty cells to reduce the risk of deadlock.

These principles will later become concrete components of the evaluation function.

3. Modeling 2048 as a search tree

To apply a search algorithm, we model a 2048 game as a state tree with two types of nodes:

• Player nodes (player turn):
  • Input: current board state.
  • Output: choose one of the four valid directions.
• Chance nodes (environment turn):
  • Handles tile spawning:
    • Select an empty cell.
    • Insert a 2 with probability 0.9 or a 4 with probability 0.1.

If we used minimax, the environment would be treated as a hostile adversary, which is incorrect. In 2048, the environment is purely random. Thus, expectimax is the proper model, where chance nodes compute weighted expected values.

4. Expectimax algorithm for 2048

The idea behind expectimax:

• Limit the search depth (typically 4–6 layers).
• At a player node:
  • Enumerate all valid moves.
  • Evaluate the resulting states.
  • Choose the move with the highest score.
• At a chance node:
  • Enumerate empty cells and both tile possibilities (2 or 4).
  • Compute the weighted expectation using probabilities 0.9 and 0.1.

A simplified pseudocode version (JavaScript-style):

function expectimax(board, depth, isPlayerTurn) {
    if (depth === 0 || isGameOver(board)) {
        return evaluate(board); // Evaluate board state
    }

    if (isPlayerTurn) {
        let best = -Infinity;
        const moves = [UP, RIGHT, DOWN, LEFT];

        for (const move of moves) {
            const newBoard = applyMove(board, move);
            if (!boardsEqual(newBoard, board)) {
                const value = expectimax(newBoard, depth - 1, false);
                if (value > best) {
                    best = value;
                }
            }
        }

        return best;
    } else {
        // Chance node: spawn 2 or 4 in empty cells
        const emptyCells = getEmptyCells(board);
        if (emptyCells.length === 0) {
            return evaluate(board);
        }

        const p2 = 0.9;
        const p4 = 0.1;
        let expectedValue = 0;

        for (const [r, c] of emptyCells) {
            const board2 = cloneBoard(board);
            board2[r][c] = 2;
            expectedValue += (p2 / emptyCells.length) *
                expectimax(board2, depth - 1, true);

            const board4 = cloneBoard(board);
            board4[r][c] = 4;
            expectedValue += (p4 / emptyCells.length) *
                expectimax(board4, depth - 1, true);
        }

        return expectedValue;
    }
}

Selecting the best move:

function chooseBestMove(board, searchDepth) {
    let bestMove = null;
    let bestValue = -Infinity;
    const moves = [UP, RIGHT, DOWN, LEFT];

    for (const move of moves) {
        const newBoard = applyMove(board, move);
        if (boardsEqual(newBoard, board)) {
            continue;
        }

        const value = expectimax(newBoard, searchDepth, false);
        if (value > bestValue) {
            bestValue = value;
            bestMove = move;
        }
    }

    return bestMove;
}

This is only the algorithmic skeleton.
The most important part for a strong bot is the evaluate(board) function.

5. Designing the evaluation function

The evaluation function maps a board state to a numeric value. The higher the score, the “better” the board. Typical approach: combine multiple features linearly:

score(board) =
    w_empty   * emptyCells(board)
  + w_mono    * monotonicity(board)
  + w_smooth  * smoothness(board)
  + w_corner  * maxTileCorner(board)
  + w_merge   * potentialMerges(board)
  + ...

Weights w_* may be tuned manually or optimized automatically.

5.1. Empty cells

The more empty cells, the lower the chance of deadlock.

function countEmptyCells(board) {
    let count = 0;
    for (const row of board) {
        for (const cell of row) {
            if (cell === 0) {
                count++;
            }
        }
    }
    return count;
}

5.2. Monotonicity

Good boards often have rows/columns increasing or decreasing smoothly:

1024 512 256 128
 64   32  16   8

This rewards smooth directional ordering and penalizes zigzag patterns.

5.3. Smoothness

Smoothness measures how similar adjacent tiles are. Tiles close in value are easier to merge later. Typically computed using log2 differences.

5.4. Largest tile in corner

Reward if the maximum tile is located in one of the four corners:

function getMaxTile(board) {
    let max = 0;
    for (const row of board) {
        for (const cell of row) {
            if (cell > max) max = cell;
        }
    }
    return max;
}

function maxTileCorner(board) {
    const maxTile = getMaxTile(board);
    const corners = [
        board[0][0],
        board[0][3],
        board[3][0],
        board[3][3],
    ];
    return corners.includes(maxTile) ? 1 : 0;
}

5.5. Potential merges

Count the number of adjacent equal-value pairs. More potential merges → higher future growth.

6. Balancing search depth vs performance

The 2048 search tree grows extremely quickly:

• Each player node: up to 4 moves.
• Each chance node: up to 16 empty cells × 2 tile types = 32 outcomes.

If the search is too deep, it becomes too slow for browsers.
Common optimizations:

• Limit depth: usually 4–6 layers.
• Prune chance nodes:
  • Examine only a subset of empty cells.
  • Avoid cells that break the corner structure.
• Optimize board representation:
  • Use bitboards (high-performance implementations).
  • Precompute row/column shift results.

7. 2048 AI auto-play demo

Below is a small demo: a mini 2048 board running directly in the browser with a simple expectimax bot. The “Auto-play” button lets the bot play automatically with a small delay per move so you can observe the process. The game stops when a 2048 tile is reached or when no valid moves remain.

8. Conclusion

2048 is a classic example of how a seemingly simple game can become an interesting AI problem. An expectimax algorithm combined with a well-designed evaluation function can yield a bot that plays extremely well, often outperforming regular players by a large margin.

By translating human game experience (corner strategy, maximizing empty cells, maintaining monotonic structure, smart merges) into quantitative features, we can build a 2048 bot that is both effective and extensible.