Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!


Forgot your password?
Classic Games (Games) Programming IT Technology

Checkers Solved, Unbeatable Database Created 359

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."'"
This discussion has been archived. No new comments can be posted.

Checkers Solved, Unbeatable Database Created

Comments Filter:
  • by Eco-Mono (978899) on Thursday July 19, 2007 @03:46PM (#19919207) Homepage
    ...ever since the swelling of Chess's "opening book" began. They randomise starting back-rank positions now in some tournaments, to stave off the eventual "book death" that has already conquered checkers.
  • It's a draw (Score:5, Informative)

    by elwinc (663074) on Thursday July 19, 2007 @03:48PM (#19919221)
    The New York Times has the story too http://www.nytimes.com/2007/07/19/science/19cnd-ch eckers.html?ref=science: [nytimes.com]. 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.
  • We'll always have Go (Score:4, Informative)

    by roscivs (923777) on Thursday July 19, 2007 @03:51PM (#19919259) Homepage
    Since Go [wikipedia.org] always comes up in these discussions, I'll take this opportunity to point those curious about the game to some places to learn more about it:

    http://playgo.to/interactive/ [playgo.to], learn how to play the game in an interactive fashion.

    http://361points.com/atarigo/ [361points.com], play "capture" Go against a simple computer opponent.

    http://www.gokgs.com/ [gokgs.com], after you've learned the rules, play against others online worldwide.

    http://www.godiscussions.com/ [godiscussions.com], have more questions about the game? Ask them on this discussion board devoted to the game.
  • Re:Chess? (Score:5, Informative)

    by rustalot42684 (1055008) <fakeNO@SPAMaccount.com> on Thursday July 19, 2007 @03:52PM (#19919283)
    RTFA: 10^46.
  • It's come a long way (Score:2, Informative)

    by djKing (1970) on Thursday July 19, 2007 @03:57PM (#19919329) Homepage Journal
    for(int i=60;i>0;i++) was the check they did to make sure Chinook only looked ahead sixty moves and didn't go over it's time limit in one of it's first challenges against a top human player. And yes that's a bug, lost the first game because of it. I was taking an intro to logic and data structures course from Dr. Schafer at the time.
  • by Eco-Mono (978899) on Thursday July 19, 2007 @03:57PM (#19919339) Homepage
    The same article, in fact the same quoted paragraph states that American Checkers and British Draughts are the same, 8x8 board game. So calling this solution a solution to draughts isn't really that inaccurate.
  • Re:So, who wins? (Score:5, Informative)

    by Anonymous Coward on Thursday July 19, 2007 @03:58PM (#19919349)
    According to the site, it's a draw.
  • by edremy (36408) on Thursday July 19, 2007 @04:07PM (#19919471) Journal
    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.

  • by Cervantes (612861) on Thursday July 19, 2007 @04:09PM (#19919497) Journal

    I've been developing an algorithm to solve that game for years, and so far all I've come up with is: start with the middle square.
    Nah, that's false.

    If you're going first, put your mark in the corner. Almost regardless of what your opponent does, put your next mark in an adjacent corner. He'll now have to block you, and then you put your third mark in yet another corner, and voila, you have 2 winning moves.
    The only defense against it is to take the middle square with your first move and then block whatever side X tries to take with your second, and then X has to block your row with his third. That ends the game in a draw.

    The only winning move going second is to play for a draw. You won't win unless your opponent makes a mistake.
  • by Anonymous Coward on Thursday July 19, 2007 @04:17PM (#19919591)
    That is not necessarily a good thing in a tournament level game. What it means is it is much more difficult to recover from a situation where you are disadvantaged in checkers then in chess. For example. In chess, if you take a game a grandmaster is playing vs your average Joe and stop it part way through then have them swap positions the grandmaster would probably still win. In checkers, once you are behind, even just a little, it becomes quickly untenable. In checkers your advantage is much more transparent then in chess and your mistakes are much more final.
  • Re:So, who wins? (Score:2, Informative)

    by poslfit (470396) on Thursday July 19, 2007 @04:24PM (#19919667) Homepage
    When correctly played, it turns out that it's a draw. The interactive game tree tool lets you explore which parts of the tree lead to which results, and if you start at the root, you can pick an edge at each node that guarantees at worst a draw for the current player. It's worth observing that the tree is not fully computed: it will often tell you that it doesn't know what happens if you make a given move in a given position, because all they needed to do was find a subtree that a player could always stay on.
  • by eclectro (227083) on Thursday July 19, 2007 @04:26PM (#19919695)
    For those that are interested, I think the parent is referring to Chess960 [wikipedia.org].
  • Re:Wow. (Score:4, Informative)

    by DavidShor (928926) <supergeek717@gm a i l .com> on Thursday July 19, 2007 @04:41PM (#19919871) Homepage
    According to TFA, a draw
  • Chinook vs Tinsley (Score:5, Informative)

    by Anonymous Coward on Thursday July 19, 2007 @05:12PM (#19920209)
    One can get much of the overall story online here [wisc.edu].
  • Ok, for other english impared people wondering what is checkers, it is the US name for game of draughts [wikipedia.org]. If you follow that link, you'll instantly recognize the board [wikipedia.org] :)

    Of course, as a brazilian, I had no idea people played that on a 10x10 board around the world. Too bad they can't reuse the chess board :)

  • by Joe Decker (3806) on Thursday July 19, 2007 @05:37PM (#19920481) Homepage
    HAKMEM item 93 [inwap.com] is solved. Back in 1972 when HAKMEM was written, the AI Lab folks estimated a year or so of computer time then, I'm guessing, given how long has passed, that this was a bit optimistic.
  • by SnowZero (92219) on Thursday July 19, 2007 @05:43PM (#19920585)
    Created/endorsed by chess genius and raving lunatic Bobby Fischer [newsfromrussia.com]: "I don't play the old chess. But obviously if I did, I would be the best."
  • Re:It's a draw (Score:2, Informative)

    by SnowZero (92219) on Thursday July 19, 2007 @05:46PM (#19920607)
    A strange game. The only winning move then is not to play.
  • by mikeb (6025) on Thursday July 19, 2007 @06:28PM (#19920961) Homepage
    for(int i=60;i>0;i++) ... that loop is going to run for some time, especially if i is declared unsigned
  • Re:Chess? (Score:2, Informative)

    by Limerent Oil (1091455) on Thursday July 19, 2007 @07:38PM (#19921657)

    How many gazillion?

    10 ^ (46 - log(1 gazillion))

  • Re:Chess? (Score:2, Informative)

    by cecil_turtle (820519) on Thursday July 19, 2007 @09:57PM (#19922663)
    I don't understand why people make up numbers like "500 billion billion" (which is meaningless) instead of using the number's proper name, "500 quintillion", or maybe "half a sextillion". It's not that complicated folks [wikipedia.org] - thousand, million, billion, trillion, quadrillion, quintillion, sextillion, septillion, octillion, nonillion, decillion, etc.
  • Re:Chess? (Score:5, Informative)

    by NewsWatcher (450241) on Thursday July 19, 2007 @10:53PM (#19922989)
    Oh yeah, not that complicated, until you consider that in the USA a billion is a thousand million, but in most of the world it is a million million. Or that a sextillion is derived from prefix "sex" which means six, (as in a sextet of ale) but is actually a one followed by 21 zeros.

    A septillion (from the word for seven) contains 24 zeros.

    So what you may ask is a one followed by 22 naughts? 10 sextillion. A one followed by 23 naughts? 100 sextillion. And yet instead of a one followed by 24 naughts being 1000 sextillion, it is all of a sudden a septillion, even though it has nothing whatsoever to do with the number seven.

    I don't even know why I care about all of this. I got to this thread late and the chances of anyone reading my post in the developers section of Slashdot are next to zero. Of course next to zero would be one and minus one. Oh gawd, don't get me started on that....
  • by Anonymous Coward on Thursday July 19, 2007 @11:15PM (#19923115)
    Does anyone read anymore? You even quoted "Level: Novice". This seems pretty indicative that you're not playing against the best version. Heck, there's a bit on the first "play Chinook" page that says

    "The program on this site is the champion but it has been reduced in strength to allow you to "have a chance" at drawing. This program does not include the solution to checkers. If you are good enough, you might even win! Good luck!"
  • Re:Wow. (Score:3, Informative)

    by PCM2 (4486) on Friday July 20, 2007 @12:39AM (#19923575) Homepage
    According to the article, checkers has been "solved" to the extent that they've developed a mathematical proof showing that it's impossible to beat the checkers software the researchers wrote. Even if the human plays a "perfect" game against the computer, the result will be a draw.

    So, in answer to your first question, none. Checkers might be "solved," but the computer is not guaranteed to win. (It is, however, quite likely.)

    In answer to your second question, if both sides play perfect games then you'll always draw. A "perfect" move yields no advantage to the opponent. In other words, you might lose a piece, but you've still played a perfect game if the piece is only lost in such a way that your opponent is guaranteed to lose one of his own in a subsequent move.

    Please note that checkers is a considerably less complex game than chess, for example, or Go.
  • Re:Chess? (Score:2, Informative)

    by master_p (608214) on Friday July 20, 2007 @07:26AM (#19925461)
    "until you consider that in the USA a billion is a thousand million, but in most of the world it is a million million."

    Where in the world a billion is a million million? I never ever met this definition in real life, even in ol' Blighty.

    million = 1,000,000
    billion = 1,000,000,000
    trillion = 1,000,000,000,000

    Each unit is multiplied by 1000 to form the next unit.
  • Re:Chess? (Score:2, Informative)

    by pelago (957767) on Friday July 20, 2007 @07:53AM (#19925643)

Evolution is a million line computer program falling into place by accident.