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."'"
The writing's been on the wall... (Score:3, Informative)
It's a draw (Score:5, Informative)
We'll always have Go (Score:4, Informative)
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)
It's come a long way (Score:2, Informative)
Re:Checkers, Not Draughts (Score:2, Informative)
Re:So, who wins? (Score:5, Informative)
Re:Theoretical vs. practical (Score:5, Informative)
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.
Re:What about tic-tac-toe? (Score:3, Informative)
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.
Re:Checkers, Not Draughts (Score:1, Informative)
Re:So, who wins? (Score:2, Informative)
Re:The writing's been on the wall... (Score:3, Informative)
Re:Wow. (Score:4, Informative)
Chinook vs Tinsley (Score:5, Informative)
For people wondering what is checkers (Score:5, Informative)
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 :)
Gratuitous nostalga post (Score:4, Informative)
Re:The writing's been on the wall... (Score:3, Informative)
Re:It's a draw (Score:2, Informative)
Re:It's come a long way (Score:5, Informative)
Re:Chess? (Score:2, Informative)
How many gazillion?
10 ^ (46 - log(1 gazillion))
Re:Chess? (Score:2, Informative)
Re:Chess? (Score:5, Informative)
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....
Re:Unbeatable? Are they sure. (Score:1, Informative)
"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)
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)
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.
Re:Chess? (Score:2, Informative)