#What this document and chat are about

This document systematizes interesting information on the following topics:

• Evolution simulation
• Artificial life
• Neural networks
• Cellular automata
• Artificial intelligence

Goal: to expand your mind, get inspired and write your own simulation of life, of evolution, or of something whose study brings us closer to creating General/Strong AI. Or just to write one for educational purposes.

It is built on the same principle as the 4D (in Russian) and hyperbolic (in Russian) repositories: there is a chat where these topics are discussed and interesting materials are posted, and then they are systematized into a document like this on GitHub.

Chat: telegram:emergevolution (in Russian)

Everyone interested is invited to the chat to discuss these topics, and to criticize and improve this document.

How you can improve it:

• Suggest new material
• Add comments and analysis to the existing material (for example, analyze an article, a video, a program). You can see that comments are lacking in many places here. You can take on this work if you're interested in figuring something out.
• Create comparison tables (for libraries, for different simulations)

There are also two trends in writing artificial life simulations:

• Focusing on the individual creature, so that it is as smart as possible
• Focusing on the ecosystem: it doesn't matter if the creature ends up dumb, what matters is that the interaction of many of them is interesting

This chat is more about the evolution of the individual creature. This poll (in Russian) shows it.

Almost all pictures here are clickable: sometimes they show that it's a YouTube video, sometimes they lead to a website.

#What is Emergevolution?

#²Etymology

The word was coined by optozorax from two words: emergence and evolution. He first learned the word "emergence" from this video:

Wikipedia says: Emergence in systems theory is the appearance in a system of properties that its elements don't have on their own; the irreducibility of a system's properties to the sum of the properties of its components.

#²The problem

All evolution simulations known to the author have the property that they converge to some single solution and can't grow endlessly in complexity and in the diversity of their forms, the way it happens in real life and in nature on Earth.

And this is very sad, because even with huge computing power we can't just run some evolution simulation program, wait a couple of years and get very interesting results: no such programs are known to exist.

That's why the author is concerned with the problem of getting an evolution simulation that can grow potentially forever, constantly making its creatures more complex.

And it's this endlessly growing evolution that he called emergevolution.

He wants to create it at least in order to explore it and see what comes out; potentially it could help us understand our own evolution and the development of intelligence.

Below are examples of how different authors define it in their own way:

---

This term was coined long before the author of this document; there's even a Wikipedia page: Emergent evolution. Only they describe it not as a type of evolution, but as a hypothesis about the origin of the mind.

---

The PostNauka video says:

Even though artificial life has achieved such successes over this time, the main problem it faced still remains unsolved: the problem of how the complexity of organisms can increase in the course of evolution.

---

It's also called Open-Ended Evolution. You can probably search for scientific papers under this name and publish your own.

The evolvingai.org website defines this term as:

Creating computational evolutionary processes that--like natural evolution--endlessly produce a diversity of complex, interesting things.

---

At the 17th minute of the video about the Tierra program, its author says that he also wants to create an evolution that becomes endlessly more complex.

#Artificial life, evolution simulation

#²Table

Turbo means that the simulation can be run without visualization, so it isn't limited by how fast the screen can refresh and no resources are spent on drawing the picture. You can read about this problem here.

	Visualization	Optimization method	Task	Video	Source code	Executable	Brains	Turbo	Creatures are made of
Tierra	-	Natural selection	Survive	+	+	+	Program	?	RAM
The Blind Watchmaker	2D	Genetic algorithm	Tell the time	+	+	-	-	-	Clocks
Evolution with muscles	2D	Genetic algorithm	Walk, jump	+	+	web	Neural network	-	Hinged rectangles
Fighting circles	2D	Genetic algorithm	Defeat the opponent	+	-	-	Neural network	-	Circles with bullets
Cars with arbitrary neural networks	2D	Evolutionary algorithm	Drive the track	+	-	-	Neural network	-	Cars
Learn 2D Stick	2D	Genetic algorithm	Walk, jump	+	-	+	Neural network	+	Hinged rectangles
foo52ru bots	2D	Natural selection	Survive	+	+	-	Program	-	Square cells
foo52ru trees	2D	Natural selection	Survive	+	+	-	-	-	Square cells
foo52ru snakes	2D	Manual, Natural selection	Survive, win	+	+	-	Neural network	-	Square cells
SnakeAI	2D	Genetic algorithm	Win	+	+	-	Neural network		Square cells
Tallensy evolution	2D	Genetic algorithm	Drive the track	-	-	+	-	-	Hexagons with wheels
Amoebas	2D	Genetic algorithm	Defeat the opponent	-	-	+	Program with genes	+	Amoebas
gencar.co	2D	Genetic algorithm	Drive the track	-	+	web	-	+	Cars with a changeable body
Cephalopods	2D	Genetic algorithm	Eat more food	-	+	web	Spiking neural network	+	Octopus-like
Evolved Virtual Creatures	3D	Genetic algorithm	Walk, jump, fight, swim	+	-	-	Skiping neural network	-	Hinged rectangles, 3D
Flexible Muscle-Based Locomotion for Bipedal Creatures	3D	CMA-ES	Walk	+	-	-	?	-	Rectangles with muscles
Onigiri	3D	Genetic algorithm	Walk	+	+	-	Neural network	?	Hinged rectangles
Framsticks	3D	?		?	?	?	?	?	?
Polyworld	3D	Natural selection	Survive	+	+	-	Neural network	?	Hinged rectangles

