Merge

2048. Slide the whole board one way, tiles of equal value join into one worth double, and a new tile arrives wherever there is room. The run ends when no slide in any direction would change anything.

Open index.html. No build step, no dependencies, no images — the board is drawn.

Draft. It is built, compiled and tested like every other game, and it is not on the hub: "draft": true in build/games.json keeps it off the cards, out of the sitemap and without a readme page. Take the flag off when it is worth playing.

merge/
  index.html      markup, and the restart button
  style.css       the frame around the canvas
  js/board.js     sliding, merging, spawning and the arithmetic
                  - no pixels, no engine, no DOM
  js/merge.js     the playable layer
  test-board.js   node test-board.js

The whole game is one function, and it has two traps in it

slideLine() slides one line towards the end it is travelling to. Both of the mistakes below produce the same symptom — a slide that merges more than it is allowed to — and only one of them is the famous one.

The first trap: a merge must be sealed

A tile made by a merge is finished with for the rest of that slide. Without the seal, 4 4 8 compacts to 8 8, the walk meets the eight it has just made and put next to the other one, and joins them:

4 4 8   ->   16       wrong; no pair of tiles paid for that
4 4 8   ->   8 8      right

The second trap: which pair

4 4 4 slid left is 8 4, not 4 8. The pair nearest the direction of travel merges and the odd tile is left behind. Slid right, the same row is 4 8. An implementation that pairs from the far end of the line is right half the time — a run of two, or of four, comes out the same either way — which is exactly why it survives a suite built on the obvious examples.

Both are handled by reading the line from the end the tiles travel towards, with one index remembering which output cell has already been merged into. lineOf() lists a line's cells in that order for whichever direction was asked for, so there is one copy of the rule rather than four.

4 4 4 4 does not catch the bug it is famous for

This is the thing worth knowing, and it was found by writing the negative control and watching it pass.

Take the cursor implementation and delete the seal. Run the famous example through it:

8 8. Correct. The seal-less version passes 4 4 4 4 cleanly, because after merging it no longer matches the tile it made against the next one — it matches an eight against a four and moves on. 4 4 8 is what catches it, and it is the example nobody quotes.

There is a second wrong implementation that does fail 4 4 4 4: compact, join any adjacent equal pair, repeat until nothing changes. That one gives 16. Two different mistakes, two famous examples, and each example catches one of them. Both are rebuilt in the test file, and both are watched failing.

So the property is exhaustive rather than sampled

A row is four cells. Restrict the values to {empty, 2, 4, 8, 16} and there are 5⁴ = 625 rows, which is small enough to enumerate every single one rather than sample them.

Every one is compared against a second implementation written in a different shape: it compacts to a list and then eats pairs off the front of it, recursively, so a tile it has just made is never handed back to the walk. The seal is structural there rather than a flag — which is the point. The same oversight cannot be present in both.

All 625 rows agree, on the resulting line, on which tiles the merges made, and on whether anything moved at all.

284 of the 625 merge something and 464 move at all, so the comparison is doing work rather than agreeing about nothing — both counts are asserted, because a test where nothing ever happens passes just as quietly.

The three rebuilt mistakes are measured against the same 625, and each is seen disagreeing with the independent implementation: the seal-less one on 33 rows, the far-pair one on 40, the keep-going one on 67.

The properties that do not catch it, which is why the 625 exist

Two of the obvious board-wide invariants are useless against a double merge, and it is worth writing down which:

floor(cells / 2) is the bound that comes to mind and it is too weak to notice anything: a line of four can hold two merges however wrong they are. Counting the tiles that were actually there is the statement with teeth — three tiles cannot produce two merges. The suite asserts both, and only one of them works.

All the sum and count properties are still there. They catch other things, and a property that only ever passes is still worth having when the code changes.

Sliding left twice is not idempotent

The first version of the suite asserted "slide left twice and the second changes nothing", and it failed 363 times before the premise was looked at rather than the code.

4 4 4 4 slid left is 8 8. Slide left again and it is 16. That is the game working: the seal lasts for one slide, not for ever, and a player who lines up four fours does get to press left twice.

What is true, and says the more useful thing, has three parts:

1. one slide leaves every line packed, so a second slide the same way can only merge and never shuffle;
2. each further slide therefore consumes at least one tile, so a line of n cells never needs more than n slides;
3. the state it settles into is genuinely fixed.

All three are asserted, along with the count of boards that needed more than one slide, so the loop cannot quietly become vacuous.

The score can be recomputed from the board

Give every tile a potential of v × (log₂ v − 1) — a 2 is worth nothing, a 4 is worth 4, an 8 is worth 16. Joining two tiles of value v raises the board's total by exactly 2v, which is exactly what that merge pays. Sliding without joining changes nothing. An arriving two is worth nothing; an arriving four is worth four that nobody earned. So at every moment of every run:

score  ==  potential of the board  -  4 per four ever spawned

Twenty-five games are played out at random, from the opening tiles to the last move — all twenty-five reach a board that cannot move, in 2747 moves between them — and the identity is checked after every one of those moves. It never looks at a single merge, which is what makes it a cross-check rather than a restatement.

The rule people forget

A slide that changes nothing must not spawn a tile.

Get it wrong one way and the board fills itself while the player leans on a wall they are already flat against. Get it wrong the other and it never fills at all. Both are lost games rather than bugs a player can describe.

The first board written for this test was completely full, which made it useless — an implementation that spawns regardless has nowhere to put the tile and looks innocent. The board that shows the harm has ten free cells and still cannot go left, because every row is already packed against that wall with no equal pair in it. Ten free cells before, ten after.

Alongside it, over two and a half thousand random boards: a step that reports it did not move must change nothing at all — not the cells, not the score, not the move count — and a step that reports it did must bring exactly one tile, never two and never none. A full board can only move by merging, so there is always somewhere for it to go.

Game over, asked twice

The rules answer "is there a move left" with a cheap scan: an empty cell, or two orthogonal neighbours of equal value. The test asks it the expensive way, by actually trying all four slides with its own independent implementation, and the two have to agree on four thousand boards — more than a thousand of them completely full, because a board with gaps in it always has a move and proves nothing.

The board that matters is the 2/4 chequerboard:

2 4 2 4
4 2 4 2
2 4 2 4
4 2 4 2

No space, no equal orthogonal neighbours, and every diagonal neighbour matches. This game is over, and a check that glances at the diagonals says it is not.

What the tests are worth

Eleven mutants, run by the test file itself rather than by hand. Each is the shipped js/board.js evaluated in its own scope with one function replaced — the real file with one thing changed, not a hand-copied imitation of it — and each is put through the whole suite of 108 assertions. The number beside each is how many of them noticed.

The spawn-regardless mutant was caught by only three assertions until the ten-free-cells board was added; it is six now, and three of those are the ones that describe the actual harm.

$ node test-board.js
110 passed, 0 failed

Playing it

Swipe, or the arrow keys, or WASD. The whole canvas is the control on a phone: a flick shorter than the threshold is treated as a tap and handed to the shell, so the menu and the pause card still work. R starts over, Escape or P pauses.

Making 2048 does not end the run — the last screen says so instead of "game over", and the board is still there to keep playing.

Still to do

• [ ] a favicon of its own; the palette is the shell's violet for now
• [ ] take "draft": true off the entry in build/games.json