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."'"
Wow. Reminds me of how awesome I thought I was when I was 7 years old and I solved Tic Tac Toe.
...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
Holy crap. .
If you are about to mod me down, keep in mind that this post was most likely sarcastic.
--- Often in error; never in doubt!
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.
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
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.
RTFA: 10^46.
Right. So, is it a win for the first or the second player? Would be nice to mention somewhere.
No folly is more costly than the folly of intolerant idealism. - Winston Churchill
the only winning move is not to play...
http://games.cs.ualberta.ca/~chinook/cgi-bin/statu s.cgi
GAME 17:
Opponent: Cmdr Taco (cmdrtaco@slashdot.org)
Chinook color: White
Level: Novice
Move number: 3
Game analysis: Chinook has a small advantage.
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!"
you didn't answer the question. How many gazillion?
-1 not first post
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
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.
So what happens if one automaton plays another? Does the universe implode in some kind of horrible checkers armageddon?
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.
I think it depends; how many Brazilians are in a gazillion?
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.
for(int i=60;i>0;i++) ... that loop is going to run for some time, especially if i is declared unsigned
Jonathan Schaeffer 's book about the development of Chinook (from 1997):
S upremacy/dp/0387949305
http://www.amazon.com/One-Jump-Ahead-Challenging-
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).
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?