Checkers has been mathematically solved -- indeed it's the largest game that has been solved so far.

What does this mean? It means that a proof has been worked out, in conjunction with some intelligent brute force move checking, that shows that if played perfectly, the game will end in a draw. And indeed, Jonathan Schaeffer, the researcher behind this (and an amazing games/AI expert in other areas, such as Hold 'Em Poker), has released a new version of his AI player, called Chinook, that cannot be beaten. The best anyone can do against this player, no matter how smart they are, is draw. End of story.

If you're having trouble understanding this, think of tic-tac-toe, which also always ends in a draw if played perfectly. Now we know checkers is exactly the same way, although while a human can be easily taught to play tic-tac-toe perfectly, I doubt the same could be said about checkers. That would be my first question for Schaeffer: can an expert learn to play it perfectly, now that we know how it's done? Or is the solution just too complex for us humans?

Scientifically, this achievement is interesting because checkers is a hard problem, and Schaeffer managed (albeit during over a decade) to finally solve it. That means similar approaches can be used for other similarly hard problems. Non-scientifically, this is interesting because it says something about games. Notably, I found this quote in the linked article worth quoting:

David Levy, president of the International Computer Games Association in London, UK, says he isn't planning to play against Chinook. "There would be a certain inevitability about the result."

Well, yes. But does this mean that expert checker players will no longer have any interest in playing? Unless my question to Schaeffer above is answered in the affirmative, probably not. Discrete games like checkers and chess are fun for humans to play precisely because the human brain is incapable of playing it perfectly. I am assuming that this will continue to be, even with Schaeffer's accomplishment, but if indeed it's possible to learn perfect checkers play, the game is effectively dead, just as tic-tac-toe is for those who care to learn the patterns.

So the next question is: can this happen to chess? The answer is yes, and it probably will one day, although the problem is on a much greater scale. If I had to guess, I would say that chess, like checkers and tic-tac-toe, always ends in a draw when played perfectly. Of course, it could be like Connect Four instead (or vice versa), where the first play always wins when playing perfectly. But if chess is ever solved, it is even less likely that perfect play could be boiled down to some trainable patterns such that a human could emulate it.

I guess that's why we call these discrete, rule-based back-and-forths "games" -- because deep down we know that the fun is all based in human shortcomings. Non-discrete games like baseball would be "solved" too, in a way, if a perfect robot batter could be constructed, but that's one kind of perfect play that normal humans could never emulate.

And so if you do figure out how to play checkers perfectly, and if chess is next to go down, then comfort yourself by learning to play Go. That's by far the largest traditional board game that humans play, and it's possible that it won't be solved until quantum computing becomes the norm. (via bb)