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.

the supercomputers advantage...

[Anonymous Coward]

It stays relatively cool under pressure.

Problem is, it heats up under load.

Re:the supercomputers advantage...

[Anonymous Coward]

in defense of kasparov, big blue also had help from kasparov's previous competitors to look over and recommend moves for big blue to move, so it wasn't really the machine alone that beat kasparov, he was defeated by a supercomputer and a few of his previous competitors.

Re:the supercomputers advantage...

[zebs]

Wouldn't a human competitor examine Kasparovs previous matches and come up with a strategy based on their own experience Kasparovs past games?

Shameless ad plug be damned

[Anonymous Coward]

Here's a direct link without the ad: http://www.technologyreview.com/Infotech/19179/?a= f [technologyreview.com]

Summary

[UbuntuDupe]

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."

Re:the supercomputers advantage...

[anonymous coward 2.0]

Computers playing chess is mostly an expression of the advances in computing power, and only slightly of our ability to create AI. Chess has too small a search space, and brute force is quasi-feasible. Larger games such as Go, (a.k.a. Baduk, Wei qi) are far more interesting, since the board is too big and the subtle effects of a single play radiate across the entire board. Computers still can't even come close to beating a talented child let alone a ranked professional. (Go is also a really fun game to play... a little web searching will tell you more about it.)

Re:the supercomputers advantage...

[Coryoth]

Are you proposing that Kasparov doesn't "tweak" his game play? That he doesn't learn and adapt?

