Networks That Grow
Fixed-width controller limit
Every animal that has walked in this book was driven by the same machine: twenty-four numbers in, twelve neurons in a middle row, six numbers out, and three hundred and seventy-eight weights. Write the controller down as nodes and links so a lineage can add structure instead of only tuning settings.
A node is a place a total is worked out. A link says which node feeds which, with what weight, and carries a number of its own that names it for the whole run. One birth in twenty adds a link, and one in fifty puts a node into a link that was already there.
A fixed-width controller can learn only within the width a person typed. Mutation may find a useful weight, but it cannot invent a new intermediate value or connect a new sensor path to an action. The architecture has become a ceiling.
The graph form keeps the same score-to-action contract. It still reads the row the creature phase supplies and still returns six scores in table order, but the wiring between those ends becomes inheritable history.
The page first proves the graph can reproduce the dense controller's arithmetic, then opens a founder graph, mutates structure, crosses two wirings, and runs twenty years of animals whose controllers can grow.
The chapters before this one evolved the flat row, and every figure they printed came off a run that spent 1,189 random numbers on each birth. A graph has a different count of genes, so a graph birth spends a different count of numbers and every generator in the valley is at a different place in its sequence by the second tick. Seed 5 still opens the same ground, scatters the same twenty-five animals onto the same cells and reads the same weather. Everything downstream of the first birth is a different history.
No count, digest, curve or pedigree on this page may be set beside one from a page before it, in either direction. The machinery carries across the line unchanged except where this page changes it.
Dense and graph controllers
A second controller type is a liability until it is proved to be the first one. Two ways of writing down the same arithmetic that quietly disagree in the last bit is the sort of defect that shows up four chapters later as a valley that will not replay, and there is one check that closes it: take a network, write it out as a graph, run both against the same senses, and demand every number match exactly.
Passing that check is not free. It fixes three things that would otherwise each have a dozen reasonable answers, and all three are decided here and never again.
Node numbers. The inputs come first, numbered from nought in the order the row arrives. Then the outputs, numbered from wherever the inputs stop, in the order the action table reads them. Then the hidden nodes, in ascending order of the number each was given. Inputs and outputs carry the same numbers in every graph in the run, which is what lets two graphs be compared at all.
The adding order. A node's total starts at its bias and then adds the links arriving at it, in ascending order of the node each link comes from. Not the order they sit in the slice, not the order they were grown in: ascending by source. That is the only order that reproduces a row of neurons walking along its weights, and the interlude below is the arithmetic showing why.
The squash. Tanh over every hidden node's total, nothing over an output's. Both of those are the rules the squash chapter settled for the middle row and the answer row, and neither of them moves because the wiring is written down differently.
// internal/mind/graph.go
// Link is one connection: the node it reads, the node it feeds, the
// weight it multiplies by, and the number it was minted under. Two
// links in two different graphs carrying the same Innov are the same
// link, whatever else has happened to either graph since.
type Link struct {
From, To int
W float64
Innov int
}
// Node is one place a total is worked out. ID is the number it answers
// to for the whole run, and B is the bias its total opens at. An input
// node carries no bias: its number arrives from the outside and nothing
// is added to it.
type Node struct {
ID int
B float64
}// Forward runs one row of numbers through the graph and writes the
// answer into out. A node's total starts at its bias, adds every link
// arriving at it, and is squashed if it is a hidden node. Nothing here
// allocates: the scratch was made when the graph was wired.
func (g *Graph) Forward(in, out []float64) {
if !g.wired {
g.Wire()
}
for i := 0; i < g.In; i++ {
g.val[i] = in[i]
}
for _, i := range g.order {
z := g.Nodes[i].B
for _, li := range g.into[i] {
z += g.Links[li].W * g.val[g.src[li]]
}
if g.Kept(i) && g.Squash != nil {
z = g.Squash(z)
}
g.val[i] = z
}
copy(out, g.val[g.In:g.In+g.Out])
}
Everything expensive happens in Wire, once, and never again on a tick:
where each link's two ends sit in the node list, which links arrive at each node and in
what order they are added, and an order the nodes can be worked out in where nothing is
read before it has been written. That last one is worked out by starting from the inputs
and taking, over and over, every node all of whose incoming links have already been
done. A graph with no loop in it always empties that way, and a graph with a loop in it
never does, which is why Wire refuses one instead of running it.
// Wired is the same controller a Net describes, written down as nodes
// and links: In inputs, one hidden node per neuron of the middle row,
// Out outputs, and a link for every weight in the flat slice.
func Wired(n Net, innov func() int) *Graph {
g := NewGraph(n.In, n.Out)
g.Squash = n.Squash
hid := make([]int, n.Hid)
for h := range hid {
hid[h] = innov()
g.Grow(hid[h])
}
for h := 0; h < n.Hid; h++ {
for i := 0; i < n.In; i++ {
g.Join(i, hid[h], n.W[n.HidW()+h*n.In+i], innov())
}
g.Bias(hid[h], n.W[n.HidB()+h])
}
for o := 0; o < n.Out; o++ {
for h := 0; h < n.Hid; h++ {
g.Join(hid[h], n.In+o, n.W[n.OutW()+o*n.Hid+h], innov())
}
g.Bias(n.In+o, n.W[n.OutB()+o])
}
return g
}$ go run ./cmd/nodes -mode wire
nodes: one controller written three times, and run against itself
the three-row network 24 in, 12 hidden, 6 out, 378 weights off stream 14
the same as a graph 42 nodes, 360 links, 18 biases
and written backwards the same 360 links, last one first
node numbers inputs 0 to 23, outputs 24 to 29, hidden 30 to 41
a node's total its bias, then its links ascending by the node they come from
the squash tanh on the 12 hidden nodes, nothing on the 6 outputs
one row of senses through all three of them
act the network the graph written backwards all three
rest -0.085074199346956814 -0.085074199346956814 -0.085074199346956814 yes
walk 0.51036943070529406 0.51036943070529406 0.51036943070529406 yes
sprint -0.12939172783575853 -0.12939172783575853 -0.12939172783575853 yes
turn left -0.24236991220617685 -0.24236991220617685 -0.24236991220617685 yes
turn right 0.2072352977262456 0.2072352977262456 0.2072352977262456 yes
bite 0.30043346439661894 0.30043346439661894 0.30043346439661894 yes
1000 more rows through all three, 6000 numbers compared against the network
the graph disagreed on 0
the same graph written backwards disagreed on 0
Three hundred and sixty links and eighteen biases against three hundred and seventy-eight weights: the same numbers, counted differently, because a graph puts a bias on a node and a network keeps its biases in two blocks of the slice. The forty-two nodes are the twenty-four senses, the six actions and the twelve middle neurons, and every one of them now has a name of its own instead of an offset into somebody's arithmetic. The third column is the same graph with its link list reversed end to end, which is the same controller written down differently, and the last three lines say all three agree on every one of six thousand numbers.
$ go test -count=1 ./internal/mind/ -run 'AGraphWired|TheSameGraphWritten|ALoopIsRefused|AWiringSurvives' -v
=== RUN TestAGraphWiredLikeANetworkAnswersLikeIt
--- PASS: TestAGraphWiredLikeANetworkAnswersLikeIt (0.00s)
=== RUN TestTheSameGraphWrittenBackwardsAgrees
--- PASS: TestTheSameGraphWrittenBackwardsAgrees (0.00s)
=== RUN TestALoopIsRefusedBeforeItIsMade
--- PASS: TestALoopIsRefusedBeforeItIsMade (0.00s)
=== RUN TestAWiringSurvivesBeingWrittenDown
--- PASS: TestAWiringSurvivesBeingWrittenDown (0.00s)
PASS
ok theworld/internal/mind 0.006s
The first of those runs the comparison at four sizes and not one, and the sizes are chosen against each other. A 24-12-6 network has three different row lengths, so an offset that muddled two of them would show up; a 1-1-1 network has none, so an offset that only works because every row is the same length would show up there instead. The third test builds a graph with a link running backwards and asks for it to be wired, which is the half of the feed-forward rule nothing else on this page exercises.
The fourth is the file. A graph goes out as one JSON object to a line, every node and every link with its own number, and comes back as a controller that answers identically on fifty rows; then a link naming a node the record does not hold is handed to the same reader, which refuses it. That refusal is the point of writing a loader at all. A wiring is a thing with references in it, and a broken reference read without checking turns into a panic on the first tick of whatever loaded it, a long way from the file that caused it.
Take the smallest network that has all three parts: two inputs, two middle neurons, one output. Give it numbers that can be done by hand.
The senses are 0.5 and -0.25. Middle neuron 0 weighs them at
2.0 and 1.0 and opens at a bias of 0.5. Middle
neuron 1 weighs them at -1.0 and 4.0 and opens at
-0.5. The output weighs the two middle answers at 1.0 and
0.5 and opens at 0.25.
A row of neurons does neuron 0 like this: start at the bias, 0.5. Add the first
input's contribution, 2.0 × 0.5 = 1.0, and the running total is 1.5. Add the
second, 1.0 × −0.25 = −0.25, and the total is 1.25.
Neuron 1 the same way: −0.5, then −1.0 × 0.5 = −0.5 to make
−1.0, then 4.0 × −0.25 = −1.0 to make -2. Squash
both: tanh(1.25) = 0.84828363995751288 and tanh(−2) = −0.9640275800758169.
The output row starts at 0.25, adds 1.0 × 0.84828363995751288, then adds 0.5
× −0.9640275800758169, and finishes at
0.61626984991960443.
Now the graph. The inputs are nodes 0 and 1, the output is node 2, the two middle neurons are nodes 3 and 4. Node 3 opens at its bias and takes its links ascending by the node they come from, which is node 0 and then node 1: bias, then 2.0 × 0.5, then 1.0 × −0.25. That is the same three numbers added in the same three steps. Node 2 takes its links ascending by source as well, which is node 3 and then node 4: the same order the output row read the middle answers in. Every addition in the graph is an addition the network made, in the same place in the same running total, so the two finish on the same bits.
Reorder any one of those and the answer moves. Adding on a computer is not associative,
because every step rounds to the nearest number a float64 can hold. Add 0.1, then 0.2,
then 0.3, and you get 0.60000000000000008882. Add 0.3, then 0.2, then 0.1, and you get
0.5999999999999999778. Both are correct roundings of six tenths and they are two
different numbers, and every comparison in this world that asks whether two runs agree
asks it with ==.
Write the links arriving at node j as a list L(j), and write
s(l) and w(l) for the node a link comes from and the weight it
carries. A node's total is
z(j) = b(j) + ∑ w(l) × v(s(l)), over l in
L(j), taken in ascending s(l)
and its value is v(j) = tanh(z(j)) when j is a hidden node and
v(j) = z(j) when it is an output. Sorting L(j) by
s(l) is the entire content of the equality: it is a rule about the order of
a sum, it changes nothing in exact arithmetic, and it is the difference between a
controller that replays and one that does not.
The first version of Wire did not sort anything. It walked the link slice
once and put each link on its target's list as it came, which is the obvious way and is
wrong in a way nothing complains about: go vet is happy, the tests that
existed passed, and the controller answered sensible numbers. The flag below keeps that
version runnable so the bill can be read instead of asserted.
// internal/mind/graph.go — inside type Graph struct
// Anyhow is the accumulation as it is tempting to write it: a
// node's incoming links added in whatever order they happen to sit
// in the slice, instead of in ascending order of the node they
// come from. It is kept behind a flag so what an addition order
// costs can be run instead of described, and it is false in every
// graph this book ships.
Anyhow bool$ go run ./cmd/nodes -mode loose
nodes: one controller written three times, and run against itself
the three-row network 24 in, 12 hidden, 6 out, 378 weights off stream 14
the same as a graph 42 nodes, 360 links, 18 biases
and written backwards the same 360 links, last one first
node numbers inputs 0 to 23, outputs 24 to 29, hidden 30 to 41
a node's total its bias, then its links in the order they sit in the slice
the squash tanh on the 12 hidden nodes, nothing on the 6 outputs
one row of senses through all three of them
act the network the graph written backwards all three
rest -0.085074199346956814 -0.085074199346956814 -0.085074199346956897 no
walk 0.51036943070529406 0.51036943070529406 0.51036943070529428 no
sprint -0.12939172783575853 -0.12939172783575853 -0.12939172783575856 no
turn left -0.24236991220617685 -0.24236991220617685 -0.24236991220617679 no
turn right 0.2072352977262456 0.2072352977262456 0.20723529772624566 no
bite 0.30043346439661894 0.30043346439661894 0.300433464396619 no
1000 more rows through all three, 6000 numbers compared against the network
the graph disagreed on 0
the same graph written backwards disagreed on 4825
the widest disagreement 3.331e-16, on row 65
Read the second and third columns. The graph as it was built still agrees with the network on all six thousand, because the wiring routine happens to lay its links down in ascending source order already. The same graph with its link list reversed disagrees on 4,825 of them, by about three parts in ten thousand million million. That is the last bit of a float64 and nothing more.
The reasoning from symptom to cause is short and the conclusion is the uncomfortable part. Nothing about the controller changed: the same nodes, links, weights and numbers, written down in a different order. A structural mutation writes links in a different order by construction, because a split takes one link out of the middle of the slice and appends two to the end. So under the flag a child that has grown a node disagrees with its parent about the arithmetic of every link the two still share, and six of those numbers are then ranked against each other by a strict comparison to pick an action: the first time two of the six sit within 3.3e-16 of one another the animal does something else with its tick. Sorting is the fix, it happens once per graph and not once per tick, and it is why the node numbers are a contract in the first place.
The founder graph
Nothing in a valley of graphs starts with twelve hidden neurons, because twelve hidden neurons is the answer a person typed and the whole point is to stop typing it. A lineage opens with the least controller that can do anything at all: every input joined straight to every output, one link each, and no hidden node anywhere.
That is a controller with no middle, and the squash chapter measured exactly what such a thing can do. One row of weights with nothing bent in the middle can only ever add up its inputs and compare the totals, so it can separate what a straight line separates and no more. It is a weak animal, and it is the right starting point precisely because it is weak: everything above it has to be paid for by a lineage that found it useful, rather than handed out at the founding to every creature whether it needs it or not.
The row those links read is thirty-two numbers wide and not twenty-four. Twenty-four of them are what a body fills in: nine rays at two numbers each, the two gradients at two each, and the store and the speed a creature takes off itself. The other eight are carried and written by nothing, and they stand at nothing on every tick of this page.
Eight columns of zero look like waste until you ask what a link's number means. A number is minted against a pair of nodes and is that pair's name for the run. Add an input node later and it has no number that anything alive was minted against; every genome born before the addition describes a row of one width and every genome after it a row of another, and no crossing between the two can line up so much as a single link. There is no version of that which can be repaired afterwards. An input that a graph might ever want has to be on the node list before the first genome exists, or it can never be on it. So the eight are there, wired like the twenty-four, weighted like the twenty-four, and multiplied by zero on every pass.
One thing has to move before any of that can be stored. The genome the row chapter wrote holds its MIND block in a slice of weights, and a graph is nothing of the kind. Nor does it want a block of its own: a creature has one controller, and whether it is written as three hundred and seventy-eight numbers in rows or as a hundred and ninety-eight numbers on links, it is the same block in the same place in the same walk. So the genome gains one field beside the slice, holds exactly one of the two at a time, and answers the same five questions about either. Everything that copies, crosses, mutates or measures a genome asks those five questions and none of them learns which of the two it is holding.
// internal/gene/gene.go, continued — inside type Genome struct
// Wire is the MIND block written as link genes instead of as a row
// of weights: nodes, links, and a number on every link that names
// it for the whole run. It is nil in a genome whose controller is
// the fixed three-row network, and when it is not nil the Mind
// slice is empty and every number of the block lives in the graph.
//
// Both are called the MIND block and both are walked by the same
// index, because everything that copies, crosses or mutates a
// genome walks it as one flat run of numbers and has no business
// knowing which of the two it is holding.
Wire *mind.Graph// internal/gene/gene.go, continued
// minds is how many numbers the MIND block holds, whichever of the two
// things it is.
func (g *Genome) minds() int {
if g.Wire != nil {
return g.Wire.Genes()
}
return len(g.Mind)
}
func (g *Genome) TemperAt() int { return Bodies + g.minds() }
// At is the i'th gene of the flat walk.
func (g *Genome) At(i int) float64 {
switch {
case i < g.MindAt():
return g.Body[i]
case i < g.TemperAt():
if g.Wire != nil {
return g.Wire.Gene(i - g.MindAt())
}
return g.Mind[i-g.MindAt()]
case i < g.LookAt():
return g.Temper[i-g.TemperAt()]
}
return g.Look[i-g.LookAt()]
}
// Copy is a genome nothing shares with the one it came from. The MIND
// block is a slice, so copying the struct alone would hand two genomes
// one set of weights and every change to either would be a change to
// both.
func (g *Genome) Copy() *Genome {
out := *g
out.Mind = make([]float64, len(g.Mind))
copy(out.Mind, g.Mind)
if g.Wire != nil {
out.Wire = g.Wire.Copy()
}
return &out
}// internal/gene/grow.go
// Latent is how many numbers the evolved sensor row carries past the
// twenty-four a body fills in, and Wide is the whole row.
const (
Latent = 8
Wide = beast.Inputs + Latent
)
// The two bounds a graph is held inside, and they are worked out from
// the tick rather than chosen. A creature phase has 50 ms of a 100 ms
// tick, and a valley carries up to three thousand creatures; 512 links
// across three thousand of them is about 1.54 million multiply-adds a
// tick against the 1.13 million the fixed three-row network costs, so a
// valley of grown controllers is under 1.4 times the arithmetic of a
// valley of drawn ones. Neither number is enforced by anything but the
// operator below, which stops growing when it reaches one.
const (
MaxHidden = 32
MaxLinks = 512
)// Sprout is one founding creature's genome in the wired world: the
// identity genome with a graph in place of the flat row, every input
// joined to every output, and every one of its numbers drawn off the
// generator handed in.
//
// The draw order is the graph's own gene order, which is the links
// first and then the biases, and every number is divided by the square
// root of how many links arrive at an output node, exactly as a drawn
// three-row network divides by the fan of the row it is filling.
func Sprout(r *rand.Rand, m *Mint) *Genome {
g := Identity()
g.Mind = nil
g.Wire = mind.Full(Wide, beast.Acts, m.Link)
small := 1 / math.Sqrt(float64(Wide))
for i, n := 0, g.Wire.Genes(); i < n; i++ {
g.Wire.PutGene(i, (r.Float64()*2-1)*small)
}
return g
}$ go run ./cmd/nodes -mode open
nodes: the controller a lineage opens with
the row it reads 32 numbers: 24 the body fills in, then 8
nodes 38: 32 inputs, 6 outputs, 0 hidden
links 192, every input joined to every output
biases 6, one on each output
pairs a link may join 192, and every one of them is already joined
numbers minted so far 192, from 38 up
the ceilings 32 hidden nodes, 512 links
the genome, block by block
block flat row graph
BODY 10 10
MIND 378 198
TEMPER 3 3
LOOK 4 4
in all 395 215
what one birth spends, and it is a different number now
flat row graph
who the second parent is (18) 1 1
which parent each gene came from (17) 396 216
the copy's mistakes (16) 790 430
the shape of the controller (19) 0 4
where the child is set down (20) 2 2
a birth costs 1189 653
The last table is the break, printed. A birth used to cost 1,189 numbers for every creature the pass asked, born or refused, and it was the same 1,189 for every animal in the valley because every genome was the same length. It now costs 653 for an animal still carrying its opening graph, and it will cost something else for an animal carrying a bigger one, because the crossing spends one number a gene and the copy spends two. Stream 19 goes from unspent to four a birth, which was written into the draw order from the start: mate choice off 18, crossing off 17, copying off 16, wiring off 19, placement off 20, in that order, every time. Nothing about the order or the counts depends on what any of the numbers say. They do depend on how many genes the parent being asked has, which is known before a single number is drawn.
The MIND block reading 198 against 378 is worth a second look, because a controller with no middle at all is smaller than one with twelve neurons even at thirty-two inputs. 192 links and six biases is a hundred and eighty fewer numbers to copy, and a lineage that grows twenty hidden nodes will still be under the row it replaced.
Put takes the same branch At does, writing through
PutGene instead of into the slice, and Name gains one: a weight
in the flat row is called weight 41, and a gene of a graph is called
link 57, 12 to 26 or bias on node 33, because a link's number is the
only name it has. Span, Block and Len are not
touched at all. They are written in terms of the four offsets, and the four offsets are
written in terms of minds, which is the whole reason the row chapter put
them in one place.
Copy is the line to stop on. It already existed to stop two genomes
sharing one slice of weights, and a graph is a pointer for exactly the same reason a slice
is: copy the struct and both genomes hold the same nodes and the same links, and the first
mutation either of them makes is a mutation to both. The bug is the same bug the flat row
had, arriving on a different type, and it is caught here rather than in a valley because
the fix is one line and the symptom would have been two lineages that mysteriously never
diverged.
Adding links and nodes
Structural mutation is two operators and they are as small as they can be made. Add one link. Put one node into one link. Each is decided once a birth, at a stated rate, off a stream nothing else reads.
Adding a link needs a pair of nodes, and the pair is named by index into a list of every pair a link is allowed to join: from an input or a hidden node, to an output or a hidden node, never into an input, never out of an output. That list is a fact about the node set and knows nothing about what is already wired. So a draw that names a pair the graph already has adds nothing, and a draw that names a pair whose target already feeds back round to its source adds nothing, and neither of them draws again. This is the same rule the mutation pass and the tournament are under: a birth that reaches for another number when it dislikes the first answer spends a count of numbers that depends on the numbers, and no run of it replays.
Putting in a node takes one link out and puts two in its place. The link
from a to b carrying weight w becomes a link from
a to a brand new node at weight one, and a link from that node to
b at weight w. There is no third state anywhere in which a link
is present but switched off. The old link is gone, its number goes with it, and two new
numbers arrive.
The split is not silent, and it is honest to say so. The old link handed b a
contribution of w × v(a). The new pair hands it
w × tanh(v(a)), because the node in the middle is a hidden node and
hidden nodes are squashed. For a small v(a) those are nearly the same number
and for a large one they are not, so a lineage that grows a node has had something done to
it and will be selected on the result like everything else.
// internal/gene/grow.go
// Grow is the structural pass: four numbers off the stream, always, and
// at most one new link and one new node out of them.
func (w Growth) Grow(g *Genome, m *Mint, s *rand.Rand) Grew {
var x Grew
joinIt, where := s.Float64(), s.Float64()
splitIt, which := s.Float64(), s.Float64()
x.Draws = 4
gr := g.Wire
if gr == nil {
return x
}
if joinIt < w.Link && len(gr.Links) < MaxLinks {
if open := gr.Open(); len(open) > 0 {
p := open[int(where*float64(len(open)))]
x.From, x.To = p[0], p[1]
switch {
case gr.Linked(p[0], p[1]):
x.Busy = true
case gr.Reaches(p[1], p[0]):
x.Loop = true
default:
gr.Join(p[0], p[1], Fresh, m.Link(p[0], p[1]))
x.Joined = true
}
}
}
if splitIt < w.Node && gr.Hidden() < MaxHidden && len(gr.Links) > 0 && len(gr.Links) < MaxLinks {
i := int(which * float64(len(gr.Links)))
l := gr.Cut(i)
id := m.Node(l.Innov)
gr.Grow(id)
gr.Join(l.From, id, Fresh, m.Link(l.From, id))
gr.Join(id, l.To, l.W, m.Link(id, l.To))
x.Split, x.Cut, x.Node = true, l.Innov, id
}
return x
}All four numbers are drawn on the first two lines, before anything is looked at. Written the natural way, with the second draw taken only when the first says yes, this function would spend anything between nought and four numbers a birth and the count would depend on the answers. That is the one thing this volume's streams may not do, and it is a two-line saving against a whole class of run that cannot be reproduced.
$ go run ./cmd/nodes -mode grow
nodes: one lineage, 2000 births, four numbers off stream 19 in every one of them
it opens with 38 nodes, 192 links and 192 legal pairs, every one of them joined,
so until something puts a node in, an added link has nowhere to go
the first 8 births that did anything at all
birth nodes links what the four numbers did genes
127 39 193 node 230 into link 172 217
139 40 194 node 233 into link 49 219
143 41 195 node 236 into link 161 221
155 42 196 node 239 into link 198 223
214 42 197 joined 19 to 230 224
290 43 198 node 243 into link 41 226
309 44 199 node 246 into link 129 228
321 45 200 node 249 into link 119 230
after 2000 births of one line
hidden nodes 32
links 290
pairs a link may now join 2400
the MIND block 328 numbers
the whole genome 345 numbers
a birth of this genome now costs 1043 numbers
numbers the counter handed out 354
numbers it handed out twice 0
the same 2000 births at the rates this book ships and at nothing at all
growing not
numbers off stream 19 8000 8000
hidden nodes at the end 32 0
links at the end 290 192
the genome at the end 345 215
two creatures putting a node into link 100, on one tick and on two
on one tick node 230 and node 230, links [231 232] and [231 232]: the same change, the same numbers
on two ticks node 230 and node 233, links [231 232] and [234 235]: the same change, two names for it
The second line of that run is a prediction the first table then confirms. An opening graph has exactly 192 legal pairs and all 192 of them are already joined, so for as long as a lineage has no hidden node, the add-link operator fires at its stated rate and achieves precisely nothing. Add-link runs at one birth in twenty and the first thing that ever happens to this line is a split, at birth 127. The first added link waits until birth 214, and it goes from input 19 to node 230, which is a node that did not exist until birth 127. Every wiring in this world that is not the opening one is downstream of a split.
Both ceilings show up in that run. The hidden nodes reach 32 and stop, the legal pairs climb from 192 to 2,400, and the links reach 290 of the 512 allowed. And the two rate settings spend exactly the same 8,000 numbers off stream 19, so a run that grows nothing and a run that grows freely read the same stream in the same places and differ only in what came out.
Innovation numbers in the archive
Numbers come from one counter for the whole run. It starts above the fixed nodes, so the first number it hands out cannot be read as an input or an output, and it only ever goes up. A number is a name, and a name handed out twice for two different things names nothing.
Beside the counter sits a table, and the table is emptied every tick. Two creatures on one tick that both put a node into link 100 have made the same change to their wiring, and when a descendant of one meets a descendant of the other the two links ought to line up rather than be treated as strangers. The table is what makes them line up: it remembers what has been minted on the tick now being worked, so the second creature is handed the number the first was given.
Two creatures that make the same change a thousand ticks apart are a different case, and this world says so: they are two lineages that arrived at one wiring separately, and one name for both folds two unrelated histories into a single gene on the strength of nothing measured. A table that lived for the whole run would do exactly that, and would read as the tidier design. The run above shows both ends: on one tick, node 230 both times and links 231 and 232 both times; a tick apart, node 230 against node 233.
Graph crossover
The crossing chapter matched genes by where they sat. Gene seven of one parent crossed with gene seven of the other, because a person wrote down what gene seven of the body block means, and because two flat rows of 378 weights were the same 378 slots in the same order for every animal alive.
Neither half of that survives a graph. Two lineages a few hundred births apart hold different numbers of links in different orders, and the fortieth link of one is a connection between two nodes the other has never held. Crossing by position would take a link between an eye and a middle node from one parent and write its weight onto a link between a belly and an output in the other. The link numbers exist for exactly this moment.
Links both parents carry, matched by number, take one draw apiece and the draw says whose weight the child gets. Links only one parent carries cannot be settled by a coin, because half a wiring is not a wiring: they come whole from one parent, and that parent is the one holding the larger store at the moment of the birth, ties going to whichever of the two the roster reaches first.
The store is doing the work a fitness score does in a bench, and it is a ledger and not an opinion: it is what the animal has left after everything it has eaten and everything it has spent. It is also the only comparison of two creatures anywhere in this valley, and it decides one thing only, which is whose spare parts a child gets.
// internal/gene/weave.go
// That rule has a consequence the page is built on. The child's links
// are always a subset of one parent's links: the matched ones are in
// both, and the unmatched ones all come from the same place. A subset
// of a graph with no loop in it has no loop in it, so a child of two
// feed-forward parents is feed-forward without anything checking.
func Weave(a, b *Genome, sex float64, s *rand.Rand, theirs bool) (*Genome, Knit) {
var k Knit
k.Two = s.Float64() < sex
k.Draws++
g := a.Copy()
ga, gb := g.Wire, b.Wire
his := make(map[int]int, len(gb.Links))
for i, l := range gb.Links {
his[l.Innov] = i
}
for i, n := 0, g.Len(); i < n; i++ {
from := s.Float64()
k.Draws++
if !k.Two || from < 0.5 {
continue
}
// ... body, temper and look genes by position; a link gene by
// its number, and a draw that lands on a link the other parent
// does not carry is spent and does nothing.
}
return g, k
}$ go run ./cmd/nodes -mode cross -births 600
nodes: two lineages off one opening graph, 600 births apart
line A line B
hidden nodes 14 12
links 218 213
genes 255 248
A is the parent of record and the unmatched links come from A
links both of them carry 168
links only A carries 50
links only B carries 45
links the child was given 218
of those, ones taken whole from B 0
the child's hidden nodes 14
numbers the crossing spent 256, which is 1 and A's 255 genes
the child has no loop in it yes
A is the parent of record and the unmatched links come from B
links both of them carry 168
links only A carries 50
links only B carries 45
links the child was given 213
of those, ones taken whole from B 45
the child's hidden nodes 12
numbers the crossing spent 256, which is 1 and A's 255 genes
the child has no loop in it yes
a genome crossed with itself, which is what a one-parent birth is
genes that came back different 0
links, nodes, numbers 218, 14, 256
Six hundred births apart, the two lines still hold 168 links in common out of 218 and 213, which are the opening links neither of them ever split and the handful of splits that happened on a tick they shared. Fifty of A's links and forty-five of B's have no counterpart at all, and those are the genes a coin cannot be tossed over.
The two blocks are the same crossing run twice with one bit changed, and they say what that bit buys. When A's unmatched links carry, the child holds 218 links and A's fourteen hidden nodes. When B's carry, it holds 213 and B's twelve. Both spend the same 256 numbers, which is one plus A's own gene count and has nothing to do with what B is holding; both come back with a wiring that runs. And the last block is the one-parent birth: a genome woven with itself hands back that genome with not one gene different, with all 256 numbers spent regardless.
$ go test -count=1 ./internal/gene/ -run 'GrowingSpends|WeavingTwo|WeavingAGenome|OneNumberPer' -v
=== RUN TestGrowingSpendsFourNumbersWhateverItDoes
--- PASS: TestGrowingSpendsFourNumbersWhateverItDoes (0.02s)
=== RUN TestWeavingTwoGrownGraphsStaysFeedForward
--- PASS: TestWeavingTwoGrownGraphsStaysFeedForward (0.00s)
=== RUN TestWeavingAGenomeWithItselfHandsItBack
--- PASS: TestWeavingAGenomeWithItselfHandsItBack (0.00s)
=== RUN TestOneNumberPerChangePerTick
--- PASS: TestOneNumberPerChangePerTick (0.00s)
PASS
ok theworld/internal/gene 0.027s
The first runs three hundred births at three rates off one seed and demands all three generators finish at the same place in the sequence. The second grows two lineages four hundred births apart off a shared counter, crosses them both ways round, and runs the child, which is the only test feed-forwardness needs: a graph with a loop in it has no order its nodes can be worked out in, so it panics instead of answering. The third is the identity crossing. The fourth asks the counter for the same change twice on one tick and twice on two.
Limits of the first graph run
A design that grows connections can be built with a great deal more machinery than this one has, and the reductions here are all deliberate. Six of them are named below, each with what it costs.
No link may run backwards. Every link goes towards the outputs, a link that would close a loop is refused before it is made, and the whole of the working order falls out of that. The cost is real and has to stay visible: a controller with a link running back into itself remembers something from the last tick, and one without has no memory whatever. Every animal in this valley meets each tick knowing exactly nothing about the one before it, and no amount of growing changes that.
No evolved squash. A hidden node is tanh and an output node is bare, and nothing anywhere can change either. A gene naming which of four curves a node runs is easy to add and expensive underneath: the squash chapter's finding was that any bend at all does the one job a middle has, and that where a curve's floor and ceiling sit is what every weight downstream of it gets set against. Move that gene and every weight below the node is mis-set at once, which is a large change wearing the clothes of a small one.
No switching a link off. A split takes its link out rather than disabling it. Keeping a disabled link means every genome carries genes that do nothing, every crossing has to decide whether the child's copy is on or off, and the count of numbers a birth spends stops matching the count of numbers that do anything. What is lost is the ability to switch a connection back on later, which this world instead does the slow way, by growing it again under a new number.
No shared score inside a group. A common protection for a new arrangement is to have members of a group divide a score between them, so an innovation is judged against its own kind rather than against the whole population in the generation it appears. There is no score in this valley to share. What a young lineage has instead is the ground: the terrarium cut pockets and refuges into this rim for reasons of its own, and an animal in one of them is competing with whatever else is in it.
No retiring a group that has stopped improving. Rules that close a lineage after so many generations without a better score need a score and a notion of a group, and this valley has neither. A lineage here ends when the last animal in it fails to put the price of a child into its store, which is a fact about food and not a scheduled cull.
No champion carried through in the valley. The bench carries its best genome into the next generation untouched, and it can, because it keeps a score and can name a best. Nothing in the valley ranks two animals, so nothing is carried: an animal that stops paying for children leaves nothing behind however good anybody thought it was. A champion needs a board, and the valley has no board.
The 20-year graph-controller run
Everything above is arithmetic on a bench. Putting it in a valley takes three joins and no
new rules. A pool that holds a counter is a wired pool and grows its children; a pool
without one runs the flat row and leaves stream 19 untouched, so every run made before
this page still reads the numbers it always read. A founding creature is handed an opening
graph with its 198 numbers off stream 14 instead of a network with 378. And a creature
driven by a graph is driven by a second implementation of the one method that has always
stood between an animal and whatever decides for it: twenty-four numbers in, one action
out. The crossing is the first of those three seen from the other side and is the same
if: a wired pool weaves by innovation number and hands the unmatched links
to whichever parent has the larger store — ties settled by p.mateAt,
the second parent's own place in the roster, which suitor writes down as it
picks — and a flat one crosses by index the way the crossing page wrote it. Both spend one number plus one a gene, so the branch changes what
a child is made of and not how much of any stream was read to make it.
// internal/gene/birth.go — inside Pool.Breed, where the child is made
// The parent whose unmatched links a child inherits is the one
// holding the larger store at the moment of the birth, ties to
// whichever of the two the roster reaches first. It is the
// closest thing to a comparison of two creatures anywhere in
// this valley, and what it compares is a ledger and not a
// score.
var kid *Genome
var spent int
if p.Names != nil {
theirs := mate != nil && (mate.Store > b.Store ||
(mate.Store == b.Store && p.mateAt < i))
var x Knit
kid, x = Weave(g, with, p.Sex, p.mix, theirs)
spent = x.Draws
} else {
var x Mix
kid, x = Cross(g, with, p.Sex, p.mix)
spent = x.Draws
}
p.Mixes += spent// internal/gene/birth.go — inside Pool.Breed
// The shape of the controller, off stream 19, between the copy
// and the placement. A pool with no counter spends nothing
// here and the stream stands untouched.
if p.Names != nil {
p.Names.Now(v.Now)
w := p.Grow.Grow(kid, p.Names, p.grow)
p.Grows += w.Draws
if w.Joined {
p.Joined++
}
if w.Split {
p.Splits++
}
}// internal/gene/head.go
// Head is a graph wired into a creature at both ends, and it is the
// second driver this world has. The first one holds a three-row
// network and is untouched by everything in this volume.
//
// Two drivers rather than one changed driver, because the seam between
// a creature and whatever decides for it is one method taking one row
// and handing back one action. A seam like that is worth having only if
// something eventually arrives on the other side of it that the first
// thing through it did not anticipate, and a controller with a
// different number of inputs and no rows at all is that thing.
type Head struct {
Graph *mind.Graph
Self *beast.Beast
Here *beast.View
// ...
row Row
out []float64
}$ go run ./cmd/nodes -mode herd -years 20 -every 4
nodes: 16x12 valley, tick 901, year 1 summer, 90 plants standing at 4654.1 grams
25 creatures founded on stream 12, each driven by an opening graph
of 192 links and 6 biases, its numbers off stream 14
a cell of ground carries one body: yes
a birth adds a link 0.05 of the time and a node 0.02 of the time
year alive born joined split hidden links genes numbers
2 9 16 0 0 0.00 192.0 215.0 33956
3 12 37 0 4 0.00 192.0 215.0 148884
4 12 71 0 7 0.00 192.0 215.0 233121
5 12 102 1 14 0.00 192.0 215.0 395155
9 8 344 1 88 0.00 192.0 215.0 2768355
13 187 1198 40 876 0.20 192.2 215.4 27616436
17 236 1875 85 1605 0.19 192.2 215.4 51942400
21 241 2060 130 1940 0.21 192.2 215.4 62333475
25 founded, 2060 born, 1844 struck off, 241 still walking after 71550 ticks
95291 creatures were asked for a child: 2060 made one, 14068 could not pay for it
and 79163 had nowhere to put it
of the 95291 children described, 130 were given a link and 1940 had a node put in
the counter handed out 6142 numbers, 4608 of them to a second creature on one tick
the pass spent 62333475 numbers, and there is no longer one price for a birth:
it is 8 plus three times the genes of whichever parent is being asked
the controllers walking about at the end
the opening graph, unchanged 193
one hidden node 46
two hidden nodes 2
links in the widest of them 194
the living creature whose controller has grown furthest
which one it was 1724
generations from a founder 41
the tick it was born on 50819
hidden nodes 2
links 194
genes in its whole genome 219
a birth of it would cost 665 numbers
the numbers of its hidden nodes [4013 4628]
71550 ticks in 35.938s, 1991 ticks a second (measured here; yours will differ)
The four columns in the middle are the ones this page is about. Nothing grows at all in the first year, because twenty-five animals on an empty ground make sixteen children between them and sixteen births is not enough for a one-in-fifty event; the first four splits land in the third year; and by the twenty-first, 1,940 of the children this pass described have had a node put in and 130 have been given a link. The ratio between those two is the opening graph's doing all over again: add-link fires two and a half times as often as add-node and lands on a pair that is already joined almost every time, because most of the animals asking are still carrying a graph whose 192 pairs are its only 192 pairs.
The hidden column is a mean over everything walking, and 0.21 of a node an
animal sounds like nothing until the table underneath breaks it apart. Of the 241 alive
at the end, 193 are still carrying the graph their founding lineage opened with, 46 have
grown one hidden node, and two have grown two. About a fifth of the valley is running a
controller no founder had, twenty years in, on a ground that started with twenty-five
animals and a rule that a cell carries one body. The line under the table is thirty-six
seconds of an eight-core Ryzen 7 3700X and is the only number in the run that belongs to
a machine rather than to the world; it is why the label on it says so.
Creature 1724 is the far end of that. It was born on tick 50,819, forty-one generations from a founder, and it carries two hidden nodes numbered 4013 and 4628. Read those two numbers as what they are: 4013 was minted on the tick some ancestor of this animal split a link, and 4628 six hundred and fifteen numbers later, and any other animal in The Hollow carrying 4013 got it from the same event, because that is what a number is for. A birth of this creature costs 665 numbers where a birth of its cousin with the opening graph costs 653.
The counter handed out 6,142 numbers over the twenty years and 4,608 of them went to a second creature on the same tick. Three quarters of every structural change in this valley was made simultaneously by somebody else, which is what happens when ninety-five thousand asks are packed into seventy-one thousand ticks; and every one of those pairs will line up when their descendants meet, instead of looking like two strangers to each other.
Why innovation numbers align links
Strip the valley out and the mechanism generalises past controllers entirely. Any time two structures that have been changed independently have to be combined, the combining is only as good as the correspondence between their parts, and there are two ways to get one. Compare the parts afterwards and guess which is which, which needs a notion of similarity somebody has to write down and defend. Or record the correspondence at the moment the parts are made, when it is free and certain. A number on a link is the second: one integer a link, minted where the change happens, turning a hard matching problem into a lookup.
What none of it buys is any promise that a bigger controller is a better one. The valley above holds 193 animals that never grew anything and 48 that did, and nothing on this page says which of those two groups is doing better. Growing is a thing the copies can now do, and whether any particular instance of it was paid for is the ledger's business and the ledger's alone.
- Given a three-row network's four weight blocks, You can write out the equivalent graph node by node and link by link, and say which node number each hidden neuron gets.
- You can state the accumulation rule in one sentence and explain why reversing a link list changes 4,825 of six thousand answers while changing nothing about the controller.
- You can say why an opening graph's add-link operator fires at its stated rate and achieves nothing until a node has been put in somewhere.
- You can explain why the eight unread inputs have to exist in the first graph rather than being added when something wants them, in terms of what a link's number is minted against.
- Handed two grown graphs and told which parent holds the larger store, You can name the child's link count before running the crossing, and say why the child cannot contain a loop.
- You can say what the per-tick table does, what a table that never emptied would claim instead, and why that claim is not one this world can support.
Exercise 1 — grow the same lineage with the node operator switched
off. Add-link has the higher rate of the two and can achieve nothing on an
opening graph. Predict what two thousand births come to when it is the only operator
left running, then edit Often in
internal/gene/grow.go to Growth{Link: 0.05} and run
go run ./cmd/nodes -mode grow.
Nothing at all happens, for two thousand births in a row. The genome stays at 215 genes, the graph stays at 192 links and 38 nodes, and the run still spends its 8,000 numbers off stream 19. The table of the first eight births that did anything is empty, because there were none.
That is the strongest form of the point the run on the page makes in passing. The
two operators are not two independent ways of growing: one of them opens the door
and the other walks through it. Then try
Growth{Link: 0.05, Node: 0.005}, which opens the door a quarter as
often and gets the same lineage to 14 hidden nodes and 245 links over the same two
thousand births, against 32 and 290 at the rate the book ships.
Exercise 2 — cross two lineages that differ by one split. The
run on the page crossed two lines six hundred births apart. Predict the matched and
unmatched counts at sixty, then run
go run ./cmd/nodes -mode cross -births 60.
Line A is still carrying its opening graph, 192 links and no hidden node. Line B has had exactly one split: 193 links and one hidden node. The counts underneath are 191 matched, one link only A carries, and two only B carries, which are the three genes one split makes. The link B took out is a link A still has; the two B put in its place are links A has never held.
So the two blocks of the run are the smallest possible statement of the whole rule. Whoever holds the larger store decides one thing: whether the child comes out with 192 links and no hidden node or 193 links and one. There is no third answer where it gets the new node and not the links into it, and that is why unmatched genes are never settled by a coin.
Exercise 3 — take the ceilings off. The graph is held to 32
hidden nodes and 512 links by two constants. Predict where two thousand births of one
lineage end up with MaxHidden raised to 200, then edit it in
internal/gene/grow.go and run
go run ./cmd/nodes -mode grow.
The lineage reaches 44 hidden nodes and 305 links, not the two hundred the ceiling now allows, and that gap is the interesting part. Two thousand births at one node in fifty is forty splits expected and forty-four is what it gets, so the ceiling of 32 was only just binding. Raising it produces no runaway at all, because nothing here pays a controller for being large and the rate is the only thing setting the size.
Then look at the second number in that run: the pairs a link may join. At 32 hidden nodes it is 2,400; at 44 it is 3,756, and it grows roughly as the square of the node count. The add-link operator picks one pair out of that list per birth, so the larger a graph gets the less likely any particular useful connection is to be the one drawn. Growing gets harder as it goes, without anybody making it harder.
A controller is now a thing with parts that can be counted, named and inherited separately, and the valley above grew forty-eight of them that no founding put there. What none of them grew towards is anything new to look at. Every one of those 241 animals is reading the same twenty-four numbers its ancestors read, off nine rays, two gradients and two readings it takes off itself, and the eight columns past them are still standing at nothing on every tick, wired to every graph in the valley and multiplied by zero in every pass. The machinery for a lineage to grow a connection to any of them is finished and switched on, and what is on the other end of those eight wires is a question this valley has not answered.