“It took nearly 2 decades, but computer is king of checkers” read the headline. The article appeared in the Chicago Tribune, and reported how a group based at the University of Alberta has at last “fully solved the game, creating an unbeatable program that will choose the best move in every possible situation.”
Hundreds of computers were employed to search through and analyze the 500 billion or so scenarios checkers affords. The project began in 1989. Within a couple of years, the team had developed a program -- called Chinook -- that amid protests was allowed to compete against humans in checkers’ world championships.
The Tribune article says that “Chinook beat the reigning world checkers champion,” although I’m not sure that is precisely accurate. In 1992, current champ Marion Tinsley defeated Chinook. Then in a 1994 rematch, Tinsley and Chinook played six games, all of which ended in draws. Tinsley then withdrew from the competition because of health complications. Soon afterwards, Tinsley was diagnosed with pancreatic cancer and would die seven months later.
Upon Tinsley’s withdrawal, Chinook played against the second-highest rated player and in twenty games won one, lost one, and had eighteen draws. (So, technically, the program did not really “beat the reigning world checkers champion.” Not then, anyhow.) Chinook’s creators then decided to stop competing with humans and instead try to “solve” checkers, a goal which has now apparently been realized.
According to the article, “the resulting program proves conclusively that checkers is a ‘draw’ game; in other words, perfect play by both players will always result in a draw.” Meaning checkers is like tic-tac-toe, I guess. If you and your opponent both know what you’re doing and play “perfectly,” there is no way the game cannot conclude as a draw.
Incidentally, this Alberta group is the same one whose poker-playing program called Polaris will be playing fixed limit Texas Hold ’em against Phil Laak and Ali Eslami next week at an artificial intelligence conference in Vancouver. The contest takes place on July 23 and 24 and will be structured a bit like the “duplicate poker” games Bob Ciaffone has been writing about recently for CardPlayer. Read more about the Laak/Eslami-vs.-Polaris match over at the “First Man-Machine Poker Championship” website.
Hearing the group has “fully solved” checkers brings a couple of thoughts to mind. One concerns the seeming futility of the enterprise. As the team leader, Jonathan Schaeffer, himself says, “In some sense, it is not interesting . . . . People play games for fun, and knowing you can never beat it is not fun.” By the way, you can actually play against Chinook online, if you want. (Software is a bit clunky, but it works.) You’re gonna lose, though.
I realize that such research isn’t simply about checkers, insofar as it advances our understanding of how systems work, generally speaking. The article notes how some of the findings here might be applied to business and biology. Still, doesn't pursuing the goal of “solving” a game -- and thus making the actual playing of the game seem somehow less significant -- feel like another example of how “we murder to dissect”?
The other thought that comes to mind is how different poker is from checkers, primarily because it is a “partial information” game where we don’t know precisely what our opponents’ have or what is coming next off the deck. For that reason, I tend to doubt that even limit hold ’em can ever be “fully solved.” (Indeed, for the same reason, poker is endlessly “fun” to me in a way that, say, tic-tac-toe is not.)
Of course, I suppose poker bot programmers needn’t worry about finding an absolute solution -- just one that works more than half the time should be sufficient to be profitable.
Or even slightly less than half the time, with rakeback.
Labels: *the rumble