No, but if I recall correctly Kasparov was not given the equivalent game history of big blue to learn how it plays. There was a crucial move one of the early games where Kasparov essentially set a trap -- a situation where computers always opt for one move, but a more subtle human player opts for a different strategy. Given the computers play so far, which had conformed exactly to how computers play, Kasparov was fairly confident. But then deep blue went the other way, against anything any other computer would have done, and completely against all expectation. That really threw Kasparov; he thought IBM was cheating since the move deep blue made was so uncharacteristic for a computer (and even for deep blue's play so far). Things quickly went downhill from there because Kasparov really had no idea what he was playing against anymore, while the computer had been trained extensively on his style of play.

As far as I know no explanation for the strange uncharacteristic move was given by IBM, and deep blue didn't make any other startlingly non computer like moves for the rest of the tournament. It's a rather interesting puzzle.

Re:This article would be more relevant if

[msully4321]

I was under the impression that the rules allowed them to do that: http://www.research.ibm.com/deepblue/watch/html/c. 8.html [ibm.com] "13. At any time during play, IBM may replace any or all of the computer hardware and/or software being used to play the games" But it's still kind of dirty..

Not quite accurate

[Fuji Kitakyusho]

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?

Re:A chess player's take on this

[AslanTheMentat]

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.

Hate to break it to you, but "No [anything computational] will ever be able to duplicate this feat.", Machines or otherwise. This is due to the fact that the complete tree of moves (i.e. all possible plies of the entire game from starting position) has on the order of 10^120 nodes to evaluate, which is slightly bigger than the number of atoms in the known universe.

"It has been estimated that the total number of possible moves in chess is on the order of 10^120, or a 'one' with 120 zeros after it. . . . A supercomputer a thousand times faster than your PC, making a billion calculations a second, would need approximately 3x10^103 years to check out all of these moves" (Dixit and Skeath, 1999: 66).

When a modern chess-playing program does its evaluations it plays out a certain ply depth bounded by the fact that each ply is exponentially larger. I believe 12 ply is about what Deep Blue played at (I might be wrong on that). The program at no times attempts to play the game to a completion state, but rather finds the move that maximizes the minimum loss (as per a minimax algorithm presumably.)

In short, the situation you propose above would take more time than our Sol has left to burn while utilizing more memory than the universe has in atoms.

P.S. to nitpickers: If you find mistakes above, please correct them. I do think this is pretty much on target though...

How blue can you get?

[amccaf1]

In case anyone is confused by the title/summary: Big Blue = IBM; Deep Blue = The Chess Playing Computer.

Re:not really AI

[canuck57]

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.

Re:Obligatory

[Empiric]

Backgammon "went down" quite a while ago. A couple Googled citations:

Hans Berliner: ``Backgammon computer program beats world champion''
Artificial intelligence 14 (1980), 205-220

Hans Berliner: ``Computer Backgammon''
Scientific American 243:1, 64-72 (1980)

I remember reading the Sci Am one in high school; excellent article if you can find a copy--Berliner is/was (still alive?) quite an authority on computer chess as well.

Re:A chess player's take on this

[klngarthur]

Hate to break it to you, but "No [anything computational] will ever be able to duplicate this feat.", Machines or otherwise. This is due to the fact that the complete tree of moves (i.e. all possible plies of the entire game from starting position) has on the order of 10^120 nodes to evaluate, which is slightly bigger than the number of atoms in the known universe.

You don't have to evaluate every node because some are clearly not going to result in victory. If you look at how they 'solved' checkers, they didn't actually analyze every move, they analyzed every possible position once the board had only 8 pieces left. Obviously this is much harder in chess as the finished state of the game can happen with 3 to 32 pieces on the board, but the set of final moves is definitely much smaller than 10^120 and working back 5, 10, 15, 20 moves from those points would also be significantly smaller. It may still be outside the realm of possibility, but i'm sure smarter minds than mine will find ways to reduce the number of relevant states so that eventually a program can be written that cannot be beaten.

Re:This article would be more relevant if

[Neoprofin]

If I had mod points and hadn't already posted I'd mod you up.

KInd of puts all the whining and cries of foul play (especially the ones that specifically say "cheated") into perspective. If Kasparov knew what he was getting into he can't complain about the outcome.

Computer's Name

[ShadowC_ar]

Its DEEP BLUE, not big blue!!!!!!!!!!!

Re:the supercomputers advantage...

[bendodge]

IBM had built a huge library of moves that computers had trouble with. That's why Deep Blue acted so hybrid.

Dennett's Dubious Proposition

[Archtech]

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 [chessgames.com] 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 [chessgames.com] 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

Re:the supercomputers advantage...

[Anonymous Coward]

I think the parent meant that computers can do calculations millions of times faster than our brains, therefore allowing them to calculate every move and possible counter in a fraction of a second (not to mention planning X number of moves in advance), whereas a human player would take far more time.

Re:the supercomputers advantage...

[feijai]

I am both a chess player *and* an AI researcher, so take my nonsense with a grain of salt. :-) IBM cheated in the spirit of the game. Who defined the spirit? IBM did. They hailed the game as the demonstration that a computer system could defeat Kasparov in a chess match. But a computer system didn't defeat Kasparov: a half-dozen computer systems beat him, each one different from the last. modified by AI researchers and a team of chess masters. And they didn't tell anyone: so far as I understand, it got leaked after Kasparov discovered that Deep Blue wouldn't make the same move twice and that inspired an investigation. It's one thing to consult with advisors. It's another thing to have advisors heavily modify your brain mid-match. What did IBM prove with all this? Just that Kasparov could only be beaten if they kept changing the goalposts on him.

Re:the supercomputers advantage...

[G Fab]

Kasparov assumed this computer would act as it had been acting and he played accordingly. Whether a person omitted the computer's actual move and just made their own specifically to counter Kasparov knowledge of computer-chess or if this computer was meant to act in this anomalous manner, Kasparov acted correctly by playing his opponent.

Almost all the time he played a computer, this tactic was effective.

I think these rules show that big blue simply didn't accomplish very much. With all the secrecy, it's possible or likely that IBM just substituted a person for a computer at this juncture. That's not in the spirit of the contest. A computer cannot be programed so that it can beat a person. It would have to be interacted with by that person's actual opponent in order to win. That sentence may not be true, but big blue certainly failed to disprove it.