Slashdot Mirror

← Back to Stories (view on slashdot.org)

Checkers Solved, Unbeatable Database Created

Posted by Zonk on from the does-that-mean-we-don't-need-to-play-anymore dept.

tgeller writes "My story on the Nature site announced that a team of computer scientists at the University of Alberta has solved checkers. From the game's 500 billion billion positions (5 * 10^20), 'Chinook' has determined which 100,000 billion (10^14) are needed for their proof, and run through all relevant decision trees. They've set up a site where you can see the proof, traverse the logic, and play their unbeatable automaton. '[Jonathan] Schaeffer notes that his research has implications beyond the checkers board. The same algorithms his team writes to solve games could be helpful in searching other databases, such as vast lists of biological information because, as he says, "At the core, they both reduce to the same fundamental problem: large, compressed data sets that have to be accessed quickly."'"

13 of 359 comments (clear)

  1. Wow. by Anonymous Coward · · Score: 5, Funny

    Wow. Reminds me of how awesome I thought I was when I was 7 years old and I solved Tic Tac Toe.

  2. It's a draw by elwinc · · Score: 5, Informative
    The New York Times has the story too http://www.nytimes.com/2007/07/19/science/19cnd-ch eckers.html?ref=science:. They claim the best you can do is draw against chinook in deterministic checkers. The Times points out that:

    The new research proves that Chinook is invincible in the traditional game of checkers. But in most tournament play, a match starts with three moves chosen at random. In solving the traditional game, the researchers have also solved 21 of the 156 three-move openings, leaving a crack of hope for humans, at least for now.
    --
    --- Often in error; never in doubt!
  3. Checkers, Not Draughts by eldavojohn · · Score: 5, Interesting
    From the Wikipedia entry:

    The most popular forms are international draughts, played on a 10×10 board, followed by English draughts, also called American checkers that is played on an 8×8 board, but there are many other variants. Draughts developed from alquerque.[2] Draughts would be a much much larger gamespace than Checkers. I noticed that draughts appeared in the tags of this story but it shouldn't.

    Also, I've heard before that "it takes longer to learn to play checkers at the master level than it does chess. What checkers lacks in breadth, it makes up in precision and finality." I realize that puts me at risk of being modded as flamebait but I wonder if any other Slashdot reader can confirm or contest that.
    --
    My work here is dung.
  4. Re:Chess? by rustalot42684 · · Score: 5, Informative

    RTFA: 10^46.

  5. Re:So, who wins? by Anonymous Coward · · Score: 5, Informative

    According to the site, it's a draw.

  6. Re:We'll always have Go by Derek+Pomery · · Score: 5, Interesting

    'course, Go would be kind of dull too on an 4x8 board (checkers only uses half the squares)
    http://www.chessvariants.com/d.betza/chessvar/16x1 6.html

    --
    -- perl -e'print pack"H*","6e656d6f406d38792e6f7267"' /. ate my old sig. Bastards.
  7. Re:Theoretical vs. practical by edremy · · Score: 5, Informative
    No. Schaeffer has a book out ("One Jump Ahead") about writing Chinook. He thought the same when he started, but the project got rapidly far harder than he thought. It helped that the existing human champion (Marion Tinsley) was literally as close to perfection as any human has ever been at any game- they exhaustively studied every professional game he ever played and found something like a grand total of 10 actual mistakes in a 40 year career.

    It's a very sad book in many ways- there was a lot of tension between certain members of the team and you realized that professional checkers was dying rapidly. Tinsley and Schaffer set up a world championship rematch between them (Tinsely won the first one) and Tinsely pulled out after six games saying he felt ill. He checked himself into the hospital, was diagnosed with some aggressive form of cancer and died a few months later. Schaeffer basically retired Chinook from human tournaments since nobody else was even remotely close to Tinsley.

    It didn't make many headlines because everyone knows checkers is easy. Except that they are wrong- it's not.

    --
    "Seven Deadly Sins? I thought it was a to-do list!"
  8. Re:Chess? by youthoftoday · · Score: 5, Funny

    you didn't answer the question. How many gazillion?

    --
    -1 not first post
  9. Re:The writing's been on the wall... by dprovine · · Score: 5, Interesting

    They randomise starting back-rank positions now in some tournaments, to stave off the eventual "book death" that has already conquered checkers.

    I made up my own variation with randomness that I call Schrödinger's Chess.

    Let me know if you try it out.

  10. Kobayashi Maru by 3vi1 · · Score: 5, Funny

    The day an automaton is "unbeatable" is the day it's 500ft tall and shoots nuclear rockets from its fingertips. I think I know a relatively easy way to beat this checkers program.

  11. Chinook vs Tinsley by Anonymous Coward · · Score: 5, Informative

    One can get much of the overall story online here.

  12. Re:The writing's been on the wall... by fractoid · · Score: 5, Funny

    Schrodinger's chess is when you set up a chess board in a box with a cat. You then shake the box, and declare that you beat the cat at chess.

    --
    Rampant carbon sequestration destroyed the Dinosaurs' tropical paradise. I'm here to help repair the damage.
  13. Re:The writing's been on the wall... by TED+Vinson · · Score: 5, Funny

    Good idea. Perhaps Checkers can be revitalized by randomizing which piece goes on which starting space too...