Cutting the tour short

Posted on 31 August 2026

Reading time 5 minutes

Comments

golang ai snake

The same tour, jumping ahead on it whenever that can be shown to be safe - and a third fewer moves

The zig-zag tour wins every game and takes twenty-five moves per fruit doing it, because it walks past ninety-nine tiles it does not want to reach the one it does.

Most of that is waste you can prove is waste. The snake is one tile long for the first fruit and the whole tour is empty behind it; there is no reason to walk all of it.

Jumping without leaving the cycle

The trick is to keep the ordering of the cycle and skip tiles on it. The snake never takes a step that is not to a tile further along the tour, so the reasoning that makes a tour safe still holds - it just gets to the fruit sooner.

Take the 6x6 tour again, numbered by position on the cycle:

      x=0   1   2   3   4   5
y=0    35   0   1   2   3   4
y=1    34   9   8   7   6   5
y=2    33  10  11  12  13  14
y=3    32  19  18  17  16  15
y=4    31  20  21  22  23  24
y=5    30  29  28  27  26  25

With the head on tile 0, the plain tour goes to 1. But 9 is directly below the head, and 9 is further along the cycle than 1 - so stepping down there skips eight tiles and loses nothing about the ordering.

if s.shortcuts {
	// A jump of one is the plain next step on the cycle; anything further
	// skips tiles, and the budget is how many of them we can afford to skip.
	furthest := 1
	maxJump := s.cutBudget(st, at)
	legal, n := legalDirections(st)
	for _, dir := range legal[:n] {
		jump := s.distance(at, s.at(tile.Step(*head, dir)))
		if jump > maxJump || jump <= furthest {
			continue
		}
		furthest = jump
		best = dir
	}
}

// distance is how many steps forward along the cycle it is from a to b.
func (s *CycleSolver) distance(a int, b int) int {
	n := len(s.cycle)
	return ((b-a)%n + n) % n
}

What a jump costs

Skipping tiles closes the gap between the head and the tail. The tail is at some position on the cycle ahead of the head; every tile skipped is a tile of that gap spent, and if the gap ever closes completely the head runs into the tail.

So the budget starts as that gap, less the body that still has to fit through it, less a margin.

func (s *CycleSolver) cutBudget(st *state.State, at int) int {
	n := len(s.cycle)
	length := st.SnakeLength()
	empty := n - length - 1
	toTail := s.distance(at, s.at(*st.SnakeTail()))
	toFruit := s.distance(at, s.at(*st.Fruit()))

	budget := toTail - length - 3
	if empty < n/2 {
		budget = 0
	} else if toFruit < toTail {
		// We reach the fruit, and so grow, before we come back round to the tail.
		budget--
		if (toTail-toFruit)*4 > empty {
			// Eating this one leaves the tail uncomfortably close behind.
			budget -= 10
		}
	}

	// Never cut past the fruit. Overshooting it costs another full lap.
	if budget > toFruit {
		budget = toFruit
	}
	if budget < 0 {
		return 0
	}
	return budget
}

Three things fall out of that.

Once the board is more than half full, there are no shortcuts at all. empty < n/2 sets the budget to zero and the player goes back to walking the tour exactly. That is the right shape: shortcuts are free when the board is empty and dangerous when it is not, and this stops trying at the point where the argument stops being comfortable.

Never cut past the fruit. Overshooting it costs another entire lap, which is the whole thing shortcuts exist to avoid.

The margin is bigger than it needs to be. - length - 3, and another - 10 when eating would leave the tail close behind.

Spending the whole gap instead - dropping the body and those constants - wins every game just the same over three hundred of them, and gets there in about a tenth fewer moves. That is a real saving and it is still not worth taking. What this player sells is that it cannot lose; three hundred games is not a proof, and the argument for why it cannot lose is the one written into that margin. A tenth off the moves of a player whose whole point is the guarantee is the wrong thing to buy with it.

How it does

solver        games   wins  stalled  avg score   best  worst  avg moves   per game
zigzag         2000   2000        0       99.0     99     99     2530.7      192us
shortcut       2000   2000        0       99.0     99     99     1661.2      258us

Same two thousand wins, a third fewer moves, for a third more time per game. That trade is worth it: the moves are what you sit and watch, and the microseconds are not.

It is also a good illustration of where the waste actually was. A third gone, and the remaining sixteen hundred moves are mostly the second half of the game - the half where the budget is zero and it is walking the plain tour, because that is the half where the guarantee is doing real work.

Pros

Every game won, a third quicker, and the same one-paragraph argument for why it cannot lose.
The change is about fifteen lines on top of the tour player. Everything expensive - the cycle, the position lookup - was already there.
It degrades in the right direction. When the board fills up it stops taking risks on its own.

Cons

It inherits the tour’s blind spot: it still needs a board with an even side, and it still cannot go anywhere the tour does not.
The margin is guesswork. Well-motivated, deliberately generous guesswork, but nobody has proved those constants are the smallest safe ones.
Sixteen hundred moves for ninety-nine fruit is still sixteen a fruit, against about seven for a player that just walks at it and dies.

Next: the same idea, but searching for a tour instead of laying one out.

Jim Wright