Building AI to Play by Any Rules

Photo: David Dear/Getty Images

Computer algorithms capable of playing the perfect game of checkers or Texas Hold’em poker have achieved success so far by efficiently calculating the best strategies in advance. But some computer scientists want to create a different form of artificial intelligence that can play any new game without the benefit of prior knowledge or strategies. The software would face opponents after having only read the game’s rulebook. An AI that can adapt well enough to play new games without prior knowledge could also potentially do well in adapting to the rules of society in areas such as corporate law or government regulations.

This idea of general game-playing AI has gotten a big boost from the International General Game Playing Competition, a US $10,000 challenge that has been held as an annual event since 2005. The AI competitors must analyze the unfamiliar game at hand—say, some variant of chess—within a start clock time of 5 or 10 minutes. Then they each have a playclock of just one minute to make their move within each turn of play. It’s a challenge that requires a very different approach to AI than the specialized algorithms that exhaustively analyze almost every possible play over days or weeks.

“This raises the question of where is the intelligence in artificial intelligence,” says Michael Genesereth, a computer scientist at Stanford University. “Is it in the program which is following a recipe, or is it in the programmer who invented the recipe and understands the rules for playing the games?”

Genesereth recently presented the latest advances in general game-playing AI at the 29th Association for the Advancement of Artificial Intelligence conference held from 25-30 January in Austin, Texas. The latest champions of the General Game Playing competition represent the third generation of AI to have emerged since the first competition in 2005.

But the idea of general game-playing AI goes all the way back to the original 1958 vision of John McCarthy, the computer scientist who coined the term “artificial intelligence.” McCarthy envisioned an “advice taker” AI that didn’t need to rely upon a programmer’s step-by-step recipe to tackle new scenarios, but instead could adapt its behavior based on statements about its environment and goals. To paraphrase science fiction writer Robert Heinlein, such AI could behave more like an adaptable human who can “write a sonnet, balance accounts, build a wall, set a bone,” rather than just perform a single task like a specialized insect.

Computer scientists use competitions based on games such as tic-tac-toe and chess as benchmarks of their progress. But general game-playing AI would not likely compete with specialized algorithms to find the best solutions to the ancient game of Go or heads-up no limit Texas Hold’em. Those specialized algorithms are programmed to crunch all the information sets about possible moves made by game opponents at each stage of play. Such an exhaustive approach often requires intensive supercomputing resources.

By comparison, general game-playing AI can easily learn to play new games on its own by doing the equivalent of translating a game’s rulebook into Game Description Language, a computer programming language it can understand. That means general game playing AI can rely upon just one page of rules to learn games involving thousands of information states; chess, for instance, can be described through just four pages of such rules.

Most examples of AI tend to fall in the category of specialized algorithms following preprogrammed instructions. Some AI uses the popular approach known as machine learning to slowly adapt to new scenarios; they are, in a sense, virtual newborns that know nothing and must learn everything for themselves. General game-playing AI provides an alternative approach, incorporating existing knowledge rather than having to learn everything on its own.

“I think there needs to be some balance between a machine that knows nothing to start and learns about world,” Genesereth says, “and a machine that is told everything about human knowledge and starts from there.”

The first generation of general game-playing AI focused on maximizing the moves available to itself and limiting the moves available to opponents. Such an approach had only limited success; computer programs still struggled to beat humans during the first “Carbon versus Silicon” competition held alongside the General Game Playing competition in 2005. Since that time, humans have never again beaten their silicon counterparts.

Starting in 2007, a second generation of AI applied the popular Monte Carlo search method by testing random gameplay moves and comparing the end results to see which moves are more likely to end in victory.  This boosted the second-generation AI’s success rates, but still represents an imperfect approach.

The third generation of general game playing AI that has dominated the competition may finally deliver on the field’s promise, Genesereth says. Such AI focuses on doing a better job of processing information about game descriptions during the start clock period in order to play more efficiently during the play clock period. It’s a change that could enable such AI to move away from just playing “slow-plodding” games such as chess and tackle more fast-paced ones such as first-person shooter video games.

Third-generation programs could also finally move general game-playing AI beyond playing games and into more serious applications such as the legal analysis of corporate and government rules. For Genesereth, that’s been the goal all along.

“Now we’re looking at applications beyond game playing that work in any situation with a set of rules that needs to be followed,” Genesereth said. “These techniques are going to be moving out of general game play into the broader arena of society as a result of what we’re doing on the third generation.”

Advertisement

Tech Talk

IEEE Spectrum’s general technology blog, featuring news, analysis, and opinions about engineering, consumer electronics, and technology and society, from the editorial staff and freelance contributors.

Newsletter Sign Up

Sign up for the Tech Alert newsletter and receive ground-breaking technology and science news from IEEE Spectrum every Thursday.

Advertisement