#²Without visualization

#³Tierra

Tierra is one of the very first artificial life simulations, in which parasites and complex forms emerged.

Project page.

A 244-page document about this program.

An executable for Windows. Versions for other platforms (and the source code) are on the official website. This is just a copy.

How the program works: there's an operating system that handles:

• Memory management
• Allocating computation time to each creature
• Counting deaths and births
• A bank of successful genomes
• Automated ecological analysis

And the programs of this operating system are the creatures.

TODO figure out how this works, because it's some seriously hardcore work that became the starting point for a lot of things

#²2D

#³The Blind Watchmaker

A video (in Russian) originally made as a dig at religious believers, but we're interested in it for its evolution simulation. What's notable here is that this simulation differs from all the others in what its creatures are made of. It also shows very well the graphs of how different types of creatures develop.

Unfortunately, a lot of things here are murky:

• The selection criteria are unclear
• Little is explained
• The source code is written in MATLAB, of all things

#³Evolution with muscles

You can run it on the official website.

How the creature is controlled: by a neural network with fully connected layers. The number of layers can be adjusted.

Inputs:

• Distance from the ground to the creature
• Current speed
• Angular velocity
• Number of points touching the ground
• Average rotation angle of all body parts
• An eye that sees distance with a single ray

Outputs:

• Control of each muscle, a value from -1 to 1
• Changing the direction of the eye

Training method: genetic algorithm

Has a fast-forward mode: no.

The creature's shape can be modified: yes.

Inspired by Karl Sims: yes.

×1
png

#³Fighting circles

Everything is clear from the video (there are no Russian subtitles, so learn English!). Here's what isn't said in the video but is said on the project's official website, with the French put through Google Translate:

The ranking system, and therefore the corresponding scoring, is a tournament system (everyone plays against everyone else), where each player gets 3 points for a match won, 1 for a draw and 0 for a loss.

The selection algorithm used is the "roulette wheel".

How the creature is controlled: by a neural network with 2 fully connected layers. The number of layers can be adjusted.

Inputs:

• The presence of an enemy in its field of view
• The presence of a cannonball in its field of view
• Whether it has already fired a missile or not
• The width (in radians) of its field of view

Outputs:

• Go straight
• Turn left
• Turn right
• Shoot
• Change the field of view

Training method: genetic algorithm

#³Cars with arbitrary neural networks

Here the video shows the car's current neural network right on screen: you can see that the inputs are the distances from the eyes, and the outputs are the speed and the steering angle.

You can also notice that the network isn't the usual perceptron, but has some arbitrary structure where, it seems, loops form.

In the end, the cars learn to drive themselves perfectly.

There's an article about "arbitrary neural networks".

#³Learn 2D Stick

Here we have creatures made of lines with muscles that learn to walk, jump, etc.

How the creature is controlled: by a neural network.

Training method: genetic algorithm

Has a fast-forward mode: yes.

The creature's shape can be modified: yes.

The program has a rich interface and tons of settings; it's probably the most advanced of all the ones presented here. Here's a video this program can generate.

You can download it here.

#³foo52ru

foo52ru is the nickname of the author in this section.

What sets this author apart from the others is his independence and original ideas. Usually people steal ideas from each other and use neural networks where they aren't needed, but this author comes up with unusual ideas himself. He has an interesting old-school style.

This author is more interested in artificial life based on square cells precisely as life, which can have interesting creatures occupying different niches.

He created the Cyberbiology group (in Russian), where people publish their work, and there's a chat of like-minded people.

#³Living square cells

His first and main work (in Russian):

In the video above, no evolution algorithm or genetic algorithm is programmed directly; it arises automatically thanks to the environment. This is called "natural selection".

He uses square "bots" whose behavior is programmed by a program made of numbers. The program is an assembly-like language, and a mutation can change a random instruction. The bots have to collect food and survive next to each other and under a harsh environment. Whether a genome is good or bad is decided by natural selection.

There are sequels to this life:

This material is also available as an article on Habr (in Russian).

This is what this world looks like:

And this is the same world, but showing the amount of energy:

#⁴Tree simulation

Lately he's been working on a simulation of life based on trees.

This material is also available in text form on Yandex Zen (in Russian).

#⁴Snake evolution

#³SnakeAI

The author trains a neural network to play Snake. The inputs are vision signals: the distance to food, to a wall and to its own body; 24 inputs in total. The output is simply which direction to move in.

The network is an ordinary fully connected perceptron.

It's trained with a genetic algorithm.

The source code and the same thing in text form are in the repository: github.com/greerviau/SnakeAI.

#⁴Snake problems

