What the network sees

Eighteen numbers, why each one is there, and the reading bug that was worth more than any of them

The board is a hundred tiles and a network takes a fixed number of floats, so something has to decide what to throw away. That decision is called the encoding, and on this problem it mattered more than anything I did to the algorithm.

Eighteen numbers go in each move.

var NeatInputNames = []string{
	"wall L", "wall A", "wall R", "wall AL", "wall AR",
	"room L", "room A", "room R",
	"tail L", "tail A", "tail R",
	"path L", "path A", "path R",
	"food A", "food X", "near",
	"hunger",
}

L, A and R are the three moves - bear left, ahead, bear right - and AL and AR the two forward diagonals. Everything is in the snake’s own frame, for the reasons in the last post.

Five lines of sight

How near the first wall or piece of snake is, along five lines.

      AL     A     AR
        \    |    /
         \   |   /
    L ---- ( @ ) ---- R
             |
           (neck)

The three the snake can move in, and the two forward diagonals. The ones behind are left out because what is behind a snake is mostly its own neck.

The diagonals matter more than they look. A trap closes diagonally, and a snake that can only see along the lines it can move in walks into pockets whose mouth it could have seen.

// nearestObstacle is how many steps away the first wall or piece of snake is
// along a line from the head. The line is walked on the board's bordered mask,
// from the head's index in it and by a fixed step of the index, so the border
// ends every line and nothing has to check an edge.
func nearestObstacle(open []state.Cell, at int, step int) int {
	if step == 0 {
		return 0
	}
	for steps := 1; ; steps++ {
		at += step
		if open[at] == state.Wall {
			return steps
		}
	}
}

The reading the network is given is one over that. Something right beside the head reads 1 and something at the far edge reads near zero, which is the way round a reactive controller wants it - a plain distance is weakest precisely when a thing is close enough to matter.

Room, and whether the tail is in it

This is the reading that cannot be got by looking in a straight line, and it is what separates a gap the snake can get out of from one it cannot: how many tiles are reachable after each move, as a share of the board.

Alongside it, whether the snake’s own tail is in that same space. Room says how big the pocket is; this says whether it is a pocket at all.

. . . . . . . .        moving left  -> a space of 3, no tail in it
. # # # # # # .        moving up    -> a space of 34, tail in it
. # . . . . # .
. . @ # # # # .        the small space is a grave; the big one
. # # . . . . .        empties as the tail advances through it
. . . . . . t .

A space with the tail in it empties as the tail advances through it, so it is never really a dead end however small it looks - and a larger space without the tail in it can still be one.

On the evidence “tail in reach” is worth having but not proven: six runs each came out at 40.5 against 37.9, which is one standard error. Not a difference you could bank.

The route the board actually allows

From the same fill: how far the fruit is from each move by the shortest route the board allows - or nothing, if the move leads somewhere the fruit is not.

This is the one that is proven, and the last addition that earned its place. The bearing below says which way the fruit lies as the crow flies, and a snake steering by that alone walks into whatever of its own body lies between. Over four runs each it took the score from 41 to 46, and nothing else tried that round came out ahead of not having it.

All three of those - room, tail, route - come from one survey of the board rather than a flood fill per move.

// Survey answers, for every tile at once, the questions Free, Saw and Distance
// answer for one: how big the space a tile is in, whether two tiles are in the
// same space, and how far a tile is from target by the shortest passable route.
func (sc *Scratch) Survey(st *state.State, target tile.Vector) {

One breadth-first pass out from the fruit labels the fruit’s region and measures the route to everywhere in it; any other region is only labelled the first time something asks about it. In the usual case - the fruit and all three moves in one space - the board is walked once, where the three fills this replaced walked it three times, and they were seven tenths of a whole training run.

Where the fruit is

Two numbers for the direction and one for the distance, rather than one signed distance.

away := tile.Vector{X: fruit.X - head.X, Y: fruit.Y - head.Y}
forward := float64(away.X*ahead.X + away.Y*ahead.Y)
across := float64(away.X*right.X + away.Y*right.Y)
reach := math.Abs(forward) + math.Abs(across)
if reach > 0 {
	forward, across = forward/reach, across/reach
}

The direction is scaled so the pair always adds up to one, which keeps it at full strength whether the fruit is next to the head or across the board. A signed distance carries both at once and does neither well: it fades towards nothing exactly as the snake closes in, which is when steering matters most, and the snake ends up weaving past fruit it is aiming at.

That was worth about three quarters of the wasted movement - 51 moves per fruit before, 12 to 16 after, against 8 for a player that simply walks the shortest path.

Distances are read as a share of the board

// nearness turns a distance to the fruit into a reading that means the same
// on any board: one over one plus the distance as a share of the board's side.
func nearness(distance float64, st *state.State) float64 {
	side, _ := st.Dimensions()
	return 1 / (1 + distance*10/float64(side))
}

A distance in tiles is not the same thing on a 20x20 as on a 10x10 - the fruit is twice as far away on average - so a network trained on the small board meets readings on the big one it never saw at home. Trained on 10x10 alone, two networks in four locked into circles from the first fruit on a 20x20. Read as a share of the board, and trained across sizes, none did.

The wall readings stay in tiles, because a wall one step away is one step away on any board.

The bug that beat every reading

None of the above is the biggest thing that ever happened to this player.

A move into a wall has no room, and the flood fill for it stopped short - leaving the tail and fruit readings for that move holding whatever the previous move’s fill had found. The network was being told, some of the time, that the wall it was about to hit had its tail and its fruit behind it.

With that fixed, the same settings went from 46 to the high fifties in a fifth of the generations, and began winning whole games.

It is worth knowing about because it did not look like a bug from the outside. The scores were respectable and the trend was upward, just slowly - which is exactly what a network learning around a corrupted input looks like. There is now a test that checks every reading against a plain, independent definition of what it is supposed to mean, over a hundred and fifty thousand positions.

Fewer, not more

The obvious thing to do with an encoding is add to it. It is nearly always wrong.

Which way the tail lies, whether the fruit is in reach at all, the two diagonals behind, the snake’s length, and combinations of those - all measured, all level with or behind the smaller set. Every reading added is another row of weights for evolution to get right, and past a point it costs more than it tells.

The measurement that made that concrete: two inputs wired in and left permanently reading zero, doing nothing whatsoever, cost half a point of score by themselves.

Pros

• Eighteen numbers is small enough that a fresh genome has a real chance of stumbling on something useful, which is how NEAT gets started at all.
• Everything expensive comes from one pass over the board.
• Because it is all relative - the head’s frame, distances as a share of the board - one network plays every board size.

Cons

• It is a lot of decisions to get right, and one of them being subtly wrong cost more than all the others being right.
• The flood fill behind nine of the eighteen is about half of what a training run costs.
• It is still my choice of what matters. The network is free to learn any rule it likes, out of the things I decided to show it.

Next: what it gets paid for.