Sentiant's Auto-Evo Algorithm

So with Nick no longer seeming to work on his auto-evo algorithm it seems the devs are now mostly pushing for a less complex approach. While I can understand that this would be easier to understand for players and more performant there is one small issue with this: Every time Thrive moves to become simpler I have a fucking heart attack and a Spore flashback.

So here I am making my own auto-evo algorithm. This will be based primarily on Nick’s auto-evo algorithm with a couple tweaks:

  1. Nick used a lot of simple estimations instead of real math resulting in some wonky behaviour. I will try to implement real math whenever I happen to know it.
  2. This algorithm will be more tied to the current game. Where Nick focused mostly on far-off multicellular stuff, I will focus on Microbes as they are in the current game with the current features. You should be able to input your current microbe from the game directly into the algorithm.
    Overall the results of the algorithm should match the experience of the player in the game as closely as possible.

For my long term goals I hope to eventually go beyond what Nick did, implementing actual evolution instead of just a population-algorithm. I’d also like to see if I could make the algorithm continuous instead of discrete for performance’s sake.

I am working on this as a separate program for now, because coding is hard enough for me when I’m not working with a largely undocumented existing codebase. But I hope to eventually turn it into a ‘harsh-realism’ mod.
In this thread I will focus on the logic behind the algorithm, similar to Nick’s thread. But I also plan to eventually make a sort of ‘game designers summary’, that only focuses on variables a game designer could tweak.

What I currently have is a very basic population algorithm. You can input a single species of microbe, and the size and amount of food sources in a patch. Species must swim towards food sources, and if they don’t find enough to sustain them within a timestep, a fraction of them will starve. The time that isn’t spent hunting for food, is spent reproducing. The amount of offspring this generates is currently based on an arbitrary factor multiplied by the time spent.
This is all very similar to episode 1-5 of Nick’s algorithm, with the following exceptions:

  • There are no deaths of old age, as microbes do not die of old age in the current game.
  • Food is not based on ‘calories required’, but on the compounds a microbe would need to survive in the actual game. Yes, this does mean that you can become an autotroph and not need food at all.
  • Distance per hunt is calculated using a more accurate model of points randomly distributed within the patch: see my comment on Nick’s auto-evo feedback thread. This fixes Nick’s issue where hunts would take unrealistically little time.
  • Clustering is not implemented yet. When it is implemented I will probably use a more simple method of simply treating each cluster of microbes like a single point on the map. This will make the logic for finding microbes and compound clouds equivalent, and the math easier.
  • Speed is not determined by hydrodynamics, but by the same calculation the game uses. More flagella = faster, more mass = slower.

To finish this post here’s a graph of how Primum Thrivium and some variations of it do in the simulation:


You can see that species grow exponentially at first, until resources in the patch run out. Then, a large fraction of them starve, and only those who can subsist on the amount of food that gets added each timestep remain.
Auto-evo appears to agree that one-hex is best hex. However, it currently thinks that both the cell-wall and the metabolosome are better than basic one-hex. This is because we assumed that reproduction is happening at a constant rate. In the real game, both of these options would slow down reproduction due to a speed reduction and an increase in resources needed respectively.

Hope to see you in the next update, where I will be allowing multiple species to coexist and compete with each other!

21 Likes

Judging by your Stellaris mod, I have high hopes this’ll prove interesting.

Good luck!

2 Likes

Awesome, it will be really fun seeing some better AI evolution.

1 Like

So, just curious, what exactly do you mean by actual evolution in this case?

I would assume they mean they are trying to make something that accurately represents survival of the fittest, just for computer generated organisms instead of biological ones.

why are there so many ants

I didn’t realize we had so many ants here before this post

2 Likes

Oh boy time for an update!

