Introduction

In 2014 a 19-year-old, Gabriele Cirulli, threw together 2048 in a weekend and watched it eat the internet. The rules fit on a napkin: swipe a 4ร—4 grid up, down, left or right; equal tiles that collide merge into their sum; every move spawns a new 2 or 4. Slide 2 into 2 to make 4, two 4s into 8, and keep climbing toward the famous 2048 tile โ€” and beyond.

Most people play on autopilot, chasing whatever merge looks tempting. But each swipe is really a decision: which direction sets up the most future merges, keeps your big tiles cornered, and avoids jamming the board into a dead end?

That gap between the move that feels good and the move that is best is not just a matter of skill. It is the same gap that separates problems a computer can solve quickly from the ones we believe it never can.

Greedy Bot vs Best Play

Here is a tiny 2048 board with a fixed, deterministic sequence of incoming tiles (so the only thing that matters is which way you swipe). Use the arrow buttons to play it yourself and watch your score โ€” the sum of every merge you make.

<p class="hint">A tiny 3ร—3 game of 2048 with a <b>fixed</b> stream of incoming tiles, so the only thing that matters is which way you swipe. Equal tiles that collide merge into their sum; your score is the total of every merge. You have <b>8</b> swipes.</p>
<div id="board" class="board"></div>
<div class="score">Score: <b id="score">0</b> &nbsp;ยท&nbsp; Moves left: <b id="left">8</b></div>
<div class="pad">
  <button class="arrow" data-dir="2" type="button">โ†‘</button>
  <div class="row">
    <button class="arrow" data-dir="0" type="button">โ†</button>
    <button class="arrow" data-dir="3" type="button">โ†“</button>
    <button class="arrow" data-dir="1" type="button">โ†’</button>
  </div>
