The artificial intelligence and computing industry is abuzz with news that computer scientists have ‘solved’ the 5000-year-old game of Checkers (aka “Draughts”). A Canadian team has created a computer program that can win or draw any game, no matter who the opponent is.
This is the most challenging game solved to date, with 500 billion billion possible combinations. Compare this with another ‘solved’ game — Tic Tac Toe — that has only 765 possibilities. It took brute-force computing power of dozens of computers more than 18 years to accomplish this feat.
The approach taken by the researchers is very interesting:
The researchers began by looking at all one-piece endings, which were obvious victories. The algorithm then figured out all the endings with two pieces and traced the outcome to a win, loss or draw. Then it moved on to calculating all the three-piece endings, and so on.
By 1996, the researchers had completed the database for endgames with up to eight pieces. But moving on to nine was beyond the ability of machines at the time.
In 2001, a new generation of computers allowed the team to replicate its previous seven years of work in a single month. By the time the program worked backward to include all scenarios with any combination of 10 or fewer pieces, it had built a database of 39 trillion possible board positions, according to the paper.
The next trick was to find the fastest way to get games to the point where only 10 pieces were left. Checkers players allow three opening moves to be chosen for them, often at random.
Of the roughly 300 such openings, the researchers determined that more than 100 were duplicates. Of those that remained, obvious losing paths of play were eliminated because they would never be chosen by a perfect player, Schaeffer said. Only 19 openings were needed for the proof.
The program followed each line of play for about 70 moves until only 10 pieces remained, Schaeffer said. Then they melded the databases together to complete the proof. The entire solution includes 500,995,484,682,338,672,639 possible board configurations.
You can play against the program, see the proofs, view a list of solved games, watch a video, play a podcast, and more at the researchers official site.
My initial reaction was that this takes the fun out of the game, but that’s not completely true. Human games of checkers will still be fun. But I do have a soft corner for chess. I dread the day when computers will finally ‘solve’ chess. It is still a long way off — it has somewhere in the range of a billion billion billion billion billion possible positions, meaning that computers, with their current capacity, would takes aeons to solve it. But I know it’s inevitable.
Photo credit: BBC