Today we’ll be introducing multiple species into the same patch and simulating them coexisting.
They won’t eat or fight each other yet, that will come in a later update. Instead we will make them compete
over compounds by racing to get there first. In this update I will explain the math behind this to you, and show you the results.
To be entirely honest, I don’t understand exactly what Nick did here or whether it was correct, so instead I started from scratch.
I put all the math stuff in a spoiler to prevent this post from bloating, but basically:

  • Competition occurs when multiple organisms (not just multiple species! ) are attempting to gather the same type of cloud.
  • Competition causes organisms to waste time, because sometimes the compound cloud they were hunting has already been eaten by another microbe. This happens even when both microbes are of the same species, and even when there is no shortage of food at all.
  • In times of shortage it also causes some species to take home a larger share of food than the others, resulting in unequal amounts of starvation. In the long run we would expect this to make suboptimal species go extinct when a more optimal species is hunting the same type of cloud.
Math stuff

First let’s consider a scenario with only one species. In this case the species would need a certain amount of clouds, and there would be a certain amount of clouds in the patch. If there are more clouds in the patch than the species needs everything is fine. In that case the species would have a success probabilty of 1. There might be some issues where two individuals go for the same cloud and one ends up wasting some time before it goes to a different cloud, but eventually it will find a cloud that no one else ate. The only thing the species can stand to lose is time.
That changes when the species needs more clouds than the patch contains; there’s a shortage!
In this case the species only achieves a success probability of clouds / hunts required (in addition to wasting time as before).

This success probability formula might break down if we introduce another species to the patch, because the species will have to compete. The total fraction of hunts that are succesfull is still clouds / total hunts required, but each species individually only contributes some fraction of the hunts. If both species are equally matched, and require an equal number of hunts this fraction will be 1/2, giving each species half of the total clouds. But that will almost never be the case. Most species will be either unequally matched, or one species will need more of a given compound than the other.
Let’s imagine the latter case first. In this case we would expect each species to take a fraction of the clouds proportional to how many clouds they require. This already happens given our current formula:
sucessfull hunts = clouds / hunts required * 1/2.
Now let’s imagine what might happen if the competition between species isn’t even:
What if one species is faster? What if there is a third species upsetting the balance?
For this I will use an abstraction that has served me fairly well in estimating probabilities in the past. We will give each species a competitiveness rating. For now we’ll set it equal to speed, since that is the primary determiner of who gets to the clouds first. Using speed = competitiveness is just a guess, but finding the actual value would require icky stuff like game theory.
Next we add up all the competitiveness ratings of all the species to find the total competition in the patch.
Finally we replace the 1/2 in the formula with competitiveness / total competition. This gives us:
success probability = (clouds / hunts required) * (competitiveness / total competition)
clouds gathered = hunts required * success probability.

But what about that wasted time I mentioned earlier? How will we calculate the amount of time per hunt, given the amount of competition?
This depends on the time per hunt the algorithm already calculates, and the amount of times a microbe has to try before he finds a cloud that he can actually get. So how many tries does it take on average to find such a cloud? Well I can’t disguise the probability theory we need for that as simple math so hold on to your butts.
Assume that each microbe picks a random cloud to swim to. Irl they would of course pick the closest cloud, but the position of the microbe is random, and the position of the cloud is random, so who cares. A competition occurs when at least two hunts are for the same cloud.
The chance that any given hunt is for the same cloud as you = 1 / clouds.
The chance that it is not not for the same cloud = 1 - 1 / clouds.
The chance that every single hunt does not pick the same cloud = (1 - 1 / clouds)^hunts
Thus, the chance that at least one other microbe picks the same cloud = 1 - (1 - 1 / clouds)^hunts.
If a microbe gets into a competition and wins, he does not waste any time; that only happens if he loses.
The chance that a microbe wins his competition = competitiveness / total competition based on the abstraction from earlier.
Thus the chance that they lose = 1 - competitiveness / total competition.
Except that in the case of wasting time, losing to your own species also counts, increasing the chance of a loss.
Therefore we add the species’ own competitiveness to the competition:
chance of losing = 1- competitiveness / (competitiveness + total competition).
The chance that they get into a competition is simply both probabilities multiplied.
Some fraction of microbes will have the opportunity to try again after losing a competition, wasting time; their competition was caused by inefficiency, not by a shortage. The chance that this happens = 1 - (hunts required - clouds / hunts required). The average amount of tries would then be: 1 + chance of competition * chance of losing * chance of retrying. Except there’s no guarantee that the microbe won’t lose again and do a retry of a retry. Or a retry of a retry of a retry! You might think that we’ve found an unsolvable infinite loop, and you’d be partially correct. It is an infinite loop. It’s not unsolvable. This monstrosity we’ve created is called a geometric series. Google it if you want to know how I got this solution:
average amount of tries = 1 / (1 - chance of competing * chance of losing * chance of retrying).

