What the network is paid for

Three terms, in descending order of how much they are allowed to matter, and the trap in each of them

Evolution keeps whatever scores highest, so the fitness function is not a scoring rule - it is the entire specification of the problem. Anything you leave out, you are asking for.

Snake looks like it should be one line: fitness is the score. It is not, and the reasons are more interesting than the fix.

Three terms

func (g Game) Fitness(opts Options) float64 {
	// Everything in terms of the reference board, so that a game on any board
	// is worth the same as an equally good game on any other.
	fruit := opts.FruitReward
	if g.MaxScore > 0 {
		fruit *= float64(ReferenceBoard*ReferenceBoard-1) / float64(g.MaxScore)
	}
	survived := float64(g.Moves)
	if g.Side > 0 {
		survived /= scale(g.Side)
	}
	if opts.SurvivalCap > 0 && survived > float64(opts.SurvivalCap) {
		survived = float64(opts.SurvivalCap)
	}
	return float64(g.Score)*fruit +
		g.Promptness*opts.PromptnessReward +
		survived
}

A fruit is worth 500. Eating without dawdling is worth up to 250 across a whole game. Surviving is worth a point a move, up to 300.

They are in that order deliberately, and the gap between the first and the other two is the point: eating is worth so much more than anything else that nothing can be traded for it.

Why pay for surviving at all

Because a fresh population cannot eat.

Generation one is a hundred and fifty networks with random weights wired straight from the inputs to the outputs. None of them has any idea what the fruit is. If fitness is the score, every one of them scores zero, evolution has nothing to sort on, and the run never starts.

Surviving is the only gradient there is at the beginning. A network that lasts forty moves before hitting a wall is measurably better than one that lasts four, and that is enough of a slope to climb.

Why cap it

Because the moment a network learns to not die, surviving becomes something to farm.

A snake that has learned to go round in a small circle survives forever and eats nothing. Uncapped, that is an infinite fitness score for the worst possible player, and a population that finds it never leaves.

Capped at the idle budget, surviving does its job for the first few dozen generations and then goes flat. You cannot get more of it by circling, because you have already got all of it.

fitness from surviving

  300 |            ,-------------------------
      |          ,'
      |        ,'
      |      ,'
      |    ,'
    0 +--'------------------------------------
      0        300                     moves

Why pay for promptness

This is the term aimed at something I measured rather than guessed.

The networks were taking about fifty-one moves per fruit, where a pathfinder takes eight. They were not circling - they were eating, steadily - they were just weaving towards the fruit instead of going to it.

Score cannot see that. A network that eats twenty fruit briskly and one that wanders to the same twenty score identically, so nothing ever pushed against wandering.

if st.Score() > before {
	// How much of the budget was left when it got there.
	promptness += 1 - float64(idle)/float64(budget)
	idle = 0
	continue
}
idle++

A fruit taken immediately counts 1, one taken at the very end of the patience budget counts 0, and the game’s figure is the average over the fruit it ate. Worth up to half a fruit on the reference board - enough to separate two networks on the same score, never enough to make a slower higher score lose.

A game has to end

A network that has started going in circles never stops on its own, and a training run cannot wait.

budget := max(int(float64(opts.IdleMoveBudget)*scale(side)), 1)
promptness := .0
idle := 0
for idle < budget {
	// ...
}

Three hundred moves without eating and the game is called. On other boards it scales with the side, since the fruit is that much further away on average.

Choosing that number is a real trade. Half of it - 150 - was measured at 84.9 against 91.5, and it makes generations noticeably quicker because games end sooner. Cheaper generations, worse ones.

A fruit is not a fruit

A 20x20 board holds four times as many fruit as a 10x10. If a fruit is worth 500 everywhere, then a genome’s fitness is decided almost entirely by the biggest board it was dealt, and the small boards may as well not have been played.

So the fruit term is scaled: a fruit is worth FruitReward adjusted so that a full board is worth the same everywhere. One fruit comes out at 786 on an 8x8, 500 on a 10x10 and 124 on a 20x20, and a perfect game is worth the same on all three.

The other two terms are not scaled, so what a fruit is worth against them moves a long way with the board. That is deliberate but it is worth knowing about: changing either of the other rewards is worth measuring on the biggest board rather than the reference one.

One game is not evidence

The last piece is not in the fitness function at all. Each genome is scored over twelve games, not one.

Where the fruit lands is luck, and a genome that got easy fruit will outrank one that played better on hard fruit unless they were all dealt the same boards. Twelve against six, over four runs each: 91.5 against 77.5, and the four runs landed within four points of each other instead of within eighteen.

It costs twice the time per generation, so the fair comparison is against spending that time on more generations instead. Six games for twice as many generations reached 84.0, still with the wide spread. Twenty-four games reached 89.4, so it stops paying there.

Of everything in this post, that is the setting that mattered most, and it is not a clever idea - it is just measuring properly.

Pros

• Three terms is few enough to reason about. When a run goes wrong you can usually say which term it is exploiting.
• Capping survival means the obvious degenerate strategy is not worth anything, rather than being merely discouraged.
• The scaling is what lets one run be dealt five different board sizes and one network play all of them.

Cons

• Every one of these numbers is a knob, and most of them were set by running the thing four times and squinting.
• Promptness is a proxy for a proxy. What I actually want is “plays well”; what I can measure is “did not dawdle”.
• The idle budget puts a hard edge on the problem: a network that could have escaped on move 301 is scored as though it never would have. That turns out to matter enormously, and it gets a post of its own.

Next: how a run is actually set up and run.