Discussing all things around software engineering.
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.
Evaluation, the loop, and making a stochastic algorithm reproducible enough to debug
Every piece is built. This is the loop around them, the parallelism, and the thing that mattered more than any of it: making a stochastic algorithm repeat exactly.
Building the next generation in parallel without making the run depend on which goroutine won
Every species knows how many offspring it is owed. This is the part that produces them - which is where the expensive work is, and where the temptation to parallelise it runs straight into the requirement that a seeded run be reproducible.
Fitness sharing, culling, and four places where an obvious-looking division is wrong
Species exist so that a genome competes mainly against genomes like itself. This is the part that cashes that in: deciding how many offspring each species gets, which members are allowed to produce them, and which species do not get to continue at all.
It is five short functions and I got three of them subtly wrong first.
Measuring how different two genomes are, and why the threshold cannot be a constant
A genome that has just grown a new node is worse than it was. It has an untuned bias, two untuned weights and no idea what the node is for, and in a straight fight with the rest of the population it loses and is gone.
Speciation is the answer: genomes compete mainly against genomes like themselves, so new structure gets a few generations to prove itself.