Evolving a snake player

Nobody tells this one how to play. It is a neural network that was evolved rather than written

Every player so far is my idea of how to play snake, written down. The greedy one is “go towards the fruit”. The safe one is “keep your tail in sight”. They are as good as the rule I thought of.

The last player in this series was given no rule at all. It is a small neural network, and its weights and its shape were arrived at by evolution: a population of near-empty networks, the ones that happen to play better kept and mutated, over and over.

NEAT, briefly

The algorithm is NeuroEvolution of Augmenting Topologies - NEAT - from Kenneth Stanley’s original paper. What makes it different from most neural network training is that it evolves the structure as well as the weights. A run starts with every input wired straight to every output and nothing in between, and hidden nodes and connections appear one at a time as they earn their place.

I have my own implementation of it in GO, neatgo, and a separate series about writing it. This series does not repeat that. Here I only care about the four things you have to decide to point it at a problem:

1. What the network is shown.
2. What it is paid for.
3. How a run is set up.
4. How you tell whether a change helped.

Those are the next four posts, and every one of them turned out to matter more than anything I did to the algorithm itself.

The player

func (s *NeatSolver) NextMove(st *state.State) direction.Direction {
	s.sense(st)
	if err := s.net.Step(s.memory, s.inputs, s.outputs); err != nil {
		return direction.None
	}

	best := 0
	for i, output := range s.outputs {
		if output > s.outputs[best] {
			best = i
		}
	}
	return s.moves[best]
}

Read the board into eighteen numbers, push them through the network, take whichever of the three answers came out strongest. Nothing overrules it - there is no safety check on top, and if the network picks a wall then the snake hits the wall. Everything it does is whatever training left in the weights.

Three outputs, not four

// turns lists the three moves available from a heading, in the order the
// network answers in: bear left, straight on, bear right.
func turns(facing direction.Direction) [NeatOutputs]direction.Direction {
	return [NeatOutputs]direction.Direction{
		direction.TurnLeft(facing),
		facing,
		direction.TurnRight(facing),
	}
}

The network does not answer in the board’s frame - up, right, down, left - it answers in the snake’s own: bear left, carry straight on, bear right.

That is the single decision that helped most, and it is not a clever one. In the board’s frame, “the fruit is to my left, turn left” and “the fruit is above me, turn up” are two different rules that have to be discovered separately, and there are four of them for every situation. In the head’s frame there is one rule and it works whichever way the snake happens to be pointing.

board frame                       head frame

    the same situation,            one rule, four times over
    four times over:

    o . .    . . o    . . .        facing anywhere:
    . @ .    . @ .    . @ .            . o .
    . . .    . . .    o . .            . @ .
                                       . . .
                                   "the fruit is ahead-left"

It also removes reversing as something the network can even attempt, because none of the three moves is backwards. That is a whole class of mistake that no longer has a way to happen.

Getting it wrong is a real cost: working in the board’s frame instead of the head’s was the difference between scoring 17 and scoring 32, back when both were terrible.

What 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
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

Ninety-eight of ninety-nine, and it wins four games in five.

It is beaten only by the three players that walk a tour of the entire board, and those win by refusing to play - they commit to a fixed route before the game starts and never look at it again. Every player that actually looks at the board and decides is behind this one, including the one I am most pleased with.

Nobody told it any of this. It was not told that the tail moves out of the way, or that a pocket smaller than the snake is a grave, or that it should go towards the fruit. It was shown eighteen numbers and paid for eating.

The worst 1 in that row is the honest bit. It is a network, not a proof, and one game in two thousand it does something silly in the first few moves. The tour players cannot do that, and that is what a guarantee is worth.

Pros

• It is the best player here that plays the board rather than ignoring it, by seven points.
• I did not have to think of the rule. When it beat my hand-written best I had no idea what it had learned, and I still only half do.
• It generalises. This one is trained across board sizes and plays a 20x20 it has never seen at 392 of 399.

Cons

• It has to be trained before it can play at all, and a run that gets near this takes minutes to hours.
• There is no guarantee anywhere in it. It does not win every game and it never will.
• When it goes wrong you cannot read the code to find out why. You have to measure it, which is a post of its own.

Next: the eighteen numbers.