ConwayLife.com

Hello, nice to meet you all !

First of all, I apologize for my bad english in advance and will ask your forgiveness for not understanding everything that you may tell me : indeed, French people are among the worst when it comes to foreign language ! ^^

And second, sorry if I'm not introducing myself at the right place... !


I've come to this website as a total newbie about Conway's Game of Life, and to be absolutely honest, it is solely to find help for my homework, but in the mean time, I think that the project my teacher gave me may also interest you, as it is based on the Game of Life and Artificial Intelligence.

Every subject surrounding my homework is still a bit blurry to me and I may seem a total idiot at times, so I beg your forgiveness in advance, I don't think I'm quite qualified to achieve my project to its fullest, but I do have the motivation to have a good grade, to the very least ! ^^

My whole project consists of ultimately making an AI that may fabricate new patterns. How it will do this will be based on the genetic algorithm.

The advancement of my project is... quite in the late. My courses were a month ago and with my work (I'm working in parallel with my school, in order to get both diploma and experience at the end of the year, I don't have the exact expression to describe it exactly :X) and I didn't take the time to start any true programming of my AI.

I've downloaded Golly to try to get a clear view on what is the Game of Life. I've also gotten GenericSharp to start with my programming. The next step is to try many other tools in programming an AI that solves problems with the genetic algorithm.


I hope the community will help me to understand further everything I need to know to succeed in my project ! If I'm not clear at times, do not hesitate to point it out ! ^^

That sounds very neat, what sorts of things are you looking to learn about and/or work on specifically?
I'm not entirely sure how genetic algorithms and AI have been - or could be - applied in the context of Conway's Game of Life, but it seems like an interesting concept.

I have to say, that does sound like an interesting project. The description is ambiguous enough that I can't tell whether the problems that the AI is supposed to be able to address are simple engineering tasks, ground-breaking ones, or ones which push the limits of home computer hardware. Of course, that doesn't mean you should be discouraged - there's definitely still many improvements to be made when it comes to algorithms for solving these problems.

I need to hop off the forums for now, so I don't have the time to fret about writing a nice edited summary of Cellular Automata concepts and stuff right now, but I wish you luck in your projects here.

tn.o.nguyen wrote:First of all, I apologize for my bad english in advance and will ask your forgiveness for not understanding everything that you may tell me : indeed, French people are among the worst when it comes to foreign language ! ^^

Don't worry, your English seems just fine. We could try using short words... but maybe that won't be necessary, since a large fraction of the long words in English were borrowed directly from French, anyway, less than a thousand years ago...!

tn.o.nguyen wrote:My whole project consists of ultimately making an AI that may fabricate new patterns. How it will do this will be based on the genetic algorithm.
...
I've downloaded Golly to try to get a clear view on what is the Game of Life. I've also gotten GenericSharp to start with my programming. The next step is to try many other tools in programming an AI that solves problems with the genetic algorithm.

Are you limited to using genetic algorithms to solve problems related to Conway's Game of Life specifically? Or can it be any CA (cellular automaton)?

It's definitely possible to pick a cellular automaton that is more compatible with genetic algorithms than Conway's Life. You might start out by looking at the Shapeloop and New Shapeloop threads, for example.

Many posts in those threads might be a bit too technical and confusing, though, at least when you're just getting familiar with things. Maybe start with this rule and sample pattern in the "Complexity in loop rules" thread.

Please post any questions here, if you have trouble getting that rule and pattern to run in Golly. (Just File > Open Clipboard twice, once after selecting the rule text, and once for the pattern.)

These loop rules have a lot of extra states to allow them to store genetic information, whereas Conway's Life is a two-state rule.

Technically none of these rules are using standard genetic algorithms to evolve their loops, though. I suppose that what they end up optimizing is fitness for survival in a Golly simulation. But at least that's a start! There's definitely a genetic component there. Can you define your homework problem so that it can be answered by some new research that makes use of a rule like one of these?

