A greedy snake dies in the same shape every time. The head takes the shortest route to the food, the body follows into the cells the head has just left, and sooner or later the snake is coiled into a pocket whose only exit is blocked by its own tail. Eating makes this worse rather than better, because every apple is another cell that can never be used as an escape route again.
Play long enough and something strange happens to the board. A skilled player near the end of a full grid is not steering any more. The body already lies along a single closed loop that passes through every free cell exactly once, and the only legal move left is the next cell along that loop. The shape has a name: a Hamiltonian cycle of the grid graph.
Seeing it is easy. Building it on 1990s mobile hardware was not. John Tapsell wrote up his Nokia 6110 Snake bot in May 2015, and the post opens with the constraints rather than the algorithm: an 8 MHz processor, about a kilobyte of RAM, and no heap allocation at all, so every structure has to live on the stack. Conventional pathfinding was out. He needed a route that could be stored in a few dozen bytes and evaluated in constant time.
Why a closed loop cannot collide with its own body
Model the board as a graph: one vertex per cell, one edge between cells that share a side. A Hamiltonian cycle is a closed walk that lands on every vertex exactly once. If the snake's segments sit on consecutive vertices of that cycle, in order, then the body is always one contiguous arc of the loop and the head can only ever move into the vertex immediately after the arc. It cannot reach any other part of itself, because the cycle has no other edges. The snake is immortal by construction.
The catch is that the cycle has to exist, and on a surprising number of boards it does not. Colour the grid like a chessboard. Every move changes the colour of the square under the head, so any closed walk alternates colours and must cover an equal number of light and dark cells. A 9×9 board has 81 cells, which is odd, and the two colours therefore cannot be equal. No Hamiltonian cycle exists on it at all. Tapsell's generator has the same hole in it: an odd width paired with an odd height produces nothing to follow.
Changing the default arena from 9×9 to 10×10 is the difference between a bot that can exist and one that cannot, and it is invisible in a screenshot.
Growing the cycle out of a half-size maze
Finding a Hamiltonian cycle directly is its own search problem, so Tapsell does not look for one. He generates a random maze over a grid of half the width and half the height, using Prim's algorithm, then walks that maze always taking a left turn when one is available. Every step of the walk is doubled, and the doubled path closes into a cycle that covers the full board exactly once. The maze is a spanning tree, so it has no loops to get lost in, and the left-hand rule guarantees the walk never revisits a node.
The memory cost of all this is where the technique earns its place. A 30×30 board holds 900 cells and produces a 15×15 maze of 225 nodes. Each node needs three bits in Tapsell's structure — a visited flag, a wall to the right, a wall below — so the whole maze fits in roughly 85 bytes. That is arithmetic on his description rather than a measurement of the compiled binary, but the order of magnitude is the point: the map costs less than a screen coordinate.
The maze is regenerated at random every run, which keeps the bot from replaying a memorised route. It also means a run cannot be reproduced later unless the generator is seeded, which is the same argument that applies to every other random choice a game makes — a seed for the maze turns an unrepeatable run into a test case.
Flattening the loop into one integer
Write the cycle out as a list of cells and give each cell its position in that list. The snake is then a contiguous run of indices from tail to head, and the only question that matters at each step is how much of the loop lies between the head and the tail. Subtract the two indices, wrapping at the length of the list, and that is the answer — one subtraction, constant time, no path search.
Because the head can turn three ways instead of one, it can step onto a cell further along the list than the next entry. That jump is the perturbation in Tapsell's "perturbated hamiltonian cycle", and it has to clear three tests before the bot will take it: it must not overtake the tail, it must not jump past uneaten food, and it must leave enough slack for the length the snake is about to gain. Tapsell chose the crudest search that satisfies those tests — look at the four neighbours and take the largest legal jump — rather than a shortest-path search, and he switches shortcuts off entirely once the snake fills half the board. The greedy version is not optimal. It is fast, and it looks right.
What the shortcuts are worth in steps
The benchmark in twanvl/snake plays each agent on a 30×30 board a hundred times and counts the steps needed to fill it. It is the clearest evidence I have that the cycle matters more than its shape.
| Agent | Rule | Mean steps | Std dev | Lost |
|---|---|---|---|---|
| zig-zag | fixed zig-zag cycle, no shortcuts | 202530 | 4653 | 0.0% |
| fixed | fixed random cycle | 202490 | 4418 | 0.0% |
| zig-zag-cut | same cycle, shortcuts allowed | 105040 | 3150 | 0.0% |
| phc | perturbed Hamiltonian cycle | 103497 | 2198 | 0.0% |
| dhcr | cycle repair along the shortest path | 60690 | 2571 | 3.0% |
The first two rows are the same bot following two completely different cycles, and they finish 40 steps apart across a quarter of a million. The shape of the loop is irrelevant; that it is a loop is the entire result. Adding shortcuts then removes 97000 steps, a 48% cut, at no cost in games lost.
The last row is the interesting one. Repairing the cycle along a shortest path gets the count down to 60690, which is 40% better than the greedy shortcut version, and it drops 3% of games doing it. That is the trade in one line: every further step of efficiency is bought from the guarantee, and the guarantee was the reason to do any of this.
A bot that never loses is a bot nobody should watch
The cycle guarantees the score. On a 30×30 board the bot finishes with a snake 900 cells long, every time, and 103497 steps is roughly 115 laps of the board to get there. There is no run it can lose and no decision it can get wrong, because the safe move is always known in constant time. As a solver it is perfect. As a game it is a wall.
This is why Neon Snake does not use one. The difficulty in a Snake that people keep playing has to come from somewhere other than the routing, and the two levers available are speed and board geometry — the tick rate, the walls, the size of the arena — which is a difficulty curve set by the designer rather than one the player discovers. A perfect route removes the discovery, and discovery is the part that takes a player ten minutes to notice and a month to master.
What the cycle is good for is testing. Run the bot against a new Snake engine and every divergence is a bug in the engine, not in the strategy. That, and nothing else, is what the 85 bytes buy.
Pros
- Legality of a move is one subtraction of two cycle indices, so the bot's cost per tick does not grow with the length of the snake.
- The maze that generates the cycle costs about 85 bytes at 30×30, which is what makes the approach possible inside a kilobyte.
- Shortcuts cut the steps needed to fill a board by 48% in the published benchmark, with no measured loss rate at all.
- The route can be recomputed from a cell's coordinates rather than stored, so the whole cycle costs no memory.
Cons
- A board with an odd cell count has no such cycle, so the default 9×9 arena cannot be solved this way at all.
- Every game ends with the same score, so the bot measures nothing about difficulty and cannot be used to tune one.
- The greedy shortcut search is not the shortest route to the food, and the versions that are cost 3% of games in the benchmark.
- A full 30×30 game takes 103497 steps, which is a very long wait to watch a result that was never in doubt.
Sources
- Nokia 6110 Part 3 — Algorithms — Tapsell's own write-up, the source for the half-size maze, the 8 MHz and one-kilobyte constraints, and the three conditions a shortcut must pass.
- twanvl/snake — the agent set and the 30×30, 100-run benchmark table quoted above, reproducible with the command in its README.
- taaha-khan/snake-game-algorithm — an independent port that rebuilds the cycle from a Prim's-algorithm maze and credits Tapsell with the shortcut method.