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

By Ed Yong | November 7, 2011 3:00 pm

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).

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.

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

More on Foldit:

CATEGORIZED UNDER: Select, Technology, Video games

Comments (11)

  1. E. Manhattan

    Talent infuses the human population, but most Einsteins end up herding goats or making shoes in sweatshops, most Curies end up raising children and doing factory work or hoeing weeds. It’s not talent that’s rare, it’s environments where talent can flourish. If Feynman had been brought up on a farm in Iowa, or if his father had died when he was a young kid, or if he’d been a she, we’d never have heard of Feynman.

    So – is the success of this project surprising? Only to people who don’t bother to talk to people who are living lives different from theirs, and who are not paying attention to the talent that infuses the human population! Thank heavens for the internet!

  2. Great post about harnessing the crowd-sourcing of science.

    In terms of improving algorithms Kaggle (featured in Feb 2011 Science Data issue, and more recently here ) is also going to be a major player.

    I have read a lot of news releases about the AIDS protein discovery on Foldit so when I first glanced at the post I thought it was going to be a rehashing of old news, but definitely putting the program in perspective is a value-added contribution.

  3. Strategic skill trumps automation once again!

  4. amphiox

    Strategic skill trumps automation once again!

    It’s more than just that, though. It’s cooperation and networking. The computer program still trumps any individual human.

  5. Hemo_jr

    Orson Scott Card should be happy. This is the essence of “Ender’s Game” come real.

  6. Michelle

    This gives renewed support for the idea that we go about educating our children all wrong. Sitting at a desk and doing the “basics” in order to pass a test put together by a company in Texas and graded by temporary workers is a terrible way to teach children. Make it interesting and challenging…child or adult will learn and create.

  7. prentice

    The fact that young people,most with no scientific background what-so-ever, can solve problems that have been puzzeling scientists for years speaks volumes. It proves it doesn’t take a lot of education but mostly common sense to solve problems. Common sense is a lot cheaper too. If a group of young people can do it on their own then we can save trillions by not earmarking all these dollars to science. Let the people speak and the scientists who think the common people are stupid may learn a thing or two.

  8. “It proves it doesn’t take a lot of education but mostly common sense to solve problems.”

    Er, no.

    First, this particular problem was framed in a very specific way that allowed groups of non-specialists to solve it. It was framed that way by specialists!

    Second, you assume “young people”… because they play video games? I said nothing about the age of the players.

  9. Leon

    If these discoveries are so important, perhaps this game should receive funding?

  10. prentice

    So Ed. Let me get this straight. “The problem was framed in a way that ALLOWED groups of non specialists to solve it”. So why weren’t the problems that have been puzzleing scientists for years framed this way back then? Maybe it wouldn’t have puzzled the scientists so long if someone already knew how to frame it so it could be solved. Sounds like another case of creating overtime to me. I guess I just assumed video gamers were young. My mistake.

  11. bob

    because there wasn’t as much emphasis on “crowdsourcing” (as it is often called) beck then?
    because it seemed to be more efficient to do it themselves?
    because not enough people had powerful enough computers to run such a program?
    because not enough people had a good enough internet connection to collaborate on such a problem well?

    it wasn’t easy to make the program that the people used.


Discover's Newsletter

Sign up to get the latest science news delivered weekly right to your inbox!

Not Exactly Rocket Science

Dive into the awe-inspiring, beautiful and quirky world of science news with award-winning writer Ed Yong. No previous experience required.

See More

Collapse bottom bar