Keeping the Winners
Selection from scored cards
The arena hands back sixty-four cards in population order and stops. Genome 43 is at the top with 179.4530 grams, half the generation is at 4.8405 grams or below, and twenty-six of the sixty-four ate nothing while the plate ran. A parent is chosen by drawing a fixed count of genomes at random and keeping the best of the ones drawn.
That count is the whole of the selection pressure, and it is one whole number anybody can turn. Exactly one genome in the population is exempt from the procedure: the best card of the generation crosses as itself, once, so the run cannot lose its current answer by bad luck.
The cards alone decide nothing. If every scored genome has the same chance to breed, the arena measured without selecting. If only the top card breeds, one lucky accident can erase the rest of the population before another useful accident appears.
A tournament of four sits between those failures. It can miss the champion, which keeps variety alive, but a high card beats a low card whenever the two appear in the same draw.
The page runs two hundred generations, then turns mutation all the way up as a failure case. The good run keeps better cards without pretending the best one is the only living animal; the bad run proves selection cannot rescue a stream of ruined children.
Four-genome tournament
Here is the whole procedure for one place in the next generation. Draw four genomes out of the sixty-four at random, with no regard for their scores. Look at the four cards. Keep the genome with the highest number on it and copy that one. Throw the other three away and do it again for the next place.
Be clear about how little that reads. It does not sort the board. It does not add the scores up, divide by the total, or care in the slightest what units the score is in. All it ever asks is whether one number is bigger than another, which means the selection pressure it applies at generation 200, where the best of the board is 1143.0000 grams and the average 1052.9949, is exactly the pressure it applied at generation 0, where the best was 179.4530, the average 24.5807, and twenty-six of the sixty-four were tied at nothing. A rule that divided by the total score would have been savage in the first generation and nearly blind in the last one, without anybody changing a line.
The other property is the one the page is named for. Four is arbitrary. Two is a gentler rule, sixteen is a harder one, and one is no rule at all: a tournament of one never looks at a score, so it hands back whichever genome the stream named. Nothing else in the procedure changes when that number does.
// internal/gene/pick.go
// StreamPick is the stream every choice of a parent draws from, and the
// third and last stream this volume's arena spends. The opening
// generation comes off 15, the trials off 21, the mutations off 16, and
// who gets to make a copy comes off here. It is its own stream for the
// reason all the others are: a run that changes how hard it selects
// must not change which genomes it started from or which four trials it
// measured them on.
const StreamPick = 18
// Rule is how a scored generation becomes the next one: how many
// genomes enter a tournament, how many of the best are carried through
// without being copied at all, and how wrong the copies are allowed to
// be.
type Rule struct {
Size int
Elite int
Rates Rates
}
// Tournament draws Size contestants and hands back the one of them with
// the highest score.
//
// One number a contestant, always, and the number is mapped onto the
// population by index: a draw evenly over 0 to 1 multiplied by the
// count of genomes and cut down to a whole number. There is no
// rejection anywhere in here and there is no second draw.
//
// A tie goes to the contestant drawn first.
func (r Rule) Tournament(on []float64, s *rand.Rand, into []int) int {
won := -1
for i := 0; i < r.Size; i++ {
who := int(s.Float64() * float64(len(on)))
if into != nil && i < len(into) {
into[i] = who
}
if won < 0 || on[who] > on[won] {
won = who
}
}
return won
}
Two lines of that are the previous page's discipline arriving at the other end of a
birth. The draw is s.Float64() scaled and floored, and not
s.IntN(len(on)), which is the call anybody would reach for first. Mapping a
whole sixty-four-bit number evenly onto a range that may not divide it cannot be done
without throwing something away, so IntN rejects the numbers that would
land unevenly and asks the generator for another one. The chance of that happening is
small for these bounds, but it is not zero. This bench fixes draw counts so that
changing a tournament setting does not also shift later draws. Seeded
IntN with deterministic call order still reproduces; variable draw
counts do not make it nondeterministic. A multiply and a floor keep one draw here,
accepting the finite-sampling bias instead of rejection's variable consumption.
The tie rule is not a corner case here either. Twenty-six genomes of the opening generation score exactly 0.0000, so a tournament of four has about one chance in thirty-seven of drawing four of them, and something has to say who wins a contest between four animals that all did nothing. Saying it in the code is the difference between a run that replays and a run that depends on how a comparison happened to be written.
Sixty-four tournaments over the board the last page left behind, printed with the first eight of them opened up.
$ go run ./cmd/pick -mode round
pick: one generation of 64 scored on grams eaten, tournaments of 4
the board the tournaments read
the best of them 179.4530
the middle one 4.8405
the average 24.5807
genomes that scored nothing whatever 26
how far apart the genomes are 0.2858
the first eight tournaments of the sixty-four
slot the genomes drawn, and what each of them scored won
0 38 0.0000 46 140.0000 30 0.0000 51 0.0000 46
1 20 0.0000 11 0.0000 1 0.0000 47 0.4357 47
2 50 0.0000 23 0.0000 7 0.0000 10 1.2740 10
3 34 4.8405 45 40.0000 26 0.0000 61 100.0000 61
4 61 100.0000 13 20.0000 38 0.0000 28 0.2160 61
5 58 0.0000 61 100.0000 40 20.0000 35 2.7889 61
6 31 14.8106 14 2.3110 14 2.3110 6 0.0000 31
7 14 2.3110 9 0.0000 42 40.0000 42 40.0000 42
what the sixty-four tournaments spent
tournaments held 64
contestants drawn, one number each 256 off stream 18
children copied, 790 numbers each 50560 off stream 16
places the champion is carried into 1 and drew both anyway
winners from the better half of the board 58 of 64
what a tournament of 4 says it should be 93.75% of 64
the average score of the winners 72.3800
the average score of the whole board 24.5807
Slots 6 and 7 are the ones to look at first. Slot 6 drew genome 14 twice and slot 7 drew genome 42 twice, out of four draws each. Contestants are drawn with replacement, so a tournament of four is four independent draws and not four different genomes, and a genome can beat itself. Nothing is wrong there. Removing the duplicate would mean drawing again, and drawing again is the branch the whole stream discipline exists to avoid; the cost of keeping it is that a tournament of four occasionally has only three real contestants in it, which weakens the pressure by an amount nobody will ever notice.
Slot 1 is the other thing to sit with. Three of its four contestants scored nothing and the fourth scored 0.4357 grams, so 0.4357 grams won, and genome 47 will be a parent sixty-three times over as good as nothing. That is not a defect in the rule. Half the board really is at nothing, and a rule that refused to breed from a bad generation would have to invent something to breed from instead.
The counts at the bottom are the accounting. Sixty-four tournaments of four cost 256 numbers off stream 18, and sixty-four children at 790 numbers apiece cost 50,560 off stream 16. Both totals are settled before the first card is read: they are the size of the population times the size of the tournament, and the size of the population times twice the length of a genome. Nothing about what the scores said can move either one. Fifty-eight of the sixty-four winners came from the better half of the board against an expected sixty, which is close enough that the gap is the ordinary roughness of sixty-four coin flips, and the winners average 72.3800 grams against the board's 24.5807.
One tournament, one question: what is the chance the winner comes from the better half of the board? The winner is the best of the k drawn, so the winner comes from the worse half only when every one of the k came from the worse half. Each draw lands in the worse half half the time, and the draws are independent, so
P(worse half) = (1 ÷ 2)k
and the chance of a winner from the better half is one minus that. For a tournament of two it is 0.75. For four it is 0.9375, which is the 93.75 percent the run prints and the 60 of 64 it expects. For eight it is 0.9961 and for sixteen it is 0.99998. Past about eight, the top half of the board has almost all of the children, and turning the dial further is buying refinements inside the top few genomes.
The more useful question is how fast one genome's descendants take over the whole population. Suppose selection were the only thing happening, with no mutation at all, and suppose one lineage holds a share p of the population and always wins when it is drawn. A tournament fails to contain it only when all k draws miss it, so the lineage takes a share
p′ = 1 − (1 − p)k
of the next generation, and while p is small that is very close to k times p. The share multiplies by about k every generation. Starting from one genome in sixty-four, the number of generations to reach the whole population is however many times k must be multiplied by itself to reach 64:
g = logk 64
which is 6 generations at a tournament of two, 3 at four, 2 at eight and 1 at sixty-four. The sweep further down this page measures the same thing on real runs and gets 63, 10, 7 and 2. Every one of those is slower than the arithmetic says, and the reason is the assumption in the middle: a lineage's members are not the champion, they are mutated copies of it, and most of them score worse than it does. The arithmetic gives the fastest possible takeover, and it is right about the ordering and about the fact that even the gentlest tournament finishes the job in a few dozen generations.
At a tournament of one there is no selection in the arithmetic at all, k is 1 and the share never grows. Lineages still disappear, because a lineage that happens to be picked no times in a generation is gone for good, and a lineage that is gone cannot come back. That is the same drift a small population always has, and it takes about as many generations as there are genomes: about 64 here, and the run measures 59.
The loop that runs a generation is the tournament sixty-four times with the two streams spent in a fixed order. Stream 18 first, for who the parent is, then stream 16, for the copy. That order is not an implementation detail: it is the order every birth in this world takes its numbers in, and a run that ever reverses it is reading two different sequences.
// internal/gene/pick.go, continued
// Loop is one run of the arena from a drawn generation to whatever it
// becomes: the population, the two streams a generation spends, the
// rule that decides who makes the next one, and the ancestor every
// genome in it descends from.
type Loop struct {
Arena *Arena
Rule Rule
Pop []*Genome
Root []int // the opening genome each member descends from
Gen int
pick *rand.Rand
mut *rand.Rand
drew []int
kept Card
held bool
}
// Step scores the population, works out what it came to, and breeds the
// next one out of it.
func (l *Loop) Step() Round {
cards := l.Arena.Generation(l.Pop)
on := make([]float64, len(cards))
for i, c := range cards {
on[i] = l.Arena.Score(c)
}
// ... the numbers this generation came to, into a Round ...
next := make([]*Genome, len(l.Pop))
root := make([]int, len(l.Pop))
for i := range next {
// ... one tournament and one copy a place, and the places the
// champion is carried into: the box below is all of it ...
}
l.Pop, l.Root = next, root
l.Gen++
return r
}
Root is the only bookkeeping in there that is not part of the algorithm. It
carries, for every genome alive, which of the sixty-four the run opened with it descends
from: a founder starts as its own root and a child inherits its parent's. Nothing reads
it, nothing selects on it, and it costs one integer a genome. It is there because
counting how many roots are left is the cheapest honest measurement of how much variety
a population has, and a page that talks about a population losing its variety without
printing a number for it is a page asking to be believed.
Elitism for the top genome
A tournament has no memory. It reads the board it is given, and the board it is given is whatever the last round of copying produced. Suppose the best genome in the world is at 179.4530 grams and every one of its children is worse, which is the usual case: about thirty-five of a genome's three hundred and ninety-five numbers move in a copy, and moving a number in a controller that is already working is more likely to break it than to improve it. If the parent is not drawn again, or is drawn and loses, the best thing this run has ever found is gone. Nothing anywhere kept a copy of it. The population is the only memory the search has.
Elitism is the repair, and it is one line: the best card of the generation is carried into the next generation as itself. Not re-copied at low rates, not copied and then checked, not re-scored to see whether it still deserves the place. The same three hundred and ninety-five numbers, in the same order, in the first slot.
Elite retention repeats the champion’s score on this fixed trial set under the recorded runtime. It avoids noisy rescoring, but the trial set can still favor a genome that performs poorly on new trials.
// internal/gene/pick.go — inside Loop.Step, the loop over places
won := l.Rule.Tournament(on, l.pick, l.drew)
r.Picks += l.Rule.Size
parent := won
if l.Rule.Greedy {
parent = r.Champ
}
kid, m := l.Rule.Rates.Child(l.Pop[parent], l.mut)
r.Draws += m.Draws
if i < l.Rule.Elite {
next[i], root[i] = l.Pop[r.Champ].Copy(), l.Root[r.Champ]
continue
}
next[i], root[i] = kid, l.Root[parent]
The two lines naming parent are the worked failure at the foot of this
page arriving early, and they can be read as though they were not there:
Rule.Greedy is false in every run on this page except that one, so
parent is won throughout and the flag is explained where it
is used.
The elite place holds its tournament, copies the winner, puts the copy through a whole
mutation pass, and then drops all of it on the floor and writes the champion in instead.
Four numbers off stream 18 and 790 off stream 16, spent on a child that is never born.
That is the rule the copying page was built on, applied to a
different question: every draw a birth would have made is made whether the birth
happens or not. What it buys is that
Elite: 1 and Elite: 0 are two runs off one seed that read the
same numbers in the same order, and differ in exactly one thing, which is the genome
sitting in the first slot. Without it the two runs would be reading different parts of
two sequences from the first generation on, and nothing you measured about the
difference between them would mean anything.
Untouched is a claim with two halves and both of them are checkable. The genome has to come across gene for gene, and the card the arena hands back for it next generation has to be the card it was carried in with, to the last bit of every one of its numbers. The second half is the one that catches a subtle mistake: a champion that was carried correctly but scored inside a world that had drifted would come back with a different number and would quietly stop being the champion.
$ go test ./internal/gene/ -run 'TheChampionCrosses|ElitismDoesNot|ATournamentSpends|HarderTournaments' -v
=== RUN TestTheChampionCrossesUntouched
--- PASS: TestTheChampionCrossesUntouched (0.09s)
=== RUN TestElitismDoesNotMoveTheStreams
--- PASS: TestElitismDoesNotMoveTheStreams (0.11s)
=== RUN TestATournamentSpendsOneDrawAContestant
--- PASS: TestATournamentSpendsOneDrawAContestant (0.00s)
=== RUN TestHarderTournamentsPickBetterParents
--- PASS: TestHarderTournamentsPickBetterParents (0.00s)
PASS
ok theworld/internal/gene 0.203s
The first walks eight generations and demands that the carried genome match the previous champion at every one of the 395 genes, that the card come back identical, and that the best score never fall. The second runs one seed twice, keeping a champion and dropping one, and then asks both runs' generators for one more number: if the elite place had skipped its draws, those two numbers would differ. The third holds two hundred tournaments over a board where everything is tied and two hundred over a board where nothing is, and demands that both leave the stream in the same place. The fourth is the dial itself: over one board, a bigger tournament has to hand back a better average parent, and a tournament of one has to hand back the average of the whole board, because it never looks at a score.
Now the same forty generations twice, once with a champion kept and once without.
$ go run ./cmd/pick -mode elite -gens 40
pick: 40 generations of 64, tournaments of 4, run twice off one seed
gen champion kept champion dropped
0 179.4530 179.4530
5 298.9953 267.7949
10 557.2623 621.8351
15 557.2623 607.6523
20 670.6833 697.9127
25 1059.0000 963.0000
30 1103.0000 1062.0000
35 1109.0000 1116.0000
40 1113.0000 1126.0000
times the best score fell, champion kept 0
times it fell with the champion dropped 12
the worst of those falls, in grams 149.4598
generations the carried card came back identical 40 of 40
numbers each run took off stream 18 10496
numbers each run took off stream 16 2072960
the two runs drew the same numbers in the same order
Read the two columns before reading the summary, because the summary is not what most people expect. The run without a champion finishes ahead: 1126.0000 grams against 1113.0000. It was ahead at generation 10, ahead at 20, behind at 25 and 30, and ahead again at the end. Elitism did not win this race and does not promise to. What it promises is the first line of the summary: in forty generations the best score in the world went down zero times with a champion kept and twelve times without one, and the worst of those twelve falls threw away 149.4598 grams of progress that something had already found and nothing had written down.
That is the trade, stated plainly. A run with a champion is a ratchet: whatever it has found, it still has. A run without one wanders, and wandering is not always worse, because a genome that is merely very good can be in the way of a genome that would have been better. What makes the ratchet the right default here is that it costs one place in sixty-four and it makes the best number the run prints mean something. Without it, the best score at generation 40 is a report on the last generation and not on the run.
The 200-generation selection run
Everything above happens in one generation. The interesting behaviour is in hundreds of them, and it costs nothing but time: two hundred generations of sixty-four genomes on four trials of six hundred ticks is fifty-one thousand two hundred trials, and the whole of it runs in about twenty seconds of wall clock on the machine this was written on, an eight-core Ryzen 7 3700X on Linux, with the generation split across eight goroutines. Yours will differ; the numbers below will not.
$ go run ./cmd/pick -mode climb
pick: 200 generations of 64, tournaments of 4, 1 champion kept
gen best average at nothing spread lineages
0 179.4530 24.5807 26 0.2858 64
1 201.6845 64.8548 5 0.2762 24
2 221.6845 110.0989 0 0.2553 11
5 298.9953 180.3688 0 0.1514 3
10 557.2623 351.8400 0 0.0616 1
20 670.6833 536.3701 0 0.0749 1
50 1116.0000 1039.9645 0 0.0661 1
100 1121.0000 1051.9895 0 0.0546 1
150 1143.0000 1060.6508 0 0.1002 1
200 1143.0000 1052.9949 0 0.1188 1
the champion of the last generation, and the one the run opened with
generation 0 generation 200
score, grams 179.4530 1143.0000
Bulk 65.7271 46.1673 factors 1.6432 and 1.1542
Bite 0.2393 1.0000 factors 0.9573 and 4.0000
Reach 3.1559 3.1616 factors 3.1559 and 3.1616
Sight 20.9548 8.0066 factors 1.7462 and 0.6672
Top 0.1823 1.7595 factors 0.4052 and 3.9099
Convert 11.4661 11.2572 factors 2.8665 and 2.8143
Full 1160.6651 1061.1300 factors 2.9017 and 2.6528
the opening genome the last champion is from 43
what that genome scored in generation 0 179.4530
where it stood on that board 1 of 64
the generation it was the last lineage standing 10
a bite of 1.0000 grams, 300 bites a trial, 4 trials: 1200.0000 grams is all there is
it scored 1143.0000, which is 95.2 percent of that
the fodder standing in the four trials comes to 1880.0000 grams
The at nothing column empties in two generations. Twenty-six genomes that
could not find food at all became five and then none, and they did not learn anything:
they were replaced by the children of genomes that could. The average follows the best up
the page and then sits about eighty grams behind it for the last hundred and fifty
generations, which is the standing cost of mutation. Every child is a copy with about
thirty-five numbers moved, most of those moves make a slightly worse animal, and the gap
between the best and the average is the size of the damage the population is carrying at
any moment.
The last block is the reason to run two hundred generations rather than twenty. A bite is two ticks, so six hundred ticks hold at most three hundred bites, and the largest bite this world's ranges allow is a factor of four on the founding row's quarter gram: exactly 1.0000 grams. So the most any animal can possibly take off four trials is 1,200.0000 grams, and the champion of generation 200 took 1,143.0000, which is 95.2 percent of a life spent with its mouth on something. Nothing told it that number. Nothing in the code knows the number exists. The score is grams eaten, and grams eaten is what it went and got.
The body it did it with is readable factor by factor. Bite sits at
exactly 4.0000, hard against the top of its range, which is the clamp inside every write to a
genome doing its job: the copies kept pushing and the range kept refusing, and a gene
pinned at an end is a gene the search is still leaning on. Top is at 3.9099, so the animal that won
this arena sprints at 1.7595 cells a tick, while genome 43, the animal that won generation
0, crawled at 0.1823 and won by standing still with a wide mouth. Two hundred generations
turned a sitter into a sprinter, because the sitter had already eaten everything it could
reach by the end of trial one and the only grams left on the plate were somewhere else.
Bulk came down by thirty percent, which is thirty percent off the bill a
standing body pays every tick. Reach barely moved at all: 3.1559 to 3.1616,
because the whole population descends from genome 43 and genome 43's reach was already
most of what a mouth can usefully have.
Sight is the odd one. It fell from twenty cells to eight. Nothing in this
arena charges an animal energy for its eyes, so nothing was saved by shortening them, and
the only other thing Sight does is set the span every eye reading is divided
by. A creature with a twenty-cell view and one with an eight-cell view hand their
controllers two different rescalings of the same world. The gene and the weights that read
it are inherited together and are moved together, and this lineage settled on the pair it
settled on. That is as much as the run supports, and more than the run supports would be
storytelling.
One line in the middle of that block is the whole of the next section in advance. The lineage still standing at generation 200 is genome 43's, and it was the only one left from generation 10. Sixty-three of the sixty-four opening genomes have no descendants at all, and the arena spent one hundred and ninety generations refining what one of them stumbled into.
Six settings of one number
Now turn the dial. Same seed, same arena, same four trials, same opening sixty-four genomes, same mutation rates, same one champion. The only thing that differs between these six runs is how many contestants a tournament has.
$ go run ./cmd/pick -mode sweep
pick: 200 generations at 6 settings of the tournament, 1 champion kept
the best score in the generation, as the run goes on
size gen 1 gen 5 gen 25 gen 50 gen 100 gen 200
1 179.4530 181.2308 398.4640 642.6098 782.8505 951.8972
2 220.0000 260.0000 1010.7753 1052.7441 1121.0000 1134.0000
4 201.6845 298.9953 1059.0000 1116.0000 1121.0000 1143.0000
8 201.6845 460.0000 1073.0000 1106.0000 1132.0000 1146.0000
16 277.4477 591.9911 1091.0000 1111.0000 1113.0000 1119.0000
64 224.3077 667.7905 1094.0000 1114.0000 1122.0000 1124.0000
and what the population looked like at generation 200
size best average spread lineages down to one at
1 951.8972 175.5683 0.2117 1 generation 59
2 1134.0000 991.0108 0.1269 1 generation 63
4 1143.0000 1052.9949 0.1188 1 generation 10
8 1146.0000 1041.6535 0.0498 1 generation 7
16 1119.0000 998.1320 0.0390 1 generation 6
64 1124.0000 943.4744 0.0331 1 generation 2
Read the first table down the columns and the ordering reverses as you go across. At generation 5 the board is in order of pressure: the hardest tournament is winning by a street, 667.7905 against 298.9953 for four and 181.2308 for one. At generation 200 it is nearly the opposite: of the five settings that select at all the two hardest are the two worst finishers, 1119.0000 and 1124.0000, and the best result on the page belongs to a tournament of eight with a tournament of four just behind it. Only the tournament of one, which never reads a score, finishes below them. Sixteen and sixty-four spent the first twenty-five generations winning and the next hundred and seventy-five being overtaken.
The second table says what they spent to win early. A tournament of sixty-four had lost sixty-three of its sixty-four lineages by generation 2, and its population at generation 200 sits at a spread of 0.0331, against 0.1188 for a tournament of four and 0.2858 for the generation everything started from. Nearly nine tenths of the variety the run was handed was gone in two generations, and it never came back, because the only thing in this world that makes variety is mutation, and mutation makes it about thirty-five genes at a time.
The bottom of the dial fails the other way and fails harder. A tournament of one is not
selection at all, and its run still climbs, from 179.4530 to 951.8972, which is worth
understanding before it is dismissed: the climb is the champion place doing all of the work
by itself. One genome in sixty-four is protected, the protected genome is occasionally
drawn as a parent, and its better children occasionally become the new champion. That is a
ratchet with sixty-three places of pure drift attached to it, and the population it leaves
behind is a wreck. The average at generation 200 is 175.5683 against 1052.9949 for a
tournament of four, and running that setting on its own with
go run ./cmd/pick -mode climb -size 1 shows twenty-eight of its sixty-four
genomes back to scoring nothing whatever at the end of it.
All of that is one seed and one arena. The ordering among the middle settings, four against eight against two, is inside the wobble of a single run and nobody can read it as a ranking. The two ends are not: no seed is going to make a tournament of one competitive on the average, and no seed is going to give a tournament of sixty-four its variety back.
Mutation at full scale
There is one more setting past sixty-four, and it is the one that is tempting to write in the first place. The board is already scored. The best genome is already known. Why hold sixty-four tournaments to find out something a single pass over the scores would tell you? Copy the best one sixty-four times and get on with it.
// internal/gene/pick.go — inside type Rule struct
// Greedy is the selection rule as it is tempting to write it: the
// board is already sorted, so hand every place in the next
// generation to the genome at the top of it and skip the
// tournaments. It is kept behind a flag so what the top of the
// pressure dial costs a population can be run instead of described,
// and it is false in every run this book ships. The tournaments are
// drawn and thrown away under it, so a greedy run and a tournament
// run read the same numbers in the same order.
Greedy bool$ go run ./cmd/pick -mode greedy
pick: 200 generations of 64, run twice off one seed
every child off the best genome tournaments of 4
gen best average spread best average spread
0 179.4530 24.5807 0.2858 179.4530 24.5807 0.2858
20 794.7282 626.2426 0.0303 670.6833 536.3701 0.0749
40 850.8741 656.0192 0.0258 1113.0000 1052.7217 0.0574
60 972.7943 812.6964 0.0275 1121.0000 1048.7328 0.0630
80 1024.8977 859.1105 0.0279 1121.0000 1062.3461 0.0687
100 1113.0000 763.3327 0.0259 1121.0000 1051.9895 0.0546
120 1126.0000 773.2897 0.0285 1143.0000 1087.1920 0.0731
140 1133.0000 853.2018 0.0276 1143.0000 1071.8725 0.0901
160 1134.0000 816.3410 0.0285 1143.0000 1077.2450 0.1081
180 1136.0000 833.5280 0.0272 1143.0000 1081.7466 0.1046
200 1136.0000 816.8780 0.0282 1143.0000 1052.9949 0.1188
greedy tourney
the best genome's score 1136.0000 1143.0000
the average of the generation 816.8780 1052.9949
how far apart the genomes are 0.0282 0.1188
how far apart they were at generation 20 0.0303 0.0749
the generation it came down to one lineage 1 10
of the 64, how many share one ancestor 64 64
The first surprise is that the greedy run is ahead at generation 20, by a hundred and twenty-four grams. That is the whole seduction of the thing: it works, visibly, immediately, in the part of a run somebody is most likely to watch. By generation 40 it is two hundred and sixty grams behind and it stays behind for the next hundred and sixty generations, finishing seven grams short after two hundred.
The seven grams are not the failure. The failure is the two columns beside them. At generation 20 the greedy population's spread is 0.0303, against 0.2858 for the generation it started from: nearly nine tenths of the variety in the world was gone in twenty generations, and the genomes left were all cousins, every one of them a mutated copy of one animal that had been alive the generation before. It came down to a single lineage at generation 1, which is as fast as that can possibly happen. And unlike the tournament run, which climbs back to a spread of 0.1188 as its lineage explores, the greedy run never recovers: every reading after the first one is between 0.0258 and 0.0303, because every generation of it is rebuilt from scratch out of one genome.
The average is where that shows up as damage. The greedy population averages 816.8780 grams against the tournament's 1052.9949, and the reason is precise: in the greedy run, every one of the sixty-three children is one fresh mutation pass away from the champion, so the population is one generation of unfiltered mistakes. In the tournament run, a parent had to win a tournament to become a parent, so it had already survived being measured, and its children are copies of something that was already checked. The tournament's population is filtered twice and the greedy population is filtered once.
The reasoning from symptom to cause has no bug in it, again. The code did what it was told. It was told that the best genome is the best genome, which is true, and asked to act on that once per place, which turned sixty-four searches into one search run sixty-four times over. A population is not a list of the answers so far; it is the list of places the next generation is allowed to look, and a population of one animal can only look in one place. Everything the greedy run does after generation 1 is hill climbing with sixty-four attempts a step, and hill climbing gets stuck where the hill stops.
Why tournaments tune pressure
Strip out the creatures and the grams and there are two mechanisms on this page, and they answer two different questions.
The tournament answers "how strongly". Its virtue is that it turns a vague preference into a whole number with an arithmetic meaning: a tournament of k gives the better half of the board 1 minus one over two to the k of the children, and lets one lineage take over in about log to the base k of n generations. It reads only comparisons, so it is immune to what the score's units are, immune to a score that grows tenfold over a run, and immune to a board where half the entries are tied at zero. All three of those would have broken a rule that divided by the total.
Elitism answers "what happens to the best one", and it is a different kind of decision that people run together with the first one because both of them favour good genomes. The difference is that pressure is a rate applied to everybody and elitism is a guarantee applied to one. Keeping a champion converts the best score from a report on the current generation into a report on the whole run, at the cost of one place in sixty-four. It also has a real cost, and the second exercise below runs it: eight champions instead of one is eight places not searching, and the population's variety pays for it.
The dial itself is the thing to carry away, and it is not particular to creatures. Every search that keeps a set of candidates has the same trade in it: pressure buys progress now and spends the variety that progress later has to come from. The measurements on this page say the same thing three ways. Turn it up and the early generations are the best on the page and the late ones are the worst. Turn it down to nothing and the population keeps its variety and does nothing with it. Turn it all the way up, past the end of the dial, and there is no population left to have variety at all. Nothing in the arena has an opinion about which of those you want; the right setting depends on how long the run gets, and nobody can read it off the first twenty generations, which is exactly when it looks easiest to decide.
- Given a tournament size, You can work out the chance its winner comes from the better half of the board, and say why that number does not change when the scores do.
- You can say how many numbers a generation takes off stream 18 and off stream 16, and why neither total depends on what any card said.
- You can explain why the contestants are drawn with
Float64and a floor instead of withIntN, and what a single extra draw would do to a run. - You can state both halves of what "carried through untouched" claims, and describe the check that would catch a champion that was carried but quietly re-scored.
- Handed a run's count of surviving lineages by generation, You can say roughly what tournament size produced it, and say what the spread number adds that the lineage count cannot.
- You can say what the greedy run gains in its first twenty generations, what it gives up to get it, and why its population averages two hundred and thirty grams below the tournament's.
Exercise 1 — a run with no selection in it. A tournament of one
never reads a score. Predict what its best score does over fifty generations, then run
go run ./cmd/pick -mode climb -size 1 -gens 50 and explain what is
actually doing the climbing.
It climbs, from 179.4530 to 642.6098 in fifty generations, which looks impossible for a rule that never compares two genomes. The champion place is doing all of it. One genome in sixty-four is carried through untouched, so the best score can never fall; the other sixty-three are copies of parents picked at random, and once in a while one of them lands above the champion and takes the place. That is a ratchet bolted to a random walk, and a ratchet alone is a real if very slow search.
What it cannot do is drag the population along. The average at generation 50 is
154.5773 against 1039.9645 for a tournament of four, and seven genomes are still
scoring nothing whatever. Take the ratchet off as well, with
-size 1 -elite 0, and the last thing holding the run up goes: the best
score falls from 179.4530 to 140.0000 in the first generation and is still at
140.0000 at generation 5.
Exercise 2 — eight champions instead of one. If keeping one
genome untouched is good, keeping eight might be better. Run
go run ./cmd/pick -mode climb -elite 8 -gens 50 against the same fifty
generations at -elite 1 and say what the extra seven bought and what they
cost.
They buy a faster start and nothing at the end. With eight kept, generation 10 is at 778.4839 grams against 557.2623 for one kept, and generation 50 lands at 1119.0000 against 1116.0000, which is a difference of nothing after fifty generations of arithmetic.
The cost is in the two right-hand columns. Eight champions is eight of sixty-four places that are not searching anything, and the run is down to a single lineage by generation 10 with a spread of 0.0456, against 0.0616 for one champion. By generation 50 it is at 0.0392 against 0.0661. Elitism is selection pressure wearing a different name, and eight sixty-fourths of it is a lot of pressure to apply without meaning to.
Exercise 3 — the same dial, a different world. The sweep is one
seed. Run go run ./cmd/pick -mode climb -seed 7 -gens 50 at
-size 1, -size 4 and -size 64, and say which of
this page's claims survive a change of world and which were facts about one run.
Seed 7 is a different arena and a different opening sixty-four: its best genome starts at 459.5906 grams instead of 179.4530, and twenty-two of its genomes score nothing instead of twenty-six. The ends of the dial behave exactly as before. A tournament of sixty-four is down to one lineage at generation 2 with a spread of 0.0309, and at generation 50 it sits at 1104.0000 with a population averaging 1020.9145. A tournament of one is still at three lineages at generation 50, still has thirteen genomes scoring nothing, and averages 221.8210.
The middle is where the single run was never evidence. On seed 5 a tournament of four reached 1116.0000 by generation 50; on seed 7 it reaches 1119.0000, and the gap between it and a tournament of sixty-four is fifteen grams rather than two. Claims like "eight beats four" need many seeds and this page has one. Claims like "the top of the dial destroys the population's variety in two generations" survive, because the mechanism behind them is arithmetic and not luck.
Every child on this page had one parent. Three lineages were still standing at generation 5 and one at generation 10, so two of them went out inside five generations with everything their lines had found, and whatever that was, genome 43's descendants had to find it again from scratch or do without it. A population that copies one parent at a time can only ever hold what one chain of copying stumbled into, and the two hundred generations above are the record of one chain doing exactly that, very well, alone.