The Mario Genome
Community Forums/Showcase/The Mario Genome
| ||
I was reading this thread over at the TIGForum earlier and noticed a link to this website showing an example of a genetic algorithm. I found this very interesting so I decided to create my own version of the app the author describes. The algorithm quickly makes an appoximation, but finds details much harder For the most part it works quite well, but the small population(only two) meant that it quickly gets into an evolutionary dead end and is unable to evolve out of it. If I wanted to experiment properly then I needed a much larger population, and the image generating algorithm isn't suited to that. As the genetic code is it's own entity it can be used to control any style of app that takes numeric input, and feeds back a quantifiable success rate. As most games take some kind of user input and give a defined score it made perfect sense to have the gene codes control a simple game and see how well they do. And so was born The Mario Genome.  Given enough time the genetic code can equal any human player 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. 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 equalling it. This was much harder and took them a very long(several hours) time to do, but they did make it at generation 7705. Ok thats enough talk here are the apps(win&mac) for anyone who wants to try them out. Evo is the image app and you'll need an image for it to test against, 256x256 pixels works best. Evoplat is The Mario Genome and the controls are on screen for that one. Some things to note. The generations may not go up every run, this is because the last batch of children were all worse performers than their parents, and the same parents have a new batch of children. My cpu is quite beefy so the apps run really fast on my setup, but I can't vouch for the speed on slower machines. The Alpha Mario is the Mario who was most successful on the previous run, he may not actually be the best of the current crop. As the genetic codes adapt to their current environment it is possible for the same codes to learn more than one game. As long as the codes can interface with the game and get quantifiable feedback then these simple gene codes can play it. What next? Well I'm done with this as I've used up too much time already. If I was to expand upon it I'd try something like Mario 1-1, and give the gene codes full game controls. Last edited 2010 |
| ||
| thanks for sharing , ill take a look can the marios 'see' the environment or are they merely selecting for the best weights between left right and jump Last edited 2010 |
| ||
| No not in this experiment. The only feedback the gene codes get are how far they got and how quickly they got there. Giving more feedback than that would have made a little experiment into a rather large one. It would still work the same way though, the only real difference would be that the gene codes could 'learn' specialised behaviour for different situations. |
| ||
| true, |
| ||
| this looks awesome, I'm defo trying this tonight. |
| ||
| . Giving more feedback than that would have made a little experiment into a rather large one. I can only imagine what kinda hyperbolic increase would be involved with more complex processes... Still, it's really interesting stuff and this is the groundwiork for all sorts of potential! Nice stuff, Oddball! |
| ||
| any plans to release the source? |
| ||
| This looks awesome Oddball. Simply fascinating! How long have you been coding for, if you don't mind me asking? |
| ||
| That's very interesting. Over a year ago I wrote a super mario bros framework to be used with an AI controller. The sim has 3 types of SMB enemies and breakable blocks, left and right movement and a random map generator. Its pretty quick, doing about 1500 games a second on my computer. I wrote the sim the day i heard about the SMB AI contest and was frustrated that the only language to use was java. This sim was intended to be compiled as a dll to be usable by any language. You can get the sim source and sample viewer with a (cheap) genetic algo controller HERE I also duplicated the Evolutionary image generation tool [EVO Mona Lisa] a long time ago, If oddball doesn't want to release the source for his, i'll put mine up for download too. |
| ||
| That's pretty interesting stuff GW. Looks like you've been working on some similar stuff. I might have a go at setting my gene codes loose in your sim if I get time, but to be honest I've probably spent too much time on this already. I'm actually supposed to be working on a different project at the mo'. @WERDNA: I've only been coding for ~20 years. |
| ||
| thanks, the api is pretty simple, so you shouldn't have any trouble plugging in your own controller. It would be interesting to try a multi objective fitness function. Instead of just calculating fitness based on farthest x value of the mario, perhaps something like: sqrt(timesteps_to_finish_map) - number_of_enemies_killed + (number_of_jumps) that could help eliminate needless jumping and being aggressive with koopa's at the same time. Last edited 2010 |
| ||
| Hello, interesting topic...I'd like to ask a question - I understand using the 'score' of some sort to determine the fitness of a gene sequence, ie number of kills, furthest distance reached, time taken to complete etc but what I don't understand is how you decide on when to 'jump' and when to 'go right'. Do the marios observe their current situation and respond, or how do they know when to jump. The AI I've usually coded in the past has been fairly 'reactional' - if a situation is encountered respond with xyz... How does one decide on a response with a genetic algorithm? What does each gene represent? |
| ||
| Matty, the answer is... any way you like. A gene sequence could simply code a list of moves, a set of weight in some kind of intelligent algorithm, or whatever. What Oddball is doing specifically is another question. |
| ||
| Ok I shouldn't still be working on this, but I altered the way genes control the Marios slightly. Behaviour should now be more consistent from generation to generation. The Marios will work out the solution much quicker, just over hundred gens in my first test, but might struggle to get a perfect speedrun. This also means I could lower the population significantly. I've added an equal number of controls for fairness, and I've altered the fitness test to use the amount of jumps as a tie breaker. If two Marios score the same on the fitness test then the Mario who made the least jumps is rated higher. Finally the genetic codes are now stored on exit to the file 'data.tmg' if you wish to start a fresh batch of gene codes then simply delete this file. The Mario Genome v2 [Win&Mac] |
| ||
| GW - how do you see the gameplay? i just get a blank screen |
| ||
| hold down the space bar. sorry i didnt put that in the readme. |
| ||
| Congratulations, you made Hackaday! About 3/4 down the page. http://hackaday.com/page/4/ Woof woof! Last edited 2010 Last edited 2010 |
   |