Jul
23
2007

Checkers is solved…on to the next problem

Perfect plays: Through 18 years of computer analysis, researchers at the University of Alberta have figured out all the moves to play the perfect game of chess. Their computer, they say, will never lose a game. (Photo by Bring back Buck)
Perfect plays: Through 18 years of computer analysis, researchers at the University of Alberta have figured out all the moves to play the perfect game of chess. Their computer, they say, will never lose a game. (Photo by Bring back Buck)
Games don’t come much easier than checkers, right? Red and black discs, 12 on each side, jumping around diagonally on a board featuring 64 squares.

Well, it’s all over now. Computer researchers at the University of Alberta have announced that they have finally “solved” checkers. Running computer simulations taking into account 39 trillion possible combinations of checkers on a checkerboard, they’ve calculated the right moves to make in any checkers situation in order to win a game. Of course, in order to have that success in order to beat your older brother or sister in a game of checkers, you’d need to have the memory capacity in your brain of some of the world’s top computers.

And how long did it take to run all those possible checkers scenarios? 18 years. Five years into the project, the Canadian computer was able to defeat the reigning world checker champion, using some standard “rule of thumb” thinking.

But the researchers wanted more, a no-lose scenario for the computer which could take into account every checkerboard possibility. That led to 13 mores years of the computer analyzing the perfect move to make on a checkerboard with up to 10 pieces left on it.

So if you take on the computer, you’ll never win. If your brain should be at peak levels and make every perfect move, the most you can hope for is a draw.

Why is this a big deal?

It lays the groundwork for computer calculations that can help to make decisions on bigger problems.

Despite the marathon scope of the effort, Schaeffer is pleased with the results and their implications for solving other gargantuan computing problems.

"It's one million times bigger than the biggest computation previously solved optimally," says Jonathon Schaeffer, part of the University of Alberta team. "I'm hoping people will try to solve something big like that with our technology or similar technology, maybe people will do bigger and better things."

Do you think you’re smarter than the checkers computer? You can play against it by going to www.cs.ualberta.ca/~chinook.

That’s all pretty cool, but I’ll really be impressed when they come up with a computer that can play the perfect Monopoly game.

Your Comments, Thoughts, Questions, Ideas

Ed Kohler's picture
Ed Kohler says:

Well, dang, if they were running the tests on an 18 year old computer, I can imagine why it took them 18 years to figure it out. :-)

posted on Mon, 07/23/2007 - 4:08pm

Post new comment

The content of this field is kept private and will not be shown publicly.
  • Allowed HTML tags: <a> <h3> <h4> <em> <i> <strong> <b> <span> <ul> <ol> <li> <blockquote> <object> <embed> <param> <sub> <sup>
  • Lines and paragraphs break automatically.
  • You may embed videos from the following providers vimeo, youtube. Just add the video URL to your textarea in the place where you would like the video to appear, i.e. http://www.youtube.com/watch?v=pw0jmvdh.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Images can be added to this post.

More information about formatting options