## There goes checkers July 21, 2007

Posted by dorigo in physics.

It’s official. The game of checkers (or draughts), the one which is played on a 8×8 board like the one used for chess, is solved. That means humans now know. We do not exactly know how to play out every position at best, but we have pocketed the crucial proof that, given perfect play, no side can win. The starting position is, in fact, a draw – something that had been considered true for a long time without a real demonstration.

The proof came just a few days ago with an extensive calculation with desktop computers, which took 18 years to complete. A subset of the hundred billion billion different positions arising in checkers have been studied in order to achieve the result. The New Scientist has the story here.

How long more will it take to solve the game of chess ? Well, fear not. Despite the achieved supremacy of computers on over-the-board play (with some caveats, true), and despite the complete solution of five- and six-men positions, computers will never solve chess, because the possible positions to study are just too many.

1. riqie arneberg - July 21, 2007

Never is a long time. If computing power keeps doubling every 3 years, it will take about 21 years.

2. dorigo - July 21, 2007

Hey Riqie,

granted: “never” is never a good estimate. But if chess has 10^40 positions, and checkers has 10^20, naively one would think one needs 10^20 times more power to solve chess in the same amount of time (although chess is considerably more complex). To get 10^20 times more power, by doubling every three years computers need 66 doublings, that is about a hundred years.

Maybe I am making a mistake here, so please tell me what are your sources…

Cheers,
T.

3. riqie arneberg - July 21, 2007

My time “estimate” was just a toss up………..still, 100 years is much sooner than never

4. John - July 21, 2007

well, It doesn’t matter much in term of your knowledge about checkers. It would take you more than a life time to be a world class checker player.

5. John - July 21, 2007

Probably chess is also a draw. The Slav and the Petroff would do it.

6. andy.s - July 24, 2007

Can a quantum computer solve it?

Sorry comments are closed for this entry