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.
How many gazillion positions are there for chess?
No trees were killed in the making of this post; however, many trillions of electrons were horribly inconvenienced.
--- Often in error; never in doubt!
This coupled with the post the other day about the fully unmanned USAF drones should give rise to Skynet-esque systems in the next decade.
Cheers.
Website Hosting
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.
Right. So, is it a win for the first or the second player? Would be nice to mention somewhere.
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.
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..."
Hasn't it always been fairly easy for a computer to beat a human at checkers? I don't recall it making the news the first time deep blue beat the world grand master at checkers.
No folly is more costly than the folly of intolerant idealism. - Winston Churchill
It's only a matter of time before a machine can out-think a man. "Unbeatably". Something to think about.
expandfairuse.org
All games between itself would be a draw.
Avoid Missing Ball for High Score
the only winning move is not to play...
Clever bastards!
I bet loads of board-game manufacturers are getting their lawyers to work overtime looking for a way to take these guys to court...
ilovegeorgebush
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.
Picture the following scenario - a system like this one can beat a human in any competition, simply because the system knows how to get the best result in any given situation. This doesn't make the system smarter than us, but it makes it more successful than us for a given task (in this case it is playing checkers).
Now, imagine there is a similar system in various structures, such as the military. At one point this dumb system [but with a huge knowledgebase] kicks our ass (simply because it can). Humans will go extinct, while this dumb system is now the only sign of civilization on the planet; the only problem is that the system has no learning capabilities and is not truly intelligent.
What I'm saying is: what protects us from being anihilated by such systems, except the fact that at the moment only some [non-critical] parts of the infrastructure are computerized, and that we can disable a system by powering it off?
The saddest poem
First of all, machines do not think.
Second of all, in this case, it's a bunch of researchers that can outthink a human.
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 "prove" something about the whole space. (I have not yet read the original paper...) This seems mostly bollucks, as most real players make all kinds of mistakes - so the games do not flow into the "important" game positions they follow. After about 3-5 moves in their java applet, I found moves that could make sense that there not in their "legal" moves database.
the only winning move is not to play. :-)
I've discovered this when i was little. It's called back, and forth, and I was unbeatable. Of course, I couldn't beat the other guy who was doing the same thing
Soon there will be robots no one can fight because they know every move we are going to do..... AHH silver foil helmet time!
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.
Chinook: 629348718327 Human: 0
How about a nice game of chess?
It's so complex, in fact, that the solvers don't know how to set the board correctly. :-p
"LinuX - Dropping the c u r t a i n on Windoze." -- Vee Schade, vschade at mindless dot com
unbeatable-automaton checkers-genius game-solving overlords!
-WtC
Creator of RPerl, Scouter, Juggler, Mormon, Perl Monger, Serial Entrepreneur, Aspiring Astrophysicist, Community Organiz
Usually it gives its thoughts on the game... but if its loosing it says nothing. Quite interesting. Everyone should play as Slashdot incase someone wins ;)
string sig = llGetSig("dimentox"); llSay(0,sig);
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.
I'm fuzzy on the whole good-bad thing. What do you mean, bad?
UTF-8: There and Back Again
They said "unbeatable" not "always wins", there is a subtule difference.
note: i'm known as plugwash most places but i screwd up registering that here somehow in the past and now can't register
So what happens if one automaton plays another? Does the universe implode in some kind of horrible checkers armageddon?
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 "possible" positions that way. So I wonder if this means their program can't win from an otherwise winnable position, because that position isn't in it's database.
Prov 9:8 Do not rebuke mockers or they will hate you; rebuke the wise and they will love you.
According to Star Trek they'll both explode in a terrific display of smoke and fireworks.
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.
Screw Go. I'll be impressed when they solve Mario Party....
The 'proof' page leads you to a game. That's not a proof, it's a telephone directory.
Somebody call me when computers have proved the Four Colo(u)r Theorem. Until then I'll be off playing CounterStrike (so I can work on my winning algorithm).
One can get much of the overall story online here.
Mario Party pfffth.
Solve the minus world on Super Mario Bros.
God spoke to me.
Who wins if it plays God?
STFU about slashdot bias.
Not only has that question been posited so many times it's ridiculous, but it's a draw.
Please, for the good of Humanity, vote Obama.
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
"Yeah, except Edmonton (where U of Alberta is) doesn't get Chinooks.
Just one of the many, many reasons why Calgary is better than Edmonton."
Baloney. Edmonton gets Chinooks, just not as many. And stop with the childish my-city-is-better-than-your-city nonsense. You're all Albertans, be proud of that fact.
The pursuit of absolute tolerance leads to the most rigorous and ludicrous intolerance. - REX MURPHY
This is pretty nifty news. Now we just need to start cracking at the 7men egtb, now that the 6men tables are done.
They went so far as to create a system that can always win checkers but didn't go all the way and implement an AI to play against me? Does anyone think this is a little sad?
Why have I got to do all the work to get beat a checkers when the AI would be so simple to implement from this point on?
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.
If the database uses lookups of all possible moves in its database, is that really solution? If you brute force a password with all possible solutions, you still haven't really solved its encryption/hash function.
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.
This is my sig. It's prescription, I swear. I need it for reading things... on the other side of things
Its a proof for 'unbeatable'? I thought its result was no win, stalemate.
members are seeing something, your seeing an ad
Hardly. The checkers program has no degree of intelligence whatsoever, it's just a gigantic brute force "tree" of board positions.
Yeah, but suppose a program was written to solve intelligence and found that the best intelligence can do is search a giant tree. Wouldn't life be so much fun?
We've already created rules and systems to help us go all day without thinking too much. When was the last time you took a big risk?
Know your pads. One time pad: good for cryptography. Two timing pad: where to take your mistress.
What happens if it plays itself then?!
Now the next big step would be to come up with the best strategy. I didn't RTFA but I guess it'll take years for someone to summarize that gigantic tree in a set of general rules...
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).
the halting problem is a doddle, call me when they solved the 'ultimate pick-up line' conundrum
The Kruger Dunning explains most post on
ergo I am unbeatable!
Engineering is the art of compromise.
Stay on the red squares.
The Kruger Dunning explains most post on
"Any game against this player will end in, at best, a stalemate" and "This player never loses; this player is impossible to beat" are the same. The second one just doesn't mention the possibility of a draw, so it can easily be read the wrong way.
Laws do not persuade just because they threaten. --Seneca
...put their top reporting talent on the story. She announced that chess remains unsolved because it's "exponentially more complicated."
rj
From the status page: (out of 40 current games)
GAME 14:
Opponent: Dixxy Cupp (dixxycupp@yahoo.com)
Chinook color: Black
Level: Novice
Move number: 59
Game analysis: Chinook has a lost game.
In Soviet Russia the insensitive clod is YOU!
Two Words: Nightmare Chess.
If you really enjoy chess, this is something you definately must check out.
Modern copyright is theft of culture from everyone and it retards the progress of the useful arts and sciences.
Deep Blue played chess, which is what I assume you meant. Technically, chinook didn't make the news either. It happened in April, and is just now in July making slashdot (by definition, not "new"s). Deep Blue didn't make the web news because it was pre-web. Neither of them made the TV news because they don't involve drugs or violence or death or sexual perversion or Paris Hilton.
Write your own Choose Your Own Adventure. http://www.freegameengines.org/gamebook-engine/
I did my undergraduate at the U of A, and had the pleasure of being a number of Jonathan Schaeffer's classes. The man is a gifted professor, and rather quirky on top of that.
..
One day, we were learning about the "Dining Philosopher" problem. The problem is about 3 philosophers that have to acquire two (shared) utensils on either side of them before they can eat the food in front of them. Those of you familiar with the problem should understand
Anyway, he came in with a pot of spaghetti, forks, and plates. He actually had some students sit down and go through the algorithm. When the first one took a bite off the plate, he asked "Pretty Good, huh?" (of course the student agreed). He also threw some spaghetti against the wall to prove that it was well cooked.
So, after the first student went through the algorithm and used the fork, you can imagine the grimace from the second student that had to use the same shared fork as the first student..
hah! Still makes me laugh.
I won't ever forget about acquiring mutexes in the correct order, however.
f u cn rd ths, u r prbbly a lsy spllr.
The only winning move is not to play (against Chinook).
Checkers computers play YOU!
??
Wait a sec..
Alberta? Soviet?
Sorry, obviously an oxymoron.
.
- aqk
F U
I won! I won! But then it tore my arms off ;
Read the 2nd sentence in TFA (the part after the semi-colon).
-Mike
I'm sorry; I don't know what I was thinking!
Game Over. I bet he's proud of the fact that he's the guy who stopped draughts being worth playing.
Travelling forward in time at a rate of 1 second per second.
The "proof" on that site is nothing of the sort. It's simply a java applet that gives an opinion on whether a particular position is a win, loss or draw. Except, of course, where, without explanation, it reports that the position was not analysed.
Let's be real. As given, that's no proof that any mathematician would recognise as such. Thanks to the cases not analysed, it's not even a brute-force proof - the reasoning behind excluding those cases could be simple, maybe even blindingly obvious when explained, but it isn't given, and for all anyone reading that site knows, it's wrong. In fact, all that the website "proof" is, is a big helping of "Trust us". With side orders of "Our logic is correct", "Our programming is accurate and bug-free", "We've crunched one HECK of a lot of numbers" and "WOW! Aren't you impressed?". But still, ultimately, just "Trust us".
One has to assume that the Schaeffer and his team have rather more and better than the webs site content to offer to the mathematical community.
with a little help from /. overloading the server...
its flag should drop since it was inable to reply in a reasonable amount of time.
1. Develop unbeatable checkers program named 'CHINOOK' 2. Market "I Beat CHINOOK at checkers" t-shirt and "Checkers players do it by jumping" bumper sticker 3. Profit!
From the article:
"Jaap van den Herik, editor of the International Computer Games Journal, calls the achievement "a truly significant advance in artificial intelligence".
Brute-forcing your way to a problem is not artificial intelligence.
Indeed. The guy is clearly just another AI-jerk trying to drum up grant money for deadend research projects. Total waste of time, electricity, and money.
TWW
"Encyclopedia" is to "Wikipedia" what "Library" is to "Some people at a bus stop"
...is how Linus Torvalds pronounces "Chinook."
--
Toro
(who just gave up mod points to make that dumb joke.)
Comon now!...I have know this for at least 30 years! Anyone with a little common sense should have at least guessed that this was true...you certainly don't need a computer to figure it out. Make sure all your checkers are 2 deep at all times..you can't be jumped ...duh!
It seems to me that the computer can only win from either the first to move or second to move a checker. I wonder which it is? This would mean that playing against itself, it could only win 50% of the time, not every time, therefore it is not unbeatable.
-Eric
What happens when two instances of the program play each other?
Maybe they have, but this work is as worthless to AI as Ford's research into LPG engines is to 100m sprinters.
TWW
"Encyclopedia" is to "Wikipedia" what "Library" is to "Some people at a bus stop"