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.

Web scraping Amazon and Rotten Tomatoes

web-scraping-amazon-and-rotten-tomatos

[Rajesh] put web scraping to good use in order to gather the information important to him. He’s published two posts about it. One scrapes Amazon daily to see if the books he wants to read have reached a certain price threshold. The other scrapes Rotten Tomatoes in order to display the audience score next to the critics score for the top renting movies.

Web scraping uses scripts to gather information programmatically from HTML rather than using an API to access data. We recently featured a conceptual tutorial on the topic, and even came across a hack that scraped all of our own posts. [Rajesh's] technique is pretty much the same.

He’s using Python scripts with the Beautiful Soup module to parse the DOM tree for the information he’s after. In the case of the Amazon script he sets a target price for a specific book he’s after and will get an email automatically when it gets there. With Rotten Tomatoes he sometimes likes to see the audience score when considering a movie, but you can’t get it on the list at the website; you have to click through to each movie. His script keeps a database so that it doesn’t continually scrape the same information. The collected numbers are displayed alongside the critics scores as seen above.

Raspberry Pi plays MIDI without an operating system

For all the interesting DSP functions locked away in the Raspberry Pi, it’s still hard to imagine using the Raspberry Pi as an eminently capable software synthesizer, tracker, or sequencer. Running any of the usual Linux digital audio programs means – surprise – running Linux, and the performance penalty associated with that.

It would be much better if all these audio programs could run directly on the Raspberry Pi without an operating system, and [Joe]‘s project is right up that alley. He’s playing MIDI files without an operating system, in effect making the Raspberry Pi a very powerful embedded platform.

[Joe]‘s build is the first bare metal audio code for the Raspberry Pi. It’s actually an LV2 plugin host that will load audio plugins, read MIDI files, and shoot the resulting audio out over the 1/8″ jack on the Pi.  This work wouldn’t have been possible without a few Raspberry Pi bare metal tutorials put together by [David Welch].

Hopefully this won’t be the last we’ll see of [Joe] and his code; the Raspberry Pi has more than enough horsepower to be an amazing sampler, synth, beat machine, or the next generation of Akai MPC. All we need are a few brave coders to take up coding bare metal on the Raspberry Pi.

Raspberry Pi and R

R

[Stephen] picked up a Raspberry Pi to do a little hardware hacking and add a blinking LED to the many feathers in his software development hat. He picked up an analog to digital converter and a temperature sensor that would serve him well in a few projects he wanted to put together, including a weather station and a small Pi-controlled home brewing setup. He ended up not liking Python, and didn’t like the C-ness of wiringPi. He’s a scientist, so he’s most comfortable with R and Matlab. Of course, playing around with a R and a Raspberry Pi means replicating his sensor-reading code in R.

[Stephen] put together a neat little package that will allow him to read his sensors over an SPI bus with his Raspberry Pi. Yes, this functionality can easily be duplicated with Python, but if you’re looking to generate beautiful graphs, or just do a whole lot of statistics on something, R is the tool you need.

It’s a cool project, even if it is only measuring the temperature. Using R for the nerd cred isn’t bad, either.

A better template for your STM32 F3 dev board

If you’ve picked up one of those really cool STM32 ARM dev boards, you’ve probably poked around looking for a good toolchain. No fear, then, because [Matt] has your back. He put together a template for the ARM Cortex-M4 powered STM32 board.

[Matt] had been using a template for the STM32 F4 we’d covered before, but found the implementation a bit lacking. Wanting to exploit the functionality of his fancy STM32 F3 board, [Matt] took the F0 template whipped up by our very own [Mike S] and got it to work with the newer, fancier dev board.

There are a few bonuses to using [Matt]‘s template; the ARM chip in the F3 Discovery board has a hardware floating-point unit that is inaccessible using the Code Sourcery G++: Lite Edition toolchain. [Matt]‘s use of gcc-arm-embedded allows access to the hardware FPU, a great benefit for a great board.

Evolutionary algorithms computes the best blackjack strategy

blackjack_banner

Don’t want to learn about evolutionary algorithms the usual way, by generating sentences from random letters, or randomly placing pixels to generate the Mona Lisa? Then make your own evolutionary algorithm! With blackjack!

[Brian] has been playing around with evolutionary algorithms, and wanted a task that’s well suited for optimization. He chose blackjack, because of the limited number of hands that can be dealt to the player (32) and low number of hands the dealer can have (10).

Even with the low number of initial conditions for the player and the dealer, there are still 4.562 x 10^192 possible combinations of hands, so brute forcing a blackjack strategy would require the computational power of the entire planet. An easier way to compute a good strategy is an evolutionary algorithm, implemented by [Brian] with the Watchmaker Java library.

For each generation in [Brian]‘s program, a 32×10 grid was generated, one cell each for possible player’s hands against the dealer’s hand. In each cell, the computer put a ‘hit’, ‘stay’, or ‘double down’, and played thousands of hands with that strategy. The best strategies were bred and eventually [Brian] ended up with a good blackjack strategy.

The resulting best strategy is pretty good – using his strategy, he can walk out of an Atlantic City casino with 96% of the money he arrived with.

Computer tracking of billiard balls

The folks at the London-based startup GoCardless have a pool table at their office. Being the techies they are, they decided to build a system that automatically scores games. The results, while not fully complete, are still pretty impressive for something whipped up during a 48 hour hackathon.

The automated score keeper uses a webcam duct taped to the ceiling right above the center of the pool table, The balls – red and yellow balls replace the rainbow of solids and stripes to make things easier – are found using OpenCV.

This build isn’t quite finished yet. The people at GoCardless are looking to improve the accuracy of their setup by using a camera with a higher frame rate and possibly moving on to physics simulation to predict where the balls should be. If these guys get the time, they could add something like augmented reality pool table to improve shot accuracy.

Vidia after the break.

[Read more...]

Follow

Get every new post delivered to your Inbox.

Join 91,345 other followers