Telling whether a change helped

Run-to-run noise, a board small enough to measure on, and three ways I fooled myself

Every number in the last five posts is a comparison, and comparisons on an evolutionary algorithm are much harder than they look. This post is about the experimental setup, which took me longer to get right than any of the code it was measuring.

The noise is enormous

Four runs of identical settings on different seeds finished at 72, 86, 84 and 68.

A spread of eighteen points, on a scale where the whole difference between a good idea and a bad one is often two. If you run a change once and it comes out ahead, you have learned nothing at all. I know this because I spent a fortnight believing things that were seeds.

On the small board I ended up measuring on, twelve runs of one setting have a standard deviation of about one point of thirty-five. That is a standard error of 0.29, so only differences above about 0.8 are worth believing, and twelve runs a side is roughly the minimum that gets you there.

A board small enough to experiment on

The thing I actually wanted to measure - the end of a game - only happens when a network is good, and a network is only good after a long run. On a 10x10 that is 1500 generations for 91 of 99, a couple of minutes each, and 34,845 for the 94.5 the old network reached.

Twelve runs a side of that is hours per experiment, which means about two experiments a day, which means you never find anything out.

A 6x6 board is the same problem a fifth of the size. Eight hundred generations of it takes twelve seconds and comes out at 33 of a possible 35 - the same share of the ceiling the long run reaches on the big board - and it loses what it loses the same way: not by dying, but by walling the fruit off and circling.

Twelve runs a side is four minutes. That is what made the last post possible; every one of the five ideas in it was measured this way, and four of the five were rejected.

Finding a proxy that is honestly the same problem is, I think, the single most useful thing I did on this project.

Trap one: judged by its own rules

The average a run prints at the end comes from replaying its leading candidates over three hundred games - under that run’s own settings.

So if the change you are testing is one that affects when a game ends, the two runs are not being judged by the same rule, and part of any difference you see is just one of them being allowed to play for longer. I spent a while pleased with a change that turned out to be mostly this.

The fix is to stop using the number the run prints. Replay every saved network afterwards under one fixed protocol - no patience budget, just the move limit the batch command plays to - so that a network trained under any settings is judged the same way as any other.

ctrl:   32.83 31.11 31.74 33.90 33.45 32.60 28.97 32.45 ... | mean 32.118 sd 1.350 | ended shut 33.6%
hunger: 34.34 33.41 34.32 33.16 34.67 34.74 34.72 33.58 ... | mean 34.182 sd 0.604 | ended shut 16.5%

Trap two: an unused input is not free

I wanted to test four different ways of handling a walled-off fruit, three of which needed an extra input. So I compared them against the run before they existed - which had one fewer input.

Two inputs wired in and left permanently reading zero, doing nothing at all, cost half a point of score by themselves. A genome starts with every input wired to every output, so a dead input is real weights that mutation has to spend its time on.

Half a point is most of the effect size I was looking for. A new reading has to be compared against a control carrying the same number of inputs, not against the code before it existed.

Trap three: benchmarking on a busy machine

Two small optimisations to the sensing code - reading a division out of a table, and answering three questions about a tile in one lookup rather than three - looked like they were worth ten per cent.

Then they looked like they were worth minus ten per cent.

A training run from an earlier experiment was still finishing in the background. Both measurements were garbage, and they were garbage in a way that looked exactly like a real result: tight distributions, consistent across repeats within a single run of the benchmark.

The honest measurement is the two versions run alternately in one command, on an idle machine, several rounds:

fast r2 BenchmarkNextMove/open   459.8      slow r2 BenchmarkNextMove/open   466.8
fast r2 BenchmarkNextMove/coiled 373.4      slow r2 BenchmarkNextMove/coiled 381.8
fast r3 BenchmarkNextMove/open   457.1      slow r3 BenchmarkNextMove/open   464.7
fast r3 BenchmarkNextMove/coiled 374.9      slow r3 BenchmarkNextMove/coiled 394.1

A few per cent. Real, worth keeping, and nothing like ten.

The thing that must not change

Performance work on the sensing code has a second problem: it must not change what the network sees, or the comparison is meaningless and every saved network quietly starts playing differently.

The obvious way to remove a division is to multiply by a cached reciprocal. It cannot be used here: a reciprocal is not exact unless the board is a power of two tiles, so it disagrees with the division on ten of the hundred and one room readings a 10x10 board can give. Those are the numbers a network was trained on and decides by.

A table holds what the division itself gives, to the last bit - and there is a test that asserts exactly that, with no tolerance at all:

// A tolerance would not do here. The readings go into networks that were
// trained on these exact numbers, and a table that was a single unit in the
// last place out would quietly change what every saved network does.
for n := range s.share {
	if want := float64(n) / float64(st.TotalTiles()); s.share[n] != want {
		t.Fatalf("share[%d] is %v, dividing gives %v", n, s.share[n], want)
	}
}

The other half of that is an end-to-end check. A seeded run is exactly repeatable, so one is kept as an oracle, and any change meant to be purely about speed has to reproduce it character for character:

generation  100 | fitness  18450.7 | best ever  22594.2 | best score  44.17 | best game 66 | nodes  21 | links  54 | species 11

a new network wins: average score 35.99 over 300 games, best 56

If that line moves, the change was not what I thought it was.

What I would tell myself at the start

• Run everything at least twelve times before believing any of it.
• Find the smallest version of the problem that fails the same way, and do all your thinking there.
• Judge every candidate by the same rule, decided before the experiment.
• Compare against a control that differs in exactly one thing, including the things that seem too small to matter.
• Check what the machine is doing before you time anything.
• Keep one seeded run as an oracle, so “I did not change the behaviour” is a fact rather than an intention.

None of that is about snake, or about NEAT. It is just that an algorithm with this much variance in it will happily tell you whatever you want to hear, and the only defence is deciding what counts as evidence before you look.

The whole series

That is the lot: eleven players, from six points of ninety-nine to ninety-eight. The three that win every game do it by refusing to look at the board, the best one that looks at the board was not written by me, and the single biggest improvement to it in thirty-five thousand generations was one number that is not about the board at all.

All of the code is at github.com/jmwri/go-snake-ai, and the NEAT implementation it is built on is neatgo, which has a series of its own.