Conundrum: Solved Games
A game is considered to be “solved” when all of the possible moves have been mapped out in a mathematical tree and thus the perfect set of moves can be determined regardless of an opponent’s play.
Tic-Tac-Toe is a pretty easy one. You solved this as a kid. There are three opening moves – corner, edge, center. And then you work from there.
Connect Four was solved in 1988. That’s because those new-fangled computer thingies were starting to get some real power behind them. If you want to play Connect Four against the best opponent you’ve ever played in your life, check out the applet on John’s Connect Four Playground which is programmed to play flawlessly, based on a database of pre-determined best moves. But if you go first, and play just as flawlessly, you can beat it.
Checkers was solved this past April by researchers from the University of Alberta. You can play against Chinook, which will play flawlessly, but the best you can hope for is a draw. It doesn’t matter how amazingly good you are at checkers. You will never win. For me, there’s something a little disturbing about that.
Could chess be next? There are an incredibly large number of possible games, but it must be finite. And if it’s finite, then the tree must conceptually exist even if nobody has been able to come close to mapping it yet. Some see chess playing ability as intutive and creative, and not merely a number cruching process. But if number crunching continues to get better, it might evolve to the point where we get a chess-playing program as unbeatable as Chinook.
To be clear, we’re not talking about a really, really good chess-playing program. We have that now. We’re talking about a program that can access an exhaustive database of pre-determined best moves in order to ensure the most favorable outcome possible.
What do you think?
Will computers ever solve chess?
December 12th, 2007 at 2:12 am
Will computers ever solve chess?
Hey, if the WOPR/Joshua can figure out Global Thermonuclear War, then anything’s possible.
December 12th, 2007 at 6:58 am
Yeah, but Joshua took way too long to figure out Tic Tac Toe for me to put any faith in his supercomputer cred, even by 1983 standards.
As for Global Thermonuclear War, Joshua determined that the only winning move is not to play. But that strategy only works if you go first.
December 13th, 2007 at 4:00 pm
As for my opinion, I think chess is solvable, and we’ll see it happen in our lifetimes. Computing power seems to be growing exponentially, and chess is finite. I say chess will be solved by 2040. It’s a humbling thought, but one that might open our minds to thoughts even more humbling.
I’ve been playing a lot of Connect Four against the applet for the past couple of days, and I’ve managed to win a good number of times. It feels like a fair fight. My advantage of going first and knowing I can force a win seems to balance out with the computer’s advantage of knowing every possible move and its consequences.
December 26th, 2007 at 3:54 pm
It ain’t what you don’t know that gets you into trouble. It’s what you know for sure that just ain’t so.