Mathematicians, third graders, and talkative defense department computers alike all know that there is an infallible way to play tic tac toe. A competent player can always force at least a tie against even the most savvy opponent.
In the July issue of Science, artificial intelligence researchers from the University of Alberta announced they had cracked the venerable game of checkers in the same way, identifying an infallible strategy that cannot lose.1
It doesn’t matter if the strategy is unleashed against a bumbling novice or a flawless grandmaster, it can always eke out at least a tie if not a win. In other words, any player adopting the strategy (a computer, say) makes for the most flawlessy grandmasterest checkers player of all time, period.
The proof of correctness is a computational proof that took six years to complete and was twenty-seven years in the making.
Tic tac toe and checkers are examples of deterministic games that do not involve dice, cards, or any other randomizing element, and so “leave nothing to chance”. In principle, every deterministic game, including chess, has a best possible guaranteed outcome2 and a strategy that will unfailingly obtain it. For chess, even though we know that an optimal strategy exists, the game is simply too complex for any kind of proof — by person or machine — to unearth it as of yet.
The UofA team’s accomplishment is significant, marking a major milestone in artificial intelligence research. Checkers is probably the first serious, popular game with a centuries-long history of human play to be solved, and certainly the most complex game solved to date.
Next stop: Poker
Meanwhile, the UofA’s poker research group is building Poki, a computer player for Texas Hold’em poker. Because shuffling adds an element of chance, poker cannot be solved for an infallible strategy in the same way as chess or checkers, but it can in principal still be solved for an expected-best strategy. Although no one is anywhere near solving poker, Poki is probably the world’s best poker bot. (A CMU team is also making great strides.)
Poki’s legitimate commercial incarnation is Poker Academy, a software poker tutor. An unauthorized hack of Poker Academy [original site taken down; see 2006 archive.org copy] may live an underground life as a mechanical shark in online poker rooms. (Poki’s creators have pledged not to use their bot online unidentified.)
Poker web sites take great pains to weed out bots — or at least take great pains to appear to be weeding out bots. Then again, some bot runners take great pains to avoid detection. This is a battle the poker web sites cannot possibly win.
| |
1Technically, tic tac toe is “strongly solved”, meaning that the best strategy is known starting from every game position, while the UofA team succeeded in “weakly solving” checkers, meaning that they found a best strategy starting from the initial game board configuration. |
| |
2The best possible guaranteed outcome is the best outcome that can always be assured, no matter how good the opponent. |
