Walking straight at the fruit

Posted on 25 August 2026

Reading time 4 minutes

Comments

golang ai snake

The greedy snake: no search, no lookahead, and three and a half times the score

The random player scores six because it does not know where the fruit is. The obvious fix is to tell it: of the moves that do not kill me this tick, take the one that ends up nearest the fruit.

That is the whole of the greedy player. There is no search and no lookahead, and it is worth three and a half times as much as random.

Nearest by what?

Manhattan distance - the number of moves between two tiles on an empty board.

// ManhattanDistance is the number of moves between two vectors on an empty board.
func ManhattanDistance(a Vector, b Vector) int {
	return abs(a.X-b.X) + abs(a.Y-b.Y)
}

On an empty board it is exactly right. On a board with a snake on it, it is a guess that ignores the snake entirely, and that is the whole story of this player.

The whole thing

func (s *GreedySolver) NextMove(st *state.State) direction.Direction {
	options, n := legalDirections(st)
	if n == 0 {
		return direction.None
	}

	head := st.SnakeHead()
	best := options[0]
	bestDistance := -1
	for _, dir := range options[:n] {
		distance := tile.ManhattanDistance(tile.Step(*head, dir), *st.Fruit())
		if bestDistance < 0 || distance < bestDistance {
			bestDistance = distance
			best = dir
		}
	}
	return best
}

legalDirections is doing the only safety work there is: it throws away the moves that would end the game this tick. Everything after it is “which of these gets me closer”.

. . . . o . . .        fruit at (4,0)
. . . . . . . .
. . . 5 . . . .        up    -> 5 away
. . 6 @ 4 . . .        left  -> 6 away
. . . 5 . . . .        right -> 4 away   <- taken
. . . . . . . .        down  -> 5 away

Which is the right move here, and would still be the right move if the whole left half of the board were solid snake, because nothing in this player looks at the snake beyond the three tiles next to its head.

How it does

solver        games   wins  stalled  avg score   best  worst  avg moves   per game
random         2000      0        0        6.4     14      4      803.6      111us
greedy         2000      0        0       22.4     47      6      182.3       42us

Twenty-two of a possible ninety-nine, and it is also the fastest player in the whole series at 42 microseconds a game. It does almost nothing per tick and it does not play for long.

That last part is the interesting bit. Greedy scores three and a half times what random does and its games are four times shorter. Random wanders around not eating for eight hundred moves; greedy goes straight to the fruit, eats it, goes straight to the next one, and after about twenty of them it goes straight into itself.

. . . . . . . . . .
. . # # # # # # . .
. . # . . . . # . .
. . # . o . . # . .
. . # . . . . # . .
. . # # # # @ # . .      the fruit is four tiles away
. . . . . . . . . .      every move that closes the gap is body

There is nothing in the code that could notice that. It compares three numbers and takes the smallest, and when the smallest one leads into a wall of snake, legalDirections refuses it and greedy takes the next-smallest instead - which is usually deeper into the same trap.

Pros

Twelve lines, no allocation, no state between moves. It is the cheapest player here by a factor of three.
It shows how much of the problem is just knowing where the fruit is. Six to twenty-two, for one line of arithmetic.
It is a genuinely useful floor. Anything with a search in it should comfortably beat 22, and if it does not then the search is not earning its keep.

Cons

It has no idea it is building a wall out of itself. That is the entire problem with snake, and greedy is blind to it.
Manhattan distance is a straight line, and the board stops being straight the moment there is a snake on it. The next player fixes exactly that.

Next: stop guessing the distance and search for it.

Jim Wright