News10Now.com

Friday, November 20, 2009   46º F

02/09/2008 11:59 AM

The death of checkers?

By: Ryan Burgess

WILLIAMSTOWN, MA. -- "Checkers only has 500 billion-billion. It's not quite the number of atoms in the universe, but we're getting up there," said University of Alberta Professor Jonathan Schaeffer.

That number, 500 billion-billion, is the number of theoretical board positions in a game of checkers. That might lead you to believe that the game can't be beat.

"In a moment of incredible naivety, I started a program running in 1989 to solve the game of checkers," said Schaeffer.

Almost twenty years later he's accomplished the death of checkers at the hands, or hard drive, of his program called Chinook.

"I now have a program that will never lose a game of checkers. You, being a fallible human, can play it, you might make a mistake, and you can lose. But you're never going to win," said Schaeffer.

It began as an obsession in the 1990s. Over 200 computers started working around the clock to figure out every board possibility. After eighteen years, it did. Now no one can win.

  To view our videos, you need to
enable JavaScript. Learn how.
install Adobe Flash 9 or above. Install now.

Then come back here and refresh the page.


"Sometimes a little bit of a deflated ego can be a humbling experience and I've seen many people humbled by my computer program," said Schaeffer.

"It's sort of an exciting result and it may open the door to solving games which have a larger search base. Both by better hardware and also some new discoveries in algorithm techniques," said Williams College Associate Professor Brent Heeringa.

Interesting possibilities, but 500 billion-billion moves on one checker board? Can humans even fathom a number that large?

"What you've got to do is walk so that you cover every single square inch of the entire surface of the earth. Once you do that, you'll know exactly how big 500 billion-billion really is," said Schaeffer.

Or we can just take his word for it.