Most Conway's Life problems turn out to be very difficult to apply genetic algorithms to, because the easiest "genes" are just the ON and OFF states of cells... but B3/S23 Life is a very chaotic system, and tiny changes often propagate across the grid at the speed of light, resulting in huge changes.

In other words, the smallest possible change in a "gene" -- one cell changing to a different state -- is not nearly small enough to allow a genetic algorithm to evolve improvements in the pattern.

For example, consider
versus versus
versus
The first is a still life, the second is a dying spark, the third is a pi explosion, and the fourth is a glider. From each pattern to the next is an absolute-minimal one-bit change.

It's as if you wanted to evolve a bird that flies better, in Real Life. You start with an emu, you change one base in its DNA and you get an eggplant. Change another base and you get an elephant, and you try again and end up with an eel. It's really hard to take small incremental steps toward greater fitness -- however you may define "fitness" -- when your only option is to make these kinds of huge leaps.

Here's a longer discussion trying to use genetic algorithms to find spaceships in Conway's Life. It's hard for anyone to even figure out how to get started defining an algorithm along these lines.

I think the most intuitive approach with any promise would be to genetically evolve the search program itself. The search program has *less* chaotic behavior in regards to mutations than the patterns we want to find themselves, and it has a structure that better resembles 'genes' as well.

Thank you very much for all your replies ! ^^

I'll be working on it this week-end, testing libs my teacher has recommanded, trying to get a better approach on GA ! And I assure you that I'll be reading each et every comment/explanation this community has to offer, though I'm not confident I will be able to ingerate the way the informations will be intended to ^^''

Everything you've explained to me is, I think, really a good start to organize what the GOL is about.

BlinkerSpawn wrote:That sounds very neat, what sorts of things are you looking to learn about and/or work on specifically?
I'm not entirely sure how genetic algorithms and AI have been - or could be - applied in the context of Conway's Game of Life, but it seems like an interesting concept.

I was also quite skeptical when my teacher gave us this project (amongst others). I was expecting a project to litteraly simulate life and find the best possible genes in order to create an army of a new ultimate race of zebra-fishes, but the Game Of Life using Genetic Algorithme isn't all about mad scientists I guess xD

Jokes aside, according to my AI teacher, we can totally make those two converge. He explained me how, but trying to translate everything may make it harder to understand later on if I'm not accurate enough, as I'm really bad at explaining back what's been taught.

To answer your first question, I think I should be expecting to have the best explanations when it comes to the GOL. I'll be trying to keep in mind the simplest rule of the GOL that is (thanks wikipedia)
000
111
000
becoming
010
010
010
in the next generation. In the mean time, my teacher said this project could really be useful to the community, and whether I totally bomb it or not, it could inspire the brightest of the community to bring the true solution ! ^^

Sphenocorona wrote:I have to say, that does sound like an interesting project. The description is ambiguous enough that I can't tell whether the problems that the AI is supposed to be able to address are simple engineering tasks, ground-breaking ones, or ones which push the limits of home computer hardware. Of course, that doesn't mean you should be discouraged - there's definitely still many improvements to be made when it comes to algorithms for solving these problems.

I need to hop off the forums for now, so I don't have the time to fret about writing a nice edited summary of Cellular Automata concepts and stuff right now, but I wish you luck in your projects here.

My teacher would think that it could be a huge step forward to the community, as it should be helping to find new patterns or even figure how to make a precise pattern. Or at least, when he is the one explaining, it seems so simple that I'm almost schocked nobody ever thought of this subject.

dvgrn wrote: Are you limited to using genetic algorithms to solve problems related to Conway's Game of Life specifically? Or can it be any CA (cellular automaton)?

Yes, the purpose of this project is to fully use the GA to find new patterns within Conway's Game of Life in particular.
I'm sorry if I'm not commenting on any other part of your answer, I just think that I should read it and concentrate fully on it, so for now, I just want to thank you all for your answers !

