Using evolution to solve complex problems

I’ve started to work on creating a game of life in a virtual environment based off on John Conway’s Game of Life. The game itself is based on a simple set of rules and demonstrates some really amazing behavior based on the initial patterns to start it off.

The first phase that I am going through is to work out how to use the least amount of resources. The game of life runs best on large binary grids when watching animations of gliders as well as large oscillators. I could probably get away with using 1 prim to represent 40 cells using some of the techniques that I used for my old tic-tac-toe game. In short, I can use a prism to display 5 different faces. Each of those faces can show a portion of a texture representing 8 cells. Multiply 5 by 8 and you get 40. I can probably start of with a 10×16 grid (4 prims), but make it dynamically expandable in some way.

With the Tic-Tac-Toe game, there are 27 possible of combinations on a 3 celled grid displaying 3 different states (x, o, empty). You could probably call it a trinary numbering system. I used a lot of randomization to keep looking for possible ways to layout a texture. It took a fair amount of time for the computer to come up with something.

For this project, I had 256 possible combinations with an 8 celled grid of on/off. There are more combinations to look for, and using a horizontal texture map seemed a bit out of the question, as it was a bit complex just to do 27 for the tic-tac-toe game. Instead, I started looking at other options. I decided to go with a two dimensional texture map. I could simply layout all possible combinations on a 928(16 groups)x16 grid. With 14, 848 cells, this would be too large to manage. I decided to write a program that could detect patterns within a smaller grid going forward, backward, up, and down. This would give me a better way to layout the image. In addition, the program is able to detect patterns through wrapping. That means, the last column may have the first bit, and then the first 7 columns on the same row contain the rest of the byte. This further gives the advantage of condensing the total number of rows and columns needed on the grid.

Another problem that I was starting to run into was time. I am a problem that was so complex, that I couldn’t create an answer on my own, and making random guesses had the potential of not finding an answer in my life time. I started to look into the ideas behind evolution itself. Evolution has some basic fundamentals such as mating, sensing fitness, and mutations. There is far more behind it, but these were the ideas that I pulled out and applied to programming. I made a simple program that had the following mating ritual.

  1. Loop through each organism and pick two additional organisms.
  2. The least fit organism dies and is replaced by the offspring of the other two.
  3. Repeat.

Fitness was based on the number of unique patterns found within the organisms “DNA”. The DNA was an array of bits that represented if a cell in a grid was on or off. The offspring’s DNA was a combination of both of the parents. If one parent had a specific DNA as “on” and another as “off”, I randomly choose between the two. Once the hereditary portion was determined, I then applied mutations on 10% of the DNA and flipped them.

Just to mess with the gene pool, I decided to just kill off 1% of the organism’s, and replace them with fresh organisms with all new randomized DNA to simulate a change in population.

The end results were always different. Sometimes, the answer came immediately. Other times, the answer took a lot longer. One thing that I found helpful was the number of organisms available. A very large pool of organisms was usually able to solve the answer more quickly.

In the end, I now have a 16×16 grid (256 cells) of binary values that represent 256 possible values. This is 98.8% smaller than literally writing out each cell. I have tried to work with smaller grid’s, but they haven’t worked out to all 256 possible values just yet. I would have considered myself lucky if I could get one with an 8×8 grid. There is a possibility that I could get it smaller if I work with diagonal rows as well.

I’m sure that I got a lot of theory’s wrong, and there is probably a better way of finding an answer to this problem. Who knows? However, this was the way that I found the answer on my own. I just find it interesting that evolution is helping me to create the components to create the game of life.

Life Texture Pattern Calculator

Comments are closed.

%d bloggers like this: