Checkers, Solved!

Make no mistakes and it's a draw, says computer scientist

6 min read
Checkers, Solved!

19 July 2007—You might have to find a new game to play on your computer or cellphone soon, because checkers will only frustrate you. Even if you play it perfectly—without any mistakes, choosing the best strategy in each situation—you’ll have absolutely no chance of winning. One of the most popular board games in history, checkers has been definitively proved to end in a draw when played perfectly by both sides, according to Jonathan Schaeffer, professor of computer science, and his colleagues at the University of Alberta, Edmonton, Canada. They published their proof today on the Web site of the journal Science.

It took Schaeffer nearly 16 years to complete his checkers odyssey. He began by inventing Chinook, the world’s first computer program to win a world championship against a human in checkers, or any other game, for that matter. The program, created in 1989, draws from a library of stored opening moves that had been played by grandmasters, an endgame database that traces backward from the final results of games (wins, losses, or draws), and a deep-search algorithm that makes decisions during play based on evaluating all possible outcomes a certain number of moves ahead.

Keep Reading ↓Show less

This article is for IEEE members only. Join IEEE to access our full archive.

Join the world’s largest professional organization devoted to engineering and applied sciences and get access to all of Spectrum’s articles, podcasts, and special reports. Learn more →

If you're already an IEEE member, please sign in to continue reading.

Membership includes:

  • Get unlimited access to IEEE Spectrum content
  • Follow your favorite topics to create a personalized feed of IEEE Spectrum content
  • Save Spectrum articles to read later
  • Network with other technology professionals
  • Establish a professional profile
  • Create a group to share and collaborate on projects
  • Discover IEEE events and activities
  • Join and participate in discussions

Why Functional Programming Should Be the Future of Software Development

It’s hard to learn, but your code will produce fewer nasty surprises

11 min read
Vertical
A plate of spaghetti made from code
Shira Inbar
DarkBlue1

You’d expectthe longest and most costly phase in the lifecycle of a software product to be the initial development of the system, when all those great features are first imagined and then created. In fact, the hardest part comes later, during the maintenance phase. That’s when programmers pay the price for the shortcuts they took during development.

So why did they take shortcuts? Maybe they didn’t realize that they were cutting any corners. Only when their code was deployed and exercised by a lot of users did its hidden flaws come to light. And maybe the developers were rushed. Time-to-market pressures would almost guarantee that their software will contain more bugs than it would otherwise.

Keep Reading ↓Show less
{"imageShortcodeIds":["31996907"]}