Games Computers Play

Artificial intelligence (AI) is a discipline that soared on the wings of optimism in the 1960s and 1970s, only to fall into disillusionment and even disrepute in the ensuing years. But in that time, AI has triumphed in a realm few people think about or take seriously: computer game-playing.

The biggest victory for game-playing computers was in 1997, when IBM's Deep Blue defeated world chess champion Garry Kasparov in a six-game match. The supercomputer, consisting of 512 specially designed chips, could consider 200 million moves per second, vs. about two moves per second for Kasparov's wetware.

Deep Blue's tour de force was the culmination of an eight-year, multimillion-dollar research project at IBM that led directly to advances in chip design, parallel-processing techniques and algorithms. That research continues as part of IBM's $100 million Blue Gene project, which during the next decade will build a machine operating at 1 quadrillion floating-point operations per second (1 petaFLOPS) to attack problems such as protein folding, molecular dynamics and drug design.

Writing software and building computers to play board games has taught computer scientists a great deal, and it has taught the artificial intelligentsia much about AI. Now research is heading in new directions, where experts say new techniques are likely to find applications elsewhere.

Jonathan Schaeffer, a computing science professor at the University of Alberta in Edmonton, uses games to aid his AI research. He developed parallel-processing algorithms to search a database of 1 trillion checkers positions, and those same algorithms found their way into commercial products for gene sequencing at a company he co-founded, BioTools Inc. in Edmonton.

Schaeffer says researchers once believed that the way to make computers play chess was to build into them the same expert rules and insights that the best players use.

"They tried to simulate the human brain, but they quickly discovered that, boy, that's really tough," he says. "The innovation was, 'If we are not smart enough to tell the computer what chess positions to look at, let's just look at them all.' " This "brute-force search," previously disdained by AI workers, proved to be the silver bullet. Today, the technique populates commercial optimization programs, Schaeffer says.

Research is now moving from games where raw searching is the answer, as it proved to be in chess and checkers, to those where that doesn't work well. For instance, in card games, there are too many combinations to consider and players don't know what cards other players have. Another example is a poker-playing program at the University of Alberta that uses a Monte Carlo simulation to assess the probability of various outcomes and neural networks to analyze the betting and bluffing history of opponents.

"We can generalize this technology so it has wider applicability," Schaeffer says. "For example, there are complex auctions with many players and interactions. How much should I bid? What are the benefits to me, and what if I don't get it? Who am I bidding against? Bluffing and misrepresentation are critical issues in everyday dealings."

Meanwhile, AI research is seeking to advance the state of the art in interactive computer games of the sort that populate teenagers' bedrooms.

John Laird, a professor at the University of Michigan in Ann Arbor, is "hooking up AI systems" to commercial games such as Raleigh, N.C.-based Epic Games Inc.'s Unreal Tournament so that characters in the games behave more realistically. "The idea of having intelligent characters in training and education is a big thing," Laird says. He has a contract with the U.S. Department of Defense to develop AI-based game techniques as replacements for expensive flight simulators and the human operators who are used to train fighter pilots.

Laird's brother-in-law is an actor who works part-time at Northbrook, Ill.-based Allstate Insurance Co., where he helps train agents by posing as an indignant customer demanding more money for claims. "You could create these kinds of training environments with AI systems instead of my brother-in-law," Laird says.

Read accompanying story:

AI researchers use games like Unreal Tournament to develop humanlike characters for training and education applications.
AI researchers use games like Unreal Tournament to develop humanlike characters for training and education applications.
AI researchers use games like Unreal Tournament to develop humanlike characters for training and education applications.
To express your thoughts on Computerworld content, visit Computerworld's Facebook page, LinkedIn page and Twitter stream.
10 super-user tricks to boost Windows 10 productivity
Shop Tech Products at Amazon