How the Snake AI works: breadth-first search, a tail-safety check and a Hamiltonian cycle

The autopilot in AI Snake is not a recording and not a neural network. It is a graph search that runs in your browser on every single move, and you can watch it think: the faint dots on the board are the route it just planned. This post explains the three strategies you can pick from, why the obvious one fails, why the careful one almost succeeds, and why a piece of 19th-century graph theory finishes the job. Every number here comes from a benchmark you can re-run.

The board is a graph

A 20×20 Snake board is a graph with 400 nodes, one per cell, and an edge between each pair of side-by-side cells. The snake's body removes nodes; the apple is a target node. So "which way should the snake turn?" becomes "what is the shortest path from the head to the apple through the free cells?" — a question breadth-first search answers exactly, in time proportional to the number of cells. The engine keeps it plain:

// BFS from the head to a target over free cells; returns the path or null
function bfs(g, from, to, blocked) {
  var prev = {}, seen = {}, q = [from];
  for (var i = 0; i < q.length; i++) {
    for (var d of ['up','down','left','right']) {
      var n = nextCell(g, q[i].x, q[i].y, d);      // null off a walled board
      if (!n || seen[key(n)] || blocked[key(n)]) continue;
      seen[key(n)] = 1; prev[key(n)] = q[i];
      if (n.x === to.x && n.y === to.y) return walkBack(prev, n);
      q.push(n);
    }
  }
  return null;
}

One detail matters more than it looks: when the snake plans, the tip of its tail is not counted as blocked, because by the time the head could arrive there the tail will have moved on. Forgetting that makes the snake refuse perfectly good moves.

Greedy search: right for the next move, wrong for the game

The obvious strategy is to follow that shortest path every time. It is fast — 16 moves per apple in the benchmark — and it is wrong, because it optimises the present and ignores the future. Every apple makes the body one cell longer, and the shortest route to an apple is very often a route into a pocket that the body has just sealed. In 100 games the greedy strategy died every time, at a mean length of 69.7 — about 17% of the board. Its best game reached 110.

Safe search: look before you eat

The fix is to ask a second question before taking the first step: if I follow this whole route and eat the apple, can I still reach my own tail afterwards? The engine answers it literally. It copies the game, plays the planned route forward — growth included — and runs a second BFS from the new head to the new tail.

// virtual walk + tail-reachability check
var v = cloneGame(g);
for (var i = 0; i < path.length; i++) step(v, dirTo(v.snake[0], path[i], v));
if (v.alive && tailReachable(v)) return firstStepOf(path);   // safe to commit
// otherwise: follow the tail along the longest path we can find

Why the tail? Because the tail is the one cell that is guaranteed to become free next move. If the head can reach the tail, the snake can keep circling indefinitely; it can never be boxed in. That single invariant — "always keep a route to your tail" — is the difference between dying and not dying. In 100 games Safe search never died. Its worst game still reached 386 cells; its mean was 395.8, a 99% fill.

When the apple route fails the check, the snake chases its tail — and here a small trick pays off. If it takes the shortest route to the tail it coils up tight and the board stays partitioned. So the engine takes the BFS path and stretches it: wherever two consecutive cells have free neighbours alongside, it replaces the direct step with a three-step detour. Repeating that until nothing can be extended gives a long, meandering route that spreads the body across the board and reopens routes to the apple. That is the "following the tail to open space" line you see under the board.

Where Safe search runs out of proof

Look closely at the benchmark and Safe search has a flaw the deaths hide: it finished only 4 games in 100. In the other 96 it reached the last handful of cells and then circled, for tens of thousands of moves, unable to satisfy its own safety condition. With three or four free cells left, almost no route to the apple leaves a route to the tail afterwards, so the check says "no" forever and the snake orbits. Not dying is not the same as winning. The mean of 198 moves per apple is that orbiting, averaged in.

The Hamiltonian cycle: never trapped, by construction

A Hamiltonian cycle is a closed loop that visits every node of a graph exactly once. If the snake only ever moves forward along such a loop, it can never touch itself, however long it is: every cell ahead of the head is a cell the tail has already vacated, or will vacate before the head arrives. The whole difficulty of Snake dissolves into "follow the loop".

Not every grid has one, but a 20×20 grid does, and it is easy to build. Sweep the rows in alternating directions using columns 1 to 19, and reserve column 0 as the lane back up to the start. Because the height is even, the last sweep ends next to column 0 and the loop closes. (Think of the checkerboard colouring: a cycle must alternate colours, so it needs an even number of cells — 400 is fine.)

// rows snake through columns 1..w-1; column 0 is the return lane (h must be even)
for (y = 0; y < h; y++)
  if (y % 2 === 0) for (x = 1; x < w; x++) order.push({x, y});
  else             for (x = w - 1; x >= 1; x--) order.push({x, y});
for (y = h - 1; y >= 0; y--) order.push({x: 0, y});

The pure cycle is safe but slow: on average the apple is half a loop away, about 200 moves. The engine therefore takes shortcuts, and this is the part with a proof in it. Number the cells along the loop from the head. Since the snake has only ever moved forward along the loop, every body cell has a smaller number than the head — the body lies entirely on the arc behind the head, ending at the tail. So every cell on the arc between the head and the tail is free, and the head may jump to any neighbour whose loop number is ahead of the head but short of the tail. The engine picks the biggest such jump that does not overshoot the apple, keeps one cell of margin for the growth tick, and stops taking shortcuts once the snake fills half the board. Result: 100 of 100 games filled all 400 cells, at 52.5 moves per apple — a quarter of the pure cycle's cost.

The benchmark

The numbers come from scripts/benchmark-snake.mjs, which loads the exact snake-core.js the game ships and self-plays 100 games per strategy on a 20×20 board with seeded apple placement, so the same 100 games are dealt every run. A game ends on death, on filling the board, or at an 80,000-move cap that only the orbiting Safe search ever reaches.

Strategy	Mean length	Board fill	Perfect games	Deaths	Moves per apple
Greedy search	69.7	17.4%	0	100	16.1
Safe search	395.8	99.0%	4	0	198
Hamiltonian cycle	400	100%	100	0	52.5

What this has in common with the other LK Forge games

Snake is the second game here built on breadth-first search — Color Lines uses it to find routes for its marbles — and, like 2048's expectimax solver or Connect 4's negamax, the engine is a plain JavaScript file that runs on your device with nothing sent to a server. The same file that plays the game is the one that ran this benchmark.