Checkers is Solved. Next?
There are 500 billion billion possible ways to arrange pieces on the board during a game of checkers. Still, after 18 years of research, Jonathan Schaeffer, a computer scientist at the University of Alberta in Canada, announced last year that his program had "solved" checkers-that is, it was unbeatable. How soon before we solve other popular games?-Kate Pickert
| Heads-Up Texas Hold 'Em|
Time to Solve: 5 years
Poker is generally no fun with just two people, but it's impossible to "solve" (in the scientific sense) with any combination of more than two players.
Time to Solve: 10 years
The element of chance (rolls of the dice) makes the number of board combinations huge (1020). Scientists know how to solve backgammon, but current computer technology can't do it.
Time to Solve: 100 years
No one knows exactly how many possible board positions for chess exist, but it's thought to be somewhere between 1040 and 1045. Schaeffer predicts that the game will not be solved in his lifetime.
Time to Solve: Anybody's guess
The extremely complicated game, which originated in ancient China, has far more board combinations than chess (10100). Scientists have no idea how to solve it and won't even venture to guess when the technology will exist to definitively do so.
Turn the page to check out how IBM is breaking Moore's Law.