Checkers has been solved
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)
Comments (16)
*ahem*
NNNNNNNNNNNNNNNNNNNNNNNNNNNEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEERRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR *cough* RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR *cough* *cough* RRRRRRDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Damn. That was what I was going to say.
This guy has made an AI that nobody will want to play with because it's guaranteed to beat you! Talk about too clever for your own good.
It's not guaranteed to beat you, it's just guaranteed not to lose.
OK, guaranteed to beat the vast majority of comers. I can't imagine that there are too many expert checkers players.
Lorelei's comment is part of the reason game AI isn't used much in real games -- a game isn't fun to play unless there's a chance of winning, and current state of the art agent evolving designs could totally crush even the best human players (in, for example, FPS games). Even if they aren't evolving, their reaction times are naturally going to be better. So these techniques aren't used, or they're dumbed down so much that they don't differ significantly from pacman-like strategies (i.e. patterns that can be learned). There are other reasons why this is true as well, mostly relating to not adding anything to the gaming experience.
Very true, Jon May. But that opens the door to a whole new problem: using game AI to simulate human intelligence, rather than finding the most efficient way to solve a problem. That's what makes game AI more of an art than a science.
I was once on a flight to london. on this flight there was an entertainment system. You could watch movies, play games, and there was also a kid's games section. I checked it out and one of the games it had was Tic Tac Toe. I played it, and no matter what I did, I could not beat the computer. We always ended up in a draw. It was really frustrating, but as an adult, I realized that TTT, when played perfectly, ends up in a draw. But what about all those little kids who played on the plane and couldn't beat the computer. I bet they felt stupid.
That's a good life lesson right there.
I was just on a flight that had an entertainment system with games and such and the games were all really lousy. No action games. No mario or anything like that. Why couldn't they get good games, some side scrollers or some such? Or do some airlines actually have real video games? They had absolutely the worst pacman clone ever. You'd think a licensing deal with, e.g., nintendo would be easy to put together.
what DID they have? lee carvello's putting challenge?
The last plane I was on had a series of games that were basically all unplayable... partially because they were lousy games, but moreso because the control was bolted to the chair in a vertical orientation when it was originally designed to be used in a horizontal orientation, so you had to constantly think fairly hard about which button to push in order to make things on the screen move the way you wanted them to. It was awful.
And by the way, while AI on some sorts of games can easily be too good for the players to compete with, in other sorts of games they consistently fail to compete: strategy games (at least turn based ones like Civilization). Computers almost always have to resort to cheating (not playing the game by the same rules they player plays by) in order to be more difficult on higher levels. It's frustrating for the player and a general disappointment. Someone needs to turn Civilization into a giant game of checkers.
There are some games that when played perfectly, the second (or not first) player will always win.
I think solving the game will make checkers more fun when playing against human players. if you win, you truly have defeated your opponent. no luck involved. somewhere along the way the opponent made a suboptimal move or two.
Are you sure the control was bolted to the chair? Those can usually be ejected and have a retractable cord.
Like I said, there was an awful pacman clone. Probably some lame card games and a towers of hanoi or 15 puzzle thing too. I want action!
Yeah, it definitely was not removable from the armrest. It also didn't match the picture they gave you on the game system. It was a slapdash solution.
According to some colleagues, this is not the first time Schaeffer has claimed to have solved checkers, so I'm suspicious of wolf-crying until more evidence is shown
You think Nature would've published the paper w/o any peer review?