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.

 

Genetic algorithms become programmers themselves

AI

[Kory] has been experimenting with genetic algorithms. Normally we’d expect his experiments to deal with tuning the variables in a control system or something, but he’s doing something much cooler. [Kory] is using genetic algorithms to write computer programs, and in the process bringing us one step closer to the Singularity.

The first experiments with genetic algorithms generating applications did so in BASIC, C, and other human-readable languages. While these programs nearly worked, there were far too many limitations on what could be produced with a GA. A simpler language was needed, and after turning to assembly for a hot second, [Kory] ended up using brainfuck, an extremely minimal but still Turing-complete language.

The use of brainfuck for creating programs from a genetic algorithm may seem a bit strange, but there’s a method to [Kory]’s madness. It’s relatively simple to write an interpreter the GA’s fitness function can look into and come up with a score of which programs should breed and which should die. Also, the simplicity of brainfuck means a computer doesn’t have to learn much syntax and grammar at all.

Right now, [Kory]’s computer that can program itself only does so by creating simple ‘hello world’ programs. It should be possible, though, for this AI to create programs that take user input and generate an output, whatever that may be. Once [Kory] is able to have the computer generate its own fitness functions, though, the sky is the limit and the Singularity will be fast approaching.

On not designing circuits with evolutionary algorithms

[Henrik] has been working on a program to design electronic circuits using evolutionary algorithms. It’s still very much a work in progress, but he’s gotten to the point of generating a decent BJT inverter after 78 generations (9 minutes of compute time), as shown in the .gif above.

To evolve these circuits, [Henrik] told a SPICE simulation to generate an inverter with a 5V power supply, 2N3904 and 2N3906 transistors, and whatever resistors were needed. The first dozen or so generations didn’t actually do anything, but after 2000 generations the algorithm produced a circuit nearly identical to the description of a CMOS inverter you’d find in a circuit textbook.

Using evolution to guide electronic design is nothing new; an evolutionary algorithm and a a few bits of Verilog can turn an FPGA into a chip that can tell the difference between a 1kHz and 10kHz tone with extremely minimal hardware requirements. There’s also some very, very strange stuff that happened in this experiment; the evolutionary algorithm utilized things that are impossible for a human to program and relies on magnetic flux and quantum weirdness inside the FPGA.

[Henrik] says his algorithm didn’t test for how much current goes through the transistors, so implementing this circuit outside of a simulation will destroy the transistors and emit a puff of blue smoke. If you’d like design your own circuits using evolution, [Henrik] put all the code in a git for your perusal. It’s damn cool as it stands now, and once [Henrik] includes checking current and voltage in each component his project may actually be useful.

Building a word clock with genetic algorithms

Maybe it was a language barrier he ran into, or possibly an inclination to do things the hard and smart way, but we really like [Alessio]’s take on building the display for his word clock. Instead of relying on a pre-designed word layout, he made his own word pattern with a genetic algorithm.

While looking at other word clock builds on the Internet, [Alessio] noticed all the DIY copies used the same pattern of letters as the original QLOCKTWO word clock. There are obvious reasons for this, laziness chief among them, but [Alessio] decided to do one better. Armed with JGAP, he made a 10×10 German language word clock and a 11×11 English language word clock.

[Alessio]’s algorithm takes a list of regular expressions – ‘five past four’ and ‘four five’ are both valid expressions for 4:05 – and combines solutions together for a hopefully optimal solution. One added bonus of [Alessio]’s method is the ability to generate non-square word clocks. On his project page, [Alessio] put up examples for round, triangular, and diamond-shaped word clocks.

[Alessio] ended up building a 10×10 square German language word clock with an Arduino Nano, DS1307 real-time clock, RGB LEDs, and a few shift registers. Very nice work for a custom-designed word clock.

MegaUpload captcha cracking in JavaScript

megaupload-the-leading-online-storage-and-file-delivery-service

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]

Genetic programming

monalisa

[Ron Alsing] wanted to try out some genetic programming, so he created a simple test problem: Could you render the Mona Lisa using just 50 semitransparent polygons? The program starts with a random DNA sequence. It then mutates and compares itself to the original image. If the mutation is closer, it becomes the new sequence. The final image he shows looks pretty good after 904,314 iterations.

[prunesquallor] pointed out a genetic algorithm project of his own. It’s a flash program to evolve a car. The car tries to get as far as possible on a set terrain without the passenger circles hitting the ground. The wheel size and positions can change along with the spring length, constant, and damping. A graph tracks the best performance along with the mean. He’s planning on building a version that lets you change the parameters.

[via Waxy]