Mario is hard, and that’s mathematically official - 14 March 2012 - New Scientist
IF YOU have ever struggled to complete classic Nintendo games, don’t feel bad - they are officially difficult.
An analysis of the computational complexity of video games, including those in the Mario and Legend of Zelda series, proves that many of them belong to a class of mathematical problems called NP-hard. This means that for a given game level, it can be very difficult to work out whether it is possible for a player to reach the end. The results suggest that some hard problems could be solved by playing a game.
The commercial versions of games are designed to be doable, of course, but Erik Demaine of the Massachusetts Institute of Technology and colleagues studied versions without that constraint. “We are working within the same rules, but we are free to design the levels however we like,” he says.
The team transformed each game into a type of logical puzzle called the Boolean satisfiability problem. This asks whether the variables in a collection of logical statements can be chosen to make all the statements true, or whether the statements inevitably contradict each other.
For each game, the team constructed sections of a level that force players to choose one of two paths - equivalent to assigning variables in the Boolean satisfiability problem. Arrangements of enemies and power-ups are equivalent to logical statements. If they allow a level to be completed, that is equivalent to all the statements in the Boolean problem being true; if they make the level impossible, that is equivalent to a contradiction.
Many of the games in the Mario, Donkey Kong, Legend of Zelda, Metroid and Pokémon series prove to be NP-hard. That means deciding whether a player can complete them is at least as hard as the hardest problems in NP, a complexity class involved in the tantalising problem of P versus NP (see “Million-dollar proof”). Not every game in each series was included in the proof, as they follow different rules.
For Mario, the team also prove that the games are NP-complete, an additional property with important consequences. Many difficult problems can be converted into any problem in the NP-complete category. Then if you can solve the NP-complete problem - say, by completing a level of Mario - you have solved the original problem too.
That includes the travelling salesman problem - finding the shortest route between a series of points - which is of real interest in the field of logistics, and also the knapsack problem, used in deciding how to allocate resources. So theoretically you could convert an example of either problem into a Mario level, and play the game to solve it. That approach would be fun, says Demaine, although it would probably be simpler to solve the satisfiability problem directly.
The results offer mixed news for game designers, says Giovanni Viglietta, a computer scientist at the University of Pisa, Italy, who was not involved in the research. If it is an NP-hard problem to decide whether a level can be successfully navigated, there is no easy way for a designer to check this. But it does ensure that playing the game is interesting, as players can’t easily decide if they are heading the right way or straying into an impassable area of the level. “The game demands some creativity and ingenuity,” Viglietta says.
How a Computer Game is Reinventing the Science of Expertise [Video] | Observations, Scientific American Blog Network
If there is one general rule about the limitations of the human mind, it is that we are terrible at multitasking. The old phrase “united we stand, divided we fall” applies equally well to the mechanisms of attention as it does to a patriotic cause. When devoted to a single task, the brain excels; when several goals splinter its focus, errors become unavoidable.
But clear exceptions challenge that general rule. Two weeks ago, thousands of computer game enthusiasts descended on a convention center in downtown Providence, Rhode Island, to observe some of these exceptions in action. They were attending the championships of one of the world’s hottest computer games, StarCraft 2. Hands fluttered over keyboards like hummingbirds mid-hover at about fifty computers set up in a dimly lit open hall. Players, many of whom flew in from South Korea to compete, vied to advance through their brackets to the finals. This game is no joke, with the prize money to prove it—$50,000 went to the winner, a 16-year-old Korean who goes by the name Leenock. The agility on display in Providence —as seen in the players’ multitasking, their nonstop decision-making, and the stunning speed of their fingers—has not gone unnoticed by cognitive scientists.
For decades, a different game, chess, has held the exalted position of “the drosophila of cognitive science”—the model organism that scientists could poke and prod to learn what makes experts better than the rest of us. StarCraft 2, however, might be emerging as the rhesus macaque: its added complexity may confound researchers initially, but the answers could ultimately be more telling.
This real-time strategy game demands the frenetic pursuit of numerous simultaneous goals, any of which can change in the blink of an eye. Players play a god-like role over a cluster of creatures, leading them to develop their economy and prepare them for skirmishes with a neighboring society. Wildly popular among gamers—StarCraft 2 was the top-selling computer game in 2010, the year it was released—for researchers the appeal lies in the data each game generates. When two players face off, their computers each produce a record of the actions taken during the game. Called replay files, those logs reflect what a gamer was thinking at every stage of play. “I can’t think of a cognitive process that’s not involved in StarCraft,” says Mark Blair, a cognitive scientist at Simon Fraser University. “It’s working memory. It’s decision making. It involves very precise motor skills. Everything is important and everything needs to work together.”
That intellectual rigor and the corresponding data trail, multiplied across hundreds of thousands of players worldwide, makes StarCraft an unparalleled resource that scientists are only now tapping for the study of attention, multitasking, and learning. (As a rough estimate, at the time of writing about 11,000 games are being played on the servers of Blizzard Entertainment, the company that created StarCraft.) Recent experiments on computer games are beginning to suggest that players develop skills that could be useful in other contexts—skills that might allow those individuals to cope better with certain types of information overload. Thousands of these gamers are now contributing to a project under Blair’s watch, called SkillCraft, to learn what separates experts from novices and everyone in between. By all appearances this study of StarCraft players is the world’s biggest experiment on how expertise develops and, ultimately, on how we learn.
Video game research has reached a turning point: psychologists are no longer asking only whether the violence in some games corrupts young minds, or whether games are dangerously addictive, thus corrupting young minds. At least in some cases, gamers are being recognized for the specific forms of learning they cultivate, with the data trail that could finally unravel some of the major mysteries of the human brain.
To really appreciate why scientists are turning to StarCraft 2, you need to know a few basics of the game. Two players, connected over the internet, fight for control of a territory of which they have an aerial view. Each player begins with a small base of one of three species—terran (humans), zerg (insectoid creatures), or protoss (photosynthetic aliens). To win, one species’ army must defeat the other, a simple enough goal. But the number of variables that can shift during the game is enormous, demanding constant slight adjustments to strategy. Unlike in a board game, StarCraft players don’t take turns—they simply do as much as they possibly can and hope their opponent is not as fast.
The species’ first task is to start extracting minerals and a fictitious vespene gas, which form the foundation of a StarCraft economy. Each player must balance building up his or her economic production with developing fighters, defenses, and eventually more bases. A player must also try to discern the economic and military strategy of the opponent, whose base is initially hidden from view. As mineral and gas production ramps up, the gamer gains capital to spend on developing more advanced technology, a larger economy, or more fighters. StarCraft 2’s overarching strategic challenge is to decide how much time and money to devote to building up either an economy or an army.
But that’s just one level of play. When you attack, you do not simply dispatch fighters—you manually control them by using your mouse to click on them and set them in motion. A skilled player will monitor the health of individual fighters in the frontlines of a battle and pull them back to the rear as they lose strength, giving them time to recover while fresher troops bear the brunt of the attack. At any given time, you can have several dozen fighters with different abilities pottering around a map, numerous laborers busily mining minerals and gas, and various facilities producing new tools and resources that should be deployed immediately. With so many moving parts, even a top-level player can succumb to paralysis.
Translating those goals into cognitive load, the brain’s executive functions manage most of the game’s demands. Several types of memory may be engaged to keep track of the weapons at one’s disposal and the locations of multiple objects on a map; attentional systems allow a player to plan future moves, switch focus to different activities around the map, and evaluate the enemy’s strategy. Motor skills are needed to rapidly click around the map to move and implement actions.
In short, the game is a relentless exercise in multitasking and constant decision-making. The winner, often, is the person who can make the most moves—an elite player can perform about 5 or 6 actions a second, which translates into a flurry of key presses and mouse maneuvers (see video, above).
But you don’t have to be elite to be intriguing from a psychological perspective. According to the Entertainment Software Association, 72 percent of American households play computer or video games. With people engaging with games at all ages, scientists have become increasingly curious about how visually arresting—and in the case of StarCraft and similar games, cognitively demanding—software might be interacting with the brain. “From the perspective of the cognitive motor system, StarCraft is the most interesting thing you could do online,” Blair says.
The Trouble with Brain Training
The question now tantalizing psychologists is whether the rest of us can learn anything from these hyper-specialized multitasking gamers. Perhaps we, too, can accomplish some 300 things each minute—such productivity! Maybe we can learn to pick up new skills faster or use such games to stave off aging.
Given appropriate practice, humans seem to improve on almost any task they tackle. Ask us to sculpt a cake in the shape of Pinocchio, and with sufficient time and motivation we probably will. But multitasking abilities tend to resist practice. Perhaps Starcraft, somehow, possesses the elixir that can morph us into successful multitaskers.
Part of the problem is that once developed, human skills generally stay specific to the original task. Expert chess players, for example, have significantly superior recall of the positions of chess pieces on a board after a brief exposure than non-experts. That is as you might expect: years and years of practice have produced deep familiarity with the arrangements of pawns, rooks, and knights and what strategic opportunities they represent. But chess players turn out to be no better than others when asked to remember the arrangements of chess pieces placed at random, in configurations that could not appear in a game. Experiments in numerous other domains have demonstrated a similar lack of transfer.
In the last decade, however, some experiments have begun to suggest that video games might indeed teach transferable skills. Cognitive scientist Daphne Bavelier at the University of Rochester and her colleagues have used video games to investigate what kinds of learning humans are good at, and along the way they’ve turned up some promising, if modest, examples of brain training. (When scientists search for newly acquired abilities that transfer from one domain to another, they boil them down to skills so basic that you could be forgiven for responding with the raise of a single eyebrow.)
Early results suggest that gamers may have faster visual reaction times, enhanced visuomotor coordination, and heightened ability to visualize spatial arrangements. They may also be better at rotating an object in their minds and may distinguish more deftly between the trajectories of moving objects. Players might also have an edge when paying attention to several objects at once.
Because the tests did not mimic exactly the characteristics of the games participants played, the researchers are optimistic that more general skills were heightened. “There are few obvious links between chasing monsters across a star-spotted “spacescape” and determining the orientation of a single black ‘T’ on a uniform gray background, or between driving a car through a crowded cityscape while shooting at rival vehicles and counting the number of white squares that are quickly flashed against a black background,” Bavelier and colleagues wrote in support of the transfer effects in a 2008 article in Psychology and Aging.
The literature, however, is no Greek chorus of collective ascent. Some studies have failed to replicate the benefits of gaming, as a recent review article points out, and most experiments in the field have struggled to prove that they’ve lopped off all of the placebo effect’s nefarious tentacles.
The vast majority of these studies focused on first-person-shooter games, which may share only a few characteristics with real-time strategy games. Nonetheless, small hints from the StarCraft 2 community also suggest that players might be developing some generalizable expertise. Most current top players initially participated in the original StarCraft, an obviously related but nonetheless distinct game, or Warcraft, another variation on the real-time-strategy theme. Of course, a selection bias may be muddying the waters: the elite players who are drawn to these types of games may already have stronger-than-average multitasking skills. Even so, the fact that long-time players entered the new game at a substantial advantage suggests that they had honed some sort of Starcraftian skill.
In a paper published this year, cognitive scientist Joshua Lewis and colleagues at the University of California – San Diego analyzed what actions players took in 2000 games to see if certain capabilities stood out as hallmarks of success. Unlike previous studies, which tested participants before and after they played games to see if their behaviors changed, the approach taken by Lewis and colleagues allowed them to look for specific differences in what players are doing and perceiving.
They tracked several measures, including how many actions players took per minute and the distances between the locations where actions occurred across the map. Not surprisingly, they found that players who made the most moves tended to win. Of more interest was the second calculation. Distributing actions more widely across a map, which the authors argue reflects a player’s ability to distribute attention, also correlated highly with winning.
Now the question is whether people can learn to divide their attention more effectively. Professional Starcraft players belong to teams, with coaches and practice schedules, and they devote the majority of their time to developing their abilities. “If there is some methodology for building up multitasking skills, we might be able to figure out a way to train people to better distribute their attention,” Lewis says. “Maybe these teams have learned that implicitly.”
A New Model Organism?
In a traditional experiment on expertise, investigators corral about ten highly ranked professionals into a study and compare them with a similar number of novices. With StarCraft 2, scientists can mine the replay files of players at all stages, from chumps up to champions.
Blair, the Simon Fraser University scientist running the SkillCraft project, asked gamers at all ability levels to submit their replay files. He and his colleagues collected more than 4500 files, of which at least 3500 turned out to usable. “What we’ve got is a satellite view of expertise that no one was able to get before,” he says. “We have hundreds of players at the basic levels, then hundreds more at level slightly better, and so on, in 8 different categories of players.” By comparing the techniques and attributes of low-level players with other gamers up the chain of ability, they can start to discern how skills develop—and perhaps, over the long run, identify the most efficient training regimen.
Both Blair and Lewis see parallels between the game and emergency management systems. In a high-stress crisis situation, the people in charge of coordinating a response may find themselves facing competing demands. Alarms might be alerting them to a fire burning in one part of town, a riot breaking out a few streets over, and the contamination of drinking water elsewhere. The mental task of keeping cool and distributing attention among equally urgent activities might closely resemble the core challenge of Starcraft 2. “For emergencies, you don’t get to train eight hours a day. You get two emergencies in your life but you better be good because lives are at stake,” Blair says. “Training in something like Starcraft could be really useful.”
Indeed. But they know what we really want. Even more useful would be stumbling on the secrets of multitasking hidden in the replay files, then distilling them into helpful hints for the rest of us.