Discussing all things around software engineering.
One game, eleven players, and what each of them is worth. From a snake moving at random, through the searches and the tours that never lose, to a neural network that was evolved rather than written.
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.
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.
Population, generations, checkpoints, and why the fittest genome is not the one you keep
The network is shown eighteen numbers and paid for eating. What is left is running the thing: how many networks, for how long, on what boards, and - the part I got wrong first - which one you keep at the end.
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.
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.
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.
Growing a route into a Hamiltonian cycle, and the two small decisions that took it from 65 to winning every game
The zig-zag tour is laid out by hand, which works because a rectangle is easy to walk. The other way to get a tour is to search for one on the board in front of you.
This player is the most fragile thing in the series and the most instructive, because almost all of its score comes from two decisions that have nothing to do with the search.
The same tour, jumping ahead on it whenever that can be shown to be safe - and a third fewer moves
The zig-zag tour wins every game and takes twenty-five moves per fruit doing it, because it walks past ninety-nine tiles it does not want to reach the one it does.
Most of that is waste you can prove is waste. The snake is one tile long for the first fruit and the whole tour is empty behind it; there is no reason to walk all of it.
Walk a route that covers every tile and you can never trap yourself. It is perfect, and it is agony to watch
The safe player never dies but stalls in nearly every game, because working move by move it eventually cannot prove any route to the fruit is survivable.
There is a way to win every single game, and it has been sitting there the whole time. Stop deciding, and follow a fixed route that covers every tile on the board.
A snake that can reach its own tail always has a way out, and that one rule is worth sixty points
Everything so far dies. The search players die at about 28 of 99, and they die because a shortest route and a survivable route are different things.
This one does not die. Not once in two thousand games, and it scores 90.8.