Chinook! From the NYTimes:
Checkers has been solved.
A computer program named Chinook vanquished its human competitors at tournaments more than a decade ago. But now, in an article published Thursday on the Web site of the journal Science, the scientists at the University of Alberta who developed the program report that they have rigorously proved that Chinook, in a slightly improved version, cannot ever lose. Any opponent, human or computer, no matter how skilled, can at best achieve a draw.
In essence, that reduces checkers to the level of tic-tac-toe, for which the ideal game-playing strategy has been codified into an immutable strategy. But checkers — or draughts, as it is known in Britain — is the most complex game that has been solved to date, with some 500 billion billion possible board positions, compared with the 765 possibilities in tic-tac-toe.