The problem with almost all implementations of snake evolution is that the snake can't remember where it has been before and what shape it has arranged its body into. That means it arranges its body either to get to the food as quickly as possible, or according to a single pattern. But it's unlikely to arrange its body sensibly enough once it has eaten too much food and its body takes up 90% of the board. You can see how a snake should ideally play here:

A simple memoryless neural network can't win like that.

One way to solve this problem is to feed a much larger amount of state into the input, for example a larger area of the board. That way the network can learn the complex patterns it forms itself and how to deal with them. For example, this is how foo52ru did it.

Another way is to directly give the network the ability to remember, or to plan steps in its head, or to use Monte Carlo Tree Search, but nobody has done that yet.

#³Tallensy evolution

Tallensy evolution for Android, plus version 2.0. It doesn't work on newer versions of Android. Here cars made of hexagons and wheels evolve; hexagons of different colors have different functions. Only the shape evolves: the cars have no brain and always drive forward. The goal of evolution is to build a car that gets the farthest on this winding road. The road is very short, so they quickly come up with a decent car.

Hexagon types:

• Green ones generate energy
• White ones store excess energy
• Purple ones push the car when it gets stuck
• Green ones give speed

#³Amoebas

TODO

#³gencar.co

TODO describe

#³Cephalopods

×1
png

An article about it.

The creatures' task: simply to move forward as fast as possible.

Unfortunately, the creatures in this simulation have no sensors at all; they can't sense anything. So at the beginning they can't afford the slightest mistake if they are to go perfectly forward, because afterwards a creature won't be able to correct its trajectory or realize that it has gone off course.

#⁴Ideas for development

There are a couple of ideas for how this could be developed:

• Give them the ability to sense the density of the particles around them, where the closer the particles, the stronger the density.
• Similarly, a sense of the density of surrounding enemies
• The density works over 360 degrees. You could dedicate 36 neurons to it, for example

And give them more time on the field, so that they manage to eat these particles and take into account where the enemies go, in order to collect as many as possible

And then test this on different fields:

• like on that website, where the field has one center
• where there are several centers
• where everything is spread evenly

Or you could make two rings of density sensing at different distances, feed them to the creature, so that it learns to tell the distance to objects from them. Then we connect a separate neural network that moves in the given direction, visualize this direction and see at a high level what the neural network wants!

#²3D

#³Karl Sims' work

A masterpiece made in 1994! optozorax wrote a review of this work, where you can find links to the originals and lots of ideas for improving it:

Evolved Virtual Creatures

MUST READ!

#³Flexible Muscle-Based Locomotion for Bipedal Creatures

A classic. Here an evolutionary algorithm is used to find muscle control for these complex creatures that makes them walk beautifully and stably. The CMA-ES algorithm is used to search for the optimal solution.

This work is very interesting because they use lots of muscles, and their creatures move very realistically. You could try reading their paper and using it for your own artificial life simulation.

This is exactly where that famous meme comes from, the one where a big cube is thrown at a walking person:

The paper where all this is described in more detail. They used the CMA-ES algorithm, which promises to be really cool.

#³Onigiri

Onigiri is a YouTube author. In these videos (in Russian) he trains creatures made of rectangles and gives them the task of moving forward. He uses neural networks for the creatures.

What's interesting is that his evolution started working better when he added crossover.

#³Framsticks

×1
jpg

TODO study

#³Polyworld

Creatures similar to the ones in Karl Sims' video. They were put together in one place to try to survive. That is, their development was left to natural selection. It was inspired by Karl Sims' work.

In theory, the creatures here should come up with complex behavior. The results are sad: no complex behavior emerged, the complexity of the brain eventually converged to some limit, and in the video itself the author seriously raises this issue.

#About evolution in general

#²Comic

×1
png

A fairly simple but big comic (in Russian) that explains well how the eye could potentially have arisen, and shows evidence for evolution that has already been observed.

MUST READ!

#²The Evolution of Trust

A game that shows how trust develops between people; it uses a lot of visualization of this process and explains it with game theory.

×1
png

#²Diversity in the real world

A quote from a chat member:

Even in practice, people who breed feeder insects themselves (cockroaches, crickets) for their pets find that after a few generations they become weak, unless you "mix in blood" from other populations

An article about the population bottleneck.

It would be interesting to understand why diversity within a species doesn't play the same role in our programs as it does in the evolution of living things on our planet. Apparently the main thing about reality is that there are tons of different genes, and the adaptability of a species depends on their diversity. In computer programs, on the other hand, we usually have one big gene, and cutting the population down to the best 1% doesn't affect the overall result at all.

It would also be interesting to understand how to write an evolution simulation in which gene diversity gives a boost to survival.

#²Why real evolution manages to adapt so easily

×1
jpg

The gist of the article: evolution in the real world makes its creatures redundant; they have too much "extra" stuff, which lets them adapt quickly to changing conditions.

#About artificial life in general

#²PostNauka video

In this video (in Russian), the speaker mentions two interesting things:

