Neural Networks And MarI/O

Minecraft wizard, and record holder for the Super Mario World speedrun [SethBling] is experimenting with machine learning. He built a program that will get Mario through an entire level of Super Mario World – Donut Plains 1 – using neural networks and genetic algorithms.

A neural network simply takes an input, in this case a small graphic representing the sprites in the game it’s playing, sends that input through a series of artificial neurons, and turns that into commands for the controller. It’s an exceedingly simple neural network – the network that can get Mario through an entire level is less than a dozen neurons – but with enough training, even simple networks can accomplish very complex tasks.

To train the network, or weighting the connections between inputs, neurons, and outputs, [SethBling] is using an evolutionary algorithm. This algorithm first generates a few random neural networks, watches Mario’s progress across Donut Plains 1, and assigns a fitness value to each net. The best networks of each generation are combined, and the process continues for the next generation. It took 34 generations before MarI/O could finish the level without dying.

A few members of the Internet’s peanut gallery have pointed to a paper/YouTube video by [Tom Murphy] that generalized a completely different technique to play a whole bunch of different NES games. While both [SethBling]’s and [Tom Murphy]’s algorithms use certain variables to determine its own success, [Tom Murphy]’s technique works nearly automatically; it will play about as well as the training data it is given. [SethBling]’s algorithm requires no training data – that’s the entire point of using a genetic algorithm.

Continue reading “Neural Networks And MarI/O”

Genetic Algorithm Programmer Gets Functions

[Kory] has been writing genetic algorithms for a few months now. This in itself isn’t anything unique or exceptional, except for what he’s getting these genetic algorithms to do. [Kory] has been using genetic algorithms to write programs in Brainfuck. Yes, it’s a computer programming a computer. Be thankful Skynet is 18 years late.

When we first saw [Kory]’s work, he had programmed a computer to write and run its own programs in Brainfuck. Although the name of the language [Kory] chose could use some work, it’s actually the ideal language for computer-generated programs. With only eight commands, each consisting of a single character, it greatly reduces the overhead of what any genetic algorithm must produce and what a fitness function must evaluate.

There was one shortcoming to [Kory]’s initial efforts: functions. It’s relatively easy to get a program to say Hello World, but to do something complex, you’re going to need something like a macro or a function. Brainfuck, it its most simple form, doesn’t support functions. This throws a wrench in [Kory]’s plan to have his computer programming computer grow smarter and get over local minima in its genetic algorithms.

The solution to this problem was the creation of a new dialect of Brainfuck [Kory] calls BrainPlus. This takes the best parts of Extended Brainfuck and adds a command that basically serves as a break statement.

With this, [Kory]’s self programming computer can develop more complex programs. Already it has created a program to generate the first few numbers of the Fibonacci sequence. It only goes up to 233 because 255 is the maximum value for a byte, and the program itself took seven hours to generate. It does, however, work. Other programs generated with the new Brainplus functions include reciting 99 bottles on the wall and a program that multiples two values.

Even though [Kory]’s computer is spending a long time to generate these programs, given enough time, there’s really not much this program can’t do. Brainfuck, and [Kory]’s Brainplus, are Turing complete, so that given infinite memory and time it can compute anything. With the new addition of functions, it can compute anything faster.

All the code for [Kyle]’s GA is available on Github.


MegaUpload captcha cracking in JavaScript


This was certainly the last thing we expected to see today. [ShaunF] has created a Greasemonkey script to bypass the captcha on filehosting site Megaupload. It uses a neural network in JavaScript to do all of the OCR work. It will auto submit and start downloading too. It’s quite a clever hack and is certainly helped by the simple 3 character captcha the site employs. Attempting to do the same thing with ReCAPTCHA has proven much more difficult.

UPDATE: [John Resig] explained of how it works.

[via Waxy]