most significant bits
newsletter of uw computer science & engineering
volume 20, number 2, winter 2011
university of washington
CSE logo
 home CSE Home    MSB archive Winter 2011 MSB    MSB Archive   Contact Info Contact Info 
contents
Center for Game Science Chair's message Mobile midwives ultrasound News Josh Smith joins CSE & EE Ed Felten named to FTC Datagrams Introducing Ms. Sprocket Awards IEEE fellows CRA recognizes undergrads Events Larry Snyder's swansong Annual Industrial Affiliates Distinguished Lecturers Annual pumpkin carving Bay Area alumni event
msb20.2 PDF

Give to CSE

We all know the difference one line of code makes to the success of new software. In the same way, one gift of any size makes a difference to the success of CSE teaching and research. Your gift provides the department with resources for scholarships, fellowships, research support, and funds to build the CSE community we hope you value. As you think about your giving, please consider making a gift to CSE. Every gift, regardless of size, helps maintain a quality experience for students that reflects the sense of community you've come to expect from us. Give online.

About MSB

MSB is a twice yearly publication of UW CSE supported by the Industrial Affiliates Program.

Editor: Kay Beck-Benton
Contributors: Ed Lazowska, Hank Levy, Sandy Marvinney
Photo credits: Bruce Hemingway, Mary Levin

We want to hear from you!

Do you have news you’d like to share with the CSE community? Comments or suggestions for future issues of MSB? Let us know! Email the editors at msb@cs.washington.edu and be sure to visit us online at: www.cs.washington.edu

Sign up for MSB email

MSB is now available via email. To sign up, send an email to
  msb at cs.washington.edu

Center for Game Science: Putting science into games and games into science

The world is full of important very hard problems that currently cannot be solved with computers or people alone. Zoran Popović, the director of the new Center for Game Science, believes that a symbiosis of people and computers that leverages the computational and creative strengths of each can make significant advances in science and in education, and perhaps can even lead to a more peaceful world. The new center aims to discover a general framework for solving hard problems using this symbiotic structure. For people to be highly effective problem solvers, they need to be engaged and involved for an extended period. Conversely, computers will be maximally effective in this framework only when they are optimally enabling human problem solving, creativity, and collaboration. Due to these unique requirements, the center will focus on games as an ideal mechanism capable of engaging people long enough to turn them into experts, and building the most effective human-enabling computer programs. The center will study automatic methods to guide this coevolution by creating self-adapting games that iteratively refine themselves based on large-scale data analysis of game play. Initially the center will focus on scientific discovery in biochemistry and bioengineering and creating student-specific learning games that cover key bottlenecks in early STEM education. The intention is to develop general set of principles applicable to all hard problems facing humanity.

Foldit: A problem-solving science discovery game

Foldit
By playing Foldit, thousands of novice players
worldwide produced a collection of protein structures
that were recently published in Nature. In this game,
players compete to discover the most compact
protein-folding structure by collaborative direct
manipulation of proteins. The calculated molecular
energy of the structure is the game score.

Foldit is a game designed to tackle the problem of protein folding. Proteins are small "machines" within our bodies which handle practically all functions of living organisms. By knowing more about the 3D structure of proteins (or how they "fold"), we can better understand their function, and we can also get a better idea of how to combat diseases, create vaccines, and even find novel biofuels.

It turns out that protein folding is a very hard problem. Although laboratory processes to determine the protein shape exist, they are expensive and very slow. For this reason, there has been a considerable research focus to predict the structure of these proteins computationally, primarily through largescale distributed computing. Unfortunately these distributed computing projects have shown promising but limited success. Seth Cooper (CSE grad student, and now Creative Director of the Center for Game Science) and Adrien Treuille (CSE Ph.D. alum, currently faculty at CMU), together with their advisor Zoran Popović, developed a game that augments the computational search for protein folds with large-scale human spatial reasoning ability. The state-of-the-art biochemistry simulations embedded within the game are created by a team lead by UW professor David Baker, a world-renowned expert in proteomics.

In Foldit, players are presented with a model of a protein, which they can fold by using a host of provided tools. The game evaluates how good of a fold the player has made, and gives them a score. Scores are uploaded to a leader board, allowing for competition between players from all around the world. Since its release, Foldit has gained over 200,000 players from all walks of life. In fact, the best Foldit players have little to no prior exposure to biochemistry. These players have helped to push Foldit to the forefront of protein folding capability, showing that for some particularly hard proteins, Folditproduced predictions outperform the best known computational methods. These results were recently reported in the journal Nature, marking the first time the leading scientific journal has published a paper with over 75,000 authors, the vast majority of whom with no background in biochemistry. More generally, Foldit has shown that it is possible to effectively "crowdsource" human problem solving to solve very hard scientific problems, and that the gaming environment is capable of turning novices into highly-skilled researchers. The goal of the Center for Game Science is to generalize and expand the success of Foldit to a wider range of problems in science, education, and beyond.

To play Foldit, please visit:

Discovering optimal pathways for learning early mathematics

