Slashdot Mirror
10 Years After Big Blue Beat Garry Kasparov
Jamie found another MIT Technology review story, this time about Chess, Supercomputing, Garry Kasparov, and trying to make sense of just what exactly it all meant when a computer finally beat a grand master. An interesting piece that touches on what it means to play chess, the difference between humanity and machinery and how super computers don't care when they are losing. Worth your time.
It stays relatively cool under pressure.
Problem is, it heats up under load.
I'll bet Big Blue has one hell of a poker face!
The game.
But what about 'Go'? 'Go' is much harder for computers to play. Let's all talk about 'Go'.
Offtopic, but I really like these '10 years after' articles, because it helps me sit back and think about the last decade. I was thinking this had been more recent, didn't realize an entire decade has passed... Kinda fun to actually think about what all has changed, and what hasn't.
An I.T. motto in the hands of an idiot is a dangerous thing...
I thought I'd save y'all some time and some page views. The following summarizes everything you will take away from the article:
"10 years ago Kasparov was beaten by a computer. The computer used a brute force searching method that pruned a lot of move trees. How do you know Kasparov's brain didn't do the same thing? The only clear difference is that humans can be intimidated, but that's not to humans' credit. Oh, and Fisher Random chess is designed to force more computational power to be used during the game rather than before."
Apology to Ubuntu forum.
People seem to be very sensitive about computers doing things they think only humans should be able to do. They dismiss defeating a chess grand master or the Turing Test as toy problems.
I did an AI degree in the mid 90s and one of the things we covered was the definition of intelligence. After running through a few unsatisfactory definitions, my conclusion was that people used intelligence to mean whatever could be done better by a human being than anything else...
Actually, my favourite definition of intelligence, partly because of its succinctness, is "productive laziness".
Peter
From the article, "Chess requires brilliant thinking, supposedly the one feat that would be--forever--beyond the reach of any computer."
Oh, please. The hubris is overwhelming.
I play the game. I am not a great players, but it is a fun diversion and can help to develop focus and thinking skills. But, please, to say that Chess could have been beyond a computer? That is small, ignorant thinking.
The human brain excels at pattern matching in massive parallelism. It is this advantage we have over our current computers. But, new computer designs have gotten fast and with lotsa memory and storage space. It was only a matter of time until a computer had the right amounts of that speed, memory and storage space, coupled with programmers to make the best use of it and then no human would ever stand a chance.
As we get better with fuzzy AI type stuff, even games like Poker, Texas Hold 'em and others will even fall from our human hands.
The intuition we exercise is some random choice being made, but based on experience and a factor of acceptable risk of failure.
Bearded Dragon
Later. Later. Right now, let's play Global Thermonuclear War.
____
~ |rip/\/\aster /\/\onkey
Garry Kasparov ego probably caused him to loose more then his brain power or his chess skills. Having a computer give him an extreamly challanging game got him fustrated thus making mistakes.
The Computer doesn't care it is just focusing on the game 100% it is not even conserned if it is breathing or not overheating or a person behind it with a gun to shoot it if it looses. It is just running a set of processes, and using its memory to play the game.
If something is so important that you feel the need to post it on the internet... It probably isn't that important.
After it was discovered that IBM was tinkering using chess experts (that is, humans) to tinker with its software between matches, they're personae non gratae in the chess world now.
Back in the early 1990s, I used to play in chess tournaments. I wasn't very good though and I didn't play at a high level, but I did play in official tournaments that the USCF (United States Chess Federation) sanctioned. My goal at the time was to try to make grand master. I gave up because of 2 reasons. The first was that I wasn't very good. I had serious problems in the middle game. My opening play and end game play were sound, but inevitably I would get beat in the middle game through carelessness. The second reason I gave up was because I realized that computers were ruining chess. Keep in mind that I am talking 1990-1993 here (I stopped playing in tournaments in 1993). In the old days, if you learned a chess opening, the moves might go 7 moves deep or so in most openings where the moves for the white and black pieces were known and any deviations from these set moves got you "out of book" as they say. If you deviated on, say, move 4 in a 7 move sequence, the odds were that your move was bad because if it was so good, it would have been known and used by other players and then be part of the book. At this time being "in book" was already starting to change because of computer analysis. Then you could go 10 moves or more in many openings and still be "in book". The amount of time and memory required to memorize these much deeper opening sequences was overwhelming. One day I realized that it just wasn't worth it and I'd rather devote my time and brain power to other things that I actually had some talent for, like learning other languages.
Chess is said to be "solvable". My understanding is that it can be proven mathematically that chess has a finite series of moves. If this is correct, then at some point computers will be powerful enough to be able win every game because they'll be able to analyze every possible opening all the way to the end and only pick the moves that will win. No human will ever be able to duplicate this feat. So it is inevitable that computers will eventually be unbeatable. I think just a few weeks ago Slashdot had an article that a computer program has been designed that is now at the point where it cannot lose at checkers - ever. Checkers is quite a bit less complex than chess and it has only now been solved. Whether it takes 10, 20, 50 or more years to solve chess, the day will come when computers simply cannot be beaten at chess under the current rules.
Should we care? Well, maybe not. Computers are better than humans at a lot of things, like mathematical calculations, so it's inevitable that they will be better than humans at chess. The downside is that once all chess games are solvable, it will ruin chess at the professional level. It will make it almost impossible for any game to be postponed until the next day because once there is a postponement, a player could, in theory, simply use a PC to analyze his game and find a sequence of moves where he cannot lose if he plays them correctly. At that point, there's no more human element in the game - it's simply a matter who can more accurately remember computer analysis. Computers ruined chess for me in the early 1990s. Can you imagine how much worse things are now? And how much worse they will be when the day comes that everybody can use a PC to analyze his game and find a way to never lose? At that point, I suspect that either chess will change to Fischer Random Chess as mentioned in the article or people who would have played chess will simply move on and play the game of go instead. Go is beyond the ability of current computers to solve and even the best computer programs can't beat strong human players.
I seem to recall that Kasparov conceded the game. While still technically a win for Big Blue, is this not somewhat different than an actual checkmate? Was a checkmate imminent?
In case anyone is confused by the title/summary: Big Blue = IBM; Deep Blue = The Chess Playing Computer.
"Flag on the moon. How did it get there?"
Mine loves to play:
- When Is The Most Irritating Time To Crash
It also enjoys
- Fatal Exception Blocking The Save Function
I tried what you just said:
i ng() std::endl;
n ing' was not declared in this scope
#include
int main(){
do {
std::cout move_that_provides_the_most_possible_ways_of_winn
} while(!check_mate());
}
master_chess_program.cpp: In function 'int main()':
master_chess_program.cpp:5: error: 'move_that_provides_the_most_possible_ways_of_win
master_chess_program.cpp:6: error: 'check_mate' was not declared in this scope
Maybe I am missing some header files?
An interesting observation on the current crop of top PC chess programs. Rybka, the program that tops all the ranking lists, does so with a node count that is much lower. That is, Rybka looks at around a tenth of the number of positions per second compared to other programs. The reason is does so well, is that it has a very sophisticated evaluation algorithm for each position it examines. In some sense, it has better chess knowledge than other programs.
And this is the difference between Kasparov and Deep Blue (and other chess computers). The computer can analyse millions of positions per second. Kasparov might examine only a couple of positions per second, but he does so with far greater knowledge and insight - he recognizes when pieces are coordinated and mobile, when pawn structures are strong, when his king is safe.
One day far in the future, we will start up our chess programs and they will immediately announce "Mate in 326". A "good" move will be one that hastens the loss by as little as possible.
"Chess is the Drosophila of artificial intelligence. However, computer chess has developed much as genetics might have if the geneticists had concentrated their efforts starting in 1910 on breeding racing Drosophila. We would have some science, but mainly we would have very fast fruit flies." -John McCarthy
Slashdot: news for Apple. Stuff that Apple.
While it was impressive to have a computer win against the "chess master" it accomplished this task by looking ahead as many board configurations as possible....
There in is why many who play chess don't take this match seriously.
Some flaws, first to play a grand master you need to qualify and play others. Then you enter a tournament and build up to play. This leave a trail of your style of play, your weaknesses and your strengths. A true match, your opponent would study your last games before he moved the first piece!
In this case, it was completely bypassed, placing the single player against machine at a disadvantage. Should it have been a real tournament play, I suspect the machine would have done well but lost. And there was one game I watched where he lost and he was either having a bad day or tossed it.
I mean, with Moore's Law improving the computing power of PC's. PCs should be 32-64x more powerful than 10 yrs ago. How big is a machine that would have the equiv processing power of deep blue of 1997?
I used to study AI for a while, and i just wanted to point out how unfair this line of reasoning is. Stuff like this ("Very nice, but it isn't *real* AI, because...") always comes up every time there's some AI break-though being discussed.
1. It's almost trivial to make a program 'learn' from mistakes. Just store some negative value for that specific decision-point. Depends on your definition of 'learning', of course. But the principle is the same in humans and AI
2. Kasparov also adjusted his style (i believe there are certain playing-styles that are beneficial when playing against an AI), and i bet he had coaches and consultants
3. So what?
4. See above.
My point is that every time some AI people actually manage to out-do humans, humans tend to re-define what intelligence is. I bet if you'd tell somebody 100 years ago that a machine would be the world's best chess player, that alone would have been enough to consider the machine 'intelligent of sorts'. But as soon as we know how it works, it somehow looses the right to be called 'intelligent' (mechanical turk). I think this is because it seems to hurt humans that AI shows them that whatever gives us the right to call ourselves 'intelligent' is nothing more than the result of zillions of relatively simple interactions of little protein-machines.
IIRC (its been a while) the best way to determine what language a given text is written in, is amazingly 'stupid': just compare the ratio of how many times the different characters appear. The result is still amazing and should be considered 'kind of intelligent'.
So, just give AI some kudos, accept that there's a lot left to be done, and that the heuristics dint really matter, as long as the result is cool. (and please dont give me none of that Chinese Room Argument crap)
A year or so ago, I saw a documentary about this. If I remember correctly, IBM has a grand master behind the scenes, working with the computer. This grand master also over-rode one or more moves made by Big Blue.
... is Computer vs. Computer
They are fearless, uncompromising, untiring. The games are far more interesting than human efforts. Check out some Rybka vs. ZapZanzibar matches (the number 1 program vs. the number 2 program). Incredible play.
Deep Blue analayzes millions of possible moves every second, resulting in a performance that eventually beat the best chess player there is. Yet grandmasters do not consider anywhere even close to this number of alternatives, and Kasparov did hold his own against the computer for more than one match. Why can humans so rapidly prune irrellevant combinations from consideration before evaluating them further and still present incredibly strong play? I believe that the answer to this question holds the key to making a computer that is actually good at chess. Deep Blue didn't beat Kasparov because it was better at chess than he was. It beat him because of the sheer overwhelming number of combinations that Deep Blue analayzed, which itself was only sufficient to beat the capabilities of considering the mere hundred or so moves at most that Kasparov would have likely considered each turn. Which is _really_ the better player?
File under 'M' for 'Manic ranting'
Its DEEP BLUE, not big blue!!!!!!!!!!!
Dennett's article suggest to me that he himself does not know a huge amount about chess. For instance, he writes, "The best computer chess is well nigh indistinguishable from the best human chess..."
Sometimes, but not always. As is well known, computers excel in "random" positions where tactics predominate. That's because they have no concept of "general principles" or strategic goals as human chessplayers think of them - instead, they just calculate furiously and find the move that, against what look like the best replies by the opponent, gives the best "worst-case" outcome after a given search depth. They are programmed to follow the game theory "minimax" strategy, which essentially chooses the best (maximum) outcome if the opponent plays as well as possible (minimum). So in a typical open position with lots of pieces flying around, where there are dozens of variations to calculate, a computer tends to have an accentuated advantage over a human player of similar strength. For many years masters and grandmasters have carefully avoided wide-open positions (like those arising from the King's Gambit, for instance) for that very reason. Playing the King's Gambit against a really strong program looks very much like suicide. You start by giving the thing an extra pawn, which is enough of an advantage for it to win. Then you try to outplay it in its natural environment. It's like fighting a crocodile underwater.
At the other end of the spectrum, there are a few closed positions (i.e. with locked pawn structures) where even very strong chess programs fail to see what a reasonably good human player spots immediately - for instance, "this must be a draw because White's queen can never escape". (However, it might also sometimes happen that a program spots a clever and previously unnoticed way to break that kind of impasse).
Returning to my assertion that Dennett is wrong in saying that "The best computer chess is well nigh indistinguishable from the best human chess," I can immediately think of two classic counter-examples. First, the game in which Deep Junior, with the Black pieces, sacrificed a bishop on h2 and soon after forced a draw. If Kasparov had tried to play on, he risked losing. No one had ever even seriously considered that sacrifice before in the given position, although the general type (the "Greek gift") is one of the most familiar even to beginners. That certainly wasn't indistinguishable from human play, because no human had ever dared to play it. My second counter-example is the way Deep Fritz squashed world champion Vladimir Kramnik flat in the sixth game of their match last year. I was watching live on the Web, and when Deep Fritz played 10.Re3 I thought "Great! the stupid computer is going to get thrashed by Kramnik's ultra-sophisticated play". After some more foolish-looking moves by White, at move 20 I thought the game was definitely going Kramnik's way. But lo and behold! 25.e5! introduced, not so much a tactical melee as the threat of one. Kramnik shuffled his pieces anxiously, on move 30 Deep Fritz grabbed a pawn - and then it was over. Deep Fritz remorselessly ground the world champion down, forcing him to resign in just 17 more moves. In the final position Kramnik, still just a pawn down, could hardly move a single piece. In that game Deep Fritz played the final, technical phase like Bobby Fischer. But it played the attack between moves 10 and 30 better than Fischer could have! Its moves looked like a beginner's, yet they defeated Kramnik.
Strong programs have a big "psychological" advantage over human players, in that they don't have any psychology! Even super-grandmasters like Kasparov and Kramnik, on the other hand, very quickly start to exhibit signs of nervousness after a few games. Eventually, this can assume proportions that start to resemble post-traumatic stress disorder - especially if the human being has had a nasty shock, such as
I am sure that there are many other solipsists out there.
Your comment made me think of two things.
First: Chessboxing
Also, the quote:
"A computer once beat me at chess, but it was no match for me at kick boxing."
The libertarian solution to the failures of capitalism is to apply more capitalism til the failures are fixed.
Yes. The go proverb for this is "loose your first 100 games as quickly as possible". The hidden truth in that statement is that Go is a somewhat different game than most others. The pieces are stationary, and can't run away from danger. It takes some repetition to quickly perceive the way in which the continual addition of stationary stones can create the same effect with respect to a group of stones. In go you don't "run away", you "grow away" :).
Version 2.0 New and Improved!
Yale CS professor David Gelernter wrote an article about the match, expressing a quite different view.
0 .html
http://www.time.com/time/printout/0,8816,986355,0
Dennett is a brilliant philosopher, but he's also well-known for propounding a particular agenda. While his view is plausible, it is not intrinsically more plausible than Gelernter's view.
By dwelling on the functional equivalence of Deep Blue chess and Kasparov chess, Dennett skillfully lays the assumption that this is the correct way to compare all differences between humans and machines. Rhetoric like "as far as we know" quietly asserts that all right-thinking intellectuals agree with him, while argument is dismissed as "cling[ing]... to brittle visions."
However, both his view and Gelernter's are merely expressions of the consequences of certain prior assumptions, and these assumptions are unprovable ones: function vs. being, for instance, or philosophical naturalism vs. methodological naturalism.
Gelernter adequately illustrates a counter-view that many of Dennett's peers would hold:
"...the idea that Deep Blue has a mind is absurd. How can an object that wants nothing, fears nothing, enjoys nothing, needs nothing and cares about nothing have a mind? It can win at chess, but not because it wants to. It isn't happy when it wins or sad when it loses. What are its apres-match plans if it beats Kasparov? Is it hoping to take Deep Pink out for a night on the town? It doesn't care about chess or anything else. It plays the game for the same reason a calculator adds or a toaster toasts: because it is a machine designed for that purpose."
"The more powerful your computer, the more sophisticated the behavior it can imitate. In the long run I doubt if there is any kind of human behavior computers can't fake, any kind of performance they can't put on. It is conceivable that one day, computers will be better than humans at nearly everything. I can imagine that a person might someday have a computer for a best friend. That will be sad--like having a dog for your best friend but even sadder.
"Computers might one day be capable of expressing themselves in vivid prose or fluent poetry, but unfortunately they will still be computers and have nothing to say. The gap between human and surrogate is permanent and will never be closed. Machines will continue to make life easier, healthier, richer and more puzzling. And human beings will continue to care, ultimately, about the same things they always have: about themselves, about one another and, many of them, about God. On those terms, machines have never made a difference. And they never will."
Dennett might not be wrong, but he might not be right.
--
Dum de dum.
Freedom is not the license to do what we like, it is the power to do what we ought.
Deep Blue's win over Kasparov was the triumph of a human team that programed a machine with 200 years of chess knowledge that could be recalled without error. Period. This match was about the same as a spelling bee with a human vs. a spell check database.
No chess program that is only programmed with the moves and rules could ever beat a Grandmaster, International Master, or even a rated Master here in the USA. Ever. A chess program with the moves, rules AND Alpha-Beta search (that counts only the value of the pieces) might beat a Master occasionally on a very fast computer. Let me hash this out in the three stages of a chess game:
OPENING: Kasparov was beaten by another human who programmed 200 years of already-known opening moves into Deep Blue. Indeed, the last game was lost by Kasparov because he fell into a "known" opening trap. "Known" to the computer through human programming.
MIDDLE GAME: Strategy used by DB was programmed by a human Grandmaster. Then it is checked during the game by brute-force calculation. DB played roughly equal here. Every Grandmaster today checks his middle game ideas for tactics or traps with a computer that can find mistakes in a few minutes that would take a human days or weeks to find.
END GAME: Knowledge of end game positions and strategy was programmed by a human Grandmaster. Kasparov outplayed DB completely here.
No machine or software has ever beaten a Grandmaster without human intervention.