Checkers has officially been "solved." A new computer-generated mathematical proof reveals that a perfectly-played game of checkers (aka draughts) always ends in a draw. University of Alberta computer games researcher Jonathan Schaeffer spent 18 years on the problem, making it "one of the longest running computations in history," according to New Scientist:
At its peak, Schaeffer had 200 desktop computers working on the problem full time, although in later years he reduced this to 50 or so. "The problem is such that if I made a mistake 10 years ago, all the work from then on would be wrong," says Schaeffer. "So I've been fanatical about checking for errors."
Schaeffer believes the techniques he has developed could be applied to many real-world problems. He gives the example of scheduling the time and work required to build a complex machine such as the space shuttle. "With these techniques, you could optimise the use of your resources to build the shuttle for the least time or cost," he says.