1. Von Neumann's cellular automaton, which can self-replicate (?).
2. Tierra - a program about taking over RAM, in which parasites and complex things appeared. Made in the 90s.

#Mathematical foundations

Disclaimer: I explain this in my own words and the way I understand it myself, without trying to write it as formally and correctly as possible, so there will be assumptions in some places and simplifications in others. If you want correct information, read books. What follows is written only to introduce the topic and to form your first associations. P.S. THIS INFORMATION IS PROVIDED "AS IS" AND ITS AUTHOR TAKES NO RESPONSIBILITY FOR IT :D

#²Derivative, gradient

The derivative of a function is an operation on a function that returns a new function; the new function shows how strongly the result of the function changes as a given variable changes. For more, see Wikipedia.

You can take the derivative only of a function that returns a real number (well, or a complex one, etc., but not a discrete one, not a natural number). You can also take the derivative with respect to different variables of a function, but only those that are real numbers. This is called a partial derivative.

Let's say we have a function: run_simulation(alpha, beta, genome) -> score. It shows how many points a creature will earn with the real-number parameters alpha and beta, and with genome, which is not a real number but a set of bits. genome defines some discrete structure of the creature, for example the number of layers and the number of neurons in each layer, all of it laid out in bits, say. The function returns a single real number: the creature's fitness score in this world. The bigger this number, the better.

Let's try to take the partial derivative of run_simulation with respect to the variable alpha; since it is a real number, we can do that. We get the function run_simulation_d_alpha(alpha, beta, genome) -> dscore. This function shows how strongly the score will change for different values of alpha with the parameters beta and genome fixed.

The gradient is almost the same as the derivative, except that it is a vector of derivatives with respect to all possible variables. That is, the new function returns not one number but several at once, one for each parameter: run_simulation_gradient(alpha, beta, genome) -> (d_alpha_score, d_beta_score). So we take the derivative with respect to all parameters at once.

The gradient is a vector that points in the direction in which the function increases.

I didn't go into details like partial derivatives, different coordinates and Jacobian matrices, just to keep things simple. I hope you'll learn all of this yourself when you study at university.

Gradients are used very heavily in tons of optimization methods (and so in neural networks), which is why I started with them.

#²Optimization methods

An optimization method is a method that finds the minimum/maximum of a given function that returns a single number. From here on we'll say that an optimization method always looks for a minimum, because you can find a maximum through a minimum by simply putting a minus in front of the function.

That is, this method takes a function that returns a single real number and finds the parameters for which this returned number is at its minimum.

The process of finding the minimum is called optimization.

An example with our function run_simulation: an optimization method will find the parameters at which the score reaches its maximum value. And the parameters of this function are the creature's genome. So with this method we'll find the creature that best solves the task we need in the simulation.

Usually all optimization methods work with functions that take real numbers and return real numbers. So finding the optimal genome in the run_simulation function won't really work (but there's a small "but", which I'll get to later).

Also, optimization methods very often require computing gradients, which is why I started talking about them. Gradient-free optimization methods exist too, but that's a separate topic, and I'll get to it later.

An overview of optimization methods with visualizations (!).

I also tried to write out the same thing in the chat (in Russian).

#³Gradient descent

This method works with a function of many variables. You've probably heard that neural networks are trained with exactly this method.

All this method needs is a starting point and a way to compute the gradient, and it will find the minimum of a smooth function.

Wikipedia has great illustrations.

Once again: gradient descent is not some component of neural networks, it's just an optimization method that happens to perform well. In fact, neural networks can be optimized with anything: a genetic algorithm, the multidimensional Newton's method, random search, anything that can find a minimum. But it's gradient descent that works best from a practical point of view.

#³These are all local search methods

There are two kinds of optimization methods: local and global. A local method finds different minima depending on the starting point and on luck. It won't necessarily find the smallest minimum, because it simply has no information about the other hills, since it's very limited in what it computes.

A global optimization method can find all minima and choose the smallest among them. But in the general case this is exotic, so don't hope that someone will ever invent a global optimization method that is usable in practice.

Almost all optimization methods aim at finding local minima. If you want to find all possible minima and invent a global optimization method, then you'd better not open this can of worms. First, because local minima should usually be enough, and second, because you can spend way too much effort on finding all the minima and get only, say, a 10% improvement over a local one.

#²What is a neural network

Some people have this stereotype that modern neural networks are successful precisely because they take the ideas for their structure from the brains of living beings. Not really. Read, for example, the article about the perceptron, which is the basis of all modern neural networks. Does this even hypothetically resemble what happens in the brain? Of course not: there are no loops, no memory elements, it's just... something very linear.

In fact, mathematically the perceptron boils down to multiplying a matrix by a vector and applying an activation function to the vector. So neural networks are more about matrices than about separate functioning elements called neurons.

If you don't know what matrices are, just think of multiplying a matrix by a vector as a way to write down many multiplications and additions done in parallel.

And a neural network lets you easily write down an approximation of some function using numbers. For example, you have a complicated function sin(x * ln(cos(x) + 2)), and you want to approximate it on the interval [-1, 1], knowing only its values. Well, with a neural network you're guaranteed to find some numbers that approximate this function with an error of 0.0001 (or any number you like). So a neural network is a way to define a function through numbers.

