Canada’s WestGrid helped crunch 500,995,484,682,338,672,639 checkers positions to produce an unbeatable player: Chinook. Image courtesy of Chinook

In 1994 computer program Chinook won the World Checkers Championship, making it the first program to win a human world championship.

Thanks in part to grid computing, Chinook is now officially unbeatable.

Using the resources of Canada’s WestGrid, Jonathan Schaeffer and his team at the University of Alberta, have solved the game of checkers, sorting through 500 billion billion checkers positions to prove that if played perfectly, checkers will always end in a draw: Chinook cannot be beaten.

Since it’s no fun to play an invincible opponent, Schaeffer has shackled Chinook’s powers and provided an online version of the program that you can play to win.

You can also check out the fascinating history of computing’s bid to beat checkers, which began in the 1950s with the efforts of Arthur Samuel.

WestGrid’s processing power played a several parts in this feat, from computing the back-end endgame databases to tackling some of the front-end solving. Chinook’s computing cycles required as many as 200 processors at once.

Schaeffer said WestGrid’s computing power “probably shaved six months off the time needed to finally solve checkers.”

Schaeffer began his research in 1989, tracking the habits of highly successful checkers players to create rules of thumb, or heuristics, and develop artificial intelligence principles by which to run his software.

WestGrid operates high performance computing, collaboration and visualization infrastructure across western Canada. It includes 14 partner institutions across four provinces: British Columbia, Alberta, Saskatchewan and Manitoba.