Checkers Checkmate

The arti­fi­cial intel­li­gence and com­put­ing indus­try is abuzz with news that com­put­er sci­en­tists have ‘solved’ the 5000-year-old game of Check­ers (aka “Draughts”). A Cana­di­an team has cre­at­ed a com­put­er pro­gram that can win or draw any game, no mat­ter who the oppo­nent is.Checkers

This is the most chal­leng­ing game solved to date, with 500 bil­lion bil­lion pos­si­ble com­bi­na­tions. Com­pare this with anoth­er ‘solved’ game — Tic Tac Toe — that has only 765 pos­si­bil­i­ties. It took brute-force com­put­ing pow­er of dozens of com­put­ers more than 18 years to accom­plish this feat.

The approach tak­en by the researchers is very inter­est­ing:

The researchers began by look­ing at all one-piece end­ings, which were obvi­ous vic­to­ries. The algo­rithm then fig­ured out all the end­ings with two pieces and traced the out­come to a win, loss or draw. Then it moved on to cal­cu­lat­ing all the three-piece end­ings, and so on.

By 1996, the researchers had com­plet­ed the data­base for endgames with up to eight pieces. But mov­ing on to nine was beyond the abil­i­ty of machines at the time.

In 2001, a new gen­er­a­tion of com­put­ers allowed the team to repli­cate its pre­vi­ous sev­en years of work in a sin­gle month. By the time the pro­gram worked back­ward to include all sce­nar­ios with any com­bi­na­tion of 10 or few­er pieces, it had built a data­base of 39 tril­lion pos­si­ble board posi­tions, accord­ing to the paper.

The next trick was to find the fastest way to get games to the point where only 10 pieces were left. Check­ers play­ers allow three open­ing moves to be cho­sen for them, often at ran­dom.

Of the rough­ly 300 such open­ings, the researchers deter­mined that more than 100 were dupli­cates. Of those that remained, obvi­ous los­ing paths of play were elim­i­nat­ed because they would nev­er be cho­sen by a per­fect play­er, Scha­ef­fer said. Only 19 open­ings were need­ed for the proof.

The pro­gram fol­lowed each line of play for about 70 moves until only 10 pieces remained, Scha­ef­fer said. Then they meld­ed the data­bas­es togeth­er to com­plete the proof. The entire solu­tion includes 500,995,484,682,338,672,639 pos­si­ble board con­fig­u­ra­tions.

You can play against the pro­gram, see the proofs, view a list of solved games, watch a video, play a pod­cast, and more at the researchers offi­cial site.

My ini­tial reac­tion was that this takes the fun out of the game, but that’s not com­plete­ly true. Human games of check­ers will still be fun. But I do have a soft cor­ner for chess. I dread the day when com­put­ers will final­ly ‘solve’ chess. It is still a long way off — it has some­where in the range of a bil­lion bil­lion bil­lion bil­lion bil­lion pos­si­ble posi­tions, mean­ing that com­put­ers, with their cur­rent capac­i­ty, would takes aeons to solve it. But I know it’s inevitable.

Pho­to cred­it: BBC

This entry was posted in Eclectic, Science. Bookmark the permalink.