Then what is a neural network that takes a picture and returns who is in it, a dog or a cat? It's an approximation of a real function (an oracle) that always correctly tells what is a dog and what is a cat. That is, we don't know the inner workings of the oracle function (and never will), but we can approximate it just by taking its inputs and outputs.

On the other hand, you can think of it this way: we don't approximate some nonexistent function from its inputs and outputs, we simply minimize a loss function, and thanks to the large number of degrees of freedom of a neural network we do it well. In the end the neural network works well enough for practical purposes.

Actually, there are a million other ways to define functions through numbers, but matrix multiplication seems the simplest and the most optimal.

One more important thought: the current success of neural networks, again, isn't a success of neural networks themselves and of taking their structure from the brains of living beings; it's a success of optimization methods and of automatic differentiation methods, which I'll talk about later.

Just look at these matrix multiplications and at finding the minimum of a function by taking the gradient. Where is the biology here? Where are the processes that actually happen in the brains of living beings? They aren't here: machine learning and "neural networks" have long been a field far removed from biology.

And in general, I think we should stop calling all this "neural networks" and explaining that a neural network consists of neurons that send signals onward, because this kind of popularization puts the emphasis in the wrong place and confuses the average person.

#²Computing the derivative and the gradient numerically

At school you learned how to take the derivative of a function whose analytic expression you know, for example: f(x) = sin(x) * cos(x^2), and f'(x) = cos(x) * cos(x^2) - 2 * x * sin(x) * sin(x^2).

But how do you take the derivative of a function whose expression you don't know, or which can't be written down at all? The numerical derivative! It's computed by definition:

f'(x) ≈ (f(x+0.00001) - f(x))/0.00001

Where 0.00001 can be replaced by any other number, depending on your needs.

So to approximately compute the derivative, you need to compute the function itself 2 times: at the original point and at a point shifted by a constant.

For our function run_simulation, this means we have to run the simulation twice!

Okay, and what if we want to compute the gradient? Well, the same thing, only for each variable. So if we want to numerically compute the gradient of a function with N parameters, we'll have to compute the function N+1 times with different parameters.

Smell that burning CPU? Now imagine we have a neural network with 400 parameters, you use this network to tell whether a picture shows a cat or a dog, and the network is being optimized to tell them apart better. Then to get the gradient we'd have to run the network on each picture 401 times! That's very bad.

#²Backpropagation for computing the gradient

Actually, just look at Wikipedia.

It's a method that lets you compute the gradients of a neural network with respect to all variables while evaluating the network only once! Sure, the method is complicated and you have to record a lot of information, but the network is still evaluated just 1 TIME!

It's precisely thanks to the invention of this method that neural networks took off and became a promising field at all. Because nobody is going to compute the gradients of a neural network of size N by evaluating the network N times.

#²Computational graph

So we've learned that for an evaluated neural network the gradients can be computed in O(1) using backpropagation.

But actually things are much better. We can do the same for any linear (and even nonlinear) computation.

To compute some formula, you can build a computational graph in advance, where traversing it in one direction in a special way gives us the values, and traversing it in the other direction in another way gives us the gradient. I won't explain how it works, just know that it works like that. For the details, see pages 69-81 of Nikolenko's book "Deep Learning" (in Russian).

In general, the process of building a computational graph and then taking derivatives through it is called automatic differentiation.

And you can compute gradients with "backpropagation" not only for neural networks but for almost anything, including simulations. For example, here's differentiable physics.

And the pictures below are just to catch your eye:

#²Noise

Most of the optimization methods here are designed for functions without noise. Gradient descent, for example. It will work well only on a smooth function, where you can always clearly see which way the slope goes. And if your function is very noisy, gradient descent will just stupidly walk in a random direction at every point and get nowhere.

To get rid of noise, people usually use all sorts of regularization, or switch to an optimization method that is designed to handle noise.

In a field like training agents, noise is the norm. So when you choose an optimization method, pay attention to this, or run experiments.

#²Other optimization methods

There are a hundred or so other methods for finding the minimum of a function. Here I'll describe the most practically useful ones, and also just so that you know they exist.

#³Newton's method

This method requires computing the Hessian matrix, which consists of second partial derivatives and has size NxN. So if your neural network has 1 000 000 parameters, the matrix has to be of size 10^12. Which is a bit much. And computing all of it takes a very long time.

But on the upside, it converges in fewer iterations than gradient descent, and it finds the direction to move in much more stably.

For small problems you can quite well use it, if you're too lazy to figure out why gradient descent doesn't converge.

#³Quasi-Newton methods

These methods let you avoid storing and computing the Hessian matrix; instead they use an approximation of it, sometimes storing it, sometimes not. To do this, they use only information about the gradients.

An example of such a method: BFGS.

If you don't want to deal with tuning gradient descent, you'd better use BFGS; Newton's method, who needs it.

#³Bayesian optimization

