When computers play games, artificial intelligence is the key to victory

Jun 22, 2005

From mahjong to Monopoly, bridge to Bingo, Sorry to Scrabble—games are serious fun. And with their diverse rules, they're also the perfect tools for exploring concepts in artificial intelligence (AI) and new approaches to programming, say Stanford computer scientists.

"Programs that think better should be able to win more games," wrote Michael Genesereth, computer science professor with the Stanford Logic Group, and Nathaniel Love, a computer science doctoral student, in an article on general game playing (GGP) to be published in the summer 2005 issue of AI Magazine.

The concept of general game playing is "drastically different," Genesereth said, from the computer programming done in the past to create programs like IBM's Deep Blue, which beat world chess champion Gary Kasparov in 1997.

"The computer just follows a recipe that has been given to it," Genesereth said of Deep Blue's highly specialized program. The applications for AI are limited in this case because the computer never has to "think" for itself. A program like Deep Blue demonstrates "the smarts of the programmer rather than the smarts of the program," said Genesereth. In AI research, what is important is the intelligence of the program itself.

General game playing requires that the computer be able to learn and understand rules, something that Deep Blue cannot do. Writing a program for GGP is like "trying to teach a child how to play a game" with the complication that "you would essentially be guaranteed that the game he will be asked to play is a game that neither you nor he has ever seen before," said Daniel Tarlow, an undergraduate who took Genesereth's course (CS227B) on GGP this spring. The final project for the course was developing a computer program capable of playing any game if given the rules. At the end of the term, the programs competed against each other in a tournament.

Competitions between GGP programs are an "evaluation technique for intelligent systems," said Genesereth. By playing the programs against each other, it is possible to compare the relative intelligence of each system.

The students discovered that simpler systems were often more reliable. "My team ran into the pitfall of trying to make things too complex," said Tarlow. "In the end, this led us to write code that behaved well in some situations, but not in all situations." Love noted that many of the programs capable of deeper reasoning were less stable in the competition setting. The winning team—Adam Reichert, Joseph Baker-Malone and Yi-Lang Mok, a.k.a. "The Pirates"—built a very reliable and robust game player that managed to correctly understand each game that was given to it, Love said.

Early programmers envision R2D2-like prototype

Programs designed for general game playing exemplify a malleable and comprehensive type of system that harkens back to the early days of computer science theory, said Genesereth. When the idea of computers was first being developed in the 1950s, early programmers envisioned machines capable of synthesizing an array of different inputs to reach an independent decision, said Genesereth. The idea was for computers to be much more "autonomous" than they currently are. It soon became clear that a system capable of synthesis would be much more complicated to design than one dependent on individual programs with specific functions, Genesereth said.

The work being done by Genesereth, Love and others pioneering GGP is a revitalization of this early theory. It also applies directly to AI research. Whereas today's computers can process information, GGP programs go beyond that to adapt to novel situations, said Genesereth, whose work was inspired by weekly board game sessions with friends. "The best part was sitting down with a game you had never played before and having to figure out how it worked," Genesereth said. This ability to receive and comprehend new rules and then adapt to them differentiates human intelligence from that of a computer. No computer program is currently able to do this.

'Hodge-podge' stumps HAL

One of Genesereth's favorite games to illustrate the differences between human intelligence and computer intelligence is called "Hodge-podge." The game is really three separate games all running at the same time: chess, checkers and tic-tac-toe. Computers are miserable at the game, because they are unable to separate the consequence of a move in checkers from that of a move in chess, said Genesereth. The computer searches for the move that will be the best for all three games at once, while a human would be able to recognize that the games were separate and that a move in tic-tac-toe would not have an effect on the checkers game. The challenge for programmers is to create a system to allow the computer to "think" on multiple levels all at once.

But the research is not just about games. The philosophy underneath GGP—that a computer program should be able to adapt with different information and make independent decisions—has wide application. Business management would be one sector that Genesereth thinks would especially benefit from this revolution in programming. A program that could automatically adjust to a new rule or regulation and make independent decisions based on those rules would have wide applicability for businesses in assessing their compatibility with specific laws. Currently, whenever a law changes, firms must recruit programmers to redesign their systems to accommodate the change in regulation. But an "intelligent" computer could simply be "told" the rule and adapt itself, said Genesereth.

To encourage more work on GGP in the AI community, the Stanford group will be hosting a GGP competition at this year's American Association for Artificial Intelligence conference in Pittsburgh, Pa., July 9-13.

"The nature of intelligence is synthesizing a wide array of information and making a decision," said Genesereth. General game playing provides the training wheels for both the programs and the programmers. Real artificial intelligence on a level with humans, the researchers avidly believe, is no longer just science fiction.

Source: Stanford University

Explore further: A forced PIN for all credit cards won't stop the biggest fraud

add to favorites email to friend print save as pdf

Related Stories

First in-situ images of void collapse in explosives

46 minutes ago

While creating the first-ever images of explosives using an x-ray free electron laser in California, Los Alamos researchers and collaborators demonstrated a crucial diagnostic for studying how voids affect ...

NASA maps Typhoon Matmo's Taiwan deluge

56 minutes ago

When Typhoon Matmo crossed over the island nation of Taiwan it left tremendous amounts of rainfall in its wake. NASA used data from the TRMM satellite to calculate just how much rain fell over the nation.

Recommended for you

Comfortable climate indoors with porous glass

12 minutes ago

Proper humidity and temperature play a key role in indoor climate. In the future, establishing a comfortable indoor environment may rely on porous glass incorporated into plaster, as this regulates moisture ...

Alcatel loss narrows in 2Q but revenue stagnates

21 minutes ago

(AP)—Telecommunications equipment company Alcatel-Lucent SA says its net loss narrowed in the second quarter thanks to lower accounting charges, while revenue stagnated and restructuring charges mounted.

Simulation models optimize water power

22 minutes ago

The Columbia River basin in the Pacific Northwest offers great potential for water power; hydroelectric power stations there generate over 20 000 megawatts already. Now a simulation model will help optimize the operation ...

User comments : 0