Forgot your password?
typodupeerror
Classic Games (Games)

Deep Blue vs. Kasparov 10th Anniversary 101

Posted by Zonk
from the machines-win-again dept.
qeorqe writes "For the tenth anniversary of Deep Blue's victory over the world chess champion Garry Kasparov, Wired has an interview with Deep Blue developer Murray Cambell. The discuss the power of the now-aging supercomputer (equivalent to just one Cell processor), and the nonexistent future of PC vs. Human chess contests. 'It's almost the end of the story for chess in the sense that matches between chess machines and grand masters are becoming less interesting because it's so difficult for the human grand masters to compete successfully. They're even taking relatively dramatic steps like giving handicaps to computers, making them play the game with a pawn less or playing the game with less time. We're past the stage where there's a debate about who's better -- machines or grand masters -- and we're just looking for interesting ways to make the competition fairer.'"
This discussion has been archived. No new comments can be posted.

Deep Blue vs. Kasparov 10th Anniversary

Comments Filter:
  • by Tackhead (54550) on Tuesday May 15, 2007 @07:40PM (#19139055)
    > We're past the stage where there's a debate about who's better -- machines or grand masters -- and we're just looking for interesting ways to make the competition fairer.'"

    How about we play overnight on January 19, 2038? I'll use this mechanical chess clock to keep track of my times, and Deep Blue can use those two 32-bit integers holding time_t, and subtract one from the other!

  • fischer random chess (Score:3, Interesting)

    by mo (2873) * on Tuesday May 15, 2007 @07:44PM (#19139097)
    Can anyone comment at how well chess apps like Junior or Fritz are at playing grand masters at Fischer Random Chess?
    • Re: (Score:1, Informative)

      by Anonymous Coward
      From what I hear (and this is just word of mouth and wikipedia) they suck at it because, like human players, they rely on "opening book".

      This might just be my imagination but I think I do better when I play against GNUchess when we play Fischer Random. Its the future of chess IMHO.
      • by simm1701 (835424)
        I suspect its more that chess comuters are trying to play this variation without being coded for it.

        Since there are only 960 valid starting combinations it wouldn't take much for it to precompute the opening moves for each possible variable - what chess computers already have for the normal game.

        Even go won't stand against comptuers for long, its still a total knowlege deterministic game. Admittedly the search space is large and we still haven't figured out good metrics for it, but thats just a matter of ti
        • How about StarCraft?
        • by Nalanthi (599605)
          Actually, it is not likely that Go will be solved in the short term. The solution space for Go is huge and defining metrics for the game is very difficult. There are 129,960 possible states for the board to be in after just two moves. Even if you get into complicated symetrical analysis to discard some of these states you are still left with a staggeringly huge number. A computer that wanted to look ahead only three moves from this state would need to calculate a paltry 17 million moves.

          It is frequent
  • by St. Arbirix (218306) <matthew.townsend@gm a i l .com> on Tuesday May 15, 2007 @07:45PM (#19139113) Homepage Journal
    and we're just looking for interesting ways to make the competition fairer.

    Make them play go.
    • how 'bout playing chess while the computer player processes environmental data, is distracted by bowel movements, wants pizza, oh yeah call the wife after game,be aware of how high the ceiling is?

      if a computer can process all these and still play chess then we need to worry.

      • by tlhIngan (30335)

        how 'bout playing chess while the computer player processes environmental data, is distracted by bowel movements, wants pizza, oh yeah call the wife after game,be aware of how high the ceiling is?

        if a computer can process all these and still play chess then we need to worry.

        Problem is, a computer can isolate tasks so much better than us. So one process can do the environmental processing, another does bowel movements, a third wants pizza, a forth handles the wife, and the fifth does the ceiling height. All

        • by Luyseyal (3154)
          Yeeeeaaahh I'll run my wife-interfacing mechanism through another VM. Brilliant!

          -l

          P.s., I actually enjoy interfacing with my wife and we do it on a regular basis. Har-dee-har-har.
    • Make them play go.


      Good idea. But, remember, computers were as bad at Chess in 1980 as they are at Go today. Wait 25 years. Exponentially faster hardware may not solve the problem, but algorithmic research certainly will.

      Computers are smarter than we are at a lot of things. It's only a matter of time until they are smarter at everything. You are as smart as the collective wisdom of hundreds of thousands of individuals. Computers can be.
    • by GrpA (691294)
      Computers playing "Go" as an alternative to chess isn't likely to happen.

      If you think about it, back in the 80's dedicated chess computers were pretty smart and you had to be very good to beat them. Then a company called Cyrus produced "IS Chess" which was able to defeat the then best-of technology dedicated chess computers (and it ran in 16Kbytes of program space on a 3.5 MHz Z-80 processor). Even back then, in the mid 80's, home PC technology was strong enough to defeat many amateur players. I never beat
      • It's not about creating a champion. The point of teaching a computer to play go is all you learn about artificial intelligence in the process. It's a true challenge and one worth pursuing.

        ------RM

    • by asninn (1071320)
      That's not a fair competition, though - unless by "fair" you mean "meant to allow pretty much any half-decent human player to win against pretty much every computer".
  • by L. VeGas (580015) on Tuesday May 15, 2007 @07:49PM (#19139143) Homepage Journal
    We knew this was coming.

    However, there are still many games that computers are a long way away from beating skilled human opponents.

    Poker
    Go
    Rock Paper Scissors
    Mixed Martial Arts

  • A Great Documentary (Score:3, Informative)

    by Coryoth (254751) on Tuesday May 15, 2007 @07:50PM (#19139145) Homepage Journal
    A quick note for anyone interested in this sort of thing who hsn't already run across it: there is a great documentary on the Kasparov/Deep Blue contest called Game Over: Kasparov and the Machine [imdb.com]. Well worth checking out.
    • First off, let me say that he always struck me as a bit on the arrogant side, but then again, I really don't know the guy.

      I remember that match though. Time and time again, Kasparov would give IBM rematch after rematch after rematch until Deep Blue finally won. It seems that, as soon as they did, Deep Blue was re-assigned and that was the end of it (maybe someone will correct me, but that's my recollection). So, you never really knew if the win was just one of those "on any given day" phenomena. One win
  • Chess is a zero sum perfect information game. Even a sufficently powerful computer with non optimal programming will at worst now hold its own with the best humans. Time to look for a different game. I believe decently talented players can still beat the best computer Go programs because although similar to chess the game strategy is more complex. When the computer programs eventually starts winning at Go, and win they will, I suggest kick boxing as the next challenge.
    • by Anonymous Coward
      Your signature is either ironic or defensive considering you just reiterated someone else's post just two up from you.
      • Re: (Score:3, Funny)

        by Timesprout (579035)
        My computer posting program made that post after considering all available posts and outcomes of those posts and then determining the optimal post to elicit a response from a twat.
    • by Frans Faase (648933) on Tuesday May 15, 2007 @08:03PM (#19139279) Homepage
      Indeed Go is a much bigger challenge. At the moment the best Go playing programs are about 8 Kyu. Which means that they are just childplay for any professional player (in Japan, China, South Korea). Even at the club where I play, half of the players beat these kind of programs with ease.
      • Indeed Go is a much bigger challenge. At the moment the best Go playing programs are about 8 Kyu. Which means that they are just childplay for any professional player (in Japan, China, South Korea). Even at the club where I play, half of the players beat these kind of programs with ease.

        Indeed, the only way to make computers competitive at Go is to give them a lot of handicap stones.

        Note that programs are getting exponentially better, partly because of better hardware, but also because of improved algorithm

    • by aquila78 (851048)
      How about the game of Diplomacy as a challenge for game AI?
      • by Phisbut (761268)

        How about the game of Diplomacy as a challenge for game AI?

        Diplomacy is for wusses. Right now lets play Global Thermonuclear War.

      • by magores (208594)
        Always hated that game. I was always the most trusting player, and therefore the first to get screwed by my "friends".

        Risk and 1942 I always kicked their butts. So I guess it balances out.
    • Even a sufficently powerful computer with non optimal programming will at worst now hold its own with the best humans.

      This is the secret that the article, or the Deep Blue group, isn't so quick to point out. The human versus computer match didn't turn the tide when computing power grew, as chess is still sufficiently more complex for exhaustive branch searches on even todays best hardware.

      No, the tide turned when the programmers employeed chess masters to detail out their end game stratiges. Once the

      • You are correct, when I said non optimal programming I was really referring to non optimal strategy programming. I cant recall the exact numbers but I remember stonking figures being put forward for bleeding edge AMD desktop chips of the time to brute force the best move.
    • by owlnation (858981)

      I suggest kick boxing as the next challenge.
      Be careful what you wish for. While the average computer isn't that agile, it needs only one seriously hard kick to win. Human strength is limited to a certain range, the computer's isn't necessarily.

      A really sneaky computer will get you under the desk, when you're not expecting it.

      I, for one, do not want computers programmed to do that. Chess? Fine. Go? Sure. Poker? Why not. Martial arts? Not so much.
      • by laejoh (648921)

        Depends on the human. Replace Kasparov with Chuck Norris and this kick boxing thing might just work!

  • I mean, anything in the last 40 years as a result of writing chess programs and building chess playing hardware?

    Yeah.

    • Re: (Score:3, Informative)

      by Chris Burke (6130)
      About soft AI, sure. All kinds of great things about tree pruning and state evaluation and stuff like that.

      No hard AI stuff, but that's because in order to have a hard AI chess machine, you'd have to make the AI then teach it chess. Much more practical to go for the direct approach.
    • Yes. We learned that an AI solution is not necessarily the best way to deal with an AI problem. Deep Blue was an engineering solution, not an AI solution.

      You can see a similar thing in Google's automatic language translation. It's purely statistical--they look at a lot of bilingual texts (such as minutes of the UN), and develop a statistical model to come up with translations of new documents. There's no attempt to build any AI into this. It's just a statistics problem and a data structures problem to t

    • I mean, anything in the last 40 years as a result of writing chess programs and building chess playing hardware?

      Deep Blue is completely uninteresting so far as AI is concerned. It used ancient game-tree search technology with pruning, rules for evaluating board positions (since full-depth search is still impossible, and you have to cut off at some point), and lots of hardware.

      A few board games are still challenges for AI, but I'll wager that they'll eventually be solved in almost identical fashion, i.e. by throwing lots of money at a rather dull search algorithm.

      Methinks video games will replace board games as a dri

  • by Timesprout (579035) on Tuesday May 15, 2007 @08:19PM (#19139423)
    I think it was the BBC a few years ago recorded a game between him and Nigel Short and intercut it with interviews of what they were thinking about the state of the game as it evolved. Kasparov was massively impressive with the sheer speed and coherence of his though and to me as a non chess player his almost psychic understanding of what Short was thinking was just amazing. Short after thinking he was winning and then realising what had just happen when Kasparov creamed him in a trap was classic.
    • by daveewart (66895)
      In the late 70s and early 80s, the BBC had a (then groundbreaking) programme called "The Master Game", which did as you described: you 'heard the players thoughts as they played'. It was superb. (The actually played the games elsewhere, recorded their thoughts immediately after the game, and then replayed the game in the TV studio, in sync with their voice recordings of the moves).
  • Trounce! (Score:5, Informative)

    by Animats (122034) on Tuesday May 15, 2007 @08:52PM (#19139709) Homepage

    Computers are so good at chess now that it's embarrassing. Unless you've been on the cover of Chess Life, any of the good PC chess programs can trounce you. Fritz [chessbase.com] at €119.90, runs on single or multiprocessor PCs, is rated at FIDE 2808 or so, and wins against Kasparov about half the time. If you're not a rated player, the chess programs for cell phones can beat you.

    One of the experts in computer chess explained what's happened. Study of human grandmaster games indicates that about one move in ten is suboptimal, even at that level. That's enough to give computers that don't make mistakes a significant edge.

    Computers are now so far ahead that there's a serious problem with cheating using a computer in chess competition, Several cheaters were caught at the 2006 World Open. [chessbase.com] "Two players are under suspicion of having received help from computers at the World Open in Philadelphia. One locked himself in a bathroom stall, the other, who was leading the event before the last round and stood to win $18,000, was caught wearing a "hearing aid" which turned out to be a wireless receiver used for surreptitious communications. The New York Times reports."

    Chess players at major tournaments are now being searched.

    • by Lazerf4rt (969888)

      ...caught wearing a "hearing aid" which turned out to be a wireless receiver used for surreptitious communications.

      They did that way back in an episode of Cheers when Sam played a game against Robin Colcord. Norm was in the office calling out moves on the computer. And Rebecca caught him and thought he was just trying to erase his beer tab.

    • Re: (Score:2, Informative)

      by Frozen Void (831218)
      Fritz is relatively weak.Latest Rybka,ZapChessZ,And Hiarcs have top ratings spots.
      Here is fritz vs rybka stats
      Deep Fritz 10 4CPU(2925)
      Rybka 2.2 64-bit 4CPU(3105)
      5.5 24.5
      (+0-19=11).
    • by Dutch Gun (899105)
      I wonder how we'll deal with this (societally, I mean) when cell phone implants, and eventually cybernetic implants, are common? This has pretty huge implications for any sort of knowledge-based testing or competition, be it for school, job-certification, or chess championships.

    • There have been a couple of games I've been in where I'm winning and, entering the end game, my opponent is suddenly getting very tough. I guess I won't complain if it helps me sharpen my end game, but, with tools like SCID so easily available, I can't help but wonder if I'm actually playing Crafty for the last third of the game sometimes.

      This is only once in a while mind you. I think most correspondance players are like me, they'd rather loose on thier own then use an engine to chalk up a win they didn't
  • The amazing thing is that the computers only beat humans by looking at every single possibility. I think Deep Blue processed something like 200 million chess positions a second. But human grandmasters usually only consider 3 or 4 moves during their typical two-minutes of thinking. The AI guys still can't figure out how the grandmasters just "know" which 3 or 4 moves to consider.

    It's hard for me to get excited about a computer playing chess. It's like watching a computer randomly generate a trillion dif

    • Re: (Score:3, Informative)

      by Dun Malg (230075)

      The amazing thing is that the computers only beat humans by looking at every single possibility. I think Deep Blue processed something like 200 million chess positions a second. But human grandmasters usually only consider 3 or 4 moves during their typical two-minutes of thinking.

      It only seems like grandmasters are only considering 3 or 4 moves. What you're missing is the fact that they can, at a glance, take in the current state of the game and instantly dismiss several million avenues of consideration based on past analysis and current variations.

      • by Drall (1006725)

        It only seems like grandmasters are only considering 3 or 4 moves. What you're missing is the fact that they can, at a glance, take in the current state of the game and instantly dismiss several million avenues of consideration based on past analysis and current variations.
        Sure, but the way in which they arrive at the decision to dismiss those several million is substantially different from how the computer dismisses options, isn't it?
      • by Arguendo (931986)

        Obviously grandmasters are dismissing millions of other options. And then they actually are considering only 3 or 4 moves.

        The point is that humans can, in a half a second, do something that the fastest computers take several minutes and billions of discrete calculations to do. Now THAT's impressive. It's not so impressive that the computer can do a tree search faster and faster and faster. It's a sign of how difficult AI really is if the best we can do to emulate human thought is a super fast tree sear

  • Slow the computer down until it can process information at the maximum speed a human synapse can fire, and see who wins a timed chess match.
    • by Dun Malg (230075)

      Slow the computer down until it can process information at the maximum speed a human synapse can fire, and see who wins a timed chess match.
      Unfair handicap. Among other things, human brains work massively in parallel, so synapse firing speed is not a reasonable comparison.
      • Yes, some compensation is required for that aspect, but it's not as if all those synapses can fire in support of solving a problem. In any case, there's no doubt that computers can perform operations much faster than humans. If not, we wouldn't be using them. The difference is reasoning which humans can do and computers cannot (so far). Speed and storage are responsible for the computer's win since there's really no other reasonable explanation.
    • by fractoid (1076465)
      Ah, but if you're being 'fair' like that, you have to reduce the human to a LOT less neurons than the billions we have. I do like the mass/power limitations, though - submarines may or may not swim and all that, you know, but they can still be compared with fish in terms of efficiency. Maybe require all future chess champions to be able to run off tacos?
  • Perhaps there should be a competition where the computer entrants are limited in mass (ca. 1.5 Kg) and power (ca. 25 Watts) as are human brains. Maybe a temperature limit as well, i.e., operating at under 40 Celsius.
    • It makes sense, but what would be the point of that.
      • Re: (Score:2, Interesting)

        by SystemFault (876435)
        Among other things, it would force programmers to do more with less -- always a valid engineering goal. It's one thing to build a chessplayer that needs multiple racks and a three phase 220 V power supply, and a much more impressive thing for a chessplayer running on a hand powered OLPC laptop.
    • not a bad idea... while we're at it maybe it has to sit in a chair and move the pieces on the board itself using an arm resembling that of a human's. While that shouldn't be a very difficult task it would do much to take away from the the other more important calculations it will be running.
  • Weird! (Score:2, Interesting)

    by localman (111171)
    This morning I was reading a different Slashdot article and came across this comment [slashdot.org], which led me to Wikipedia and in turn:
    • Robert Heinlein
    • Alfred Korzybski
    • General Semantics
    • Aristotlian Logic
    • Martin Gardner
    • Mathematical Games
    • Soma Cube
    • Pentomino
    • Solved Games
    • Endgame Tablebase
    • Computer Chess
    • Kasprov and this famous matchup

    Then I come back here and find this article. I don't know what my point is but I just love the semi-random nature of brain feeding on the internet. For more information:

    Baader-Meinhof Phenomenon [damninteresting.com]

    An [xkcd.com]

    • From your link:

      The reason for this is our brains' prejudice towards patterns. Our brains are fantastic pattern recognition engines, a characteristic which is highly useful for learning, but it does cause the brain to lend excessive importance to unremarkable events. Considering how many words, names, and ideas a person is exposed to in any given day, it is unsurprising that we sometimes encounter the same information again within a short time. When that occasional intersection occurs, the brain promotes th

  • by HockeyPuck (141947) on Wednesday May 16, 2007 @12:52AM (#19141413)
    There was an article in Scientific American magazine circa 1992 that predicted that at some point a computer would have enough power to have every possible move stored up, and upon starting the game it would have immediately announed "Mate in X moves." As you continued to play, it would eliminate millions of games, while still counting down "Mate in X-1 moves.."

    Almost all chess programs now have an "opening library" of opening move strategies, so it's not that far to extend that library to 10-15-20-50-100 moves...

    • I'd venture a guess that chess is like Tic-Tac-Toe, in that optimal players would always draw. Since "mate in X" means there's no possible way to escape, I doubt the computer could show a count until you make your first mistake (probably in one or two moves).
    • Re: (Score:3, Insightful)

      by daveewart (66895)

      Almost all chess programs now have an "opening library" of opening move strategies, so it's not that far to extend that library to 10-15-20-50-100 moves...

      Actually it *is* a big deal to extend it: remember also that opening libraries are not necessarily *perfect* moves, they're just commonly-played and probably-OK moves. The opening book represents an incredibly small subset of all legal moves in the opening.

      If one assumes approximately 50 legal moves in any position during the opening (close enough f

    • Heh, I definitely hope to see the day when we have a chess "win or draw" algorithm. That is, you follow it, you win, unless the other player is also following it, in which case you draw.

      But as a side note ... computers could beat Kasparov in 1992 already. You just had to decrease the time allowed for moving to a fraction of a second. The computer would have no problem, while the human would have to play instantly.
    • Opening theory works both ways,so the best you can get is a draw.
      All clearly winning lines "winning"
      will either be refuted or avoided.
      • by AvitarX (172628)
        Chess isn't symetric, and it isn't simulteneous.

        It is possible that any opening for white has an optimal response from black that leads to defeat.

        Or that going first white can control the game and always win.

        Though if we use 5x5 go and Tic Tac Toe as our knowledge base you are correct, going first and playing the perfect game you can always tie at worse (playing second too, but a bad first move does not garentee player to a chance to win).
  • ...and eventually took up more useful causes.

    He's been last seen getting arrested for "protesting" the Putin regime (actually, he was picked up off the street just for suspicion that he was going to). Good for him. With his brains, he could probably beat Putin from inside a cell, and may have to. :^(

    --
    Toro
  • personally, as strictly a hobby programmer, i've found the challenge of writing a chess program a fun opportunity to poke around in some code. writing a chess program is a problem that's been solved a zillion times now, but it is still a fun challenge.
  • I created an account just to make this comment. Those who are interested can go back and look at the event itself; those who don't care needn't bother. The long and short of it is, Deep Blue was programmed (during that event) specifically to beat Kasparov. This itself is not so bad-- Grand Masters carefully study past games of future opponents as part of their preparation. But Kasparov was not given access to any of Deep's previous games. This is a significant handicap.

    Does this mean the current world's b

  • I say start making better AI for regular computer games.

    Have computers emulate how humans play.
  • But they fail miserably at first person shooters.

The world is moving so fast these days that the man who says it can't be done is generally interrupted by someone doing it. -- E. Hubbard

Working...