So Many Schemes

A few days ago I attended a talk by Luis von Ahn from CMU. Luis von Ahn is one of the creators of the ESP Game and Peekaboom, both interactive, multiplayer online games that harness human computing power while also being entertaining. These games get people to help label images, generating data that will ultimately be used to make better image search engines and better computer vision image analysis and segmentation algorithms. Basically, Amazon Mechanical Turk got it wrong: fun is a better motivation than money.

Luis von Ahn opened his talk by saying that people spend many millions of human hours on solitaire each year, and that it would be useful if even a small fraction of that time could be harnessed to get people to play games that are also useful. If this is his goal, he has succeeded — some people spend over 40 hours a week on the ESP Game, which has been very successful.

Luis also presented a general approach for turning computationally hard pattern recognition problems into two player games and suggested that many problems can be solved in this way. He is currently thinking about such things as language translation and common-sense knowledge collection.

While it is cool that the ESP Game, if adopted by a major gaming site like Yahoo! Games, could label most of the web’s images in just a few months, the most exciting thing for me is the wealth of training data that this would generate for researchers to make better computer vision algorithms. This would also be true for things like language translation and common-sense knowledge collection — these would empower new algorithms.

Luis ended by pointing out that The Matrix got it all wrong: we’re useless as batteries, but we make great pattern recognition subroutines. That’s why the computers will need to keep us around, at least for the time being. They keep us entertained, and we compute for them. Oddly enough.

If you haven’t seen this, you absolutely have to check out this video (or the more complete version) about Will Wright’s new game, Spore. In Spore, you start life as a microorganism and evolve to the point of terra-forming whole galaxies and creating interstellar civilization. The scope of this game is immense, and this game is exciting on so many levels, not least of which is its obvious giant leap forward for game design, artificial life, and procedurally textured landscapes, environments, and worlds. I’m blown away.

I think one of Spore’s largest advancements is its leverage of other player’s content to bootstrap your world. Instead of requiring the game developers to come up with varied designs for thousands of species of life forms or civilizations, Spore finds content created by other players that will work well with your needs, and brings those to you in the form of tools or buildings to be purchased, other life forms, and alien races to encounter. This is brilliant. The game can only get more advanced and varied as players use it.

Spore’s worlds and creatures are procedurally generated. I previously wrote about procedurally generated environments, but I’ve never seen anything like this before. You can create creatures by combining many different parts, each of which has functionality. You can also reshape and mold parts as if they were clay. Then, the system analyzes the morphological structure of your newly created creature and figures out how it might move — how it should walk, fight, eat, mate, and more. The generated movements are plausible and visually pleasing. No motion capture or hand-animation required.

Spore tackles an incredible scale. I watched the video, and at every stage I thought, “wow, that’s a great game!”, then I found out that what I had seen was just the tutorial/prerequisite for the next, even larger stage of game play.

I just read a very interesting and insightful article at Wired called Why Data Mining Won’t Stop Terror. It’s worth a read and points to the same “base rate fallacy” that you see popping up when you do Bayesian analyses of cancer tests and stuff.

SongTapper.com is a cool AI application/demo/toy — tell users what song they’re trying to remember by having them tap the spacebar to the song’s beat. Their system is based on research [PDF] that the authors performed at Simon Fraser University and presented at AAAI05. The online system also seems to be able to learn new songs, which is very cool and might let it bootstrap it’s way into becoming a useful (or at least fun) tool. I’m not sure if it learns new songs by having the authors add additional MIDI files, or if it learns from the actual tapped rhythms. The later would be cooler, and certainly would be possible with some machine learning.

I’ve been exploring game AI for a private project. (Perhaps something I can announce at a later date.)

Read the full post for a partial breakdown of current game AI and some interesting tidbits.

(more…)