Eleven ways to play snake

A series on writing snake players in GO, from random moves to an evolved neural network

I wanted a problem small enough to hold in my head and awkward enough to stay interesting. Snake is that. The rules fit in a sentence, and playing it well turns out to be a problem about not building a wall out of yourself.

So I wrote a snake, and then I wrote eleven different ways of playing it. This series is one post per player, starting with the one that moves at random and ending on a neural network that was evolved rather than written.

The code is at github.com/jmwri/go-snake-ai.

The game

A board of tiles, a snake, and a fruit. The snake moves one tile a tick and cannot stop or turn back on itself. Eating the fruit makes it one tile longer and puts another fruit down somewhere random. Running into a wall or into itself ends the game.

. . . . . . . . . .
. . . . . . . . . .
. . . . o . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . @ # # # . . .
. . . . . . # . . .
. . . . . . # . . .
. . . . . . . . . .
. . . . . . . . . .

@ head   # body   o fruit

On a 10x10 board there are 100 tiles, the snake starts one tile long, and the highest possible score is 99 - the snake filling the board.

A player is one function

Everything in this series implements the same interface.

package solver

type Solver interface {
	Name() string
	NextMove(s *state.State) direction.Direction
	Init()
}

NextMove is handed the board and returns one of Up, Right, Down or Left. That is the whole contract. There is no separate “is this legal” step and no supervisor - whatever the solver returns is what the snake does, and if that is into a wall then the game is over.

Init is called before each game, so a solver that keeps anything between moves can throw the last game’s away.

The board itself is a state.State. The parts a solver cares about:

func (s *State) SnakeHead() *tile.Vector
func (s *State) SnakeTail() *tile.Vector
func (s *State) Segment(i int) tile.Vector
func (s *State) SnakeLength() int
func (s *State) Fruit() *tile.Vector
func (s *State) Tile(x int, y int) tile.Type
func (s *State) Dimensions() (int, int)
func (s *State) Clone() *State

Clone is the interesting one. It hands back a copy of the board that can be played forward without touching the real game, which is how the smarter solvers try a move - or a whole route - before committing to it.

Watching one play

go run ./cmd/snake -size 10 -solver shortcut

That opens on a menu where you pick the player, the board and the speed, and , and . wind the pace up and down during a game.

Measuring them

Watching is no way to tell two of them apart, so there is a second command that plays batches with no window at all, a game per core.

go run ./cmd/snakebatch -solver all -size 10 -batchSize 2000

Two thousand games each on a 10x10 board:

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
shortest       2000      0        0       28.2     51      8      228.1      423us
astar          2000      0        0       28.5     52      6      229.5      485us
longest        2000      0        0       19.1     44      4     1495.6      449us
safe           2000     22     1978       90.8     99     83     9916.6     3.10ms
hamiltonian    2000   2000        0       99.0     99     99     2520.1      242us
zigzag         2000   2000        0       99.0     99     99     2530.7      192us
shortcut       2000   2000        0       99.0     99     99     1661.2      258us
neat           2000   1643      185       97.8     99      1     5783.8     4.24ms

Stalled means the snake was still alive when the move limit called time. A solver that neither dies nor wins would otherwise hold the batch up forever.

Two thousand games rather than two hundred, because the averages still move by a few tenths over two hundred and every figure in this series is quoted to one.

There is a lot in that table, and most of the series is spent explaining one row at a time. The short version: chasing the fruit sensibly gets you to about 28 of 99, refusing to die gets you to 90, and only the players that commit to a tour of the whole board win reliably. The evolved one - which was told none of this - wins four games in five.

The posts

I will update this list with links as I write them.

1. Introduction
2. Playing at random
3. Walking straight at the fruit
4. The shortest path
5. The same path, less searching
6. Taking the longest way round
7. Never dying
8. The tour that always wins
9. Cutting the tour short
10. Searching for a tour
11. Evolving a player
12. What the network sees
13. What the network is paid for
14. Running a training run
15. The reading that is not about the board
16. Telling whether a change helped