Sphenocorona wrote:I think the most intuitive approach with any promise would be to genetically evolve the search program itself. The search program has *less* chaotic behavior in regards to mutations than the patterns we want to find themselves, and it has a structure that better resembles 'genes' as well.

I'm not sure if I fully got your answer, but yeah, the purpose of the search program is to combine many solutions at the same time, while I try to validate myself what is considered a "good solution", so that the program will understand what it is programmed to ultimately looking for.

Let's say, for example that I want a starting pattern to stay indefinitely alive so that the area in which it lives (a square of 50*50 pixels) never dies out. Or I could be ordering it to at least be the exact same pattern every few generations, meaning that they will never cease to exist as long as no external change is brought.


I hope my answer will give you all a better idea of what I'm currently working on. I will work further on my side to get to the next level of my project, as I'm discussing more with the teacher about the subject. (hey, maybe he is hidden somewhere on this forum, watching my every move ? or he could even be one of you ?! 'suuuup teaaaach' ! :p )


TL;DR :
The purpose of my project is to make a good use of the GA with the GOL, to find interesting patterns, new or not.
I have to understand how GOL works on one hand, and on the other learn how to program an AI with GA.
The next stage will be to build an AI that is searching for the simplest patterns.
The interesting part is when the AI can make new complex and never seen patterns.

The ultimate goal that should assure me to have the highest score possible and even an idea to start a company based on AI is to make Gemini 2.0 that will be able to construct a machine that can indefinitely clone and evolve itself to overthrow humanity !! (just kidding ;p )


Many thanks to you all ! ^^

I think dvgrn's post gave a very accurate summary of why GA and CGOL are not very likely to work well together.

tn.o.nguyen wrote:when he is the one explaining, it seems so simple that I'm almost schocked nobody ever thought of this subject.

The topic has come up before, with people trying to find spaceships: see here. Also in that thread is another of dvgrn's responses demonstrating that what we as people think are "small changes" make large differences. This makes it really hard to put a bound on the impact of "mutations" typically introduced in GA.

You could do a GA without any mutations, just by breeding pairs of patterns using some "offspring" function. But any offspring function has to make a choice as to which parent gives the child each piece of DNA. The most intuitive pieces of DNA are just the state (OFF or ON) of the cell at each position. But then the smallest difference the offspring function can make also amounts to changing one cell, which has a large impact. That means, whatever your definition of a "fitness" or "score" for two parents, the "fitness" of their offspring is still nearly random. In a GA, the programmer assumes that two high-scoring parents make a higher-scoring child on average then two low-scoring parents. But if you average randomness, you get no correlation, so there is no way the algorithm can improve scores over time.

If someone can find a way of describing the information in a pattern such that a small change can be made with a small impact, that would make GA much more viable. But CGOL is specifically interesting because it is so chaotic. The mathematical definition of chaotic is that small changes have a large and unpredictable impact.

I don't want to just tell you it won't work. I anticipate you are going to try to make something anyway, so I can offer an approach that might do something. Limit your starting CGOL patterns and your DNA to a small test space. For example, the space might use only a few small stationary CGOL objects and one moving one, like the following: The "score" could be some function of the smallest rectangle enclosing the pattern after 1000 generations. Maybe the smaller, the better. Or perhaps the highest ratio of length:width. It's entirely up to you. Breed two parent patterns by taking the locations of the small objects from one or the other. Mutate by changing the objects out for other possible small objects, such as turning a blinker into a block. Then when you breed two high-scoring parent patterns, their offspring might have some higher score on average, even if only a little.

Even this restricted example might have a lot of the problems listed above. But it might be slightly better than changing one cell at a time, for the reasons dvgrn mentioned.

I wish you the best of luck!

biggiemac wrote:Limit your starting CGOL patterns and your DNA to a small test space. For example, the space might use only a few small stationary CGOL objects and one moving one, like the following...