Refraction screenshot
The Center's first prototype math game, Refraction,
recently won the Grand Prize in the Disney
Learning Challenge. Refraction targets conceptual
understanding of fractions, one of the key
bottlenecks in early math education.

In an effort to relieve the crisis in STEM education, CSE grad students Erik Andersen and Yun-En Liu and Professor Zoran Popović are leading a team of undergraduate students and artists to create video games that can discover optimal pathways for learning. They have focused so far on early math, including topics such as fractions and algebra, which are some of the main bottlenecks preventing students from pursuing a career in science. Currently, there are many competing theories for how best to teach these subjects, and a lack of experimental data to evaluate these methods prevents development of provably effective learning mechanisms. Large-scale in-school pen-and-paper studies can be prohibitively expensive and timeconsuming.

However, children naturally gravitate toward video games, which can attract tens or hundreds of thousands of players. The goal of this project is to leverage this popularity to acquire huge amounts of learning data and discover the best ways to teach early mathematics. If players receive different versions of a game that have particular concepts changed or introduced differently, and the game records how players perform, researchers can use this data to understand how students learn. An additional goal is to make the game adapt to every player, so that it will never be too easy or too difficult and each student will always be working on the next concept he or she needs to learn.

Using data from Refraction, an early prototype game, Andersen and Liu developed a new visual datamining method to analyze the behavior of large numbers of players to quickly uncover game design flaws and common player confusions. They also used the game's analytics framework to run large-scale experiments on player motivation, by randomly removing sound, music, animations, and optional rewards for some players and observing the change in play time and return rate. Ongoing in-school educational trials are evaluating the effectiveness of the games for improving pen-and-paper test scores. These games have already become a hit in the community. Refraction won the Grand Prize in the Disney Learning Challenge at SIGGRAPH 2010. Over 100,000 people have played Refraction since its release on Flash game website Kongregate.com (www.kongregate.com), and dozens of elementary school students are already playing the game at school. In the coming year, the game will reach up to 50,000 students through K12 Virtual Academies, helping to gather the data necessary to answer big educational questions.

To play the game, please visit:

Photocity: Reconstructing the world in 3D

Photocity
Photocity is played in the real world rather than in
front of a computer. To compete, players provide
images that contribute most toward reconstruction
of real world geometry. This image depicts locations
of images contributed by players during the
competition to reconstruct the UW campus.

Imagine a real world video game stretching across the whole of UW campus. There are virtual flags to capture and real territory to defend; you could even become the ruler of Suzzallo library! All you need to play is a digital camera, and you capture flags and buildings by taking photos of them.

This game is a reality. Developed by CSE grad student Kathleen Tuite, from the Center for Game Science, PhotoCity is a realworld video game for collecting thousands of photos. The purpose of the game is to collect enough photos to reconstruct not just the UW campus in 3D, but eventually the whole world. To play, PhotoCity players at UW go outside and take dozens (or sometimes hundreds) of photos of the buildings on campus from all different angles and then upload their photos to the website (www.photocitygame.com). The game automatically adds their photos to a giant, ever-expanding 3D model of campus, and awards points and virtual conquests to players who grow the model the most. As players take photos of different parts of campus, we get a more complete reconstruction that will eventually extend to cover all of UW. We currently have over 50,000 photos of UW.

Taking thousands of photos may remind you of Google Street View, where Google drives a car mounted with cameras down every single street so that you can see a picture of any place in town. PhotoCity is a lot like Street View in some respects, but very different in others. For starters, the Street View car cannot drive everywhere on campus. There are narrow footpaths and stairs that only humans on foot can get to. Secondly, it is expensive to get a car, special cameras, and gas. We want to collect photos for free! Essentially, PhotoCity crowdsources the photo collection process, and players use whatever cameras they already have, including cell phone cameras. Thirdly, and perhaps most interestingly, is how PhotoCity uses the photos: to make accurate, detailed 3D models.

PhotoCity is one of several 3D reconstruction projects out of UW. It is a direct descendant of Noah Snavely's (CSE Ph.D. alum, now faculty at Cornell) Photo Tourism project, which may be more familiar as Microsoft's Photosynth. More recently, the Rome in a Day project used hundreds of thousands of Internet photos to reconstruct all popular landmarks in Rome. We imagine using PhotoCity to fill in the gaps and connect all Rome in a Day models, essentially using our game to incentivize people to take the "missing" photos of Rome that are not on Flickr, but that are necessary for building a complete reconstruction of the city.

PhotoCity wraps a real world game around amazing 3D reconstruction technology and puts the ability to model a city or school campus in the hands of the players. It lets them compete for points, flags, and glory, but also collaborate on a 3D reconstruction without requiring special skills or equipment (beyond a digital camera and an Internet connection). To see how the UW campus is coming along or view the models growing in 21 cities and 7 different countries around the world, visit:

CSE logo
Computer Science & Engineering Box 352350, University of Washington Seattle, WA 98195-2350 Privacy policy and terms of use