</div>
<div class="status" id="status">Swipe to play, or let a bot try.</div>
<div class="btns">
  <button id="greedy" type="button">Greedy bot</button>
  <button id="best" type="button">Best (search)</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.board { display: grid; grid-template-columns: repeat(3, 56px); gap: 6px; margin: .4rem 0;
         background: #bbada0; padding: 6px; border-radius: 10px; width: max-content; }
.cell { width: 56px; height: 56px; display: flex; align-items: center; justify-content: center;
        font: 700 22px ui-monospace, monospace; border-radius: 6px; background: #cdc1b4; color: #776e65; }
.cell.v0 { background: #cdc1b4; color: transparent; }
.cell.v2 { background: #eee4da; } .cell.v4 { background: #ede0c8; }
.cell.v8 { background: #f2b179; color: #fff; } .cell.v16 { background: #f59563; color: #fff; }
.cell.v32 { background: #f67c5f; color: #fff; } .cell.v64 { background: #f65e3b; color: #fff; }
.cell.v128, .cell.v256, .cell.v512 { background: #edcf72; color: #fff; font-size: 18px; }
.score { font-size: 1rem; margin: .5rem 0; }
.pad { margin: .5rem 0; }
.pad .row { display: flex; gap: .35rem; margin-top: .35rem; }
.arrow { font: 700 18px system-ui; width: 48px; height: 40px; border: 1px solid #8f7a66;
         background: #8f7a66; color: #fff; border-radius: 8px; cursor: pointer; }
.arrow:disabled { opacity: .4; cursor: default; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; } .status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button#greedy, button#best, button#reset { font: 600 14px system-ui; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Tiny deterministic 2048. The board lasts exactly MOVES swipes; after each swipe the next fixed stream tile spawns. Score = sum of all merges.
// Greedy picks the biggest immediate merge; Best exhaustively searches every swipe sequence โ€” the optimum is strictly higher, which is the whole point: playing 2048 optimally is NP-hard (Abdelkader, Acharya & Dasler, 2015).
const ROWS = 3, COLS = 3, MOVES = 8;
const START = [ {r:0,c:0,v:2}, {r:0,c:1,v:2} ];
const STREAM = [
  {r:2,c:2,v:2}, {r:2,c:0,v:2}, {r:0,c:2,v:4},
  {r:1,c:1,v:2}, {r:2,c:1,v:2}, {r:0,c:0,v:2},
  {r:1,c:2,v:2}, {r:2,c:2,v:4}
];
const empty = () => Array.from({length:ROWS},()=>Array(COLS).fill(0));
const clone = b => b.map(r=>r.slice());
function start(){ const b=empty(); for(const s of START) b[s.r][s.c]=s.v; return b; }

function slideLine(line){
  const n=line.length, xs=line.filter(v=>v), out=[]; let gain=0;
  for(let i=0;i<xs.length;i++){
    if(i+1<xs.length && xs[i]===xs[i+1]){ const m=xs[i]*2; out.push(m); gain+=m; i++; }
    else out.push(xs[i]);
  }
  while(out.length<n) out.push(0);
  const moved = out.some((v,i)=>v!==line[i]);
  return {line:out, gain, moved};
}
// dir: 0=left, 1=right, 2=up, 3=down
function move(board, dir){
  let b=clone(board), gain=0, moved=false;
  if(dir<2){ for(let r=0;r<ROWS;r++){ let l=b[r].slice(); if(dir===1)l.reverse();
      const res=slideLine(l); let nl=res.line; if(dir===1)nl.reverse(); b[r]=nl; gain+=res.gain; if(res.moved)moved=true; } }
  else { for(let c=0;c<COLS;c++){ let l=[]; for(let r=0;r<ROWS;r++)l.push(b[r][c]); if(dir===3)l.reverse();
      const res=slideLine(l); let nl=res.line; if(dir===3)nl.reverse(); for(let r=0;r<ROWS;r++)b[r][c]=nl[r]; gain+=res.gain; if(res.moved)moved=true; } }
  return {board:b, gain, moved};
}
function spawn(board, idx){
  if(idx>=STREAM.length) return board; const s=STREAM[idx]; const b=clone(board);
  if(b[s.r][s.c]===0){ b[s.r][s.c]=s.v; return b; }
  for(let r=0;r<ROWS;r++)for(let c=0;c<COLS;c++) if(b[r][c]===0){ b[r][c]=s.v; return b; }
  return b;
}

// โ”€โ”€ interactive state โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
let board, score, idx;
function reset(){ board=start(); score=0; idx=0; render(); setStatus('Swipe to play, or let a bot try.',''); }
function render(){
  const el=document.getElementById('board'); el.innerHTML='';
  for(let r=0;r<ROWS;r++)for(let c=0;c<COLS;c++){
    const d=document.createElement('div'); const v=board[r][c];
    d.className='cell v'+v; d.textContent=v||''; el.appendChild(d);
  }
  document.getElementById('score').textContent=score;
  document.getElementById('left').textContent=Math.max(0, MOVES-idx);
  const over = idx>=MOVES;
  document.querySelectorAll('.arrow').forEach(b=>b.disabled=over);
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
function playerMove(dir){
  if(idx>=MOVES) return;
  const m=move(board,dir);
  if(!m.moved){ setStatus('That swipe changes nothing โ€” try another direction.','bad'); return; }
  board=m.board; score+=m.gain; board=spawn(board, idx); idx++; render();
  if(idx>=MOVES) setStatus(fmt('Game over. You scored %score%. The best possible is 48.', { score: score }), score>=48?'ok':'bad');
  else setStatus('','');
}

// โ”€โ”€ bots โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function greedyScore(){
  let b=start(), sc=0;
  for(let i=0;i<MOVES;i++){
    let best=-1,bg=-1;
    for(let d=0;d<4;d++){ const m=move(b,d); if(m.moved && m.gain>bg){ bg=m.gain; best=d; } }
    if(best<0) break;
    const m=move(b,best); b=m.board; sc+=m.gain; b=spawn(b,i);
  }
  return sc;
}
function bestScore(){
  let best=0;
  (function dfs(b,sc,i){
    if(sc>best) best=sc;
    if(i>=MOVES) return;
    for(let d=0;d<4;d++){ const m=move(b,d); if(!m.moved) continue; dfs(spawn(m.board,i), sc+m.gain, i+1); }
  })(start(),0,0);
  return best;
}

document.querySelectorAll('.arrow').forEach(btn=>
  btn.addEventListener('click',()=>playerMove(Number(btn.dataset.dir))));
document.getElementById('greedy').addEventListener('click',()=>{
  const s=greedyScore();
  setStatus(fmt('Greedy bot grabs the biggest merge each turn โ†’ score %s%. (Best is %bestScore%.)', { s: s, bestScore: bestScore() }),'bad');
  console.log('greedy', s);
});
document.getElementById('best').addEventListener('click',()=>{
  const s=bestScore();
  setStatus(fmt('Exhaustive search of every swipe sequence โ†’ best score %s% (vs greedy %greedyScore%).', { s: s, greedyScore: greedyScore() }),'ok');
  console.log('best', s);
});
document.getElementById('reset').addEventListener('click',reset);
reset();
Result
Console

Then press the two bots. Greedy picks, on each turn, the swipe that merges the most right now. Best searches every sequence of swipes to the end and reports the highest score reachable. Notice the asymmetry: the greedy bot is instant but often leaves points on the table, while the optimal answer costs an exhaustive search that explodes as the board and tile stream grow.

The Real Complexity

How hard is 2048, really? Not the swiping โ€” the deciding.

  • Checking a finished game is trivial: replay the swipes and add up the merges to confirm a claimed score.
  • Greedy is fast but myopic: grabbing the biggest merge now can wreck your board three moves later.
  • Brute force tries every sequence of swipes. With up to four choices per move and games hundreds of moves long, that is roughly 4n4^{n} paths โ€” hopeless beyond a handful of steps.
  • It's NP-hard. In 2015, Ahmed Abdelkader, Aditya Acharya and Philip Dasler proved that for a generalized 2048 โ€” even a deterministic version where you are told the whole stream of incoming tiles โ€” deciding whether you can reach a target tile (or beat a target score) is NP-hard. They did it by encoding a known hard problem directly into a starting board and tile sequence.
  • So even the yes/no question "can this value ever appear?" is hard โ€” let alone the optimization question "what's the best I can do?".

That is the punchline: the moment you ask for the best line of play rather than a good enough one, 2048 stops being a casual game and becomes a genuine instance of the same wall behind P vs NP. The status is settled: optimal 2048 is proven NP-hard, not merely suspected.

Where It Matters

"Pick a sequence of moves that maximizes a reward, when each move reshapes everything that follows" is one of the deepest shapes a real problem can take, and 2048 is its friendly face:

  • Planning and logistics: routing trucks, packing warehouses and sequencing factory jobs are all "find the move order that pays off most" โ€” and usually NP-hard.
  • Reinforcement learning: 2048 is a classic testbed for agents that must learn to favor long-term board structure over short-term greed, exactly the trap our greedy bot falls into.
  • Heuristics over optimality: because finding the best play is intractable, real systems lean on smart approximations (keep the big tile in a corner; build a monotone gradient) โ€” the same compromise self-driving and game AIs make.
  • Teaching complexity: everyone has swiped 2048, so it is a vivid on-ramp to why "good enough fast" beats "optimal but never".

Learn why optimal 2048 is hard and you've met sequential decision-making under combinatorial explosion โ€” the same engine behind scheduling and countless planning problems.

Conclusion

2048 hides a beautiful secret: the same swipes that taught you to corner your biggest tile can encode a known hard problem, so that even asking can this tile ever appear? is NP-hard. Checking a finished game stays instant; finding the best way to play is as hard as anything in computer science.

So the next time the greedy move betrays you and the board locks up, take comfort โ€” you haven't played badly. You've simply run into P vs NP hiding behind a pile of glossy tiles, and there may be no shortcut to the perfect game at all.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/2048/Content licensed under CC BY-NC 4.0.