2010-03-27

One man's game is another man's crowdsourced computation.

I stumbled across an iPhone app today called "The travelling salesman". To those of you with a background in computer science:  yes, it is exactly what you think it is.  From the blurb on the page:
The Traveling Salesman is a new puzzle for the iPhone. The object of the game is simply to find the shortest route between a set of cities, visiting each city once and returning to the starting city. In game are presented cities from each of the 50 states. Each state has four levels of difficulty for 200 puzzles in total.
As I read the blurb it struck me that for any computation where you need to find a viable solution to NP-complete problems you could map the concrete problem you need to solve into a suitable on-line game, possibly disguising the problem somewhat, and have the faceless millions go at it mechanical turk-style, picking what is at any given time the best solution that has been discovered.

That is, if you succeed in making the game interesting enough and succeed in getting mass adoption.

I am sure I am not the first person to think of this and I will no doubt be bombarded with links of clever projects who have found ways to do this in a systematic manner to broad classes of problems.  Nothing would please me more.

If I am mistaken in this assumption I do hope that someone would explore the subject further and that this someone is not averse to the idea of actually writing code rather than just make the idea an object of dull academic masturbation.

5 comments:

  1. I have heard of several projects that allow people to view images on websites to, for instance, identify things like comets and supernovae in photographs from automated telescopes. The idea is to use volunteers crowdsource the type of pattern recognition tasks that come naturally to heuristic computers like the human brain, but are very difficult for digital ones. At least one of these presents the information as a game, though it doesn't seem to be the type of thing you're likely to play just for fun.

    I've never heard of a puzzle being hidden in a commercial game so that players can solve it for the creators except in fiction (this happened in the first episode of Stargate Universe). It reminds me of the spammers who trick internet users into solving captchas for them so that they can register email addresses automatically. This is usually done by offering free porn. Finding a way to turn a puzzle for which the solution is valuable into a game so that people will solve it for the fun of playing would be more difficult.

    ReplyDelete
  2. The playing itself doesn't even have to be fun.

    Why not give people points for solving menial, repetitive tasks, let's call them experience points. And then once they get enough they gain a level. Give them some privileges for gaining levels, and put up several scoreboards showing various highscore lists, so they have something to compete for.

    Now if only someone could figure out a way to crowdsource all those hours wasted playing WoW, to turn that grinding into something productive.

    ReplyDelete
  3. Given that there are already people making a living "mining gold" in multiplayer online games, this might be a good storefront for services like Amazon Mechanical Turk :-).

    I predicted a while back that the virtual economies in games would soon be subject to taxation. Perhaps when companies begin to farm out work in this manner there is no way around this legally.

    ReplyDelete
  4. As chance would have it I came across this http://fold.it today. From what I can tell they haven't figured out if humans are more efficient than computers yet; it's just an experiment.

    ReplyDelete
  5. That's one of the ones I was thinking of, I was going to post the link, but I couldn't remember what it was called.

    ReplyDelete