Computers master the game board
They reign supreme in checkers and chess. Poker may be next. What other areas will artificial intelligence soon dominate?
from the August 8, 2007 edition
Page 2 of 3
Superhuman and perfect AIs
The Deep Blue style of simply throwing processing power at a problem has led to breakthroughs in most of America's popular board games. Often programmers don't even need supercomputers to claim victories. Normal laptops will do just fine.
•The same year Deep Blue battled Mr. Kasparov, an applications running on a regular PC took down the world champion in Othello in a six-game sweep.
•A Scrabble world champ fell in January to a nasty program written by Eyal Amir and Mark Richards at the University of Illinois at Urbana-Champaign. The code anticipates what letter tiles its opponent holds and finds ways to block possible high-scoring moves.
•Researchers at University of Alberta announced last month that they broke down the game of checkers into every possible position – all 500 quintillion of them (that's 5 followed by 20 zeros). The team had already written a checkers code that was superhuman, now their program is perfect. The computer cannot be defeated. The best an opponent can do is tie.
•Simpler games such as Connect Four and Tic-Tac-Toe were "solved" years ago.
Except for Scrabble, these examples are what artificial intelligence researchers call games of "perfect information."
"That means games where everything is right there in front of you," says Jonathan Schaeffer, chairman of the computer science department at the University of Alberta. "There are no hidden moves, no secret information."
That's why Mr. Schaeffer is happy to put checkers behind him (he led the 18-year effort to crack the game) and focus on poker. His new project, Polaris, poses a much more interesting challenge, he says.
After all, how do you teach a computer to predict an opponent's hand?
Man versus machine
For the July tournament against Mr. Eslami and poker celebrity Phil Laak, the University of Alberta team developed three different computer personalities for Polaris. The first script played it safe, calculating and betting in the hopes of coming out even. The next was aggressive, putting pressure on its opponents. The team programmed the last personality to learn as it went, reading opponents and acting accordingly.
Polaris faced off against the pros at the same time but in separate games. To minimize the luck of the draw, Eslami and Mr. Laak received mirrored hands – so if one player received a great hand it meant that in the other match Polaris was dealt that great hand. At the end of each of the four rounds, the humans' scores were combined.
RSS feed