Computer gamers develop problem-solving algorithm that beats scientists’ best efforts

View Images

A group of computer gamers are making habit of outshining scientists at their own game. Most of them have no scientific background, but they have a track record of cracking tough scientific puzzles, including at least one that went unsolved for over a decade. They are the Foldit players, and for their latest trick, they’ve shown that they can not only solve hard problems, but also create problem-solving tools that outperform the best in the business.

Foldit is an online multiplayer game, created by Seth Cooper and Zoran Popovic at the University of Washington. It’s designed to tap the collecting problem-solving skills of thousands of people, by reframing scientific problems in a way that even a complete novice can tackle.

In the game, players work together to decipher the structures of proteins. These molecules are feats of biological origami; they consist of long chains of amino acids that scrunch up into complicated three-dimensional shapes. Scientists need to resolve these shapes to understand how the proteins work, and the usual methods involve bouncing X-rays off purified crystals (which is difficult) or using predictive software (which is imperfect). Cooper and Popovic went down a third route: they got gamers to play their way to a solution.

Their game converts the complicated business of protein structures into simple language and mechanics. While scientists might “rotate alpha-helices” and “fix degrees of freedom”, Foldit players use intuitive controls to “tweak”, “wiggle” and “shake” their colourful, on-screen shapes. The system seems simple, but the players have used it to outperform Rosetta, the state-of-the-art programme for solving protein structures (and the one that Foldit itself spawned from). They even helped to figure out the structure of a protein that gone unsolved for over a decade – it took them three weeks.

Their achievements are a testament to the power of human intuition and ingenuity, but the team behind the game wanted to better understand the strategies and tactics that the players were using. The obvious option would be to mine the data from the various games to extract the successful techniques. Instead, Firas Khatib opted to “rely on a superior learning machine: Foldit players themselves”.

The players had already mooted the idea of recording their best strategies as macros, which could be automatically applied to new problems. The team agreed and as of June 2009, Foldit players could encode and share their own “recipes”.

In the following months, the players created almost 5,500 different recipes; the graph below shows the 26 most popular ones. Each bar represents the number of times that recipe was used, and each coloured slice represents a different player (the solid pink bar represents a private recipe that was only used by its creator).

View Images

The recipes didn’t automate the game. None of them could solve a Foldit puzzle without human intervention. Instead, they acted more as power tools than robots: players used them to augment their own strategic skills, and they still had to choose the best time to use each one. For example, a recipe that makes small tweaks is useless at the start of the game, because the resulting structure might radically change later. Likewise, the more aggressive recipes that rebuild entire chunks of protein are most useful in the midgame, and they need to be carefully targeted to the right area. Khatib found that expert players grasped these subtleties better than novices.

The recipes also evolved over time. Some players devised entirely original ones, while others combined the best of existing efforts. Acid Tweeker v0.5 eventually spawned Blue Fuse, which in turn gave rise to many modified descendants. Blue Fuse was so successful that it rapidly spread through the community and came to dominate the game. It even proved to be more efficient than Classic Relax, the algorithm that has fuelled the Rosetta programme for the last decade. “In 7 months, they were able to come up with a method that outperformed our best published algorithm that had been used since 2002!” says Khatib.

View Images

Meanwhile, Khatib’s team had been working on overhauling Rosetta, and they developed a superior successor to Classic Relax, known as Fast Relax. On the surface, Fast Relax and Blue Fuse looked uncannily similar – the scientists and the gamers had independently arrived at strikingly comparable solutions to the same problem. However, Fast Relax wiped the floor with Blue Fuse in a straight comeptition.

“We were so impressed that the players had been able to beat Classic Relax that we didn’t really think much about the fact that they weren’t able to outperform Fast Relax,” says Khatib. But when he submitted his paper, an eagle-eyed reviewer pointed out that the competition had been rigged against Blue Fuse.

Fast Relax had been written in Rosetta, a far more powerful platform than what the Foldit players had to work with. Comparing it to Blue Fuse was like racing two cars, one of which had been secretly fitted with a Ferrari engine.  To level the playing field, Khatib coded Fast Relax into Foldit. The result: Blue Fuse emerged as the better and more efficient algorithm.

This achievement highlights how everyday people can contribute to scientific research if they’re given the right opportunities, even without a formal understanding of what they’re doing. It is, after all, one thing to solve a problem. It is quite another to create tools that will allow others to solve similar problems.

The team are now expanding Foldit’s scripting language to allow the players to come up with even more sophisticated algorithms. “We look forward to learning what Foldit player ingenuity can do with these additional capabilities,” write Khatib.

Reference: Khatib, Cooper, Tyka, Xu, Makedon, Popovic, Baker & the Foldit Players. 2011. Algorithm discovery by protein folding game players. PNAS http://dx.doi.org/10.1073/pnas.111589810

More on Foldit: