Artificial Life. The battle of clans. Technical details
ฝัง
- เผยแพร่เมื่อ 23 พ.ย. 2024
- A boring video about the technical details of my latest artificial life project.
1. Order of execution
2. Energy transfer
3. Insides of the genome
You can support the channel on Patreon:
/ simulifehub
More support, more opportunities for new projects.
![The moment we stopped understanding AI [AlexNet]](http://i.ytimg.com/vi/UZDiGooFs54/mqdefault.jpg)
this guy is either a genius or some sort of eccentric artist/creator
you can tell by the fact that when a cell dies it makes a squeaky noise
Why not both, haha?
I realize that comes with a ton of other issues but I think "the fairest" you can possibly be is to go simultaneous.
The big issue with that is, that multiple cells might want to affect another cell at the same time, and it's unclear how to solve that.
The next fairest thing is probably a *random* order where, over short time horizons, things may be a bit unfair, but things should smooth out pretty quickly.
And that's perhaps also one way how to deal with simultaneity: Basically, for every conflict, decide randomly which cell wins, and then give whoever didn't get to win an opportunity to do a different move instead if that's still possible after all initial conflicts are resolved.
If you don't want to rely on randomness of opportunity at all, you'd have to adjust your world rules in ways that simply make all possible behaviors deterministically resolvable.
And if simultaneity isn't gonna fly, there are sequences strictly fairer than a linear order. - The Thue Morse or fair-share sequence is a simple sequence for *two* players that slowly eliminates the advantage of the first player by "taking turn taking turns". This property is derivable by considering a simple ball game:
Imagine both players are extremely unlikely to hit a ball into a goal. First player to get the ball into the goal wins. - You simply keep track of what the winning chances for your players where *thus far* and then let whose ever chances are lower go next.
On the very first move, player 1 has a small chance to win.
Player 2's chances to win now are that Player 1 hasn't won yet times the same small chance to win. - Since it depends on whether Player 1 already won, the overall chance is slightly lower.
And it turns out to *still* be lower after Player 2 went once. So they get to go again.
Then the chances are better for Player 1 again. That way you generate the sequence
1221211221121221 ...
which is exactly the Thue Morse sequence.
Now this is the sequence you get for *two* players. However, it turns out you can, in fact, generalize this concept to more players. Search for "What's the fairest turn sequence for n players?" on math StackExchange to see how.
Interestingly, unlike the two player case, higher player counts appear to eventually fall into some sort of loop. Though I don't yet understand the patterns of that loop very well. This *eventually* looping behavior is actually an advantage in terms of this greedy algorithm though: It ends up requiring basically static memory *eventually,* (and not all that much of it) whereas the two player case would involve looking into ever higher orders of an ever expanding polynomial.
(To be clear, for that two player case, it's easy enough to generate terms with arbitrarily deep time horizons using much simpler methods)
In principle this also means you could simply precompute the start of the sequence until you hit the loop and then just keep doing that loop. (It's not the same as your loop here, as such a loop might be quite a bit longer than the number of players. In fact it's *definitely* at least twice the number of players long, as all sequences created this way, after they go through every player once, will then go through every player *in reverse order* again, and only then begin doing something potentially new)
That is how you can *greedily* minimize undue advantage due to a deterministic turn order. However, it's actually possible to do better still, by using a turn order that is fine with a larger early discrepancy, granting slight leeway in the order, but getting an exponentially faster convergence towards fairness. That presumably *could* also be generalized to more players but I'm not quite sure how. If you look at the full answer in the Stack Exchange, that method is also mentioned but not explored further.
All that said, these choices are completely independent of where you'd place a new cell in the sequence. These sequences are meant for a static number of players. Perhaps doing exactly as you're already doing here except you use such a "fair share" sequence instead of a regular loop would be an improvement still. But I can't know that for sure. I guess to figure out "the correct" sequence in that case, the problem would have to be reframed to directly model a situation where players could go away or duplicate on top of everything else...
8:44 "Its existence is meaningless"
I think it should be up to evolution to "decide" if something is meaningless or not. Such creature can still participate in kin selection for example by being a shield against parasitic cells.
I tried this option.
The cell does not die immediately, but releases energy into the soil. Over time, it still dies from an excess of energy in the soil (if someone nearby does not collect this energy).
But the simulations often died, and when they survived, the world did not look interesting.
I'm constantly trying different versions of the rules. The rules I use now give the most interesting results.
I guess another way of resolving the "cell order" or the "buffer energy" would be to maintain two complete separate state of everything, an actual state and a "future" state, all calculus are based on the actual, create the "future" and then the two are swaped to iterate. very memory consuming tho
Problems may arise when a pair of cells appear in the same place.
But with the movement of energy it can work. I'll think about it
@@wallcraft-video having a current and future buffer also opens the way to do all cell calculations in parallel (eg. use a compute shader on the GPU). You will need some atomic writes and also some additional rules to deal with contestants for the same space...
@@wallcraft-video When more than one cell tries to appear in the same place at the same time, create the cell but for each bit in its genome choose randomly which parent that bit comes from. Call it sexual reproduction.
boring is subjective :p
fascinating project and thanks for updating us regularly!
At 2:40 you have described a doubly linked list with prev and next indices stored per cell. This is overkill for what you are using it for, and you only need to store a next cell. The reason is because you are always iterating in one direction rather than randomly accessing the cells. Lets call your current cell "cur" whenever you move to the next cell, store the old location:
old = cur;
cur = cur->next;
to add a new cell behind cur:
new = findEmpty();
old->next = new;
new->next = cur;
when cur dies:
old->next = cur->next;
temp = cur
cur = cur->next;
kill(temp);
Doing this you can reduce the memory usage, and should help performance.
I would like to add that although you can make the list singly linked and that will help somewhat, I suspect that using a linked list is bad for performance. Linearly going through an array and not having a next index at all would be better.
There are several reasons that linked lists are not ideal. An obvious one is that if you just have an array the next index is implicit. Another reason is that jumping around a linked list is bad for caching, and also disallows the computer from prefetching data from ram. If you sequentially go through memory, the access pattern is predictable and memory will be read from slow ram into fast cache before it is actually requested by a CPU instruction. Lastly, a linked list creates a dependency chain between memory reads. CPUs run multiple instructions in parallel (called instruction level parallelism) and keep track of dependencies between instructions to ensure that the end result is as if they were done sequentially. Creating dependencies, especially through memory reads, limits the ability to parallelize instructions, and will reduce your instructions per clock.
If you could relax your requirement about needing to add a cell right after the iterator (does that bias you described actually have a noticeable effect in the first place?) then you could very easily use a plain array. This would also be a step towards enabling multi-threading to parallelize processing the array of cells across multiple cpu cores. Dependency chains are bad for performance in lots of ways and limit your options for optimization.
Looks reasonable. I'll think about this option
When I do this kind of thing, I avoid order of operation problems by updating in two phases. A decision phase and an execution phase. In the decision phase, I iterate over all of the agents, creating an array of actions. An action in this case could be something like "transfer energy to the north" or "grow a sprout to the east". In the execution phase, I apply all of the actions.
The main disadvantage of this method is that you have to define rules for actions that contradict each other. For instance, if there are two actions that would grow into the same tile, we have the order of operations problem again. The base rule in these cases could be as simple as "neither action resolves", but you can also use a tie-breaker system first, like "the action that originates from the cell with the most energy wins", falling back to the "neither action resolves" case if they have equal energy.
The advantage is that order of operations becomes a non-issue. In a way, it functions a little bit like your buffered energy transfer system, where no matter the order in which you evaluate the cells, the outcome is always the same.
Another advantage is that you can make the model more robust. It'll all boil down to a state and a function that takes a state at timestep n, and returns a state at timestep n+1.
The biggest advantage is that this becomes highly parallelisable. The decision phase doesn't modify the state, so you can run each cell on a different thread. The cells can read the rest of the state to output their decision. The execution phase creates a new state from the previous state and the list of actions. You can't run the actions on different threads, because of the contradictory actions problem, but you can assign actions to cells, and again run each cell on a different thread. If the cell doesn't have any actions, it just returns the previous value, otherwise it evaluates the actions and outputs the updated state.
I love this content, great job man! I wonder in what you program this, C or CUDA? It must be something pretty fast since it looks big. I really like your animations and visuals as well.
Love th video but I'm wondering if you ever plan on letting the public use your simulations?
To my knwoledge its available paid on patreon
these projects are the reason im a nerd. so interesting to see intelligence emerge from algorithms, and even sometimes simple neural network
You put so much work into both the video and the project. excellent work. looking forward to future episodes!
I don't have many ideas for thos but i want to see there bee more incentive to being a single celled organism. Maybe make them have some sort of way to proliferate off of superorganisms? Also love the work that you have done and seeing your videos helps me wind down from a day. Thank you for existing in my life!
The video already described the parasitism command which makes a transfer cell link to it giving it energy
@@dylanherrera5395 ik but still single cells need to have some sort of buff
this is my favorite series of the world
this makes it so much more interesting, knowing the basics of how the orgasms work :D
I'm interested in how you're finding the free cells. I would imagine iterating through the list from the beginning could be slow if there are lots of alive cells before the first free one. It might be useful to have a vector of free cells and every time a cell dies, its index gets appended to the end of it, and once you need to find a free cell, you just read the last index from that list and pop the last value. If you're starting the simulation with 1000 cells, index 1000 would be added to the empty free cells array and if you use up all of the cells from the free cells vector - you just need to add index after all of the existing cells (if there are 3252 cells - index you add to the vector is 3252). You can do this because this approach doesn't use any index that's higher than the current number of cells (always fills up all of the holes first, kinda like how I assume you're doing it now, but as I said - I'm not sure if you are linear probing from the beginning until you find a free spot or you're doing something else).
UPDATE: Also, like someone else already mentioned - it seems like you don't need a doubly linked list but a one way linked list which only stores the next index would suffice. Actually, I guess you need the previous index to know which node to update once you're adding or removing nodes, but you could perhaps store the previous node you came for in a single variable and update it every time you go to the next node or something. Not really sure if this would be faster than keeping the prev values for every node and having to only update them once you are adding or removing the nodes as opposed to what I suggested where you have to update a variable which tell you what node you came from every time you jump. This could make your list smaller however and there's a good chance it would be able to fit in the CPU cache better and you could get some performance from less cache misses.
Thank you.
I use something like a stack for free cells. When a cell dies, it adds its index to the stack.
When I need a free cell, I take it from the stack.
I added this later. In the first versions I simply ran through the list looking for a free cell.
I read about “a double linked”.
Sounds reasonable.
Fascinating. Thanks for explaining. I’ll need to rewatch this a few times to understand and I may try to implement in on the GPU. But I’m
Using Swift+metal which may not suit most people. I seems brilliantly thought out to have just the required complexity
Amazing video! How do you render the cells (graphics)? To me it seems like it's the most impressive part of your simulation.
This is very cool 😁
Thank you for sharing the technical details with us!
Is there any way we can try it for ourselves, or future plans to release the code?
I post a code on Patreon for paid subscribers
This is actually usefull for some other project I have so quite a neat system
Have you thought about trying to implement physical properties of energy itself in terms of fluid, thermodynamics in that they tend to take the path of least resistance? Kind of like how water flowing over a path of varying types of objects with different densities? For example, water flowing over sand will tend to move some of the sand yet if the amount of water and it's combined forces (momentum) is relatively small and it encounters a heavy stone or rock, it pushes up against it and then eventually flows around it. If the total force of the flowing water (it's overall momentum) is greater than the mass / density of the rock, then it will begin to push or move that rock with it. I think something like this might add a bit more dynamics to the system making the overall system a dynamic system as opposed to a specific discrete state machine.
I’m all for adding more physical reality but the transport of fluid and food within a cell is highly active and artificial in a sense. It’s not flowing in the direction it naturally would although adding physics and gravity might mean horizontal rather than vertical transport is easier
This is inspiring! Excellent work :)
I hadn't seen this video when I made my recent comment on another of your videos.
I love this vid I cant wait to see what you will do next! Also would it be possible to use the software you made?
Thank you.
Now I run two identical simulations and in one I delete one of the cells. It's interesting how two identical simulations will differ over time. If I get something interesting, I'll make a video about it.
There is also a project where two boxers learn to box themselves during a fight. (without using neural networks)
I want to return to this project and try to add artificial selection with crossing.
I post a code on Patreon for paid subscribers
This is good stuff
At 10:00 you describe a system of copying energy values between cells that seems complicated and I don't really understand why the simpler solution of double buffering the energy values would not be sufficient. You describe a cell having 3 copies of bufferA, bufferB and energy.
I suggest you just have 2 values. Lets call them an array of energies E[2]. But lets reference them for the moment as x = E[0] and y = E[1] for the moment. For all the cells you do you operations such that you add energy into y and when done processing the cell clear x to 0. Once you processes all the cells, all the x values will be 0 and the y values will have the correct energy values for the next simulation tick. So you moved energies from E[0] to E[1]. Then in the next tick you go the other way around, moving the energies back from E[1] to E[0]. Now you can see why I reference the energies, because on tick T,
ix = T & 1; // and with 1 bit
iy = ix ^ 1; // xor by 1 to flip the bit
x = E[ix];
y = E[iy];
Sounds reasonable.
I have to think about this option
Could you not solve the directional issue by simply alternating which direction you iterate the list? In one tick, you go in one direction and then in the other, you go the opposite direction. Or simply do both as part of a single tick, though that then doubles the amount of work needed for every tick. Alternating seems fairly realistic though. Plenty of a living organism's processes actually do run in multiple steps like this anyway; see: breathing or your heartbeat, for example.
How much programming experience do you have?
Have you thought of making a similar simulation using neural network brains?
What language is this coded in?
It'd be neat if you could somehow expand the command concept to allow arbitrarily long genomes with many more commands (but attach some energy cost to commands to keep things from exploding)
Also, I *think* there is a chance that, because you more or less number the commands from 0 to n, and after that simply put all the no-ops, certain mutations become far more likely than others, simply because certain commands are more useful than others and so those numbers will appear more often, presumably including in *other* spots, right? - You didn't explain in this video how mutation and, if that exists, recombination works, so I'm not sure whether the presence of a number in one spot has any bearing on the chance of it appearing in another spot. If it's just point-mutations, then no such thing would happen, I think.
But in case it does, it could be fun to add a meta layer that essentially encodes the meaning of the genome in itself, so a genome that starts differently in that meta layer might take the numbers to be completely different things, including the possibility of redundancies and complete absence of certain ops in that genome (because multiple or no numbers map to them respectively). This would automatically also be an approximate way to add speciation into the mix.
Creating a genome of arbitrary length sounds cool, but is more difficult to implement. Maybe I'll try it sometime.
In this project, more than 20,000 cells with a randomly generated genome are first created. Most die at the very beginning.
When a cell gives birth to a new cell, it passes on its genome to it.
But in 1% of cases an error occurs.
One random number in the genome is replaced by another random number.
That is, in this project there are only point mutations.
I need to think about the "meta layer".
@@wallcraft-video ok so in that case, with this simple point-wise mutation, positions are completely independent from each other as you don't have any sort of mutation that involves rearranging what's already there. Then the concern about number frequency doesn't really come up.
I mean, certain numbers are gonna be more common in *specific spots* of the genome, but they aren't going to, therefore, also be more common in *other* spots (due to such random rearrangements)
The simplest form of the meta layer would be a sort of dictionary where you take any number from 0 - 65535 (say) and make it map to some random gene as you currently have it. The gene then becomes a sequence of those remapped numbers instead.
It'd basically separate the genotype and phenotype, allowing each organism to basically find *different* ways to the *same* solutions. And moreover, this could grant robustness: An organism might evolve multiple gene inputs to map to the exact same gene output.
If you then do statistics over how often some redundancy evolves, or how strongly it tends to evolve, you basically get an importance measure "for free". If the same sort of redundancy evolves over and over, and very strongly so, it's gonna be for a reason.
Also, by giving *loads* of genotype-level ways to cause the same phenotype, you get the phenomenon of convergent evolution, but you could still take the genetic sequence to, with high likelihood, deduce evolutionary paths. It might be possible to estimate how often one sort of evolved trait follows another.
This could later be taken further to also serve as an open-ended genome. The dictionary could also contain information about whether a specific location is considered a command, say.
In the most life-like implementation, you wouldn't have a fixed-size dictionary but one that itself can grow and shrink. Considering all the edge cases of that is probably tricky though.
Really, the way genes are read might not be that different from Turing machines where you have a potentially infinite tape and a read head and the tape gives instructions about how to move the read head, right? So that could be a way to do something completely arbitrary:
Moving the head costs energy (discouraging long read paths and avoiding non-termination) as do any actions (such as growing or moving in some direction), and mutations would simply be the addition, removal, or replacement of genes, some of which encode what gene corresponds to what instruction, and other simply being such instructions.
I feel like your current approach to genes already is partway there, except the read order, gene length, and meaning is, at the moment, completely fixed
How can I run similar simulations with my own rules?
What coding language do you use to make your simulations?
I watched your videos without the volume in school, and I was so impressed. Then I rewatched one with volume, and I was so disappointed. Please use your real voice bro, I mean it's ok if you're nervous or something but it would add so much more personality.
I had an absolutely wild thought:
People have shown Conway's game of life to be Turing complete, in the sense that you can assign certain configurations of "life" to components of modern computer logic, allowing you to do computation via Game of Life.
What if you assigned specific locations and/or cells in your simulation to correspond to virtual input and virtual output of computer logic gates (AND, NOR, XNOR, etc), and provided a small "reward" (energy) for calculating specific logic gates?
Well, you would have a very inefficient evolutionary logic gate solver.
What if you then provided a larger reward for more complex behavior, such as solving certain algorithms with combinations of logic gates (which would be encouraged with the previous step)?
Well, you'd be able to evolutionary solve certain algorithmic problems in an abstract, evolutionary manner.
The big one: What if you produced a set of matrix multiplication problems to be solved in parallel, and provided a larger energy reward to the life form that could solve the most problems with the same configuration?
I think you could potentially produce a very efficient general matrix multiply solution, and I think it would be an interesting study of evolution in the sense that it would be interesting to see if it came up with a similar solution to us, or if it came up with a solution that was very alien, or even if the solutions from multiple runs of the simulation were not self-similar.
I distincly remember a different alife simulation doing just this, i dont quite remember he name but it rewards organisms depending on what operation they do ex. or gates will give little reward but xor gates being more complex will give higher rewards
source code when
Source code available to Patreon subscribers
At 1:40 should have broke into song.
What is something like this made in? Is it a game eninge, c++, processing, I obviously know nothing about any of it but I am curious. It seems super taxing as far as all the comuputations required to achieve these masssive simulations. Anyone?
He said it's made in Processing before.
I'm currently using the Processing environment.
This is a simplified version of Java for non-programmers.
Actually, that's what I am.
ах вы жук, на два фронта строчите!
code??
Source code available to Patreon subscribers
@@wallcraft-video i want to donate
@@wallcraft-video sounds like a nice practice, i like what you do with code
Welcome to the world, there's no turning back, even while we sleep, we will find you, everybody best behavior, turn you back on mother nature, everybody wants to rule the world. Skibidi dop dop dop yes yes. Speakerman theme
Cringe
Gen alpha detected
make a brain