Slashdot Mirror
Checkers Solved, Unbeatable Database Created
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."'"
...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.
(rot13) rpbzbab@tznvy.pbz
--- Often in error; never in doubt!
Since Go 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/, learn how to play the game in an interactive fashion.
http://361points.com/atarigo/, play "capture" Go against a simple computer opponent.
http://www.gokgs.com/, after you've learned the rules, play against others online worldwide.
http://www.godiscussions.com/, have more questions about the game? Ask them on this discussion board devoted to the game.
~ roscivs
RTFA: 10^46.
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.
Free as in "the Truth shall set you..."
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.
(rot13) rpbzbab@tznvy.pbz
According to the site, it's a draw.
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!"
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.
If I knew the wedgies I gave you back in 6th grade would have resulted in this . . . I might have taken a moments pause.
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.
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.
According to TFA, a draw
One can get much of the overall story online here.
Ok, for other english impared people wondering what is checkers, it is the US name for game of draughts. If you follow that link, you'll instantly recognize the board :)
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 :)
Rethinking email
HAKMEM item 93 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.
I'm a nature photographer.
How many gazillion?
10 ^ (46 - log(1 gazillion))
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 - thousand, million, billion, trillion, quadrillion, quintillion, sextillion, septillion, octillion, nonillion, decillion, etc.
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....
If the pattern goes 9am, 10am, 11am, why isn't noon 12am?
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!"
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.
Breakfast served all day!
"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
etc
Each unit is multiplied by 1000 to form the next unit.
See http://en.wikipedia.org/wiki/Billion and http://en.wikipedia.org/wiki/Long_and_short_scales