Christian Cieri – Illustrator
If you sit down and play a virtual game of checkers on your computer, there’s a good chance it’ll let you win. After all, computers aren’t very sore losers, and for poor hal9000-light sitting on your desktop, the more fun you have, the better it’s performed.
But it certainly didn’t need to lose.
In fact, for some computers, they could make it impossible for you ever to win. No matter how many long years you devoted to the game, how many strategies you tried, you could even practice for centuries and still not win.
In fact, it’s irrelevant how good you are; beating a sufficiently sophisticated computer at checkers has become mathematically impossible.
Checkers was added in 2007 as the latest of a long series of “solved games.”
These are games for which every possible game has been calculated until there are none left, and a conclusive way to either win or tie has been found for every scenario.
The most simple example of a solved game is tic-tac-toe; you may have figured this out in your late childhood, as the appeal of the simple cross of Xs and Os disappeared once you figured out how to make every game a tie.
Computers can do the same thing, but of course at many billions of times the speed and thus have achieved the solutions of games as comparatively complex as Connect Four, Hex and Nine Men’s Morris.
There are several hierarchies to solving games, however, that segregate the form and method of the solution. Ultra-weak, weak and strong solutions are all very distinct and are approached in very different ways.
Ultra-weak solutions determine whether a game will result in a win, loss, or tie given perfect play from both sides—contrary to the name, many mathematicians feel this is the purest form of proof, given the conceptual and algorithmic understanding they require to solve.
On the other hand, weak solutions are defined for games in which only one player makes perfect plays for every turn.
Strong solutions include a winning strategy for any stage of the game regardless of prior mistakes.
These latter solutions typically have no pure mathematical solution and must be solved through the brute force of computing power.
Given the strict conditions for each solution type, it’s been hotly debated as to whether a solved game can apply to systems that contain a random element.
Many solved games adhere to Zermelo’s theorem, which states that any two-person turn based game without chance or a tie condition must contain a perfect strategy. But some research teams have challenged that definition by claiming a statistical game can be solved simply through overcoming the human element–a poker robot named Cepheus has been claimed to have “essentially weakly solved” Texas Hold ‘em, as opposing strategies have a statistically negligible chance of succeeding.
But despite the increasing number of solved systems over the years, the repertoire of these games should not indicate that the solving process is easy.
While a game of tic-tac-toe can be solved on the playground, even the weak solution to checkers took almost 17 years of continuous computing power to determine.
It has been speculated that some games will never be solved simply due to their overwhelming number of possible moves—in the case of chess, while certain endgames of seven pieces or less have been solved, it’s possible that a strong solution for the full game will be impossible to achieve given the game’s 10^120 possible variations in play.
Jonathan Schaeffer, who leads the checkers project, predicted that a massive breakthrough in a technology such as quantum computing will be required before the game can ever be approached, although, he was quick to note that if there was one thing he learned from his work on checkers, it was “never underestimate the advances in technology.”
Ultimately, chess may join the ranks of tic-tac-toe in games that have been predicted inside and out, never to be played originally again.
But, in the meantime, you can take heart in the thought that maybe, just maybe, the next game you start will be one that even the most powerful computers in the world have not forseen.
Copeland is a member of the class of 2015.
