Tuesday, July 27, 2010 - The Vancouver Sun - "You Can Never Win Again"
The title of Jonathan Schaeffer's latest computing science paper, which appeared in the journal Science last week, has the succinctness that one associates with only the boldest, most thunderous of claims: "Checkers Is Solved."
For more than 20 years, Schaeffer's group at the University of Alberta has led the world in creating computer programs that can compete with humans at traditional human games. The announcement that Schaeffer's "Chinook" is now smart enough to never lose against any opponent, whether flesh or silicon, is the greatest triumph yet in the field; the most complex game hitherto analyzed to exhaustion by computers was Connect Four. For the first time, computers have attained perfect mastery of a game that intelligent humans have, in the past, devoted major parts of their lives to.
And though checkers devotees will deny it, the discovery cannot help but have psychological implications. Anyone who now breaks out the eight-by-eight board and settles in with the red and black counters must do so in the implicit knowledge that he is engaging in an idle activity that an inorganic calculating machine could perform with absolute assurance. He is mimicking an electronic device, and probably doing it pretty poorly. The pastime might once have been considered a crude art form, but now it has been placed on the level of reciting pi to a thousand digits or racing with a friend to add a column of figures.
One important subtlety did go unobserved in most of the coverage of Schaeffer's feat, which required 18 years of work by up to 50 computers. Technically, checkers has been solved only "weakly": Schaeffer has shown that a game will inevitably result in a draw with perfect play from the initial position by both sides, and he has produced an algorithm that can play perfectly in ordinary time. But Chinook does not possess a "strong" solution that would allow it to play optimally in any position outside its tree of perfect moves; if you forced it to start off the game with a series of mistakes, or merely presented it with a random mid-game position, it would be helpless.
In fact, Chinook "knows" nothing at all about checkers and could, in one sense, be said not to really "play" the game. It could be thought of as merely a very stupid sort of secretary or clerk than can play perfectly if he is allowed to start from the initial position and react to the opponent's moves by looking them up in a very large "book." The essence of the software is not the clerk at all, but the permanent "book" of optimal moves at his side, itself compiled through an arduous but equally brainless brute-force investigation.
Human players thus have some room to console themselves: "Ah," one might say, "Chinook plays perfectly, but doesn't 'understand' the game's patterns and themes like a human player. Indeed, it doesn't even know it's playing checkers --it's merely manipulating symbols."
But manipulating symbols is what we're doing when we play checkers (or write a newspaper column), and a win counts as a win even if the loser had a deeper understanding of the game than his opponent. And even if you don't play checkers, it is unsettling to consider that we all now have access to knowledge of exactly how God or some other omniscient creature would play the game. In fact, Chinook would never lose to God if He played fair.
The irony is that Schaeffer's checkers research is one of the less philosophically interesting things his group has been up to in recent times. He solved the essential tree-searching checkers problem years ago; since then it has merely been a matter of waiting and occasionally upgrading equipment and code. But his team is now developing software that can play Texas hold-'em poker against talented humans; the best iteration of their "Polaris," reigning world champion of computer poker, is being tested this week in a head-to-head game against star professionals Ali Eslami and Phil "The Unabomber" Laak.
So far, it is giving a decent account of itself, and perhaps that's bigger news than "Checkers is solved." Poker is much more like the things we ultimately want artificial intelligences to do; like marriage or politics, it is a rule-bound game environment in which each player has access to different information and psychology plays an enormous role. The solving of checkers is just one small step for the electronic children of man. The giant leap for automaton-kind lies ahead.