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.
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...
What about backgammon? Go is the same sort of problem as Chess; it's a completely deterministic game, just just has a bigger decision tree. Both are games that could have been designed to be played by machines, rather than humans. Backgammon, as well as being older than both, is still incredibly hard for a computer to play well (and, bringing it somewhat back on-topic, the author of the best backgammon program, based on neural networks, currently works at IBM).
I am TheRaven on Soylent News
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 based on the current board and the probability its opponent would make certain moves. This is a stategy no human could ever employ due to the sheer processing power it requires to run all the permutation calculations. I believe a system capable of actually "learning", like a trained neural network, would be a fair match for the human brain. As it stands there is no real intelligence being used.
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.
Sure. But Kasparov didn't have access to Deep Blue's "previous games", or indeed any information about the system at all. They kept him in the dark. IBM also insisted that there be no game breaks -- not an issue for Deep Blue of course -- but a very *big* deal for professional chess players. But most importantly, IBM's team of chess masters and coders modified the system between chess games after analyzing Kasparov's strategy the previous game. That is, he wasn't playing Deep Blue: he was playing Deep Blue being adapted in semi-real-time by a bunch of human experts. And crucially, IBM hid this fact, knowing that it'd be (rightly) considered highly suspect.
Actually, backgammon was essentially 'solved' in the 80's by a program known as TD-gammon, which used Temporal difference learning along with self play. http://en.wikipedia.org/wiki/Temporal_difference_l earning
As far as I know, the major difficulty in writing a strong go playing program isn't the search space, but the fact that there are so many opposing aims that it's very hard to write a good heuristic. For instance, players have to decide wether to go for speed or security in their play. Deciding whether to expand territory quickly and risk invasion, or to build up a small stronghold is a major factor in the game.
Slashdot: news for Apple. Stuff that Apple.
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.
I just returned home from the 2007 Scrabble Players Championship, which for this year was the largest North American tournament - substituting for the North American National Scrabble Championship which just returned to an even-year schedule from its brief flirtation with an annual schedule.
There are few in the Scrabble tournament field who think that humans have a chance against a well designed computer program. Sure, as the game contains a significant portion of chance, even an intermediate player like myself has occasionally beat the best computer programs. But given a statistically significant series of games, even the best players will lose to a computer program that was written in spare time by a bright MIT student running on a Pentium 2.
But this does not reduce the fun or competitiveness of the game as a Human endeavor. The value of competition is not in our superiority to computers, but rather that it pushes the limit of the Human mind. There is value in realizing that the human mind has finite limitations and knowing how to push it to them.
Scrabble requires players to memorize gigantic lists of words, index them in useful patterns, unscramble them under pressure of time, calculate probabilities, take risks.
Computers can be programmed to do almost all of the tasks a Scrabble player does, and much faster. But it just isn't all that amazing to watch a computer find a 14 letter bingo play that spans 7 disconnected tiles. Of course the computer found it. Watching a person find it is spectacular.
Chess may be a closer match for Human v Computer, but it still doesn't make the human competition any less spectacular.
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?
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'
As a result, recent advances in Go-playing programs have actually come simply because a new "evaluation function" has arisen: random play. When you get to the end of your search tree, to evaluate whether a move is good or not, you simply randomly play a bunch of games starting at that position, with random moves by both sides, and see what happens. It's a pretty dumb "evaluation function", and isn't really even very static (so it's much slower than, say, most chess evaluation functions), but it has still resulted in a reasonable increase in program strength.
Dlugar
Computer Go: Writing Software to Play the Ancient Game of Go
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!
My difficulties in spelling has always been an issue with me. Part of the problem is when I was tought when I was a little kid was to use sight words, not phonics, some crazy test thing for kids figuring they would learn faster, it didn't work for me. So what happened is my brain is hard wired to spell the way that it seems to feel the best way to spell the word. If someone says this word is wrong then I can normally correct it, and tell them why it is wrong. But that doesn't stop me from making the same mistake over and over again. It is not about being lazy or not taking pride in my work. For college it often took/takes me hours to write a single page paper, not because of content but because I cannot trust what I write, matches what my brain says. Posing on Slashdot and other sites has helped a little bit but still it is just as big as a problem as it always has been. And I cannot afford taking an hour to write a paragraph busting on RMS or something that I readly know that people will disagree with my violently no matter what I say.
If something is so important that you feel the need to post it on the internet... It probably isn't that important.
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.