Story from BBC NEWS: http://news.bbc.co.uk/go/pr/fr/-/1/hi/sci/tech/6907018.stm
Published: 2007/07/19 18:07:41 GMT
Computers crack famous board game
It could be a case of game over for draughts – scientists say the ancient board game has finally been solved.
A Canadian team has created a computer program that can win or draw any game, no matter who the opponent is.
It took an average of 50 computers nearly two decades to sift through the 500 billion billion possible draughts positions to come up with the solution.
Writing in the journal Science, the team said it was the most challenging game solved to date.
Jonathan Schaeffer, lead author on the paper and chair of the department of computer science at the University of Alberta, Canada, told the BBC News website: “This was a huge computational problem to solve – more than a million times bigger than anything that had ever been solved before.”
Here is the full story.
Quote: I think we’ve raised the bar – and raised it quite a bit – in terms of what can be achieved in computer technology and artificial intelligence Professor Schaeffer
will they ever be able to do the same for chess? i don’t think so…
What I have been able to read about the matter suggests that chess is going to be far more complicated to solve.
Whereas checkers has 5E20 different positions to calculate, chess has 5E45. If these computers calculated for 20 years, the same computers should be calculating for 5E23 years… the universe is not that old 😛
But, computer power is always increasing. Why not match it with more’s law?????
Perhaps a more pertinent question is whether or not we want to do the same for chess.
My answer is emphatically NO.
We know that if both sides play perfectly in checkers, the result is a draw.
How motivational is it to aspire to a tie as a perfect performance?
How satisfying is it to know that the only reason you ever win or lose is human error?
Forunately, chess has many more variations and possibilities than checkers, but in my mind the same principles apply.
>>It took an average of 50 computers nearly two decades to sift through the 500 billion billion possible draughts positions to come up with the solution.
>>
Unfortunately, they forgot to write it down and will have to start over again.
Checkers can offer the human mind as much scope for effort and accomplishment as chess. No doubt about it.
According to the American Checker Federation’s website, the entire game of checkers has not been “solved.” Rather, and this is a subtle error, the computer program CHINOOK has solved the game when only 10 pieces are left on the board (5 for both sided)…the 10-piece database.
In other words, the endgame database for Chinook cannot be defeated when each side has only five pieces (total of 10 on the board). This is NOT saying that from the beginning position with ALL pieces on the board that the game has beem solved.
Also, regarding the number of positions possible between chess and checkers, according to the magazine the “Machinist,”: “”Checkers has roughly the square root of the number of positions in chess (somewhere in the 1040-1050 range),” see http://machinist.salon.com/blog/2007/07/19/checkers/
as I quoted this from that site…don’t know if
that number is accurate but still worth mentioning.
This is an important difference. The ACF and Jonathan Schaeffer say this. Just check the ACF’s website. Furthermore, and to again reiterate the fact since the media has distorted this story somewhat, the GAME OF CHECKERS HAS NOT BEEN “SOLVED” FROM THE BEGINNING POSITION ONWARD WITH ALL PIECES ON THE BOARD.
Again, it has only been solved when each side has 5 pieces (total of 10 on the board).
Finally, as I mentioned in another post that our super-GM’s could learn a lot from Checker GM’s, I agree with the following quote from Checker super-GM Don Lafferty,
“Don Lafferty, age 61, the second-best human checkers player in the world, thinks that the two games currently attract different sorts of people. “I never met a checkers player I didn’t like; they’re all even-tempered,” he says. “Chess players are egotistical. They think they’re intellectuals and that everyone else is beneath them. Checkers players aren’t like that.” It certainly is true that the top chess players have a kind of charisma that the top checkers players lack. This probably leads to a self-perpetuating lack of interest in checkers.”
This is so true and the reason I
mentioned that the childish antics
of Elista only hurt the image of chess.
GREAT!
And the answer was: 42 For sure! Great again! Breaking news! Sensational!
But, – ehhh – and the question was? What? OH NO!
Do it again, for exercice only, not for punishment, of course!
🙂
I have heard that even in Chess, perfect play from both sides will result in a draw always.
Anonymous 9:56:00 AM would have you believe that the American Checkers Federation says Checkers has NOT been solved from the starting position, and that the Chinook team of researchers have only produced a 5 piece endgame database. 20 years of computation for such an unambitious database? I don’t think so.
But Mister Anonymous fails to provide a link to any ACF article that would make, let alone prove, such a claim. In fact, the ACF aknowleges the Chinook team’s achievement. It merely states that checker GMs have long suspected that the game was a theoretical draw, and that the game won’t be made any less interesting by this recent breakthrough.
But don’t take my word for it. You can read it all here: usacheckers.com/repscorner.php?id=14
With current computer technology, chess cannot be solved. Don’t even think about it.
Maybe when Quantum Computation has come to us in the future, then it will be probably the day zero of chess solving. After that day, how many years it will take ? may be hundreds, may be thousands, may be more. I personally think that no one of us will see chess solved.
>>Checkers can offer the human mind as much scope for effort and accomplishment as chess. No doubt about it.>>
I doubt it, so that proves your statement wrong.
Couldn’t disagree more with Mr. Lafferty. I would say that chess players as a lot tend to be headstrong and self-confident, which is a great thing in my opinion. Just look at Susan and how those qualities have helped her accomplish so much for the sport. But to call most/all top chess players EGOTISTICAL is way, way out of line. Do I think some chess players fit in this category? Yes I do. But it is clearly a minority.
Indeed, we know that if both sides play perfectly in checkers, the result is a draw. Same goes for Chess!!!
But ‘perfect play’ is not something that gets seen much…. well… almost never! Even at top GM level, small slips are made. We are NOT computers!! And that brings us the beauty of this game!!!
After all, isn’t the initial position in chess ‘a draw’ too!?! 😉
It is equal, but nothing stops us from transforming it into something that might be winning 🙂
I am the “anon” that mistakenly did not put a web link to support the fact that checkers has ONLY BEEN SOLVED when there are 10 pieces left on the board….here is but one of the web addresses and it’s from the website “New Scientist”:
http://www.newscientisttech.com/article/dn12296-checkers-solved-after-years-of-number-crunching.html
Just scroll down to the fifth paragraph that begins with:
“The crucial part of Schaeffer’s computer proof involved playing out every possible endgame involving fewer than 10 pieces.”
And, yes, for those very few that have achieved an “expert” or “master” rank in both chess and checkers will say that checkers “can offer the human mind as much scope for effort and accomplishment as chess.”
However, this is only an opinion. I totally agree but, again, opinions are not scientific fact.
Checkers is a game that utilizes many of the same concepts as chess and one can spend a lifetime studying the intricacies of the game and never become a super-GM.
The good thing is that chess and checkers never have to compete for one’s affections. Anyone can enjoy both quite easily and love them both. I do.
Regarding Mr. Lafferty’s assertion that Checker GM’s have somewhat of a different mentality and are less egotistical…I wholeheartedl agree. Yes, absolutely.
This is not to say that every chess GM is egotistical. Far from it. I do not at all thing GM Polgar is like this. I’m thinking more along the lines of Kramnik, Topalov, and the top, elite GM’s of chess. Yes, it is true that many chess players at all levels think of checkers merely as “country chess” not to be taken as serious as chess.
For those (and I know many from various clubs who have this opinion) who think this way, I cannot help but feel quite dismayed at such an attitude.
There are exceptions but, on average, the chess elite are egotistical. Again, just look at what happened in Elista. Childish behavior. Flash back to the 70’s Karpov and Korochnoi kicking each other in the shins under the table during a match. Kasparov fuming because he was defeated by Deep Blue…just to name a few childish incidents.
Yes, chess has many egotistical super GM’s that act in very unsportsmanlike ways.
If a single person can provide even ONE example of a World Checker Champion (past or present) that has
done something during a match as embarrassing as what happened between Topalov and Kramnik…please enlighten me….no, enlighten the world.
I’ve followed both games for decades and there is and has not been a single World Checker Champion act in such a way toward their fellow competitor(s). Period.
OK folks, I now have to admit that I made an error. According to the Chinook web site located at:
http://www.cs.ualberta.ca/~chinook/project/
Checkers has, indeed been solved from the starting position regardless of which opening is utilized. Since the computer will play perfectly, then each game will end in a draw.
I stand corrected and publicly apologize for my previous erroneous post stating that it was solved with only 10 pieces on the board.
However, amongst human players, even the world checker champion, “perfect play” is virtually impossible just as it is in chess.
Even the best lose. Well, Dr. Marion Tinsley was never defeated in a checker match in his life and lost fewer than 8 games in over 40 years (and two of those losses where to a computer when he was dying with pancreatic cancer).
He was about as “perfect” a human player that ever played an intellectual game such as checkers.
Nevertheless, even though Chinook has solved checkers, I don’t think all humans should burn their checker boards and give up. No human player can defeat Rybka in a match. Computer chess programs have far surpassed the greatest chess players. Yet, we haven’t given up on chess.
No. Even though checkers is solved any person can still spend a lifetime studying an enjoying checkers… and chess, too.
Above all, this is a testament to the power of technological progress.
Even if chess is not going to be solved in the next 1,000 years…it might as well be because no human can defeat in a match the best computer program…and computers are going to continue to improve at a far faster rate than the best human players. In this sense, we’re in the same boat as checkerists.
Maybe the world checker champ, GM Alex Moiseyev will weigh in on this development soon with his deep insight into the game.
Regarding computers and their ability to defeat the best human chess or checker GM’s, this fact can’t be denied. The closest to a “perfect” human player (in checkers) would have been Dr. Marion Tinsley who lost only 7 games in 45 years. Two of those were, as the previous post says, to the computer program Chinook.
This incredible record of losing a mere 7 games in an active 45 year playing career is In the domain of competitive mind games, such as chess or bridge, Tinsley’s
record is unparalleled. Strong players come to the fore frequently, but their
tenure at the top is usually short-lived. Emmanuel Lasker was chess World Cham-
pion for over twenty years, is an isolated exception but he did not defend his title as often as he should have.
Being the best, as Tinsley was in checkers, over a 45-year
period is unprecedented.
There simply is not a single human GM past or present that can compare to this record. It’s unbelievable. And considering the extremely complex nature of checkers and the great difficulty it is to Master, this makes such an accomplishment even more remarkable.
Even today’s world champ can’t campare to Tinsley. Whatever made him so many light years of everyone else is a mystery. He couldn’t even answer it himself.
Interestingly, though he was the greatest checkerist of all time, he was also an Expert-level chess player.
Checkers has been ‘solved’ as regards the initial position and any position in their endgame database (which does include 5-5 positions).
The theoretical value of all checkers positions has not been determined – so Checkers has not yet been ‘strongly solved’, only ‘weakly solved’.
g
they solved it with a 10 piece database. thats means its virtually solved because alot of three move openings in checkers are banned. sometimes the first three moves are selected to start the game for each player.when i mean 3 moves it means player A moves then player B moves then player A moves and not player A and player B move three times. have to make that clear to be precise. so in checkers your hardly ever starting from the beggining as you do in chess. checkers is virtually solved. which means that chess shouldnt be to long before its solved since checkers total permutations are chess permutaions to the 1/2 power.
the reason we play these games is not to solve them perfectly… there is always the human element… who blinks first ???