This gives us all the information needed to start making microbes compete with each other.
The first thing I did was ran 3 tests to verify that the system works even in weird scenarios:

  1. I ran the exact same scenario as last time. This gives a slightly lower population than last time, but only as much lower as can be explained as intraspecific competition. This proves our changed algorithm gives the exact same result as the old algorithm given no competition.

  2. I divided Primum Thrivium in two. Both halves of Primum Thrivium are exactly the same kind of microbe, I just arbitrarily declared that they are two different species. The result is that both species have an identical population: half of what they would have had if they were still one species. This proves that the simulation does not favour any individual microbe based on what species they belong to.

  3. I introduced a second species, that does not compete with Primum Thrivium in any way. They have a completely separate food source. The result is that they have the exact same population they would have had if they were the only species in existance. This proves that the changes of the algorithm only apply when two species would realistically interact.

Now for the graphy stuff! If any of you have scenario’s you’re interested in let me know but here is one I came up with: We have two species, Primum Thrivium and Primum Abyssus (two hexes of cytoplasm with a single membrane). Both of them compete for glucose.

P. Thrivium immediately has an edge due to being faster, which allows them to get to the glucose first. Despite this they eat less glucose in total, because they need less. Thus, it is Abyssus who causes the food to run out, and Abyssus who pays the price. Thrivium then starts growing again, but quickly runs into his own food shortage, settling into an equilibrium population just before the simulation ends.

Second graphy thing! This time we pit P. Thrivium against P. Flagellum (one metabolosome and one flagellum). P. Flagellum needs way more glucose to survive, but is also way better at competing. Place your bets everyone!

F in the replies for P. Flagellum, who was unable to even gather enough glucose in a month to sustain themselves. Even if there was no competition they would have died within a couple months. P. Flagellum’s natural habitat would have to be very glucose rich. That said, I do think it’s a good thing that the algorithm is harsh on species like this. It shows that it actually knows what species are suboptimal in the game.
Meanwhile P. Thrivium is just chilling, barely noticing that P. Flagellum was ever there.

I’ll see you in the next update, where reproduction will work just like in the real game. Microbes won’t just have to compete for food, but also for phosphate, and ammonia!

11 Likes

“why are there so many ants”
“I didn’t realize we had so many ants here before this post”

No reason, nothing suspicious here. Guys, they’re on to us!

1 Like

Make this man a thrive dev. NOW.

1 Like

Hello fellow ant

