The Mario Genome!

Evolutionary algorithms can be used to solve problems that would take humans forever to do, but they can also be used to see if a computer can match what a human can do. A great example of this is “The Mario Genome,” a program developed by Oddball at the TIGSource forums. What it does is take a group of Marios with certain traits and uses evolution to navigate the course in as little time as possible.

This popped up at Reddit, apparently, but I have no memory of where I found it (sorry!). While I am sort of familiar with the idea of genetic algorithms, and many are cooler than what this does, I think the Mario Genome easily illustrates what the idea is all about to someone with little prior knowledge. The analogies to biological evolution are easily made here.

To use the program, click the links in the original post, download the files, unzip, and run either evoplat or tmg depending on the version you download. It basically runs itself after that point.

I’ll just let the author describe how it works:

The premise is simple, a platformer with two controls, right and jump, and a population of 1,000 genetically controlled Marios. Each run the genetic codes attempt the level, and are given feedback on their success. The 500 least successful codes then die and the remaining 500 reproduce to bring the population back to 1,000. This lifecycle is repeated indefinitely, and every generation, as a whole, makes improvements over the last. In theory the Marios should keep improving until they can complete the level in the perfect time.

Basically, mutations and selection. This is pretty effective:

So how did they do? Well the first task was for them to complete the level, which they did in only 1935 generations. It actually surprised me how quickly they learnt how to get to the end. Next I played the level myself and decided that a good speedrun time was 452 ticks(1/60 second). The evolving Marios made the time at generation 3010. Finally I calculated the best time possible was 431 ticks and set them about the task of equaling it. This was much harder and took them a very long(several hours) time to do, but they did make it at generation 7705.

Playing with the population size should allow for drift to play a role but I don’t know where to change that parameter. Luckily, however, the two different versions posted allow one to examine differences in population size with no coding knowledge needed.

Although there are some coding differences between the two versions posted, the major difference I see is population size. Version 1 has 1000 Marios and Version 2 has 1-10 Marios. While the coding of version 2 has the Marios reach the end more quickly than Version 1 (apparently), the problems of population size are easily detected.

There are basically 3 initial paths in the short level – high, medium, and low. High is optimal, but low is the easiest to enter first. The low path is what the Marios usually take, but it quickly becomes nearly impossible to navigate. Some of the randomized Marios can actually pull it off, but I cannot and the evolving Marios don’t seem to be too good at it either.

Figure 1: Top third = evolving population, middle third = a control group with randomized traits, bottom third = a Mario you can control. Here, the Marios have taken the lower path which is immediately beneficial, but imposes severe limits.

Figure 2: The Marios make some progress along the lower path. I become worried that they will be stuck, or constrained, to this phenotype and not be able to escape.

This is where it gets interesting though: Once a Mario takes the low path, he gets a bit of space to run on flat ground (Figure 1). That distance brings him farther to the goal than if another Mario just makes the jump to the medium or high paths. The low path quickly fixes and the Marios are pretty much stuck – the path is too difficult to navigate (Figure 2). To escape, the Marios basically have to wait for a lucky mutant that can make the jump across on the medium or high paths AND then run some more. It’s like a fitness peak! The population of Marios is stuck at the top of a low fitness peak but any descent is eliminated – instead a jump to another peak must be made. This problem does not happen to the 1000 Mario population due to sheer size.

Figure 3 shows the success of the lucky mutant compared to the low-path Marios. Once the Marios get to the high path, their success of reaching the goal is guaranteed.

A lucky mutant manages to take the high path and advance farther than those on the lower path. This highly beneficial mutation quickly fixes, eliminating those on the lower path.

The analogies to biological evolution are limited. There is a strong teleological bent to the program but introducing a moving goalpost could make the analogy stronger. Even if that change doesn’t work, I think programs like these have some larger use – they show evolution in action with Mario!

I also think it also shows the power evolutionary algorithms have in solving problems. This problem is fairly simple, but a friend recently told me how a genetic algorithm was used to independently derive a formula for the integration of a pendulum’s path using only addition and subtraction without the calculus theory.

For another example, check out the page linked to in the TIG forum post by Oddball, here, which uses a genetic algorithm to approximate the Mona Lisa. Really cool stuff!