This is a global search method that tries to use the minimum number of function evaluations to get the maximum of information.

Just look at the GIF of how this method works in this repository. All the other information is also there, and I see no point in retelling it.

#³CMA-ES

A very promising algorithm for optimizing problems where we don't know the gradient and there's a lot of noise. It works on parameters that are real numbers.

The paper.

A page with tutorials and source code in different languages.

Slides from the video above.

From the slides, you can tell that the algorithm is based on a multivariate normal distribution and, depending on the information it gets, adjusts this distribution so that its ellipse is oriented and shifted towards the region with the highest probability of success. Plus a bunch of other tricks; in theory it should work very well.

This method is very popular, I recommend it.

#³Genetic algorithm

Remember that all the optimization methods above work only with real numbers, and none of them allows for integers or any kind of discrete structure. Well, this method is a total game changer, because it can work with exactly that: discrete structures (remember genome in the run_simulation function).

It's based on evolution and mutations. It has already been explained a million times in the videos earlier in this document, so I won't repeat it.

Let's take the definition from Wikipedia: A genetic algorithm is a heuristic search algorithm used to solve optimization and modeling problems by randomly selecting, combining and varying the sought parameters, using mechanisms similar to natural selection in nature.

An important part of a genetic algorithm is crossover. So when you don't use crossover, formally you can't say that you're using a "genetic algorithm"; formally you're just using an "evolutionary algorithm". But since nobody cares, everyone says "genetic algorithm".

So if you want to search for the optimal program or the optimal body shape, this method may come in handy. I don't know any other methods for optimizing discrete parameters. If you know of something like that, please, please tell us in the chat.

Unfortunately, nobody has come up with as huge a science for discrete structures as the one for real numbers: no gradients for you, no line searches. That's probably why everyone strives to turn any discrete structure into a real-valued one. For example, you can represent an arbitrary neural network as a graph (a discrete structure) and try to optimize its structure, or you can represent the neural network as a matrix whose structure is defined entirely by real numbers. Obviously, the second approach will be more successful at solving the optimization problem, because the math there is just plain better.

#⁴About genetic algorithms

A decent lecture about genetic algorithms (in Russian). I'm not sure how good the video is, because I watched it a long time ago when I was a kid; I liked it back then, but now it seems to me that it's not all that great.

#⁴Implementing genetic algorithms in practice

This video (in Russian) is pretty weak, not much is clear, you can skip it. But the second part is good:

Thanks to this video I learned why crossover is needed and how to do it, so it's a must-watch. In it he shows with an example that crossover in the form of shuffling real numbers works well only for close individuals and makes no sense for distant ones.

I also really liked how he defined the behavior of a unicycle individual with just 4 points! I would have started hacking together all sorts of neural networks, and he just used 4 points! And on top of that, these 4 points freaking learned to hack the physics!

#³When crossover is justified and when it isn't

Whether to use crossover in evolution is a tricky topic: on the one hand it can bring a negative result, on the other a positive one. To figure it out, we can look at a couple of examples:

A Twitter thread about crossover having a negative effect on a genetic algorithm solving the traveling salesman problem.

A striking example of when crossover comes in handy is Onigiri's video (in Russian). Here crossover is applied to the weights of neural networks that are roughly the same. Crossover here can be explained like this: it lets you find a point in the middle between two good close points. That is, in this case crossover would have performed very badly if the networks differed too much in their weights: such offspring would simply be unviable.

And this thought is confirmed above too.

As for crossover of discrete structures, it's a very controversial topic, and it has to be considered separately for each specific case.

If you're making your own genetic algorithm over discrete structures, better not do crossover.

Crossover is the kind of thing you should only use when you clearly understand what you're doing. In other cases ordinary mutations are enough.

#³Natural selection

This method is used in artificial life, but it's not really an optimization method.

This term came up somewhere in the cyberbiologists' chat. It means the following: we create some environment and put creatures into it that can reproduce and die, and even interact with and affect each other. In that case you don't even need to program any optimization algorithm specifically; you only need to define what lets creatures reproduce and what makes them die, and add mutations during reproduction; and they will evolve by themselves. Different generations of creatures will exist at different times, no restrictions are imposed here.

In a genetic algorithm it's assumed that all creatures of a given generation are born and die at the same time, and are evaluated in the environment independently of each other. On top of that, there's a special function that says how well adapted a given creature is. In natural selection there's nothing like that, and everything is determined by the environment, implicitly.

With this method we make a kind of soup of simulated creatures that do something. It can lead either to something unusual (as in the case of foo52ru), or to no result at all (as in the case of Polyworld).

But this method obviously requires a large number of creatures on the field at the same time, and preferably a very, very large field, so that ecosystems can form.

#²Differentiable things

#³Physics

Remember that you can build a computational graph and compute the gradient for any formula in O(1). The authors of this work did the same, only for physics. So their creatures in the simulated environment can learn directly, without any workarounds like Reinforcement Learning. And the solution is found very quickly.