Another specific, though very arbitrary, problem that you might be able to tackle with true genetic algorithms would be a method of "breeding" larger and larger connected still lifes. For example, if you think of a fishhook eater as having the following genetic information --

{start} S E E SE S W {end}

-- and a shillelagh is {start} S E NE E SE S W {end} --

then you could use standard genetic algorithms to recombine this "DNA" and get different connected strings.

It would probably be better to avoid hard-coded directionality, come to think of it, so I guess I really mean

{start} 0 +90 0 0 -45 -45 -90 {end} and {start} 0 +90 +45 -45 -45 -45 -90 {end}

where each number is how far you turn in degrees clockwise (positive) or counterclockwise (negative) before taking the next one-cell step. You can negate all the numbers and get another valid string, and you can also reverse the list of numbers... except that you have to record which way the still life is pointing at the end, and if it's 45 degrees you have to start with a 45-degree step.

If you get more ambitious, you could include two-cell steps, to be able to represent disconnected still lifes like table on table. But I'd advise starting with nice simple connected still lifes, and experimenting later if you have time.

Your fitness function could be just the population (assuming stability), or something more complicated like density -- population divided by bounding box area. You'd evolve different-looking still lifes depending on your fitness function.

No matter what the fitness function is, most mutant children would die immediately because they wouldn't be valid still lifes. But a small fraction in each generation would happen to be stable, which would increase the number of "species" you'd have available to cross-breed in future generations:
If you run this kind of genetic experiment for enough cycles, you'll start generating still lifes that no one has ever seen before. Now, unfortunately this isn't really such a big accomplishment, because pretty much any random 250-cell still life you might happen to draw by hand will also be one that "no one has ever seen before"... nobody tries to collect things like that, because a library containing all of them would have to be written on a Jupiter-sized hard drive with electron-sized bits. They're just too common to be interesting.

However, this exercise _would_ give you some useful experience with how genetic algorithms work, and it would give you an interesting-looking collection of evolved "species", probably different for each new simulation, but all recognizably similar if you use the same fitness function, or recognizably different if you come up with a different fitness function.

--------------------------------------------

Unfortunately, if you try to apply GA to connected objects when you're looking for anything bigger than period 1 -- well, or possibly maybe p2 or p3 if you went about it very cleverly in some way I can't quite think of offhand -- then you're basically going to be fishing in such a big ocean with such a small net that you'll have a very small chance of catching anything that's actually new, interesting, and unknown to the Life community.

Better to dodge that level of frustration and at least start with something you know you can succeed at, right? And then if the experiment gives you new ideas for ways to generalize the experiment, then take that and run with it.

Another way of looking at it:

Start by evolving still lifes, claim success at discovering some new ones, and then try to adapt the method to discover spaceships. It will work, sort of -- a glider is just {start} 0 0 90 45 {end} or {start}0 45 135 -45{end} or several other equivalent representations, after all, and an LWSS spaceship is {start at 45} 45 0 90 0 0 45 {end}.

A GA would have no trouble evolving from that to {start at 45} 45 0 90 0 0 0 45 {end} [an MWSS and then incrementally to {start at 45} 45 0 90 0 0 0 45 {end} [an HWSS]. Your algorithm will probably hit an evolutionary dead end there, though...!

If you want to evolve oscillators, maybe with a fitness function involving the size and period, then you could start with a blinker -- {start} 0 0 {end}. Theoretically you might get to a pentadecathlon ( {start} 0 0 0 0 0 0 0 0 0 {end} is a predecessor) eventually. But it's hard to see how the intermediate strings of zeroes would be judged to have any particular fitness as oscillators.

This is just the chaotic nature of Conway's Life causing trouble for you again. You aren't likely to discover anything actually new and interesting, because there are far more efficient ways to randomly search for new oscillators, starting with Catagolue/apgsearch.

dvgrn wrote:pretty much any random 250-cell still life you might happen to draw by hand will also be one that "no one has ever seen before"

Example image →