[|87

How do I install this mod. I must know

You can’t it’s not even remotely close to being done yet.

Do you have a flowchart or something similar so it is easy to visualise?

A flowchart of what exactly? Competition? The whole algorithm?
The only thing I currently have a flowchart of is the steps an individual microbe goes through when finding a cloud.

Sorry if I was confusing, just woke up.

I meant a flowchart of the AutoEvolve process, but at this stage I think it wouldn’t be fully complete right?

At the current stage the only thing that’s fully simulated how I want it is gathering compound clouds. The algorithm then shows you the population of species over time based on how good they are at gathering clouds.

There’s not even actual evolution yet, which will come once I’m happy with the population algorithm.

2 Likes

Is there a plan of making sort of dev builds.

Making dev-builds is kinda pointless because in my current plan any sort of UI is literally the second to last step. The last step is “see if you can turn it into an actual mod instead of a separate program”.

So unless you have basic coding knowledge and access to the source code the only thing you’d be able to do is run the same scenario over and over again.

In other news I tried to get the ‘collect compound clouds to reproduce’ thing working today, but I’m having a hard time balancing it.
I’m also being plagued by an annoying bug where the order in which you enter organelles into the species has an effect on the compounds they can produce.
If you first give it an organelle that costs ATP (e.g. nitrogenase) and then one that produces ATP (e.g. mitochondria) the species correctly realises it can use the mitochondria to make ATP for the nitrogenase.
But if you order them the other way round it just goes
image

7 Likes

Time for an overdue update:
Today I overhauled the way reproduction worked.
Previously I was doing reproduction exactly the same way Nick was: Every microbe has an arbitrary reproduction factor. For every full timestep spent reproducing they create a number of new microbes equal to the reproduction factor (set to one in the previous updates). This has two unrealistic consequences I’d like to fix:

  1. Reproduction takes equally long for every species. This means that giant eukaryotes are taking just as much time to reproduce as tiny P. Thrivium (who breed like rabbits in the real game).
  2. Food supply is the only limit to how many microbes can exist. This means that autotrophs could keep exponentially growing their population forever, filling the entire patch several times over.

In the simulation, I made microbes gather and compete for clouds of ammonia and phosphate just as they do for food. The amount they need to collect to create one new microbe is based on the composition of their organelles, taken from the source code of the real game. There, I noticed to my HORROR that metabolosomes and thylakoids both cost LESS than cytoplasm. I resisted the urge to correct this because it doesn’t make sense, and will adjust my speedrun strategy in the future.

Anyway, this fixes both issues:

  1. Now reproduction takes longer depending on the cost of your organelles, and how fast you are at gathering compounds. P. Thrivium has an edge over giant eukaryotes in both departments.
  2. Because there is only so much ammonia and phosphate in a patch, there can only exist so many microbes at once. Once all the compounds in the patch are used up, that’s it. Naturally, if a microbe dies, he deposits his compounds back into the patch. Otherwise patches would run a net loss and die out over time.

Here are some example scenarios:
A cyanobacterium (1 thylakoid, cell wall membrane) is alone in a patch, what will happen now that he has to work with limited resources like this?

It still grows (almost) exponentially at first, but the graph levels off once ammonia and phosphate run out.

For our next experiment let’s see what happens when we make P. Thrivium compete against Ammoniae Aedifex (one metabolosome and one nitrogen fixing plastid). A. Aedifex will be able to make ammonia out of thin air, but constantly spend ATP doing so:


Unfortunately A. Aedifex was not able to keep up with the ATP costs and quickly starved to death. A look into the internal variables reveals that they were not able to collect glucose fast enough to keep up with their ATP demand once it got below a certain density. Once they go extinct P. Thrivium briefly peaks due to its new lack of competition, and then falls into its equilibrium population.

For the final experiment I want to test how much better metabolosomes really are than cytoplasm. So I pit P. Thrivium against P. Metabolosomus (one metabolosome):

ngl I was completely taken aback by this. P. Thrivium actually held his own! This is the first time in all my testing that a species was able to survive in the face of superior competition. Not only that, but he never actually reaches a stable equilibrium, instead bouncing back and forth between two populations. I suspect that this is a fluke of how various numbers are discretised (like the number of clouds, number of microbes, etc.) and that the population would simply reach 72 in a continuous model. But who knows, irl sometimes shit like this happens too.

I am beginning to suspect that the patch I’ve created might be a bit too harsh, if even super-optimised species like P. Thrivium and P. Metabolosomus are barely clinging on with less population than they started with. That’s why I’ll see you next update when I’ll be recreating some of the patches that are actually in the game.

Until then hmu if there’s some scenario you’d be interested in seeing.

9 Likes

what about glucose decrease? Will you add it to tbe simulation?