For those who didn't know: Reinforcement Learning was invented precisely because in tons of problems we don't have the compute to use something like CMA-ES, and we can't optimize with backpropagation either.

The paper.

#³Ray tracing

Ray tracing is a method for rendering three-dimensional objects into an image.

In this video the authors made a ray tracer whose gradient can be taken cheaply with backpropagation, thanks to which you can easily tune the parameters of materials and appearance so that the object looks like what you need.

#³Programming

If you generalize this topic even further, you can write fully differentiable programs, so that you can easily find the optimal parameters with modern tools. Maybe this is a very hyped topic, and it will take off in the future.

The video shows exactly an example of writing such a differentiable program in Julia with some framework:

And an overview article:

×1
jpg

#Neural networks

#²General information

A guy explained it in one minute:

And here are some very long videos from 3Blue1Brown (they have Russian subtitles):

Playlist.

#²WANN

×1
png

This presents a way to get a neural network that doesn't really care what its weights are. What the network does is defined by its structure and by the different activation functions in each individual neuron.

Actually, it's not that every weight can be randomly distributed there; instead, all weights must be equal to the same number from -2.0 to 2.0.

It's quite interestingly described how they did the mutation of neural networks.

They say they wanted to get closer to how real neural networks work, where the structure is most likely defined by genes.

A review in Russian.

#²Adversarial attack on a neural network

You know all those adversarial attacks on neural networks where someone changes one pixel or adds some noise and gets a completely different result? Well, here they did the same thing, only for two fighting agents. The red agent knows the blue agent's neural network completely and learns to "hypnotize" blue into making losing moves. After all, blue somehow receives information about the state of red's body, so red can influence blue's neural network with its body.

It seems that neural networks should be designed from the start so that such attacks are impossible: so that only high-level information is available to the next layers, so that you can't tweak the answer with one pixel or with barely visible noise.

#²Controlling a creature

There they not only create a neural network that can be controlled, but also imitate movements using a GAN; the movements look as if they were simulated by physics, but they actually aren't.

#²Arbitrary neural network

I wrote an article about a neural network with arbitrary connections, just like in the video with the cars:

×1
png

#AI

#²Alan Turing's paper

The paper in fb2 format (in Russian).

I recommend reading it and understanding what Alan Turing actually meant when he proposed his test for identifying an intelligent machine. It seems to me that society misunderstands this test.

#²The Chinese room

In Russian, in English (to make sure that the Russian one is a real translation).

This is where the terms Weak and Strong AI are introduced. I recommend reading it and forming your own opinion about this thought experiment.

#²Automata and Life - Kolmogorov

The article (in Russian).

In it, he says this interesting thing:

And in any case, this is no objection to raising the question of whether it is possible to create artificial living beings capable of reproduction and progressive evolution, which in their highest forms possess emotion, will and thought. This same question was posed elegantly, but formally, by the mathematician Turing in his book "Can a Machine Think?".

Can one build a machine that could not be distinguished from a human? This formulation seems to be no worse than ours, and it is also simpler and shorter. In fact, however, it does not fully capture the essence of the matter. After all, what is essentially interesting is not the question of whether one can create automata that reproduce the human properties known to us; we want to know whether it is possible to create new life, just as highly organized, though perhaps very peculiar and completely unlike ours.

#²Criticism of AlphaStar

AlphaStar is a program that uses neural networks to play StarCraft 2, building on the ideas of AlphaGo. The following videos (in Russian) criticize the behavior of this program from the point of view of a professional player:

For example, one of the videos showed AlphaStar building a wall in such a way that units walk through it, so the wall is pointless. To a human it's obvious that nobody should be able to walk through a wall, because we take that from our life experience.

#²Criticism of deep learning

An interesting article that soberly examines the problems of the current deep learning approach.

×1
jpg

#Cellular automata

#²An automaton that regenerates into a picture

×1
png

This automaton is based on a neural network.

#²Von Neumann automaton

A wiki link.

According to the PostNauka video, in this automaton you can encode an object that can create a copy of itself; it has to consist of several elements:

• A set of instructions
• A device that can copy the set of instructions
• A device that can reproduce the automaton itself from this set of instructions

Interestingly, the structure of DNA and how cells use it were discovered only later!

But of course, such an automaton can't be subjected to evolution that easily, because changing 1 bit in the instructions can break the whole automaton; plus, the environment itself has no factors that would force it to change its "DNA". This is called the digital sterility problem.

#²Reversible cellular automaton

It's an automaton that can easily be simulated backwards, and it has a unique past. An example of such an automaton: Critters.

optozorax wrote a simulation of this automaton and wrote several posts about it, starting here: telegram:optozorax_dev/235 (in Russian).

There's an interesting principle related to reversible computing: Landauer's principle.

An executable to play with: critters.exe.

#²A cellular automaton that copies a picture

With these rules for cell birth and death, the automaton for some reason copies the whole image it's given:

×1
jpg

You can watch a video of how it works at telegram:emergevolution/853

It's not yet clear whether it's possible to come up with rules that would let you simulate it backwards, because you can see that it preserves some information.

