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.
...what happens if it plays another version of itself?
they've spent all their time trying to beat checkers and forgot to solve the game of slashdotting.
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.
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
Anyone who wants to see CmdrTaco loss terrible should hop on over to table 17.
http://www.streetracingwar.com/
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.
What's wrong with a world where Harry Potter encoded spam ends up in a slashdot comment about checkers IA?
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.
Has or has not the world's most dangerous criminal committed high crimes?
People need to know given that Congress doesn't care.
Thanks a lot.
Pax,
Kilgore Trout, EX-Patriot
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.
is not to play!
Munge.
This may sound of Science Fiction but they may have solved two dimensional checkers but isn't here three dimensional checkers. Like the "Star Trek" 3-D Chess, 3-D checkers have a vertical layer to make it more challenging.
Mathematical systems are easy to solve and prove.
Call me when you have solved things like mass psychology.
Then i can have a computer writing slashdot messages which will be moderated high, or a little simpler, investing in stock options.
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.
Just one of the many, many reasons why Calgary is better than Edmonton.
Screw Go. I'll be impressed when they solve Mario Party....
"The prospects of completely solving chess are generally considered to be rather remote. It is widely conjectured that there is no computationally inexpensive method to solve chess even in this very weak sense, and hence the idea of solving chess in the stronger sense of obtaining a practically usable description of a strategy for perfect play for either side seems unrealistic today. However, it should be noted that neither has it been proven that no computationally cheap way of determining the best move in a chess position exists, nor has it even been proven mathematically that a traditional alpha-beta-searcher running on present-day computing hardware could not solve the initial position in an acceptable amount of time. The difficulty in proving the latter lies in the fact that, while the number of board positions that could happen in the course of a chess game is huge (on the order of 1040[citation needed]), it is hard to rule out with mathematical certainty the possibility that the initial position allows either side to force a mate or a three-fold repetition after relatively few moves, in which case the search tree might encompass only a very small subset of the set of possible positions. Still, it can certainly be said that nothing at present indicates a practical possibility of solving chess in any sense of the word."
http://en.wikipedia.org/wiki/Chess_computers
Chess is a very different game from Checkers, between the 3-move-repetition and 50-move-no-capture draw rules...
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).
Yeah, sure... its easy to win... if you never move your back row!!
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
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.
Back and forth? Back and forth forever?
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
This is why you should RTFA.
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?!
Go is a doddle. Call me when you've solved the halting problem.
Please, for the good of Humanity, vote Obama.
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
http://en.wikipedia.org/wiki/Shannon_number
I beat that shit easy and it brings up a page "you have taught chinook a new move, thankyou for expanding our database", thats just some project a kid came up with it's not some well thought out work.
...put their top reporting talent on the story. She announced that chess remains unsolved because it's "exponentially more complicated."
rj
http://games.cs.ualberta.ca/~chinook/cgi-bin/statu s.cgi?14
In this game DixxyCupp (dixxycupp@yahoo.com) has Chinook stating it has lost -- 66 moves in each has two Kings, Dixxy also has a single left as well.
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.
Around move 70 or so. Clearly not unbeatable after all!
The only winning move is not to play (against Chinook).
well, did they try having it play itself? did it win? well then, i guess it's not unbeatable.
-Yourmomisfasterthanabeowulfcluster
Can someone log in to two games at once, and copy what the AI opponent does in one game as your move in another, and test the universe implosion theory? At least you should have a chance of obtaining that draw.
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.
So; if this database is unbeatable, can it beat itself? Who does first move, or second move wins, or is it a tie? Either case, don't look unbeatable to me..
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.
Anyone else that has won?n km4.jpg
http://img73.imageshack.us/my.php?image=chinookwi
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!
Here is a video (qt) from Jonathan Schaeffer on the same subject
1 7_JS_sml.htm
http://westgrid.ca/downloads/archive/webcast_0601
also, other westgrid/coasat to coast videos can be found at
http://westgrid.ca/media_events.html
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
java.lang.ClassFormatError: Bad major version numbera :250)
at java.lang.ClassLoader.defineClass(ClassLoader.jav
You are running an older version of java.
Java applet loads but I only see a gray background
* This is may be a firewall problem so the java applet needs to connect to a remote server on port 54000. Please be sure you are allowed to open connections to the remote server.
* You might be running an older version of JRE (java runtime enviroment), please refer to the "you are running an older version of java" help above
Why is it a firewall problem? Do you want to disactivate my firewall and to release the 54000 port?
Don't sir! You don't follow the W3C recommendations!.
It's more easy than tic-tac-toe:
O | X | X
X | O | O
O | X | X
What happens when two instances of the program play each other?
Clearly you don't work in AI. This may be sad to a lot of people, but it's how a lot of AI is done. Jaap and Jonathan have done a lot for the field. And yes, I really am on a first-name basis with both of them.
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"