Behind Deep Blue 229
| Behind Deep Blue: Building the Computer that Defeated the World Chess Champion | |
| author | Feng-hsiung Hsu |
| pages | 298 |
| publisher | Princeton University Press |
| rating | 9 |
| reviewer | ianb104 |
| ISBN | 0691090653 |
| summary | A real-life historic triumph of the nerds |
My wife gave me this book as a birthday present. I was thrilled that finally someone wrote what really happened behind the scenes at the two historic matches, but Behind Deep Blue turned out to be far more than just about the matches. The early part of the book is equally absorbing and full of surprises.
Who & What
Feng-hsiung Hsu, the author, was the father of the Deep Blue project and a troublemaker. When you see a section title like "Mr. Rogers' Neighborhood" in a book about computer history, you know something is up. What he did in this particular section would have been an awful career move today, like landing him in a jail. As it was, he almost got kicked out of grad school. This precarious position played an important role in how the project got started.
The book has two main parts: the beginning and the history of the project at Carnegie Mellon University, and the successful conclusion at IBM, including the two matches with Kasparov.
Carnegie Mellon
During the matches, the IBM web site de-emphasized the Carnegie Mellon part of the project. The instant chess books also failed to fill the void. It was a shame.
The main ideas behind the project apparently were formed at Carnegie Mellon--several of them at a fateful night in Hsu's apartment. I know little about IC design, but his description of the new ideas discovered at that night, underlying the first single chip chess move generator, made me feel like that I could design the chip myself. His thought process in coming to the discovery is also quite interesting. Hsu seems to be a diehard Trekkie. In his description of the selective search algorithm "singular extensions," he repeatedly used the Starship Enterprise in his analogies.
For fans of AI, the book contains a big surprise. Even though Deep Blue's triumph over Kasparov might be considered as a major victory for AI, several of the early members involved in its creation had a definite anti-AI opinion. An exact quote from the book is "AI is bullshit." Hsu himself had an ambiguous feeling toward AI. The main approach taken by the Deep Blue project was to push the technology envelope, which is certainly non-AI, but he also talked of the need for chess knowledge repeatedly in the book.
The central story at Carnegie Mellon revolves around the rivalry between a ragtag group of graduate students and a powerful professor, Dr. Hans Berliner, who is a former World Correspondence Chess Champion and world renowned authority on computer games. I have a feeling that there are things left unsaid in the book, but the intensity of the rivalry and the male egos all come through clearly. One of the thorny points to the students, strangely enough, was that they were not Dr. Berliner's students but the press kept on saying they were.
After the students came out with Deep Thought, the first Grandmaster strength computer, the incorrect press perception produced a very funny story. The story of "The Poor Lieutenant Colonel at Darpa" tells how an overzealous reporter wrote a cover article for the British magazine Spectator, purporting to have discovered that the U.S. Department of Defense had enlisted the service of chess computers. In the process of this discovery, the reporter phoned Dr. Berliner, whom the reporter thought was heading the Deep Thought project, for the inside scoop, and afterwards cold called a Lieutenant Colonel at Darpa in charge of expert systems research, which had nothing to do with the Deep Thought work...
IBM
I did not realize that the Deep Blue team played Kasparov publicly three times. The first time was with the machine Deep Thought, during the transitional period when the team moved to IBM. Kasparov won that match 2-0. The publicity from this match and the subsequent confusion between "Deep Thought" and "Deep Throat" were partially responsible for the new Deep Blue name. The original Deep Thought name came from the sci-fi trilogy Hitchhikers' Guide to the Galaxy.
The story of the completion of the first Deep Blue repeats a theme that recurs throughout the book--the machines always barely work in time. "Four Hours to Spare" describes a period when the first Deep Blue chip had to be used in a new program and had to win or tie an exhibition match, in order for the project to survive. The team barely got the new program "working" with four hours to spare. They managed a tie.
The late-to-arrive situation in the 1996 Deep Blue match itself was not much better--the very first ever game played by Deep Blue was none other than its first game with Kasparov. Deep Blue itself was being put together only weeks before. Deep Blue won this game. What Kasparov said right after the historic game is priceless. There should have been a microphone at the playing table. The behind-the-scenes coverage of this match is more detailed than available anywhere else, but not quite as extensive as that of the final match in the book.
Deep Blue's loss in 1996 spurred a series of activities by the team. I don't recall seeing them mentioned explicitly during the 1997 match. A new Deep Blue chip was designed, along with new software tools for match preparations. The story of "The Phantom Queens" is quite amusing. The team discovered a design bug in the new chip that caused phantom queens to be generated on the chip's internal chessboard. One way to fix the bug was to slow down the chip by disabling a design feature. As a result of this slowdown, we have the only match outcome of what might have happen if Deep Blue had been running at the same speed as commercial chess programs when competing against them. I will let you find out for yourself what the outcome was. A workaround was later implemented, and Deep Blue did not suffer the same slowdown in the match against Kasparov.
The big chapter on the 1997 match alone is worth the price of the book for me. It was a great deal of fun to read. The wild accusations, the missed opportunities, the psychological war game off the board, the battle through the media, and plain simple misunderstanding all make for wonderful reading. The arbiter, Carol Jarecki, summed it up quite well, "This match has it all." I don't want to spoil all the fun for you, but I will mention two interesting tidbits from game 1 and game 6. Deep Blue played the last move of game 1 as a result of bug, although the game was already lost. Kasparov's team was surprised by the move and spent all night to find out why Deep Blue played the move and concluded that Deep Blue played its move because it saw a very deep mate if it had played what should be played... Game 6 was widely reported as Kasparov forgetting his own opening preparations. It could very well have been a deliberate gamble instead. All the other programs at the time, including the 1996 version of Deep Blue, very possibly would have lost the white side of the game.
Other Stuff
The epilogue of the book contains a short description of what happened after 1997, including an aborted attempt to answer Kasparov's repeated challenge for a new match. The first appendix gives autobiographic materials. The other two give selected game scores and pointers for further reading.
General Comments
This is not a chess book, and you don't need to be a chess player to enjoy it. The few paragraphs on technology should be readable for high school students or younger kids with scientific interests. Or you can just skip them.
The book is not really one contiguous story, but a collection of short stories and anecdotes. I read the whole book in one setting, but you could easily read the book in smaller chunks at a time.
Quibbles
Okay, you probably don't need an index for this book, but it would have been nice to have one. Interestingly enough, at www.bn.com, the review mentioned "a strange, inaccurate index", which must have there in the prepublication copy.
Conclusions
I highly recommend the book for general reading. You are not going to learn how to build something like Deep Blue from this book, but you get a good sense of what kind of human struggles it takes. Computer scientists and electrical engineers should get a good kick out of the book, but a layperson can enjoy the book just as well. If you have young kids with interests in engineering or science, this might be a good gift for them.
You can purchase Behind Deep Blue from bn.com. Slashdot welcomes readers' book reviews -- to see your own review here, read the book review guidelines, then visit the submission page.
Please, Deep Blue is not AI, chess is a limited (Score:5, Insightful)
True AI would be a real thinking, feeling machine, and I'm not sure if that's possible. Perhaps the day when we see a computer sit down and ponder it's origins, and even pray, then we can think we've created an AI ( but will it have a soul?).
Re:Please, Deep Blue is not AI, chess is a limited (Score:1)
i'll be impressed when a computer can take the initiative to create 'episode II - attack of the clones' or 'pride and prejudice'. the humanity and imagination put into artistic works represent true intelligence to me.
then again, some of you may not think episode II was very artistic. sorry, but i loved it.
Re:Please, Deep Blue is not AI, chess is a limited (Score:5, Insightful)
True AI would be a real thinking, feeling machine,
Thinking yes, feeling no; that would be AE, and I don't see much point in that.
Anyway, I do believe Deep Blue had intelligence, just in a very narrow way. Why? Because humans playing chess is seen as a sign of intelligence in humans, because before we built a chess playing computer we thought it would be an intelligent thing for a computer to do.
Just that you know, and are able to understand how it does it, does not mean it's not intelligent.
But of course, stupendously narrowly intelligent :-). It couldn't recognize a chess piece if it had a .png of one. General AI is, of course, a very different beast. But suppose we solve that problem and you'll still be able to understand how it works - wouldn't it still be general AI?
And feeling... nah, in us that's a result of our evolution, but general intelligence doesn't need it.
Re:Please, Deep Blue is not AI, chess is a limited (Score:5, Interesting)
It is possible to play chess either by raw computation or intelligence. People use their intelligence to play chess. Deep Blue did not.
Here's an analogy that works for me. A computer can be easily programmed to determine that 1000000003 is not a sum of two square by exhaustive computation. No one (I hope) would contend that is an intelligent computer program. On the other hand, if a person (or a computer program) independently realized that it is a consequence of 3 not being the sum of two squares mod 4, I would regard this is at least a narrow intelligence. Deep Blue took the exhaustive computation approach to chess.
Re:Please, Deep Blue is not AI, chess is a limited (Score:3, Insightful)
If you think Kasparov doesn't use an "exhaustive computation computation approach to chess" then you don't have a great understanding of how the brain works. We're a great big pattern matching machine. Kasparov has trained his pattern matching machine to take in chess positions and output decent chess moves. He then selects among those decent chess moves based on... exhaustive computation.
If you'd like to arbitrarily choose a definition of intelligence that machines will never be able to attain... pick a different arbitrary definition. The difference between warm fuzzy intelligence and cold computational intelligence... can be engineered. And in this case, it doesn't matter.
Re:Please, Deep Blue is not AI, chess is a limited (Score:2, Interesting)
Hmmm... I'm not sure I agree. A human chess player's computations are specifically *not* exhaustive. A human player seeks to hold or threaten strategic squares or pieces and works backwards to see which moves make that most likely. Deep Blue runs through tons of moves and sees which moves hold or threaten strategic squares or pieces.
There are chess programs that work like human players work: establishing strategic goals and trying to work out ways to get to them. But none of them are very good.
Kasparov's strategy was to keep DB out of any position that would let it come up with a surprising (to a human) move through exhaustive analysis, which is why all the matches looked like Flanders in WWI. Also, Kasparov is probably the worst GM for a computer/human match... he plays very dramatic, emotional games and wins by humiliating and terrifying the opponent, which wouldn't work against a computer.
Re:Please, Deep Blue is not AI, chess is a limited (Score:2)
Whatever process it is that humans use to play chess, we're still a pattern matching machine that has to establish good algorithms, and then execute them exhaustively. Those algorithms might not be a move search, but rather a search for the key peices or squares. Grandparent poster decided that since Deep Blue wasn't introspective enough, it's not AI, or it's not interesting, or something. Actually, I'm not sure what his complaint was. So I was trying to illuminate his poorly defined complaint.
Now I'm muddled.
Re:Please, Deep Blue is not AI, chess is a limited (Score:2)
There are many higher level tasks that we do that become about pattern matching, and the best example are tasks that involve expertise. You become an expert at something when your brain optimizes its storage of the patterns it sees. Chess is a classic example. So is music composition. And spelling. And speech.
Re:Please, Deep Blue is not AI, chess is a limited (Score:2)
On the other hand, if a person (or a computer program) independently realized that it is a consequence of 3 not being the sum of two squares mod 4, I would regard this is at least a narrow intelligence.
You've just described a test for intelligence that 99.9% of humans would fail. And yet a computer, who could pass the test but by some different method, isn't as intelligent as a human? Doesn't sound like a good test.
Re:Please, Deep Blue is not AI, chess is a limited (Score:2, Insightful)
There are two schools of AI: "applied" AI tackles all the problems that conventional engineering hasn't a clue about (which is why "applied" AI fails so often); cognitive science attempts to come up with plausible, implementable explanations for various kinds of cognition (which is why you won't find cognitive scientists tackling applications-level problems.)
I see no reason to argue one way or the other that a sophisticated machine intelligence (i.e. something which most people agreed was "intelligent" after observing it in action) would or would not exhibit behaviours that we might interpret as emotional responses.
To put this in context, I only give other people the benefit of the doubt that they experience consciousness: there is as-yet no way for them to prove they actually are conscious rather than just automata giving a convincing impersonation.
One final point on the topic of awareness: every computer program with finite resources can be reduced to a state machine which can be reduced to a lookup-table and an index into that table. People often get upset that even the fanciest AI program would also be subject to this sort of construction - they spend ages arguing why the lookup table would be a fake (would not be "aware") and the more complex program the real thing. The problem here is that nobody has a handle yet on what constitutes "aware"ness, so it seems to me that until we resolve this one, we have to stick to functionalism: if it looks like a dog and barks like a dog, at least for the time being we might as well call it a dog.
Re:AI vs AE (Score:2)
It doesn't matter how intelligent you are; if you don't have a purpose to put it to, you may as well be a jellyfish.
So why did Deep Blue play the game then, instead of just closing itself down? Why do computer programs do anything at all? Because they want to? No, of course not, because we tell them to. And it will be the same for any intelligent program.
Re:Would we want our computers to have feeling? (Score:4, Funny)
[user@localhost ~]$gcc -o hello hello.c
bash: gcc: command not found
[user@localhost ~]$which gcc
I don't know. Nevermind.
[user@localhost ~]$wtf?
I shouldn't have to tell you what's wrong...
Re:Would we want our computers to have feeling? (Score:3, Funny)
Re:Please, Deep Blue is not AI, chess is a limited (Score:5, Insightful)
What you say is true is true, but in the past, chess seemed like a problem that computers would never "understand" and thus would always be second to humans. Even though the solution may not seem elegant, it nonetheless works.
This solution may not have been imaginable forty years ago. Perhaps forty years from now, we'll be able to brute force "a real thinking, feeling machine."
A great book for idiots like me on how true AI may be possible is Marvin Minsky's Society of the Mind [amazon.com].
Re:Please, Deep Blue is not AI, chess is a limited (Score:5, Interesting)
There are actually two major branches of thought on the matter, neither one is proven. The statement you make is one such branch of thought, that can be stated more precisely as:
A perfectly played game of chess will never result in a loss, and will only result in a tie if the opponent also plays a perfect game
However there is also another school of thought, which points out the lie in your statement. This thought can be stated as:
In chess, strategy is equally important to board condition. There are most likely branches of play that look to be promising but that a significantly skilled chess player can turn into a win.
The reasoning behind this is that there is no single opening move that results in the entire game-tree having no checkmates for one player. And that no subsequent move can prune out checkmates, until the end-game. Thus, a perfect player could possibly get itself into a situation where a check mate is forced on it.
I don't know whether that's true or not. One part of me says yes, that seems true, while another part of me says, why doesn't the program just choose a path where any move it can make results in an end-game with no checkmates with itself. I'm not sure such a path exists; even if it does, I would call a system built to choose this path AI.
Artificial Intelligence has absolutely nothing to do with emulating HUMAN intelligence, as you seem to believe. Artifical Intelligence is about embuing a machine with the ability to go beyond it's basic programming.
Certainly a chess program can never truly go beyond it's programming; which is to win a game of chess. But what about it's basic programming; a few thousand lines of code written by a team. It can take those lines of code and make assumptions, strategies, tactics, and observations. This most certainly is beyond it's basic programming, which really just included a set of the rules for chess and a way to look ahead a few dozen moves predictively.
Such a system would certainly qualify, in my eyes, as AI.
Re:Please, Deep Blue is not AI, chess is a limited (Score:3)
Re:Please, Deep Blue is not AI, chess is a limited (Score:2)
Actually, I said that there were two schools of thought and that neither one was proven. So, yeah, you're right and so am I. No proof. None. And I kept up the same "I don't know which one is right and neither does anyone else" tone throughout the whole post.
Read more carefully before replying next time. Move along. Nothing to see here.
Re:Please, Deep Blue is not AI, chess is a limited (Score:2)
I must say that this is one of the best reviews that I've read on slashdot - not the usual crap^H^H^H^Hstuff.
Re:Please, Deep Blue is not AI, chess is a limited (Score:3)
- The game is a win for white.
- The game is a win for black.
- The game is a draw or stalemate.
Some games have been solved like this: certainly 3x3 noughts and crosses, and there was a Slashdot story about Owari a while ago. Chess is a long way off because the space of possible games is so vast.
Re:Please, Deep Blue is not AI, chess is a limited (Score:2)
My point being that, until we've done that, one can't really make a statement to the effect of "An infinitely powerful computer will always win"... which is, paraphrased, what the original poster said.
There are two ways to prove such a statement; both of them result in a general solution to the game of chess, as you describe. The first way is to compute all possible games and characterize them mathematically. Though difficult, this is possible. This is analguous to brute-forcing a public-key encryption algorithm whose key-length is equal to the number of possible moves. It's gonna take a while, but it's possible. There's no reason you can't do it.
The second way is to take a couple dozen smart mathematicians and have them look at the system and analyze it mathematically. This is analguous to breaking an algorithm. Most algorithms it's possible to break, though a precious few it is not. So far chess looks unbreakable, and we've found pretty strong evidence that it is theoretically unbreakable.
Re:Please, Deep Blue is not AI, chess is a limited (Score:2)
- The game is a win for white.
- The game is a draw or stalemate.
This is because white has the (rarely used) option to pass first move to black.
Re:Please, Deep Blue is not AI, chess is a limited (Score:2)
Having the first moves is clearly an advantage in chess (that is to say, for strategic reasons, without knowing the entire game tree).
Re:Please, Deep Blue is not AI, chess is a limited (Score:2)
Re:Please, Deep Blue is not AI, chess is a limited (Score:2)
No I don't have any references. I did a quick google search and didn't find anything. It's a 'school of thought' in that when talking with people I know, you know, in the 'real world', that kinda 'exist' and when I 'told' them about it, 'they' agreed that 'it sounds' plausible. That these people, all of whom know something both about 'computers' and 'chess', all agreed that it certainly has not been proven that a perfect game equals a draw or win every time.
Riposte: do you have a reference that says that a perfect game is possible? Because unless there's a logic proof of same, then my viewpoint is as valid as yours.
Oh, and just because you put my words in quotes doesn't mean they have any less value.
In chess, strategy is equally important to board condition
In the context of talking about whether the game of chess is a theoretical win or draw, all that matters is the 'board condition'.
Yes, but what about the move before this theoretical win or draw? And the move before that? What about planning, cunning, and trickery? What about a branch of play that receives a low initial score, so it isn't explored by the brute force algorithm, but that makes it possible to solve the endgame?
There are most likely branches of play that look to be promising but that a significantly skilled chess player can turn into a win.
First of all, I assume you mean to say "don't look to be promising", because the sentence doesn't make any sense otherwise. Assuming that's what you meant, we're talking about whether chess is a theoretical win or draw - all that matters is what happens with perfect play, not whether the position "looks promising".
Let me rephrase: There are most likely branches of play that look to be promising to an AI but that a significantly skilled chess opponent can turn into a win.
That done... assume by "looks promising", I mean "This is a branch of the tree that gets a high score and therefore is further scrutinized by the AI, and may even result in a move being made to bring this branch into being," but I assumed that most programmers would understand what "looks promising" means.
Artificial Intelligence has absolutely nothing to do with emulating HUMAN intelligence, as you seem to believe. Artifical Intelligence is about embuing a machine with the ability to go beyond it's basic programming
Well, as someone who works in AI research, I gotta say - thanks for defining our field for us, man.
Look, I, and everyone here, certainly understands that AI is a tough field to define and that most people choose to define it a little differently. I gave what I have heard, over the years, to be a generally accepted definition. I rebuffed a definition that I believed to be false. For instance, I do not consider that a computer must pass a turing test to display intelligence.
What is your problem, anyways?
Certainly a chess program can never truly go beyond it's programming; which is to win a game of chess. But what about it's basic programming; a few thousand lines of code written by a team.
So is there some well-defined distinction between 'programming' and 'basic programming' that you're trying to make here?
No. Not well-defined. In case you haven't figured it out, I could give a flying fuck about well-defined. I care about me-defined. Words and thought images that matter to me. I think it was pretty clear from context that 'programming' could be construed to be the particular problem that a program was written to solve, and that 'basic programming' is the basic code written to solve that problem. No tricks, no voodoo, no special optimizations. Just code.
It can take those lines of code and make assumptions, strategies, tactics, and observations. This most certainly is beyond it's basic programming, which really just included a set of the rules for chess and a way to look ahead a few dozen moves predictively.
Err... how do you know exactly what the 'basic programming' of this hypothetical chess program exactly includes? If, as you say, the 'basic program' really just consisted of an algorithm to search game trees, then that is exactly what the program will do - it's not going to magically start 'making assumptions, strategies, and tactics' unless that is in the code.
I'm discussing a theoretical opponent that does those things and happens to be embodied by bits running through a piece of silicon. Though I vehemently oppose the turing test as a measure of general artificial intelligence, I will borrow it as a tool to use to measure specialized intelligence. In this case, if the program acts as a human player would act, then couldn't it be said to be utilizing the same process as a human player?
Or to state another way: most chess AI programs, recognizing limited resources (time alloted for game, processing abilities) must prune their predictive tree in some way; some way of discarding branches that seem to be unfruitful and exploring ones that seem fruitful. Could not this algorithm be said to be making assumptions, strategies, and tactics?
Sorry all, for the tone. It's just that, being someone who actually knows something about chess and ai, that last post caused me physical pain, and I had to get it off my chest.
I apologize to you for the consternation. Maybe I should've prefaced my post with something to the effect of IANACP or IANAAIP or something equally banal. Except I didn't want to be cute. And I don't apologize for my opinions. I would've prefaced my post with "This is just my opinion." But this is slashdot. Every post is someone's opinion. That's the beauty of slashdot. I very sorry that your viewpoint differs from mine.
And I'm very very sorry that you find your viewpoint so important to you that you feel physical pain when someone says something that contradicts your viewpoint.
But, all the same, fuck you.
Re:Please, Deep Blue is not AI, chess is a limited (Score:2, Interesting)
The day a computer sits down and prays is the day I get the next spaceship off this planet.
And anyway, if a computer is intelligent enough to be 'a real thinking
Just my 2p worth
Catholic AI (Score:2)
int i,x;
i = confess(sins());
for ( x = 0; x <= i; x++ )
say_hail_mary();
}
Would Poker be a good AI test? (Score:4, Interesting)
You would think that Poker would be a good choice (real poker, not Video Poker [littlecutie.net]). You don't win just by playing the odds -- you have to gauge your opponents' playing style and determine when they're bluffing and when you should bluff. I know how tough that is... I lost $40 to one guy in high school playing nickel-ante poker (do you still have that watch, Ted?).
But so much of that kind of poker depends on body language... setting a CRT in one of the chairs just wouldn't be the same.
Now, when they make a computer that can play An Enchanted Evening [gamegallery.com], I'll be impressed! (And maybe a little creeped out...)
Re:Would Poker be a good AI test? (Score:4, Interesting)
And, Moore's law not withstanding, we probably won't be able to build a computer to brute force the problem. It'll HAVE to be solved by an AI that thinks and strategizes, instead of one that just computes the entire game tree and picks the best branch.
Another game that seems surprisingly difficult to program well is Monopoly; the value of any particular piece of property for trading is a complex algorithm involving not only the player's personal desire, but the value the opponent may place on that piece of property as well as the value that every other opponent MAY be able to place on it at any point in the future. It doesn't seem hard, I just think the hardcore AI guys don't consider a contemporary board game worthy of their attention.
Of course if I could pick a contemporary game that would be the ultimate AI test, I'd go with Turing's approach and pick Dungeons and Dragons. Because there's no way to brute force the thing EVER, and it requires GENERAL problem solving and logic algorithms...
Re:Would Poker be a good AI test? (Score:2)
It's interesting how many so-called "children's games" end up having deep implications.
Re:Would Poker be a good AI test? (Score:2)
Interesting. Would you happen to have any references, essays, examinations, or what have you, to this?
I find your ideas intriguing, and wish to subscribe to your newsletter.
Re:Would Poker be a good AI test? (Score:2)
It'd be an economics problem, not a computer science problem. It probably wouldn't even be the hardest of economics problems. Not that I've ever taken an econ class. Once you have defined the algorithm to make this determination, monopoly would be solved, there would be no decisions to make, and it would be 100% luck.
What's Hard about Monopoly?
Re:Would Poker be a good AI test? (Score:3, Interesting)
But I've played quite a few of the various computer monopolies, and every one that I've played has been vulnerable to 3-way trades. That is, property that is invaluable to you and invaluable to the computer agent you are purchasing from, but extremely valuable to a third party can be had cheaply. Therefore the "seems to be"... I don't think any serious economics or AI people have ever really looked at it.
There is one very important part here; that this value is a more or less arbitrary continuum. Though initial costs and future earnings certainly factor into the value proposition, there are cases where even that is superseded by something humans are good at and computers are bad at; judgement calls.
For example, let's say you own a monopoly. Noone else does. Someone wants to trade with you, net result, you get one more monopoly and they get one more monopoly. Most value algorithms that I can think of would say that this is a more-or-less even trade. Maybe a little bit of cash should be thrown in by one side or the other, but it's an even trade.
But I would never make that trade, all other things being equal, because it would erode a significant advantage. This is just a simple example; there are more complex ones, that I think humans would be good at solving and a simple algorithm bad at solving.
BTW, Monopoly is not 100% luck. There is one choice that you can make that affects your board position, which is ultimately what decides wins and losses.
Whether or not to stay in jail.
Re:Would Poker be a good AI test? (Score:2)
Since chess moves are limited to a certain domain, what *would* be a good game for creating and/or testing an AI computer system?
I like someone's suggestion of Dungeons and Dragons. The problem is defining success. There's no optimal way to play, and you could make something almost Eliza-style to make it play in a very boring, stupid, non-cooperative way. It'd be back to a judgement call.
Perhaps a better approach is to just have a system that can learn games. User invents a game, sits down, tells the computer how to do it, computer plays it legally and does its best. Bonus points if it recognizes when it can use brute force, or another strategy it can do well, but playing strength isn't the point - after all, almost all humans totally suck at any game they've just been taught as well - and many don't even improve with practice.
I think requiring knowledge of natural language is too much, human language is very weird and connected to the specific architecture of our brain. If we ever figure it out we can teach computers, but before that, it must be possible to be intelligent and not know human languages. However, the artificial language used must be complex enough to explain the rules of basically any game. Perhaps something like Lojban?
Take this to extremes, and you have Nomic - where the rules are trivial to begin with, and players vote for new rules, changes to existing rules, etc. Anything goes. If you can play Nomic, you're intelligent :-).
Re:Please, Deep Blue is not AI, chess is a limited (Score:2)
Re:Please, Deep Blue is not AI, chess is a limited (Score:2)
'Anything a computer can do is not AI.'
Why do you think that is true? That's like saying a computer can never do AI and that's something that I certainly don't believe (after all, the 'A' in AI stands for 'articifial'). The problem may be defining what AI actually is. This boils down to defining what intelligence is. And that's something I'm not going to do here in this limited space
Greetings,
Re:Please, Deep Blue is not AI, chess is a limited (Score:2)
Re:Please, Deep Blue is not AI, chess is a limited (Score:2)
Greetings,
Re:Please, Deep Blue is not AI, chess is a limited (Score:2)
It is extrememly unlikely that you could ever build a machine to 'solve' chess (i.e. analyse every possible play). Therefore a chess computer (or a human for that matter) can never play a 'perfect' game of chess.
Therefore, any good system would also have to take into accound some sort of strategic play (fuzzy logic, A.I - whatever) - this is what makes chess programs interesting.
Re:Please, Deep Blue is not AI, chess is a limited (Score:2)
True AI is would be nothing, because the entire concept of Artificial Intelligence is an oxymoron. We call systems AI (aerospace anti-collision systems, "smart bombs", and Rainbow Six's "Tagno's"), but in reality these systems - even though they "learn" - are still complex calculators.
Re:Please, Deep Blue is not AI, chess is a limited (Score:2)
Billions? That's a little low... I read somewhere that there are more possible configurations on a chess board than there are atoms in the known universe (something like 10^743 combinations, IIRC). So no, I doubt processing power will be catching up anytime soon to do a real exhaustive search (and remember, after searching all combinations, you have to figure out which is the best one).
Re:Please, Deep Blue is not AI, chess is a limited (Score:2)
Even the most recent man-machine match featured the human winning 2 games against the strongest computer in the world (it's much stronger than Deep Blue was), despite being able to see 20ply ahead in all lines and over 100ply ahead in selected lines.
My point is that just brute force is not good enough to be an effective chess program; the programs also use various forms of reasoning to assess the position. Is intelligence more than just the use of heuristic algorithms?
Re:Why would it pray? (Score:2)
oh-oh - sounds like what fundies call prayer. Now the ludites will want to burn you at the cross for blasphemy.
Now, can we integrate this into the next version of SimCity - have those little critters pray to me that I don't destroy them, etc...? After all, I am the creator/ruler/god of their world.
Re:Why would it pray? (Score:2)
Peter Molyneux? Is that you?
Re:Why would it pray? (Score:2)
Don't try to stop me! (Score:4, Funny)
Yeah, tonight I'm rushing home. I've got paint drying in the living room. Don't wanna miss a single moment!
Deep Blue good chess player....not strategist (Score:4, Insightful)
This book is a cover-up (Score:4, Interesting)
Deep Blue was powerful, and it could predict nearly every possible move in the future, but the match was rigged -- the programmers ran heavy analysis of Kasparov's moves, but Kasparov himself never got to see one line of Deep Blue's algorithm/source codes. It had little to do with advancing AI and search algorithms on a supercomputer, and more to defeat Kasparov publically so consumers would gain more confidence in IBM.
Deep Blue could have been easily defeated if it was open source -- computers are only as smart as the humans that program them are, and one flaw in the code could easily be exploited for a laughable victory... Perhaps even a 4 move beginning checkmate?
Re:This book is a cover-up (Score:3, Interesting)
Why would you assume that? From what I've heard, Deep Blue's chess algorithms aren't incredibly "clever", i.e. they don't use special tricks designed to beat humans that you could discover in the code. It's a straight forward brute force approach. If so, then access to the source wouldn't do anyone much good.
Kasparov would probably have benefited from looking at a play history, but I doubt it would have guaranteed his win.
Re:This book is a cover-up (Score:5, Interesting)
It's not just brute force, otherwise the programmers wouldn't have needed to adjust it between matches (presumably to compensate for Kasparov's playing style.) It's not like the programmers thought, "gee if Deep Blue only had a few billion more moves thought out, it would have won," and then went and instantly and significantly improved their brute force algorithm. The adjustments they made in between matches must have been specific strategies against Kasparov, which is then like having a groups of chess experts plus a super computer against one man under pressure.
Deep Blue only showed that computer tools can give would be runners-up the edge over the favorite, which isn't surprising or remarkable.
Re:This book is a cover-up (Score:2)
Sure you would. "Gee, Kasparov really seems to like using his knights, so lets bump their priority up a bit, to slay them more quickly, and thus screw with Kasparov's preferred strategies."
Re:This book is a cover-up (Score:2)
That's entirely different; you're talking about counter-strategy now, customized against a knight-favoring playing style. That's exactly the type of thing I'm saying they probably did between games; i.e. they used more than brute force, and the computer wouldn't have won without it. (although I'm sure there's already code that dynamically compensates when the computer notices human piece-favoring. if not, I want a job programming deep-blue
Re:This book is a cover-up (Score:2)
They used directed brute force. It's still brute force; it's just a question of what they were brute-forcing their way towards.
Parent is a no-brained Zealot (Score:3, Insightful)
Just because it isnt open sournce doesnt make it evil or inferior, and I for one am sick and tired of silly zealots spouting nonsense out of their asses and getting modded up due to the lines "closed source=bad" or "open source=good" somewhere in their posts.
Re:This book is a cover-up (Score:5, Insightful)
The moral of the story is that Gary surely knew the basics oh how Deep Blue worked. In the end however, the brute processing power of Deep Blue is what triumphed, not strategy. With the increasing power of computers, there is no turning back. Soon enough, we'll all have computers powerful enough to beat any Grand Master. It's just a matter of time. The complexity is certainly not in the chess program itself.
Re:This book is a cover-up (Score:5, Interesting)
>(not quite sure how many Deep Blue could
>handle). For each end position, a score is
>assigned. The computer then picks the first move
>based on the end position it thinks is best and
>assuming its opponent will always play his best
>possible move. It's all based on what's called
>the "Alpha-Beta" search algorithm.
Deep Blue went on average 12 levels deep, current top programs can go over 16 in the middlegame and much more in the endgame.
What you describe is minimax, not alpha-beta. alpha-beta is an optimization that cuts branches that cannot affect the result.
--
GCP
Re:This book is a cover-up (Score:2)
"For each end position, a score is assigned. "
Sorry, I disagree. Even if the computer can see 20 moves deep, which ones it chooses is based on the evaluation of each of the positions - the computer picks the best one of however many.
If Kasparov's team could've examined the source-code and seen that it values Open files for rooks too strongly, or passed pawns, or whatever... That could've been exploited. No matter how many moves it can see, it's still a matter of judgement as to which is "best" unless the branch results in checkmate.
Re:This book is a cover-up (Score:3, Insightful)
>was open source -- computers are only as smart
>as the humans that program them are, and one
>flaw in the code could easily be exploited for a
>laughable victory... Perhaps even a 4 move
>beginning checkmate?
I wonder who the morons were that moderated you up.
What you write is utter and complete nonsense. Proof: several excellent quality open source chess programs that CANNOT easily be defeated by humans even if they study the source.
--
GCP
Re:This book is a cover-up (Score:2)
Since there's only one of those, I highly doubt the computer would be susceptible. It's easy enough to program in the defense of it, and every chess player that's had that one done to them very quickly learns the defense.
And the 4-move beginning checkmate leaves the player trying it in such a bad strategic position it's risky to try it in a real match that counts for something as important as your reputation as a chess player.
Since Deep Blue was a brute-forcer, it wasn't technically making strategy moves. No strategy moves = no weaknesses, unless it's a bug.
Re:This book is a cover-up (Score:3, Insightful)
The source code doesn't matter. What matters is that Kasparov was never allowed to see Deep Blue's games.
Deep Blue was quite a system, but it was also specially tuned to play effectively against Kasparov. In any top-level tournament involving multiple to GMs, Kasparov would place near the top and Deep Blue at the bottom. Deep Blue beating Kasparov in a single match under asymmetric conditions in no way proves that Deep Blue was or ever will be as strong as Kasparov; in a fair match or in a tournamament I'd put my money on Kasparov every time (and I don't even like him or think he's the best human player any more).
Re:This book is a cover-up (Score:2)
Well I guess we better throw out any open source programs that do encryption then.
Re:This book is a cover-up (Score:2, Insightful)
the press ? (Score:2, Insightful)
"...the incorrect press perception produced a very funny story."
When did any new scientific/technical stuff did not get messed with in the non-scientific press ?
And the story usually are not funny to read when you were interviewed. Either the journalist have to be taught how to do some basic reality check in high-tech, or high-tech people have to learn "how to communicate with press 101".
</Bitching>
Mr. Rogers? (Score:3, Funny)
Do I?
"What he did in this particular section would have been an awful career move today, like landing him in a jail. "
Wear knitted sweaters all the time?
Slowly change shoes while singing?
Re:Mr. Rogers? (Score:3, Informative)
For those who don't know, Carnegie Mellon is located adjacent to the building where Mr. Rogers lives in real life -- it's literally Mr. Rogers' neighborhood.
Re:Mr. Rogers? (Score:2)
Recent computer matches vrs humans (Score:5, Interesting)
some info from Wired (Score:2)
Re:Recent computer matches vrs humans (Score:5, Informative)
What the Deep Fritz team discovered was they needed to keep the Queens on the board--essentially, it is the old cliche about computers vs. human chess players: The computers are generally better at tactics, and the humans are better at understanding the position.
Re:Recent computer matches vrs humans (Score:2)
Not sure where you heard IBM destroyed Deep Blue after the match. They may have altered it.
In 1998 I was a participant in the ACM programming contest world finals in Atlanta, Georgia, sponsored by IBM. We got all kinds of interesting things from IBM, including a copy of ViaVoice, multiple copies of their VisualAge developer suite (I hate it), and in particular several Olympic t-shirts and related items (IBM had just sponsored the 1998 Winter Olympics in Nagano.) But perhaps most interesting of all was that one evening they had a computer lab connected remotely to Deep Blue and we actually got to play against it. We were told that each session was actually just playing against a single Deep Blue processor, rather than the entire machine, so there may have been some modifications.
Of course, we certainly couldn't actually beat the machine, so we got bored and played two sessions at once, using the moves Deep Blue generated for one game as input to the other. It seemed one side had the edge for awhile, and then amazingly the other side fought things down to a tie. :)
What's the quote? (Score:4, Interesting)
So what did he say? Seems kinda dumb just to leave it like that.
Re:What's the quote? (Score:3, Informative)
Behind Deep Blue eh? (Score:3, Funny)
why not deep blue2? (Score:5, Interesting)
deep fritz was run on an 8-cpu intel workstation, and i'm assuming that deep junior will run on a machine with similar specs. it is likely that both junior and fritz use more advanced algorithms than those used on deep blue (the source code for deep thought is online somewhere). deep fritz in the kramnik match was doing 6M moves/sec and deep blue did 1.1M moves/sec.
computing power has come a long way since 1997. if IBM or even SGI put together a chess supercomputer written with current algorithms, wouldn't the smarter algorithms + raw processing power crush the top grandmasters? It would definatly be a boost for PR and the cost to the company would be marginal if they stuck to standard hardware.
I'd like to see a modified deep fritz running on the Earth Simulator [top500.org] vs a FIDE dream team of grandmasters. [fide.com]
Re:why not deep blue2? (Score:2)
woops, i meant to type 1.1B moves/sec.
Sounds like you just created "First Art" for... (Score:2)
Now all of those other fantasy sports games should be quaking in their boots. I mean fantasy chess wouldn't just beat you in a parallel universe, but it would do it with a "fantastic" mind.
--Puns, unfortunatly, were intended.
Re:why not deep blue2? (Score:3, Insightful)
If you don't understand the insides of a chess program, and what speed means to comp vs comp games...
I've dabbled with my own little chess program, nothing major... so I know roughly how they operate. Everyone knows that raw power means nothing if you don't use it correctly. If you're evaluating moves on a line that goes nowhere then those moves/sec are wasted. Deep Blue isn't all that smart, its just freakishly fast.
Here is a boat analogy for you. You got a 265HP boat vs a 150HP boat. The 265HP boat has its props 2 meters above water. Which one wins the race?
Re:why not deep blue2? (Score:2)
4.5 to 1.5 (win on white, draw on black) would be a crushing defeat. I think there is still a position for the first chess computer to deliver an ass-whoopin to a grand master. A 1 vs 1 match might be difficult to arrange with such a strong chess computer since a humilating defeat like that would be damaging.
More on Deep Blue vs Deep Fritz (Score:3, Informative)
In 1995, Fritz beat deep thought in the 1995 WCCC event in Hong Kong with a opening book cook. Had nothing to do with deep blue other than it was the machine prior to deep blue 1.
Fritz is a PC program. Nothing to do with a special-purpose hardware design made especially to play chess like deep blue.
The real story here (Score:4, Interesting)
That is a very revealing revelation, as it goes it speaks to the notion of what makes machines different than people.
If the computer was working properly, it would have resigned. Instead, a bug forced it to make a move that threw Kasparov off balance and won the game.
You cannot capture tactics like that in an algorithim. Only true sentience or a computer bug allows for that.
Re:The real story here (Score:2)
Why would a computer ever resign? Its algorithm should calculate as many paths as possible, and choose the best one ("best" must be defined by players/programmers much more talented than I). Even if the best one is the end of the list, and still probably leads to a checkmate-loss, the computer should still try it. Resignation is to relieve the losing player of the indignity and stress of getting checkmated. A computer needs no such relief, it has nothing to lose. If the computer calculates midgame that it will lose as long its opponent keeps its current strategy, then the computer should at least try to use moves that maximize game time, to try to make the human so tired it makes a mistake.
Instead, a bug forced it to make a move that threw Kasparov off balance and won the game. You cannot capture tactics like that in an algorithim. Only true sentience or a computer bug allows for that.
And sure you can program it to be unpredictable. Just have it calculate the most predictable/sensible move, and (if many paths seem to lead to an eventual loss) don't do that move.
BTW, unless you're talking about a magical lightning strike [eonline.com], a computer bug is just as algorithmic and programmed as bug-free piece of code; it just has unexpected actions. If my math function always returns one too high an answer, then it is still behaving algorithmicly based on logical code, it is just not behaving as I planned. If the Deep Blue bug made unpredictable moves because of a 'bug' in a line of code, there's no reason an expert programmer couldn't have intentionally told it to make unpredictable moves using that same line of code. The difference between a bug and a feature is that the bug is unintentional.
Re:The real story here (Score:2)
Computing every possible move is a an unsophisticated and inefficient method of victory.
For example, a human can ruthlessly punish or even taunt another when they make a mistake, putting them off-balance. Or on the flip side, you can assist or soothe someone and gain their sympathy.
Maybe grandmaster-level chess isn't the best measure of artificial intelligence.
Re:The real story here (Score:2)
Actually, it is. From a pure computational stand point, having computers play chess is certainly interesting, but only to a point. What will be much more interesting is when computers can play chess with the emotional component. When a computer can be intimidated into losing a chess match, then AI will have succeeded. That is especially true if you believe the point of AI is to emulate/duplicate human intelligence. If you believe that the point of AI is to perform complex computation and nothing more, then the chess thing is pretty much a done deal for you.
Oh, and for those who question the value of the emotional component, I have two observations for you:
1. If emotions are unimportant, then why do we have them? If you believe in evolution, then you must believe that emotions serve some purpose such that having emotions makes us a more successful organism than if we didn't have them.
2. If AI gets to the point that emotion can be emulated properly and that we are unable, through blind screens, to tell the difference between artificial intelligence and human intelligence, then the AIs will become a very useful way to understand human intelligence and behavioral conditions better. This would allow us to experiment more freely and find prevention and cures for a whole host of psychological problems. Of course, then you potentially have large ethical issues. After all, if a computer can pass the Turing test, then some will claim that it is indeed sentient.
Somewhere behind deep blue (Score:4, Funny)
--Quote adapted from Frank Oz.
Re:Somewhere behind deep blue (Score:2)
--Time for another cup of coffee.
One game which Kasparov did win (Score:5, Interesting)
Re:One game which Kasparov did win (Score:2)
Similarly, about a decade ago (+/- 5 years), Michael Basman defeated someone (Spassky? Botvinnik?) using similar unorthodox opening moves. I think it was something like f2-f4. I seem to recall that it worked for a couple games and then he was soundly trounced.
But, as I said, I don't know much about chess, so I may be completely incorrect.
Isn't the greatest story of this the human element (Score:3, Interesting)
Kasparov's Reaction & chess geek link (Score:4, Informative)
Also, if you're interested in chess programs from a programmer point of view this link [chessopolis.com] has quite a few links to various tutorials on chess playing algorithms as well as many different free Winboard engines.
we have a winner! (Score:3, Funny)
-gerbik
Deep blue was a fraud (Score:3, Insightful)
The fact is, the machine was reprogrammed DURING the chess match. Gee, go figure. The people at IBM built it SPECIFICALLY to beat Kasparov, and it was promptly dismantled after the game, leaving Kasparov with no opportunity for a rematch. Also, who else did this Deep Blue play that was any good? More proof that it was designed to play against Kasparov's style.
Sorry, but there was heavy and reasonably criticism of Deep Blue, and IBM didn't alleviate matters by having it dismantled before a rematch could be worked out, or before any other top players could have played it.
Re:Deep blue was a fraud (Score:2)
The fact is that a computer beat the world's top-ranked chess player in a tournament. Period. No, it probably could not have beat every single grandmaster at the time, but again, it was never claimed that it could.
Why should IBM have felt obligated to offer the machine up for a re-match, or set up against all comers? IBM isn't in the chess-playing business. They proved their point and moved on.
SirWired
Re:Deep blue was a fraud (Score:2)
They even reprogrammed it in the middle of the tournament, as they noted flaws or different tactics by Kasparov. Again, stacking the deck against Kasparov.
Then they wouldn't allow a rematch. Yes, indeed, why would they want to allow a rematch, or anyone else to play Deep Blue? That would've proven that Deep Blue was a fraud, which couldn't beat Kasparov a second time around (once he'd learned from his mistakes) or any other top player.
Exactly what point did IBM prove? That when they cheat and manipulate the situation to put the opponent at an unfair disadvantage, they can win? Kasparov wasn't even allowed to play practice games against Deep Blue, or analyze Deep Blue's previous games, but the developers of Deep Blue considered Kasparov's games in detail when making it. If for nothing else, the situation was certainly unfair, as Kasparov couldn't even analyze his opponent before the game, while his opponent (Deep Blue) was built with great consideration of all of Kasparov's games and his playing style.
In short, Deep Blue v. Kasparov was anything BUT a fair competition. It was one of the most pre-arranged, unfair, manipulated match in chess history. IBM proved nothing, except that by cheating they can win. I could have done that too, without spending billions to make a super-computer. Sure, if you cheat enough, create an unfair enough advantage for yourself, you win.
Re:Deep blue was a fraud (Score:2)
Kasparov knew that he would not have access to the computer before the tournament. He knew that the team would have access to his previous games. He probably knew the computer could be reprogrammed between games.
Kasparov collapsed. So what? That's his problem. The fact that he made some major mistakes is not IBM's fault. Are you saying that Deep Blue should have gone easy on him when he stopped playing well?
Just because Kasparov did not negotiate more preparation for himself does not make the tournament unfair. Perhaps this was due to arrogance on his part. He might have assumed he could beat the machine without prep. If he didn't like the pre-conditons, he never had to agree to play.
"...the most unfair, manipulated, match in chess history"?!?! You act as if IBM drugged his food and deprived him of sleep. He lost, fair and square. If he wanted to prepare more, this could have been negotiated ahead of time. If he wanted a rematch, he could have asked for that too. Not IBM's problem.
SirWired
Re:Deep blue was a fraud (Score:2)
IBM also sternly INSISTED on their terms, which meant no preparation time for Kasparov. If Kasparov didn't agree, there would have been no tournament. IBM was stiff-arming him to put themselves in the most favorable position possible, giving their program several unfair advantages.
The simple FACT of the matter is that Deep Blue had three unfair advantages over Kasparov which most chess players never have against their opponent: (1) Built to play Kasparov specifically; (2) Reprogrammed after each match (cheating); (3) Well-prepared for Kasparov, but Kasparov wasn't allowed to prepare against him. You cannot possibly call this a fair match, no matter what Kasparov agreed to. The only reason Kasparov agreed to it is because he had no choice: IBM was not accepting reasonable terms.
Here's a summary: IBM stacked the deck against Kasparov. It's that fucking simple. Got it? Just because Kasparov agreed (because if he didn't, there would be no match) doesn't mean this match was fair. It was set up to give the computer every possible advantage. You will notice that in the recent match between Kramnick and Fritz, Kramnick was allowed prep-time, and Fritz wasn't reprogrammed after each match; also, Fritz was designed as a general-purpose chess-machine, not a machine specifically to play well against Kramnick. In other words, it was obvious that looking back the chess match was so unfairly stacked against Kasparov that he had no way of winning.
Like I said, all that match proves is that even a weaker opponent like Deep Blue can beat a vastly superior one like Kasparov if its given every possible unfair advantage. Just a ploy by IBM to make money.
Fischer may be somewhat justified in saying that modern chess is all predetermined anyways. In the case of Kasparov v. Deep Blue, he's most certainly right.
Try reading about the history of something before saying a computer program has really beaten a human.
Even Deep Fritz hasn't truely beaten (or really tied) Kramnick. Kramnick resigned a game he could have easily drawn, the result of a draw would be that Kramnick would have won the match. And there's plenty of evidence suggesting that despite Kasparov's collapse against Kramnick, he's still a better player than Kramnick (Kasparov recently beat Kramnick in a blitz-tournament). Kasparov's poor performance against Kasparov can be explained by a few things: (1) His ego was shattered 5 years earlier in the unfair match against Deep Blue; (2) Personal problems; (3) He was ordered not to play well (under penalty to his relatives) to advance the career of a favored up-and-coming star (this is the Fischer-theory).
In short, no computer has yet equaled the best chess player in the world to my satisfaction, nor to grandmaster's opinions. Doesn't mean it can't be done, but I think it'll still be a while. And of course, once we switch to playing Fischer-random chess, computers will be set back another 40 years, because there will be no "opening theory".
Re:Deep blue was a fraud (Score:2)
If he refused the terms, IBM would have set out to slander him, calling him a coward and whatnot, in front of the public.
Btw, they never said they would reprogram it between matches. And its never been proven that the machine didn't have human help. I personally think it was Fischer playing the games Deep Blue won.
Re:Deep blue was a bagel toaster (Score:2)
First of all, IBM participated in this chess match as a publicity stunt. The technology they were promoting was their ability to built a box with a very large number of computing elements that coordinated effectively. The nature of the standard chess algorithms (90% brute force) make them a good "animal model" for the kinds of technical problems involved in building massively parallel computing systems.
Chess has an additional chachet because in the history of computational theory Alan Turing and others from his era considered chess to be a good "animal model" of complex human thought processes. Back in that era it was broadly assumed that the hallmark of human intelligence was formal reasoning. Within twenty years the evidence started to mount that the human mind is actually very poor at formal reasoning, and that the areas where the human mind holds significant advantages over deductive computation are of a stochastic nature (what people often refer to as "pattern recognition").
The next turn in this story is uniformly neglected once the narrator begins to beat on the man-versus-machine jungle drum. (Another characteristic of the human mind is that analytic thought ceases completely once the preening reflex takes over.) It turns out that it is more useful to build machines that do the things we are not already exceptionally good at. Like adding more than three numbers together and getting the right answer, first thing on a Monday morning after the Super Bowl weekend.
The reason that computers have been so greatly developed in the brute force dimension is because humans are terribly bad at this stuff. The reason why computers have not developed stochastic algorithms of the same power is because humans are already damn good at stochastic pattern recognition. Hand me a four function calculator I can calculate sums and products faster than Newton, Gauss, or Kepler. Yet our best results in visual processing are easily outmatched by a four week old puppy. Do you think it is easy to win grant approvals to underperform a four week old puppy? This is yet another example of how poor the human mind is an analytic reasoning. It's terribly stupid for us to think that underperforming a four week old puppy is slight progress, but we do.
A lot of people say, because of this situation, that computers aren't very good at this kind of application. That's not true. They are good at this kind of application (and they can still get an awful lot better), just not good enough to impress anyone who was born with superior innate abilities courtesy of mother nature and 100 million years. If you look at recent advances in accoustic processing, such as filtering background noise, there are clear signs that we are entering a phase of surprisingly rapid progress. Visual systems are a harder problem, I suspect the same progress curve will be shifted back by about ten years.
In this light, the most important knowledge we gain right now from the study of chess computers is the nature of the boundary between brute force methods and alternative methods. Deep Blue represents the fairly extreme side of brute processing. The advantage held by Deep Blue, at that point in time, was the vast number of coordinated processing elements it contained. IBM had the choice of pursuing a pure brute force approach, or a brute force algorithm tempered with subtlety. Unfortunately, the state of the art is such that adding subtlety to a massively parallel system seriously degrades the massive parallelism. Pure brute force is relatively easy to coordinate. Hybrid brute force is a nightmare to coordinate.
IBM being what they are, and the economic incentives for begin good at brute force being what they are, you can guess which tactic IBM chose. There was only one problem remaining. Pure brute force was not yet at the level of beating Kasparov. The pure brute force has a fairly large number of known weaknesses and sinkholes. The problem for IBM was to "tweak" the evaluator and search heuristics so that it didn't fall into the classic holes (which Kasparov would have exploited mercilessly). So they trained the program (by debasing various weighting factors) to avoid the kinds of positions that offer blood to a shark of a known and especially vicious species.
At this point it is worth mentioning that Kasparov was actually a fortunate choice of opponent for IBM. Kasparov has long been known for his tremendous ability to compute complex lines of play and he has used this weapon to crush many excellent players who could have competed on even terms otherwise. The problem for Kasparov is that his computational ability is roughly equivalent to a four day old puppy feotus compared to the computational ability of Deep Blue. Because Kasparov favours computationally rich positions, he has a tendency to play into mentally exhausting positions if his adversary shows the slightest weakness. The only aspect of the competition I regard as unfair is that Kasparov wasn't given nearly enough time to rest between games.
The question about building a computer SPECIFICALLY (emphasis from the other dork) to beat Kasparov really misses the point. I would guess there is perhaps 1% of such a system that can be tweaked without the immediate prospect of the entire house of cards collapsing. Half of the Deep Blue source code has nothing to do with chess at all (the parallelism, transposition tables, the basic min-max framework, etc.) Leaf evaluator functions have been studied for decades. How much do you think you can improve one in three days? And still have it run correctly in dedicated silicon? I don't think so.
So you end up tweaking a few weighting factors, such as the desirability of retaining the queens. You can witness this same kind of tuning in an elementary school chess club: "Joe is a titan with his queen at the end of the game. I'm going to try as hard as I can to whack his queen with my queen!" Kasparov SPECIFICALLY beaten by a kindygartner! (To quote Home Alone.)
The kind of tuning they did between games is on the order of the batting coach telling his hitters about the pitcher they will face in their next start "watch out for that wicked slider nailing the outside corner". If they didn't tune the program between games, once Kasparov found an area of superiority, he could have won every game on the same basic pitch. What would be interesting about watching chess played like that? And these tweaks were no simple matter. Your desire not to see the queens exchanged could cause some other aspect of how Deep Blue plays the game to deteriorate spectacularly. There's a name for this risk: it's called regression, and it's the curse of clever improvements. If tweaking was 1% as effective as the previous poster would have us believe, a computer would be president already. If your program is tuned to a local optimum, any single parameter you adjust makes the program play worse. In human beings 99.9% of genetic mutations (cosmic tweaks) are benign (if you are lucky) or deleterious, often fatally deleterious. In fact, large chunks of the human genetic system is devoted to removing tweaks. Kasparov didn't get to be world champion by having only one strength. He beat everyone out there, who represent the best of every different style. What do you think was happening between games? They change a 1.6 weighting factor to 1.55 and Kasparov falls to pieces? His vanquished opponents will lynch you if they hear you saying that.
I think Kasparov with more rest between games would have beaten Deep Blue. Ten years from now a machine computationally equivalent to Deep Blue will be a very ordinary piece of equipment. What's the point of keeping Deep Blue alive if they aren't going to invest in continual improvement at the software level as well? Anyone who thinks IBM was setting themselves up for a long term participation in the man versus machine debate really has no clue as to why IBM involved themselves in this chess match to begin with.
Let's not forget that Deep Blue played some positions Kasparov was convinced he would win better than Kasparov believes any human opponent could have played those positions. He commented at the time on how Deep Blue would constantly amaze him by finding slight resources in losing positions that stretched the process out, sometimes until Deep Blue stretched the losing position all the way to a draw. This is a classic observation about computer chess: if these programs weren't so damn good at hording slight resources, they might not be despised for their strategic weakness. The problem with computer chess is they are penny wise and pound foolish. But then we forget that the computer has no difficulty in keeping track of 100,000 slight advantages in a position each worth 0.001 cents.
What I find interesting to observe is the progress of programs like Fritz that plays at a very high level with not nearly as much brute force as employed by Deep Blue. It's a very difficult thing to successfully exchange brute force with additional subtlety. It's like grafting a plastic heart into a human being. Most forms of subtlety are immediately rejected by the host brute. It's difficult to add subtlety into chess algorithms, because the subtlety has to be manufactured exclusively with platinum, titanium, and teflon, otherwise it does more harm than good.
The best thing about having such great chess programs on the classical paradigm is that they will serve as an excellent foil to test out new classes of algorithms. Along the way we'll learn an amazing amount about the limitations and advantages of brute force versus domain heuristics. Compared to that, I find the man versus machine jungle drum exceedingly dull.
Damn. I can't believe I wrote a post this long in a freaking web form. When the computers find out, they'll laugh like hell. Long live 1980.
Re:Deep blue was a bagel toaster (Score:2)
No one's saying that IBM intended to be a long-term player in the chess arena. That still doesn't justify their underhanded tactics in denying Kasparov or anyone else a rematch.
The simple fact is, this match was so unfairly biased against Kasparov from the start that its completely meaningless. The only significant outcome of this match is that Kasparov's ego took a big hit, as can be observed in Kasparov v. Kramnick.
As you mentioned, Kasparov wasn't given enough resting time between each match. This puts him at an unfair disadvantage, as computers need no rest. He wasn't given any time to prepare against Deep Blue by playing practice games against it: IBM denied him that. Deep Blue was modified between matches and designed with Kasparov's style of play in mind. In short, there was no doubt that Kasparov would lose this match because he suffered every possible disadvantage a human opponent could suffer.
Thus, Kasparov v. Deep Blue was nothing but a meaningless farce.
Deep Blue = Deep Cheat (Score:2)
1. IBM specifically built Deep Blue to play Kasparov, not to be a general-purpose chess machine.
2. Deep Blue was reprogrammed between matches. Again, extremely unfair. As if normal opponents can "reprogram themselves" between matches. This is the equivalent of switching opponents in the middle of a chess match.
3. Fischer was not allowed to study any of Deep Blue's previous games, or to play matches against Deep Blue to familiarize himself with Deep Blue, yet Deep Blue was given extensive knowledge of Kasparov's styles specifically. In fair tournaments, each player has the opportunity to study the other. Kasparov did not have that opportunity.
In short, this was one of the most unfair matches in chess history. All IBM proved is that if you cheat enough and put the other player at enough of an unfair disadvantage, you can win, even if they are the second greatest ever (Fischer is the greatest ever). This was nothing more than a publicity stunt by IBM to get more recognition and money, and they did it by mandating that Kasparov agree to a fundamentally unfair match.
It is interesting that in the game in which Kasparov won, he played anti-chess, using very unorthidox "non-best" moves. Interestingly, this is what its rumored that Fischer is doing now-a-days in his annonymous online blitz games, starting out with very unorthidox openings (i.e., moving all pawns forward).
The best games of the last century were played by Fischer and Kasparov. The thing that we're looking for this century is Fischer v. Kasparov, the match the chess world deserves to see.
Re:Rushing home !?! (Score:1)
I have been to a number of matches, alwais fun live and on TV.
And yes not seeing it live takes away some of the charm.....
Re:Deep Blue != AI (Score:2)