#Writing your own simulation

#²Things to keep in mind

If you're writing a Snake game, you can keep the snake problems in mind.

#³Simulate and draw separately

Very many simulations are made so that the simulation runs in real time, with every step shown on the screen. This is bad, because the CPU can usually run the simulation much faster, but it's limited to 60 steps per second. You need to plan the application's architecture from the start so that the simulation is completely decoupled from the display. That way the simulation can be sped up, or turned into a separate console program.

For visualization, at the first stage you can draw the world into a picture or a GIF; for that you can just add libraries for the corresponding formats. Moreover, if you write the code for drawing the world into a picture right away, you can later adapt it for a GUI, while the other way around won't be as easy.

#³Defining a creature's behavior with a program

In the foo52ru simulation and some others, the behavior of a creature is defined by code. The problem with code is that the slightest change to it changes its result drastically. This is very bad for evolution, because evolution works well with things where small changes give a small result, so that it can feel its way towards something.

From this point of view, neural networks are very good, because a small change to their numbers changes the result only slightly, so you can feel your way towards the right direction of development.

The fact that it worked for foo52ru is more likely just luck; besides, his task is simple enough to be solved by brute-forcing code. If you solve a harder task, creatures driven by code will never evolve into anything decent.

So if you want to make your creatures controlled by code, think twice, or try to come up with code where small changes to the code make small changes to the result.

So far there's this idea (in Russian):

We have the original algorithm; let's denote it as a function:

func(input) -> output

We make a mutation; the algorithm can change very strongly and becomes:

funcMutated(input) -> output

And then, in order not to introduce this very strong mutation into the algorithm, we do this:

funcResult(input) = func(input) * 0.9 + funcMutated(input) * 0.1 -> output

So in essence, the mutation has a strong effect, but we dampen its influence and gradually increase its weight.

You can have many such weighted mutations at the same time.

The main problem with this idea is that the outputs must be real numbers. If they are discrete, you can't apply this. Although it can work if the function gives the probability of ending up in the right place; then weights fit right in, we just modify the weights. Then again, if these are real numbers anyway, maybe neural networks are better after all?

#³A book about evolution and neural networks

Hands-On Neuroevolution with Python. Iaroslav Omelianenko. (The link leads to the Russian edition.)

#²Platforms, libraries

#³spiril

spiril is a library for Rust that makes it very easy to write a genetic algorithm: code.

#Ideas

#²To implement

#³Clinging to 2D space

#³Training neural networks in blocks

An idea from my article:

×1
png

An example based on training a "human": if we need a 3D human to learn to walk on two legs, we know that he walks without falling, so first we need to train some block: keeping balance. We can put this human in an upright position with the legs shifted to the side, with some velocity, and make him either keep his balance or get into a position where the balance is kept.

And then, once we've trained this balance module, combine it with the walking module and train it so that he learns to move his legs forward, somehow keeps his balance, and doesn't fall while doing it. And the balance block can be combined in parallel with the jumping block, etc., so that he learns to keep his balance in completely different situations.

When he learns to walk, this will help him by keeping him from falling, and the walking block won't have to do the work of keeping balance.

#³Typing for program genes

In real organisms, protein structures interact with each other thanks to having a certain shape that fits like a key into a lock. In the video about Tierra, at the fifth minute, they suggest doing the same thing, but for computer programs. We need to give them a shape, so that different programs can be joined together like genes.

This is a bit like the idea of static typing (the input data type must equal the output data type) or like duck typing.

#²Abstract

#³Life without suffering

If you think about it, all life on our planet is based on suffering:

• predators eat other creatures
• there's constant competition between creatures
• everyone has to die

I wonder whether it's possible to come up with a kind of life that doesn't have to suffer like this in order to develop into very complex and even intelligent beings.

If such life is possible, then it seems to me that the global goal of humanity could be exactly creating and maintaining such life, for example in a simulation.

This is much harder than creating an evolution where creatures develop endlessly (emergevolution).

This needs a name.

Benevolution?

#Fun stuff

#²Memes

#²Funny things from evolution simulations

An eye-catching picture: here they evolved the shape and the neural network of a creature so that it would jump higher. But evolution took the easiest path and created a creature that simply falls from a huge height (thanks to its body), which created the effect of a jump, and it survived better than the rest. Clicking the picture takes you to the PDF of the paper it was taken from.

×1
png

#²Professional deformation of data scientists

×1
jpg

#²Evolution hacks in the real world

×1
jpg

#²Strong AI will never be created

A repost from somewhere

Why strong AI will never be created. An article by a respected scientist in Nature:

https://www.nature.com/articles/s41599-020-0494-4

I just love bold statements like this: Strong AI will never be created!!1

This claim is demolished by a simple thought experiment:

1. We live until the year one million
2. We write a physics simulation
3. We put a human brain into this simulation
4. The human brain is strong AI, and it runs in a computer
5. ????
6. PROFIT!!!

And the article itself isn't very good IMHO, you can read it here: telegram:emergevolution/739.

#Useful resources for improving this document

Online table editor.