Lucian (LKB)

Syndicated from my blog. Canonical: https://lkforge.com/blog/game-ai-three-algorithms/

I built six small browser games — 2048, tic-tac-toe, sudoku, and a few others — and gave each a real AI opponent or solver. No libraries, no WASM, no server calls. Three textbook search algorithms cover all of them:

  • Minimax with alpha-beta pruning — perfect play for adversarial, fully-observable games (tic-tac-toe).
  • Expectimax — the same idea, but averaging over chance nodes instead of assuming a rational opponent. This is what drives the 2048 solver, because tile spawns are random.
  • BFS pathfinding — for the games that are really shortest-path problems in disguise.

The 2048 solver, concretely

2048 isn't adversarial — there's no opponent, just a 90/10 random 2-or-4 spawn after each move. So minimax is the wrong tool; you want expectimax, which alternates max nodes (your move) with chance nodes (the random spawn), weighting each outcome by probability.

The heuristic is what actually matters. Mine rewards three things:

  1. A corner-snake gradient — a weight matrix that pins the largest tile in one corner and wants values to descend in a boustrophedon "snake" from there.
  2. Empty cells — heavily weighted, because running out of space is how you lose.
  3. Smoothness — adjacent tiles close in log2 value, so merges stay available.

Search depth adapts to how full the board is (deeper when there's more empty space to reason about), and chance nodes sample a bounded number of empty cells so branching stays tractable.

The honest part: I measured it instead of claiming it

It's easy to write "unbeatable AI" in a README. I ran a headless self-play harness instead — thousands of games, logged outcomes — and published the real numbers, including the unflattering ones (a depth-capped tic-tac-toe search can still drop a game; the 2048 solver reaches the 2048 tile ~70% of the time, 4096 ~30%, and never 8192 in my runs). The full benchmark write-up and the reproducible harness are linked from the canonical post.

Why vanilla JS

Zero dependencies means the whole thing ships as a static file, runs entirely in the visitor's browser, loads instantly, and never phones home. For small games that's not a constraint — it's the right call.

Full post, charts, and the "run it yourself" harness: https://lkforge.com/blog/game-ai-three-algorithms/

You can also play the 2048 solver (Hint names the best move; Auto-Play runs the whole strategy live): https://lkforge.com/games/2048/