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

Checkers Solved, Unbeatable Database Created 359

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

Checkers Solved, Unbeatable Database Created

Comments Filter:
  • Wow. (Score:5, Funny)

    by Anonymous Coward on Thursday July 19, 2007 @04:44PM (#19919185)
    Wow. Reminds me of how awesome I thought I was when I was 7 years old and I solved Tic Tac Toe.
  • by Eco-Mono (978899) on Thursday July 19, 2007 @04: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.
  • by ookabooka (731013) on Thursday July 19, 2007 @04:48PM (#19919215)

    They've set up a site where you can see the proof, traverse the logic, and play their unbeatable automaton.


    Holy crap. . .you have any idea how badly their server is going to be slashdotted now? It's bad enough when its a php driven webpage but now you've just encouraged slashdotters to try a game or two against it. . .if the server crashes in the middle of a game is it considered a win for the human player?
    • Re: (Score:3, Insightful)

      by garcia (6573)
      Holy crap. . .you have any idea how badly their server is going to be slashdotted now? It's bad enough when its a php driven webpage but now you've just encouraged slashdotters to try a game or two against it. . .if the server crashes in the middle of a game is it considered a win for the human player?

      It's a little difficult to play when you can't even load the game...
  • It's a draw (Score:5, Informative)

    by elwinc (663074) on Thursday July 19, 2007 @04: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.
    • by $RANDOMLUSER (804576) on Thursday July 19, 2007 @04:56PM (#19919317)

      They claim the best you can do is draw against chinook in deterministic checkers.
      Ooooohhhh! Nondeterministic checkers!!

      <clack....clack....clack>
      "That's a inside giraffe, king me."
      • by Kjella (173770)
        Ooooohhhh! Nondeterministic checkers!!

        Well, if you read the article most tournaments start with three random moves, so it would be possible that some opening positions are win/lose instead of draw which would make it non-deterministic (but not fun, since the game is decided before you start to play).
    • Strange (Score:3, Funny)

      by hcdejong (561314)
      the only winning move is not to play...
    • While I can't argue with solid data. I really find it hard to believe that there isn't a single line of perfect play for either side. Granted I can see many draws, but not 100% draw in every single perfect line of play.
  • by eln (21727) * on Thursday July 19, 2007 @04:49PM (#19919237) Homepage
    Now, far be it from me to criticize the research of a group that can manage to convince someone to give them a grant to play checkers with a computer all day, but their "proof" on that site is a little suspect.

    When I click on the proof, all I get is a Java error saying "Unable to connect to server". While the inability to connect to the Checkers server may make it "Unbeatable" in a Wargames-esque "the only way to win is not to play" kind of way, it's kind of a cop-out.
    • It's real, they used a common tactic that's also used in Chess egtb's. You start with a couple pieces at the very end, permutate till all are solved, add a piece and keep doing that backwards till you get at root position.

      What I find more interesting is that it took 18 years to do this, on around 50 computers. That has to be the longest simulation or computation I've ever heard of. Wonder how much it cost, just in terms of the power bill to get this dataset.

  • We'll always have Go (Score:4, Informative)

    by roscivs (923777) on Thursday July 19, 2007 @04: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.
  • by eldavojohn (898314) * <eldavojohn@@@gmail...com> on Thursday July 19, 2007 @04:51PM (#19919261) Journal
    From the Wikipedia [wikipedia.org] 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. [smithsonianmagazine.com]" 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.
    • Re: (Score:2, Informative)

      by Eco-Mono (978899)
      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.
    • by tgeller (10260)
      10x10 draughts has a state-space of around 10^30, according to Dr. Schaeffer. (That was in the article's original draft -- no pun intended -- but was cut for space.)
    • Re: (Score:3, Interesting)

      by tgeller (10260)
      Here's a relevant quote from Bob Newell (editor of The Checker Maven [bobnewell.net]) that didn't make it into the story:

      "[Checkers is] a very finely balanced game, and a very subtle game. The subtleties of checkers are not very well appreciated by the average player. You play as a kid and someone always wins. In chess, differences are larger: In chess, you can make a mistake and still recover. In checkers, if you make a mistake, even a small one, you probably won't recover. People are fascinated by this game of minutiae,
      • Re: (Score:3, Insightful)

        by pugugly (152978)
        I've never particularly seen that as an indication of 'subtlety' - Great, it's so subtle that you're allowed one mistake, then your done. By that definition, Tic Tac Toe is a deeply subtle game. Golly Gee.

        Or to put it differently, it's a game so subtle that one bad move will kill you, and tournament chess requires three moves at the beginning just to randomize it a bit.

        I guess I have a Chess bias - [Grin] Pug
    • by mebollocks (798866) on Thursday July 19, 2007 @05:55PM (#19920051) Homepage

      I will, therefore, take occasion to assert that the higher powers of the reflective intellect are more decidedly and more usefully tasked by the unostentatious game of draughts than by all the elaborate frivolity of chess. In this latter, where the pieces have different and bizarre motions, with various and variable values, what is only complex is mistaken (a not unusual error) for what is profound. The attention is here called powerfully into play. If it flag for an instant, an oversight is committed, resulting in injury or defeat. The possible moves being not only manifold but involute, the chances of such oversights are multiplied; and in nine cases out of ten it is the more concentrative rather than the more acute player who conquers. In draughts, on the contrary, where the moves are unique and have but little variation, the probabilities of inadvertence are diminished, and the mere attention being left comparatively what advantages are obtained by either party are obtained by superior acumen. To be less abstract --Let us suppose a game of draughts where the pieces are reduced to four kings, and where, of course, no oversight is to be expected. It is obvious that here the victory can be decided (the players being at all equal) only by some recherche movement, the result of some strong exertion of the intellect. Deprived of ordinary resources, the analyst throws himself into the spirit of his opponent, identifies himself therewith, and not unfrequently sees thus, at a glance, the sole methods (sometimes indeed absurdly simple ones) by which he may seduce into error or hurry into miscalculation.
      Edgar Allan Poe - The murders in the Rue Morgue.
      Great Story!
  • So, who wins? (Score:5, Interesting)

    by drfuchs (599179) on Thursday July 19, 2007 @04:53PM (#19919293)
    Right. So, is it a win for the first or the second player? Would be nice to mention somewhere.
    • Re:So, who wins? (Score:5, Informative)

      by Anonymous Coward on Thursday July 19, 2007 @04:58PM (#19919349)
      According to the site, it's a draw.
    • Re: (Score:2, Informative)

      by poslfit (470396)
      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 o
  • 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.
    • Re: (Score:3, Informative)

      by Cervantes (612861)

      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 winn

      • If the first player puts their mark in a corner, the only correct moves for the second player is to mark one of the 2 adjacent squares. There is no way to garauntee victory in tic-tac-toe, regardless of who goes first. There are plenty of ways to lose though.
        • by Cervantes (612861)

          If the first player puts their mark in a corner, the only correct moves for the second player is to mark one of the 2 adjacent squares. There is no way to garauntee victory in tic-tac-toe, regardless of who goes first. There are plenty of ways to lose though.

          Incorrect. The only way to defend yourself is to take the middle square. Otherwise:

          X--
          ---
          ---

          XO-
          ---
          ---

          XO-
          ---
          X--

          XO-
          O--
          X--

          XO-
          O--
          X-X

          (or some minor variation thereof) is the final and inevitable outcome.
          If you take the middle square, and then block the side that X tries to fill up, X has to block your string through the middle and you've a draw. Otherwise, you lose, just that easy, every time.

          The range of possibilities when you're playing second against someone who doesn't employ this strategy is too great to g

      • by BubbaFett (47115)
        Absolutely. I've written a brute-force tic-tac-toe solver (in PROLOG...ugh) for an undergraduate programming assignment. It's pretty trivial.
    • That was an intro to AI project I did in school. Try a different class of language like prolog or lisp to solve it. If both players make no mistakes a cats eye (draw) can be reached. The only way to win is if the other player makes a mistake. The code to have the computer play flawlessly is only a few lines (in the right language).
    • by tverbeek (457094)
      The solution is the same as for Global Thermonuclear War [imdb.com]: "The only winning move is not to play."
  • It's come a long way (Score:2, Informative)

    by djKing (1970)
    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 x.Draino.x (693782) on Thursday July 19, 2007 @05:03PM (#19919421)
    http://games.cs.ualberta.ca/~chinook/cgi-bin/statu s.cgi [ualberta.ca]

    GAME 17:
    Opponent: Cmdr Taco (cmdrtaco@slashdot.org)
    Chinook color: White
    Level: Novice
    Move number: 3
    Game analysis: Chinook has a small advantage.
  • So, I've struggled with the issue of the really large numbers in game AI problems. In go, for example, there are about 10^170 possible legal board layouts for the 19x19 board.

    There are (esitmiated) only about 10^81 atoms in the universe.

    Do all of the 10^170 positions exist in any meaningful way? It is impossible to count, enumerate, or articulate them all?

    Getting the point back to chess, these folks have done a similar thing - it seems they articulated 1/10000th or so of the legal boards and used it to "p
    • by pclminion (145572)

      So, I've struggled with the issue of the really large numbers in game AI problems. In go, for example, there are about 10^170 possible legal board layouts for the 19x19 board. There are (esitmiated) only about 10^81 atoms in the universe.

      I'm not sure what you think the problem is. There are 361 board positions. Therefore you only need 361 pieces (atoms) to play.
    • Re: (Score:3, Insightful)

      by TaoPhoenix (980487)
      This type of proof is not the same as "your checkers set comes with a handheld database reader to show you the solution of the position you are in" - because it's NOT about 'average players making mistakes'.

      They went for the proof of the math behind the game. This article will also be a good flash answer against the wailers who say "but there are 500 billion billion *possible* positions in the game..."

      The answer: only a small portion of them *matter*.

      Here's the basic chain logic.

      "All endgames of 8 pieces or
      • by tgeller (10260)
        Well put!

        Dr. Schaeffer said it well in an email to me. I trust he won't mind if I quote it:

        "Say player 1 makes a really dumb move. It is now player 2's move.

        Player 2 has a choice of 10 moves.

        Player 2 examines the first move and, voila, it is a win! Great!

        Do we need to look at the other 9 moves?

        No. Move 1 leads to a win, and moves 2 through 10 can do no better.

        Some of those moves might also lead to a win, but who cares. We have
        one winning move and that is all that matters."
        Now you folks see how much goes int
  • Chinook wind (Score:5, Insightful)

    by hey (83763) on Thursday July 19, 2007 @05:23PM (#19919645) Journal
    For non-Albertans... a Chinook wind is some hot air the blows down the mountains and melts the winter snow for a week or so.
    http://en.wikipedia.org/wiki/Chinook_wind [wikipedia.org]
    So it an analogy for a bright new idea -- like a lite up light bulb.
    Therefore there are a zillion things called "Chinook" in Alberta.
  • If they can come up with a Go that can beat a 5-Den professional (middle of the pack in terms of professional Go player), I'll truly be impressed.
  • Hmmmmm (Score:3, Funny)

    by TheOldSchooler (850678) on Thursday July 19, 2007 @05:43PM (#19919905)
    So what happens if one automaton plays another? Does the universe implode in some kind of horrible checkers armageddon?
    • by 3vi1 (544505)
      Almost. We call it stalemate.

      My universe imploded when W.O.P.P.E.R. played Tic-tac-toe against itself.
  • Well, almost. I've been trying to convince my chess-playing friends that someday computers will be (literally) unbeatable at the game, but they've always been skeptical. Like TFA says, there are a finite number of positions and if the computer can store and map all non-losing paths through all of them, the game is solved.

    Now interestingly, it sounds like they short cut that strategy by excluding positions reached by moves that this machine will never make and significantly reduced the number of "possibl

    • by EggyToast (858951)
      Interestingly enough, computers can only win at games that are purely strategical with no element of luck. So yes, a program will one day be unbeatable at chess simply due to the fact that there is no random element in the game. It's just a matter of figuring out the right algorithm, or series of algorithms. The neat thing about this checkers "simulation" is that it charts out end games, so it's likely a relatively lean program. Rather than having the program evaluate each position and all following pos
      • Interestingly enough, computers can only win at games that are purely strategical with no element of luck.
        Actually, there are some pretty good Backgammon AIs out there. They use neural networks. And the UA team that built Chinook is working on building AI for Hearts and Spades.
        • by Yvanhoe (564877)
          More funny : a simple Markov chain algorithm beats a standard human player at Rock-Scissor-Paper 70% of the time. (Good players manage to be actually random in their choice and come closer to a 50/50 figure)
      • by Bob-taro (996889)

        That is an interesting point about chance games. Obviously, a computer can't be unbeatable at games of chance, but with anything like a card game, it could figure out the BEST chance. Poker would be interesting because of the element of bluffing -- the human players would be at an advantage if the computer always bet based on the odds, however, I imagine a sophisticated enough program could "learn" the strategies of individual human opponents and still do quite well against them. I mean, it would always

  • by 3vi1 (544505) on Thursday July 19, 2007 @05:49PM (#19919975) Homepage Journal
    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.
  • by marcosdumay (620877) <marcosdumay&gmail,com> on Thursday July 19, 2007 @06:20PM (#19920287) Homepage Journal

    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 :)

  • This is pretty nifty news. Now we just need to start cracking at the 7men egtb, now that the 6men tables are done.
  • by Joe Decker (3806) on Thursday July 19, 2007 @06: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.
  • This seems to be the linchpin of this form of checkers... and the computer's ability to win. That was never a rule in any game of checkers I've played before.

    I just know that if there were a chess version of this with a forced capture rule, people would be screaming blood muder.

    Poor checkers... so maligned... so misunderstood.
  • by ferguson731 (547854) on Thursday July 19, 2007 @08:15PM (#19921439)
    Jonathan Schaeffer 's book about the development of Chinook (from 1997):

    http://www.amazon.com/One-Jump-Ahead-Challenging-S upremacy/dp/0387949305 [amazon.com]

    Includes the details of the Tinsley matches and Tinsley's untimely death. Interesting for people interested in the effects of technology on human societies, as well as some of the technical aspects of the program (as it was in 1997).

"The vast majority of successful major crimes against property are perpetrated by individuals abusing positions of trust." -- Lawrence Dalzell

Working...