Checkers is Solved

I found an interesting write-up about the familiar game of checkers that has an unusual mathematical result. Like Tic-Tac-Toe, when played perfectly, it is a no-win game. This means that if both players make no wrong moves, the game ends in a draw. After all my years in grade school playing checkers on break, I never had a game end in a draw, unless the teacher called an end to break or one player got mad and pushed the board off the table. So what is a draw in checkers? To my imagination, it would be when each player has one piece left, so that one player could endlessly run away from the other as to not get jumped, or something to that extent. Called a tie, it was thought to be impossible so make the game end in a draw. 

Checkers is most like a military battle. The strategy, written by hardened veterans, deals with the analytical side of checkers. Being able to quickly calculate the possible moves at hand gives an advantage to the player. Being able to calculate all possible seems to be the common trend among experts and they calculate this quickly with an mXn rule; the number yoyur checkers left on the board times all possible moves each one can make. But, there is the opponent element. You could say that your opponent will probably do this, or probably do that, but you can never know until he/she does move. That is why being able to invision the next move, and the next move, and the next, proves to be an advantage in Checkers.

In 2007, Jonathon Schaeffer and colleagues used computers to prove the result. It took hundreds of computers and 18 years to prove the most complex game ever solved. A solved game is a game whose outcome (win, lose, or draw) can be correctly predicted from any position, given that both players play perfectly. Games which have not been solved are said to be "unsolved". This is a mighty feat considering there are roughly 5 x 10^20 possible positions or arrangements. How did they do it? The team considered 39,000 billion arrangements with 10 or fewer pieces left on the board and then determined if red or black won. Then, they used a special search algorithm to study the start of each game and to see how moves funneled into the 10 checker configurations. The solving of checkers represented a major benchmark in the field of artificial intelligence. 

So what did they do with this research? Can you think of anything better than matching the computer up against world champion checkers players? Nope! The program they called Chinook played former world champ Marion Tinsley to a series of draws and other respected players consisting of 40 matches. Chinook has a website and you can actually play him/her. Be prepared to lose... at best, tie. https://webdocs.cs.ualberta.ca/~chinook/play/

Checkers was not the first board game to be "solved." Many others including connect-4, tic tac toe, and awari have all be solved. There is also some information on the webpage detailing the specifics of the programming. Proof number search is best-first search algorithm used to solve many games. What!? Even a link to solve your own game. Solved games and helping you solve yours.