How many games of checkers can you win in a row before someone beats you? Quite a few? Doesn’t matter, eventually you’ll lose right? You think, “it’s only a matter of time.” Well some Computing Sciences researchers at the U of A have figured out why – it’s because humans make mistakes. They’ve solved checkers, completely, and have software that is invicible:
After more than 18 years and sifting through 500 billion billion (a five followed by 20 zeroes) checkers positions, Jonathan Schaeffer and his colleagues have built a checkers-playing computer program that cannot be beaten. Completed in late April, the Chinook program may be played to a draw but will never be defeated.
Their research and “proof” were to be published in today’s edition of the journal Science.
This is pretty incredible when you think about it. It speaks to the advances we’ve made not only with technology, but with our understanding of how to harness it to do things that previously seemed impossible.
I generally consider checkers to be a fairly simple game, but don’t let that fool you:
The popular game may be simple to play, but it holds a potential 500 billion billion positions. That’s one million times more complicated than any other game solved before, says Jonathan Schaeffer, the computer science professor who began the project in 1989.
Congratulations to Schaeffer and his team! I can’t imagine what they’ll figure out next.