The Game of Life

This is not an article on philosophy.

This is about a zero player game called, Life.

Considering its a zero – player game, who would want to play it???

Gosper

But before that, let me just give you a brief intro on what it is and how it is played. It is what one would call in computer science terminology as a cellular automaton. Cellular automatons are studied primarily by biologists, mathematicians and Computer Scientists.

In the second year of our computer science course, we had a paper on Thoery of Computation. And “automata”

was the most uttered word in the class. The paper was complete theory and did not seem to give any scope for fun or enjoyment, unless you were a nerd, or a mathematician.

It was in Robert Kruse’s, Data Structures and Design, that I first came across Life. So here’s the deal.

The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, live or dead. Every cell interacts with its eight neighbours, which are the cells that are directly horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

1. Any live cell with fewer than two live neighbours dies, as if by loneliness.
2. Any live cell with more than three live neighbours dies, as if by overcrowding.
3. Any live cell with two or three live neighbours lives, unchanged, to the next generation.
4. Any dead cell with exactly three live neighbours comes to life.

The initial pattern constitutes the ‘seed’ of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed — births and deaths happen simultaneously, and the discrete moment at which this happens is sometimes called a tick. (In other words, each generation is a pure function of the one before.) The rules continue to be applied repeatedly to create further generations.

Simple. Very basic indeed, simulations of how Life may exist, overcrowding, loneliness, all only too familiar for us humans. Simplicity is always a defining characteristic of an automaton. So there would be starting population, and once the sequence starts, it continues, without any intervention.

I see no further point in explaining in theory about stuff that you really can enjoy once you see it for yourself. I’ll direct you here to a Java Applet at Math.comhere Somewhere in the page is a link to a Java applet. I had also seen an online Flash implementation, as an active essay, which I am unable to retrieve now. Anyway, Go ahead. Experiment. Try your own signature, and see what it results in. How about if you draw a smiley, what happens??? Chances are most likely that the population eventually dwindled into nothing or it stabilised, i.e.., split up and formed gangs, stopped interacting with other gangs, and eventually settled down.

When John Conway published his ideas in Scientific American in 1970, he had conjectured that there could not exist initial populations, that would neither die off nor stabilise. He offered \$50 as prize money to anyone who could prove or disprove his conjecture. A team from MITlead by Bill Gosper won the prize. Gosper disproved Conway’s idea by developing an initial population, called the Glider Gun, which generated a glider after every 30 generations. Thats the picture at the top of the page. Eventually more and more initial populations were found that had traits similar to the Glider Gun. Many of them were more or less.., Guns. After every X generations the population would produce a unit that would fly away, and live an endless life. I have provided a link at the bottom, in case you are interested.

Glider

Gosper’s glider was a hit. So much that, this symbol called ‘Glider’, to the right was proposed to be adopted as the symbol of the hacker community. “The Hacker Community” I am referring to here is not the one that goes around busting the Internet. Any enthusiastic coder, who tweaks a software.., could be roughly called a programmer. I am obliged to give a reference here.

[ A similar, but not related concept is the Collatz Sequence. A simple rule indicating what one particular number would mutate into next. The sequence of numbers end, when you reach one. The conjecture is that from any number, on applying the rules, it always ends in the same pattern => 16-8-4-2-1 ]

It only gets more interesting. This, “Game of Life is said to be Turing Complete“. A Turing machine is essentially an infinite tape with a pointer attached to it. But, amusingly, you can do EVERYTHING using a Turing machine that you can do using a modern day computer. It may sound , a little insane perhaps, when I say that a tape can simulate a PC. I restate, this Game can simulate your PC. Look at it this way. You would believe it if I say that AND, OR and NOT gates could simulate a PC. Naturally, that’s what PCs are made of right? Maybe it would sound a little more sane or credible to say that the game can simulate all of these gates.

Hash Life

Consider implementing the Game of Life using say, Java. Most normal approach is to keep two copies of a 2D Boolean array and juggle between them as the current population. Bill Gosper also developed an algorithm for a much faster implementation of Life called Hash Life. There are various places where one could tweak the original approach, but Hash Life remains the one of the fastest algorithms known. I hear that there are only 200 or so implementations of the algorithm all over the world. Maybe one day, I could implement one on my own…

In retrospect, John Conway’s implementation was using using stones and pebbles.

A crazy Proposition

I have been recently getting more interested in Evolution, physiology and Genetic Algorithms. And I started wondering if one could evolve an initial population that would keep multiplying. It seems utterly non-sense in one sense in that the “World” is utterly chaos. How do you judge the fitness of populations? How would one implement a cross-over?? Anyway, just a crazy idea. I just wanted to put it down, in case, somebody stumbles upon it and gives me a hint.

A new kind of a Game

It doesn’t look visually enticing, but I am pretty sure its darn good. No, I have not played the game yet.

NERO

Now, I wasn’t expecting to write a post on a game, any time soon. Not even on DotA. But this is just too good a game for me to resist. I have been quite intrigued by the concept of Evolutionary Computation. One lazy Sunday, I started looking for more stuff on Evolutionary Computation. I found a lot. Particularly, a post-doctoral researcher’s blog. Julian Togelius. He’s published a paper on solving Sudoku using Genetic Algorithms. Serious stuff that! One of his other papers have been judged as one of the top ten AI game innovations of the year. This dude was one of the organisers of a Simulated Car Racing Championship atWCCI 2008. It seems there are not a lot of games available that actually use the latest Learning Techniques.

It was very funny in the beginning when I looked at the games’ graphics( WCCI ). Not a ‘Need for Speed’ then. On further reading, I found more on the rules of the game. From a programmer’s stand point, I thought, not very easy to program a controller. All the various cases. How could it adapt?? Perhaps learn?? Neural Networks then?? Neural Networks are to put it very very simple terms, like a brain. ( Please note that this is a gross over-estimation, it resembles the brain only in that it can learn new stuff. It is not even close to the functioning of a brain ). Perhaps neural networks would have been the answer if the same question had been put forth a few years ago. Today, ANNs alone will not suffice!!

Genetic Algorithms are now used to train Neural Networks. OK. Imagine you are given the job of teaching something to someone. If you couple GA with ANN, it’d something like, you just have to tell the person, how well he has learnt the subject, and he’ll keep improving all by himself. ( Of course, this is another gross over-estimation. If this is very non-technical please refer to one of the links given in the side )

It just got more interesting after that. I learnt that one of the Car controllers was evolved using rtNEAT( real time NeuroEvolving Augmenting Technologies ) developed by Kenneth O Stanley at University of Texas at Austin. NEAT not only evolves the best neural network of a given structure, it also evolves the best structure for the purpose. Fantastic stuff. As I kept reading, link after link. I get here. The page gives a detail overview of how NERO is played and how it is being developed. Please do read it. Its an interesting read. You’ll start wondering what kind of games will be the next big trend.

I have added on my links lists some of the more interesting blogs I have found during my research. Anyone interested in AI, please do have a look at these pages. I definitely plan on writing more posts on my own discoveries on the Web about AI, more particularly, Evolutionary Computing. And next time, I hope I try to convey more technically what I actually wish to convey. Cheers.