The tour that always wins

Walk a route that covers every tile and you can never trap yourself. It is perfect, and it is agony to watch

The safe player never dies but stalls in nearly every game, because working move by move it eventually cannot prove any route to the fruit is survivable.

There is a way to win every single game, and it has been sitting there the whole time. Stop deciding, and follow a fixed route that covers every tile on the board.

Why a tour cannot lose

A Hamiltonian cycle is a route that visits every tile exactly once and comes back to where it started. If the snake walks one, its body lies along the cycle behind the head, so the tile in front of the head is always the tile the tail left length ticks ago.

It cannot run into itself, because the only way to reach its own body would be to leave the cycle. It cannot run into a wall, because the cycle does not. And the fruit is always somewhere on the cycle, so it is always eaten eventually.

The snake fills the board, every time, and the game is over because it has been won.

Building one without searching

You can search for a tour - that is the next-but-one post - but on a rectangle you do not have to. Lay the tiles out in boustrophedon order, across and back and across, and reserve the first column as the lane that returns to the start.

// zigZagRows tours columns 1 and up row by row, alternating direction, then
// comes home up column 0.
func zigZagRows(tileNumX int, tileNumY int) Path {
	p := make(Path, 0, tileNumX*tileNumY)
	for y := 0; y < tileNumY; y++ {
		if y%2 == 0 {
			for x := 1; x < tileNumX; x++ {
				p = append(p, tile.Vector{X: x, Y: y})
			}
			continue
		}
		for x := tileNumX - 1; x >= 1; x-- {
			p = append(p, tile.Vector{X: x, Y: y})
		}
	}
	for y := tileNumY - 1; y >= 0; y-- {
		p = append(p, tile.Vector{X: 0, Y: y})
	}
	return p
}

On a 6x6, numbering each tile by where it falls in 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

Tile 35 is next to tile 0, so it closes. Every step is to a neighbour. Every tile appears once.

It does not always exist

func ZigZagCycle(tileNumX int, tileNumY int) (Path, bool) {
	if tileNumX < 2 || tileNumY < 2 {
		return Path{}, false
	}
	if tileNumY%2 == 0 {
		return zigZagRows(tileNumX, tileNumY), true
	}
	if tileNumX%2 == 0 {
		// The same layout rotated a quarter turn.
		rotated := zigZagRows(tileNumY, tileNumX)
		p := make(Path, len(rotated))
		for i, v := range rotated {
			p[i] = tile.Vector{X: v.Y, Y: v.X}
		}
		return p, true
	}
	return Path{}, false
}

The row layout needs an even number of rows so that the last row is travelled leftwards and ends against the return lane. If the rows are odd but the columns are even, the same thing works rotated a quarter turn.

If both sides are odd there is no tour at all, and not because this construction is not clever enough. Colour the board like a chessboard. Every step of a cycle moves to the other colour, so a closed tour alternates, so it needs the same number of each - and a board with two odd sides has one more of one colour than the other. No closed tour can exist on a 9x9, by anybody’s method.

When that happens the player hands the game to safe instead.

Walking it

The cycle is built once, and a flat array records where each tile falls in it, so the solver can ask how far ahead of the head any other tile is.

func (s *CycleSolver) NextMove(st *state.State) direction.Direction {
	if !s.buildCycle(st) {
		if s.fallback == nil {
			s.fallback = NewSafeSolver()
			s.fallback.Init()
		}
		return s.fallback.NextMove(st)
	}

	head := st.SnakeHead()
	at := s.at(*head)
	if at < 0 {
		return mostOpenMove(st)
	}

	step := s.cycle[(at+1)%len(s.cycle)]
	if !space.Passable(st, step) {
		return mostOpenMove(st)
	}
	best := tile.DirToVector(*head, step)
	// ...
}

s.order is the board laid out flat rather than a map. The shortcut player in the next post asks it six times a tick, and hashing a pair of coordinates is a lot of work to reach a number a board-sized slice already has to hand.

The two escape hatches are for the start of the game: the snake spawns on a random tile facing a random way, so for the first move or two it may not be on the cycle at all, or may be pointing so that the next tile on the cycle is behind it. Take any safe move and pick the cycle up next tick.

How it does

solver        games   wins  stalled  avg score   best  worst  avg moves   per game
safe           2000     22     1978       90.8     99     83     9916.6     3.10ms
zigzag         2000   2000        0       99.0     99     99     2530.7      192us

Two thousand games, two thousand wins, best 99, worst 99. And it is sixteen times cheaper per game than safe, because it does not think - it looks up the next tile in an array.

Here is what it costs, though. Two and a half thousand moves for ninety-nine fruit is about twenty-five moves a fruit, on a board where the average distance to a fruit is about seven. It walks a full lap of the board past ninety-nine tiles it does not want in order to reach the one it does, and it does that ninety-nine times.

Pros

• It wins. Every game, on every board with an even side, and you can prove it in a paragraph.
• It is the cheapest interesting player here. No search, no lookahead, one array lookup a tick.
• The guarantee does not degrade. safe gets worse as the board fills; a tour does not care.

Cons

• Twenty-five moves a fruit. It is correct and it is unwatchable.
• It needs an even side, and on a 9x9 it is not a tour player at all.
• It ignores the board completely. The fruit could be one tile in front of the head, and if it is behind on the cycle then the snake takes the long way round.

That last one is a gap you can drive a bus through, and the next post drives one through it.