The reading that is not about the board

A good network does not die any more. It gets stuck - and the fix is one number that has nothing to do with the board

I had a network that scored 94.5 of 99 after thirty-five thousand generations, and it had stopped improving. More generations, bigger populations, more games per genome - nothing.

So I stopped trying to make it better and went to find out what it was actually losing to.

Measuring how games end

cmd/snakebatch says what a player scores. It does not say why it stopped scoring, so there is a second command that does: it replays a network over seeded games under a fixed move limit and reports how each one ended.

games 300 on 10x10 with networks/final.json
  average score 94.53  median 97  worst 1  best 99
  died 0  stalled 201  won 99
  games where the fruit was ever shut off: 298 (99.3%)
  games that ended with it shut off:       181 (60.3%)
  moves spent with it shut off: 338926 of 646921 (52.4%), longest run 94

It never dies. Not once in three hundred games. Everything I had been assuming about the remaining fifteen per cent was wrong.

Sixty per cent of games end with the fruit walled off behind the snake’s own body and the snake circling until the limit calls time. And just over half of every move it plays is made with no route to the fruit at all.

. . # # # # # # # #        the fruit is three tiles from the head
. . # . . . . . . #        as the crow flies, and there is no
. . # . . . . . . #        route to it through the board
. . # # # # # # . #
. . . . . . . # o #
@ # # # # # # # . #

That is not a rare corner. It is what the end of every good game looks like.

Why it never gets out

Here is the part that took me embarrassingly long to see.

A feed-forward network is a function of what it is shown. Everything it is shown is a function of the board. So the network is a function of the board - and the moment a game comes back round to a position it has already been in, with the same tiles of snake, facing the same way, the fruit in the same place, it makes the same move it made last time. And the one after that. Forever.

board A ---> board B ---> board C ---> board D
   ^                                     |
   +-------------------------------------+

nothing inside a function of the board can leave that loop

It is not a learning problem. No amount of training fixes it, because there is no move the network could make that it is not already making.

I had already met this exact bug, in the safe player, which is also a function of the board and also used to lock into loops. That one is fixed by tossing a coin between equally good moves, and it was worth nearly three points a game.

A network has no coin.

Giving it one

// hunger is how long the snake has gone without eating, as a share that starts
// at nothing and closes on one. It is the only thing the network is told that
// is not on the board in front of it, and that is exactly what it is for.
func (s *NeatSolver) hunger(st *state.State) float64 {
	if score := st.Score(); score != s.lastScore {
		s.lastScore, s.idle = score, 0
	}
	// Moves already made since the last fruit, so the move straight after one
	// reads nothing at all. Counted in turns of the whole board, which is what
	// makes it mean the same on any of them: half a turn reads a third, a whole
	// turn a half, and it closes on one from there without ever reaching it.
	x := float64(s.idle) / float64(st.TotalTiles())
	s.idle++
	return x / (1 + x)
}

One reading that cannot repeat. Two moves into a circle are no longer the same move, so the loop cannot close.

Counted in turns of the whole board rather than in moves, so it means the same on a 6x6 as on a 20x20, and shaped so it starts at nothing and closes on one without ever reaching it.

hunger

  1.0 |                          _____________
      |                  ___----
      |           __---
      |      _--
      |   ,-
  0.0 +-'-----------------------------------------
      0     1 board      2 boards     3 boards
              turns since the last fruit

What evolution makes of that is its own business. What it does make of it is a snake that stops doing the thing that is not working.

Does it help?

Twelve runs a side on a 6x6 board, replayed afterwards over three hundred games each under one fixed limit for both, so neither is judged by its own rules:

Nearly five standard errors apart, and the runs are steadier as well as better - the spread across seeds falls from 1.35 to 0.59.

Eight runs a side of 1500 generations on the real board, replayed over two hundred games each:

The average moves four and a half points, which is a lot this near the ceiling. What it really does is finish: a run without it gets into the mid nineties and sticks there, and one with it wins the game.

And end to end, one 1500-generation run - about seven minutes - against the thirty-five-thousand-generation network it replaced:

games 300 on 10x10 with hunger.json
  average score 98.03  median 99  worst 83  best 99
  died 19  stalled 32  won 249
  games where the fruit was ever shut off: 300 (100.0%)
  games that ended with it shut off:       30 (10.0%)
  moves spent with it shut off: 839647 of 1755526 (47.8%), longest run 90

Ninety-nine wins to two hundred and forty-nine, in a twentieth of the generations.

What did not work

Before I thought of hunger I tried the obvious thing four different ways: tell the network the fruit is walled off, and point its fruit readings somewhere more useful while it is.

• Just a flag saying “walled off”: 32.8, against 32.1 for the control.
• Zero the fruit bearing when walled off: 32.5.
• Reverse it, so it steers away from the pocket: 33.0.
• Point the readings at the snake’s own tail instead: 31.6 - actively worse.

Hunger scores 34.2. The best of the four is worth under half of it, and none of them adds anything on top of it.

I also tried changing the training rather than the readings: a separate move budget so that waiting for a pocket to open is not counted as dawdling, which is clearly the right thing to do on principle. No measurable difference either way. And dealing some games from a board already part way through one, so the population is judged on the hard part of the game rather than the ninety easy moves before it: 33.6 against 34.1, and slower.

All of that is out of the codebase. Only hunger is in it.

The rule it breaks

There is a test that says every reading the network is given depends on the board in front of it and nothing else. It exists because the readings go into a buffer the solver reuses, so a reading that stopped being written would go unnoticed - the network would be quietly shown what it saw a move ago.

Hunger deliberately breaks that rule, so it is exempt, and it has tests of its own instead: it starts at nothing, it rises with every move that does not feed the snake, it drops straight back the move after one does, and it is cleared between games.

It is worth being explicit that this is a trade. Sensing is no longer a pure function of the board, and that is a real property to give up. I gave it up for two points on a 6x6 and a hundred and forty extra wins in two hundred games on a 10x10.

Pros

• It fixes the failure mode by construction rather than by learning. The loop cannot close, so no amount of bad luck can reproduce the old behaviour.
• One reading. Eighteen instead of seventeen.
• It is the same fix as the coin toss in safe, arrived at from the same diagnosis, which is a nice sign that the diagnosis was right.

Cons

• It changes the shape of the input, so every network and checkpoint trained before it is refused and has to be retrained.
• It is a counter, not a sense. The network is being told something about itself, which is a category of input I had deliberately kept out.
• It does not fix everything. Thirty-two of three hundred games still stall, and nineteen now die - the network takes more risks with a full board than it used to, and occasionally that is the wrong call.

Next, and last: how any of these numbers can be trusted at all.