COMPARED with their human counterparts, today’s game-playing computer programs are really quite boring. However skilful they may be, each is only ever good at one game.
Take the chess-playing computer Deep Blue, developed by IBM. Although it beat human world champion Garry Kasparov in 1997, present it with much simpler games such as checkers or noughts and crosses (tic-tac-toe) and it wouldn’t have a clue where to begin. “Deep Blue can’t play checkers at all,” says Michael Genesereth, a computer scientist at Stanford University in Palo Alto, California.
Now a new breed of programs that specialise in general game playing (GGP) is emerging. Unlike specialist game players, which are pre-programmed with sets of strategies borrowed from human players, these programs devise their own game plans using nothing but a list of rules given to them 30 minutes before play begins. “The computer has to conceptualise the game and come up with appropriate strategies,” says Genesereth.
Advertisement
Last week he organised the second General Game Playing competition at the annual conference of the American Association for Artificial Intelligence (AAAI) in Boston. The winner, a bot called Fluxplayer, earned its creators Stephan Schiffel and Michael Thielscher at the Dresden University of Technology in Germany a $10,000 prize.
Until recently, the field of game-playing was dominated by specialised players such as Deep Blue and the chess-playing bot Hydra, which last year thrashed a human ranked seventh in the world. But since such specific programs now regularly beat humans, the focus of the AI research behind them is shifting to general game players.
“We can’t keep coming up with a one-of-a-kind solution to every problem. We must start generalising what we do, so that we can have general problem solvers,” says Jonathan Schaeffer, a games expert at the University of Alberta in Edmonton, Canada, who created champion checkers bot Chinook.
This new breed of multi-purpose programs could reap huge rewards for their developers. They could lead to military or household robots that no longer have to be programmed to carry out a specific task, but can simply be given their objective and a list of constraints and left to develop their own methods, says Genesereth’s graduate student Nathaniel Love, who ran this year’s competition. Mine-clearing bots, for example, could upload information about the area to be cleared – the equivalent of a set of game rules – and then create their own strategies to rid the region of explosives.
The approach would also be ideal for software agents designed to monitor investments, pay bills or manage a supply chain, says Genesereth. Such agents would not need to be reprogrammed to adapt to new contracts, laws or clients, but would just develop new ways to achieve the same goals when given a fresh set of rules. “I want to be able to say: ‘Here are the rules, you go figure it out’;,” says Genesereth. That is much closer to the way humans solve problems.
“I want to be able to say to the program: ‘Here are the rules, you go figure it out’”
To this end, Genesereth last year published a “game definition language” (GDL), a set of terms that can be used to describe any game, irrespective of what programming language it is originally written in. These essentially translate the rules of the game into a standardised form so that the program can follow them (see “Playing by the rules”). However, getting your program to play by the rules is only part of the problem. If it is to play well, it must be able to choose between good and bad moves.
One option is for a program to construct a map of all the legal moves open to it, followed by all the moves its opponent could make in response, and repeat this until it finds a strategy likely to win the game. This works well for simple games such as tic-tac-toe, where there are only a small number of possible moves, but becomes far too laborious for almost any other game.
So for more complicated games, one possible approach is to construct one of these “decision trees”, but instead of following each branch to the end, look only a few moves ahead. The program then evaluates the “state” of the game at this point along each branch, such as the possible arrangements of pieces on a checkers board, to determine how likely each is to lead to a win.
To evaluate each branch’s chances of success, the program considers each one’s game state as if it were actually the end of the game, attributing points to each branch according to factors such as how many of the opponent’s pieces have been taken, and then picks the ones with the highest scores. Those branches that offer little chance of success can then be “pruned”, freeing up processing power to search further ahead on the more promising branches.
However, the virtual player can be misled by this tactic, says Love. Although its score at the intermediate stages along these branches may be higher, the opponent could still strike back further into the game.
An improved approach is for the program to quickly analyse the rules of the particular game in the short period before play begins, and generate a set of heuristics – loose tactics to help it to play the game. For example, if the game involves a board, one tactic might be just to attempt to get across to the other side in as few moves as possible. If the game involves pieces, two opposing tactics might be to try to keep, or lose, as many pieces as possible.
This approach was employed by two of the bots taking part in last week’s competition: the winner, Fluxplayer, and Pires5600, created by Greg Kuhlmann and Peter Stone of the University of Texas at Austin, which came in third place. “We generate candidate heuristics, some of which might be strategically good, some strategically bad,” says Kuhlmann.
To weed the bad from the good, Pires5600 runs a mini virtual tournament before the real competition. The bot creates a set of “slave” bots, each programmed to use one of the candidate heuristics, and then pits them against each other according to the rules of the game. For the real tournament it then adopts the heuristics of the slaves that do well.
Despite the development of these techniques, however, GGP bots still trail woefully behind specialised programs like Deep Blue. “No one has provided a strong chess or checkers player,” says Schaeffer. “If I want high performance, I still have to build a highly specific game.”
Max Bramer, an AI expert at the University of Portsmouth in the UK, says that a competition with a hefty reward like Genesereth’s is probably the best way to spark the innovation needed to generate really smart GGP programs. However, he also believes the bots will need to be tested against humans as well as other programs if they are to improve significantly. “You need to have opponents who are stronger than you,” he says.
Sure enough, Genesereth is planning to pit the winning bot of next year’s competition against a high-calibre human, to help it grow stronger. “Ideally, I would like the human to be the president of the AAAI or some renowned game-playing expert,” he says.
Playing by the rules
How do you create a computer program capable of playing any game you throw at it? The first step is to create a standardised language with terms that you can use to specify the rules of any game to your program. That is exactly what Michael Genesereth of Stanford University in California has done with his game definition language (GDL).
In this year’s General Game Playing competition, organised by Genesereth and Nathaniel Love, also at Stanford, each “player” received a set of five rules written in GDL before play began. No human intervention was allowed once the rules were issued to the programs. The rules contained:
- A description of the game. For example, the description of tic-tac-toe would include the fact that there are 9 cells, that each cell can be blank or can contain an X or an O, and that in the game’s initial state all cells are blank.
- How each team takes its turn. For tic-tac-toe this would be: “When team A takes a turn, an X appears in one cell; when team B takes a turn an O appears”
- A list of all legal moves
- The objective of the game
- How the game ends
The system does not yet allow for games that involve chance, such as poker, or where players can keep cards or pieces hidden, but Genesereth says there is no reason why the GDL couldn’t be expanded to include terms for these games as well.
