Playing snake at random

The simplest player there is, and the baseline everything else is measured against

The first player I wrote does not know where the fruit is. It looks one tile ahead, throws away the moves that would kill it this tick, and picks from whatever is left at random.

That sounds like a waste of a post, but it is the number every other player is measured against, and it turns out to be worth understanding why it scores what it does.

The whole thing

package solver

func NewRandomSolver() *RandomSolver {
	return &RandomSolver{}
}

type RandomSolver struct {
}

func (s *RandomSolver) Name() string {
	return "random"
}

func (s *RandomSolver) Init() {
}

func (s *RandomSolver) NextMove(st *state.State) direction.Direction {
	return anyLegalDirection(st)
}

All of the work is in anyLegalDirection, which several other players use too.

// legalDirections returns every move the snake may take this tick: forward or
// to either side, onto a tile that is neither wall nor body.
func legalDirections(st *state.State) (dirs [3]direction.Direction, n int) {
	head := *st.SnakeHead()
	backwards := direction.Opposite(st.SnakeDir())
	for _, dir := range direction.All {
		if dir == backwards {
			continue
		}
		if !space.Passable(st, tile.Step(head, dir)) {
			continue
		}
		dirs[n] = dir
		n++
	}
	return dirs, n
}

// anyLegalDirection picks at random from the moves that don't kill the snake
// this tick, and gives up if there are none.
func anyLegalDirection(st *state.State) direction.Direction {
	options, n := legalDirections(st)
	if n == 0 {
		return direction.None
	}
	return options[rand.Intn(n)]
}

There are at most three moves, so they come back in a fixed array with a count rather than a slice that would have to be allocated. This runs on every tick of every game of every batch and it is nice not to make the garbage collector part of the experiment.

        ^ up
        |
left <- @ -> right
        |
      (neck)

Three moves, never four. A snake cannot turn back on itself.

The tail is not a wall

There is one rule in Passable that is easy to get wrong.

// Passable reports whether the snake can move through v. The tail counts as
// passable because it vacates its tile on the same tick the head arrives.
func Passable(st *state.State, v tile.Vector) bool {
	if !st.ValidPosition(v.X, v.Y) {
		return false
	}
	if st.Open()[(v.Y+1)*st.Stride()+v.X+1] == state.Open {
		return true
	}
	tail := st.SnakeTail()
	return v == *tail && *tail != *st.SnakeHead()
}

The snake moves as a whole: the head goes onto a new tile and the tail comes off its old one in the same tick. So the tile the tail is standing on right now is free by the time the head gets there, and refusing to move into it costs the snake a legal move on a board where legal moves are the scarce thing.

The one exception is a snake of a single tile, where the head is the tail and there is nothing to vacate.

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

Six of a possible ninety-nine, and it never once won or stalled - every game ended with the snake running into something.

The number that surprised me is 803 moves. It survives for a long time. On a nearly empty board almost every move is legal, so a random choice is rarely fatal, and the snake stays short because it hardly ever finds the fruit. It is a snake wandering around a big room, and it is only when it has blundered into eight or nine fruit that the room starts having walls in it.

That is the whole shape of the problem in one row: staying alive is easy while you are short, and the thing that makes you long is the thing that makes staying alive hard.

Pros

• It is nine lines. There is nothing to get wrong.
• It never stalls. A random player cannot lock into a loop, which is a problem that turns up later in this series in players far cleverer than this one.
• It is a real baseline. Any player that cannot beat 6.4 is doing something worse than nothing.

Cons

• It cannot see the fruit, so every point it scores is an accident.
• It cannot see more than one tile ahead, so it walks into pockets it cannot get out of and then dies in them.

Next: give it the one thing it is missing, and tell it where the fruit is.