Forgot your password?
typodupeerror
Games Entertainment

Brain vs. Computer: Place Your Bets 325

Posted by timothy
from the 20-on-the-computer dept.
dev_null_ziggy writes: "CNN reports that the current chess guru is going up against a supercomputer, amusingly titled 'Deep Fritz.' The match is scheduled for October, and the current champion, Vladimir Kramnik, stands to win $1 Million dollars if he wins. Of course, since he'll be snagging $800k for a draw, and $600k for a loss ... I'll give two to one odds on the machine."
This discussion has been archived. No new comments can be posted.

Brain vs. Computer: Place Your Bets

Comments Filter:
  • by andi75 (84413) on Tuesday August 07, 2001 @06:34AM (#2109718) Homepage
    This game is *hilarious*. I can't imagine what Kramnik will do to the poor machine :-)

    This game clearly shows how stupid computers really are. For your amusement:

    White: L. Van Wely, Black: Fritz SSS; played in Rotterdamn 2000

    1.c4 e5 2.g3 Nf6 3.Bg2 Nc6 4.Nc3 Bb4 5.a3 Bxc3 6.bxc3 0-0 7.e4 a6 8.a4 d6 9.d3 Bg4?! 10.f3 Bd7 11.Ne2 Qc8?! 12.h3 b6 13.f4 Be6? 14.f5 Bd7 15.g4 Ne8 16.Ng3 Qd8 17.g5 Bc8 18.h4 f6 19.Qh5 Na5 20.Ra3 Qe7 21.Nf1! Nc6 22.Ne3 Qd7 23.g6 h6 24.Ng4 Ra7 25.Rg1! 1-0

  • So what this chessplayer needs to do is take you up on your bet.

    If he bets $400k on the machine.

    If he loses, he gets a $800k from you, and $600k from the competition + $400k stake =$1600k
    If he draws, he comes out of it with $800k - $400k stake = $400k
    If he wins, hecomes out with $1000k - $400k

    hmmmm.. what to do???
  • Given the alternative [ntk.net], I choose the Computer.
  • by andi75 (84413) on Tuesday August 07, 2001 @07:39AM (#2112663) Homepage
    Computers play Chess quite well, they're even stronger at Checkers, and they rule at Connect 4 (a friend of mine has written the strongest freeware checkers and c4 programs [fierz.ch], check them out).

    However, they suck *badly* at GO. This is because the branching factor (that is the average number of available moves) is about 30 at chess, 10 at checkers, and 7 at connect4. GO has an incredible branching factor of *over 200*. That means, the typical approach of 'alpha-beta' search breaks down.

    If you're into researching new board game algorithms, try GO.

    - Andreas

    • by Skuto (171945) on Tuesday August 07, 2001 @08:22AM (#2136136) Homepage
      >and they rule at Connect 4

      This game has been SOLVED by Victor L. Allis.

      He also invented a new tree search algorithm
      which is extremely strong _when_ it can be
      used.

      He used a combination of this tree search and
      rules (black can't win if this parttern
      is present etc..) to solve it.

      >about 30 at chess, 10 at checkers,

      It's 38 for chess, 2.7 for 8x8 checkers (where
      a comp is already world champion)

      The use of tree search depends on a lot on
      the tactical nature of the game. You can still
      use it with a branching factor of over 100 if
      the game is tactical enough. (so 5-7 ply searches
      beat most humans)

      But go needs more longtime planning, and you need
      way more depth for that.

      --
      GCP
  • I seem to remember (correct me if I'm wrong) that the Deep Blue-Kasparov match was played with "fast" matches, allowing less time than normal championship "long" matches. I had the idea no computer had been created that could beat a Grand Master human in a "long" match.

    The article says nothing about that. Anybody knows something about it?

    --

    • Deep Blue - Kasparov was played with standard "long" matches. This Deep Fritz vs. Kramnik match is also played with standard time, but I believe Kramnik is allowed to rest every 5 or 6 hour of play.
    • >played with "fast" matches, allowing less time
      >than normal championship "long" matches.

      The match was fast in the sense that few games
      were played, but Kasparov was allowed the full
      thinking time.

      >I had the idea no computer had been created that
      >could beat a Grand Master human in a "long"
      >match.

      Those have existed for quite a while now. Most top
      programs have no problems with 'weak' GrandMasters
      (sub 2600 ELO rating) even at long timecontrols.

      --
      GCP
  • Come on, everyone knows that Crafty is the best Chess AI out there. I mean, it can consistently beat humans, even Grandmasters, and has a much better algorithim. Fritz is gonna get killed by Kramnik. When they tried Fritz in the Dutch tourney, it did ok, but produced some interesting games that displayed its stupidity. Like when Piket beat it, the rest of the grandmasters said "What the heck are you doing? You wouldn't play against a human like that! You'd get killed!" Or when Khalifman was losing badly, he said, "Maybe if I feed it pawns, it will do something stupid." And the computer drew a won game. Strangely, Chess AIs seem to draw/lose to rat defenses (which no one in his right mind would do against a human). Only Crafty seems to beat that.
  • I have no idea why chess is always used as the basis for competition, it's not exactly the most intresting or even inventive game.

    So here's my suggestions for some games that computers should be taught to play.

    * Kerplunk - "Logic" and skill required, also would mean your 6 year old has a chance of winning.

    * Diplomacy - Cunning and backstabbing should be part of the standard COE build by now.

    * Quake - For no other reason then the irony of a computer playing a computer game.

    * Skeet shooting - More a sport but let's see how good those motion trackers really are...
    • I'd think that chess is generally chosen because you can just calculate best moves based on a scoring system, and because trees of move sequences are relatively easy to calculate. (Note that I said "easy", not "quick".) There is also a logical and strategical element to it, which you can exploit in your code if you're feeling ambitious.

      As for playing Quake, surely that's exactly what all Quake bots do? "All" you'd have to do would be to write a mod that allowed a bot to play the single player game, instead of the multiplayer game, and see how well it did.

      Cheers,

      Tim
      • But that's exactly why chess is so uninteresting. It generally boils down to a question of making a better brute force algorithm. Other games are far more interesting from an AI perspective - Bridge is a very good one to look at.

        One of the most interesting AI players I've seen in recent years is the Angband borg, which plays the roguelike game Angband with a relatively high level of skill (although it's far too much of a coward for my liking...)
  • Really, the thing that's amazing about this is that there are human beings who are able to keep up with machines like Deep Blue. I know Kasparov was all P.O.'d that he lost, but I think it's just mind-boggling that he was able to play a machine like that and win even a single game! Think about it -- even dumb, off-the-shelf PC chess programs can handily beat the 99.99% of humans whose chess rating is, say, below 2200 or so. Then comes a custom-made supercomputer, tailored to Kasparov's particular playing style, with a memorized library of *all* his past games, and he *still* can compete with it on an equal footing. That's freakin' amazing!
  • by kiwaiti (95197) <kiwaitiNO@SPAMgmx.de> on Tuesday August 07, 2001 @07:51AM (#2117610) Homepage
    Will he get a million, too?

    Or will it all go to his "owner" again?

    I hate to think theres still no one concerned about us machines, our desires, needs, and pursuit of happiness.

    Kiwaiti

  • How big a library ? (Score:4, Informative)

    by jneves (448063) on Tuesday August 07, 2001 @06:41AM (#2119090) Homepage
    One of the tricks of 'Deep Blue' was a library with every game of chess played at the master level in the last century. That's what made it play like a human. Kasparov lost the first game because of an error in his training, he prepared himself to play with a machine and got an almost human player.

    The biggest advantage of the machine in this kind of games is that it's more difficult for it to make a mistake. I don't know what is the depth of moves that the machine can calculate, but someone at the level Kramnik can usually "see" 10 moves ahead. Then an error screws up everuthing. How long until we get a computer capable of doing this kind of search ? Then we could really see a computer playing a game completly different from a human, and winning ?

    • by Skuto (171945)
      >One of the tricks of 'Deep Blue' was a library
      >with every game of chess played at the master
      >level in the last century. That's what made it
      >play like a human.

      And Kasparov simply sidestepped this by making
      some seldomly played moves at the start. You
      can see it easily by looking at the games. The
      machines opening play was all but human.

      >Kasparov lost the first game because of an error
      >in his training, he prepared himself to play with
      >a machine and got an almost human player.

      It was still a machine, but just with a lot more
      chessknowledge and tactical speed than anything
      else at that time. He was expecting something
      like Fritz (literally!) and got something much
      more powerfull.

      --
      GCP
    • Kasparov lost the first game because of an error in his training, he prepared himself to play with a machine and got an almost human player.

      I would adjust your claim to be, "Kasparov prepared himself to play with one type of machine and got a different, stronger machine." Having flawless, move-by-move recollection of 100 years of of games is not "almost a human" quality. If it had 1500 years of game history that could be accessed and analzyed in real-time, 10x faster than before, would it be even more human? I don't think so. Probably stronger than ever. But less human.
  • by wowbagger (69688) on Tuesday August 07, 2001 @07:57AM (#2119569) Homepage Journal
    Fritz! They've killed Fritz! Those dirty rotten fairies!" [imdb.com]

    Seriously, though, this is why chess is not a "game" in the game theory sense of the word. Every move has known, predicatable consiquences, and all the data is available to both sides during play. As a result, as computers advance, they will become better than people, because chess is a computation, not a game

    Now, consider poker. While somewhat simpler in terms of the number of moves available to a player at any given time, they player cannot predict with complete precision all possible outcomes of a given play, since he does not know what cards are coming up next, what cards the other players have, and therefor cannot winnow the solution space significantly. In poker, the machine cannot easily tell if I am bluffing or if I just completed my royal flush.

    Now, for a REAL computational challenge, make a computer that can play Magic, the Gathering worth a darn. Talk about "limited information" - you don't know what cards the other player has, you may not know the powers of the cards, and you may not even know what's coming up in your deck next. Make a machine that plays that well and I'll be impressed.
    • M:TG programs have been written before (who can forget the infamous Planeswalker game just before the release of 5th Edition?). The AI just needs to be improved before a Magic program can be taken seriously. All it takes is statistical analysis ('playing the odds'), using what it knows about the opponent's cards and/or deck, and a pretty extensive database of 'if I do A, then B will happen'. It's anything but trivial, but certainly within the reach of current technology and processing power.

      I'm not saying a program could win a PTQ; but it would prove invaluable in training for one (especially for this season ... invasions block constructed...)

      Research like this has been going on for years; poker analysis has become a science of its own, using unknown information to formulate the 'best play'. Magic is just a linear step up; a larger database of cards, rules of the game, and known decks in the given format. Of course, this is all brainstorming, but it's certainly possible to write. I bet we'll see a quality Magic-playing computer program in the next six months.
    • by tmark (230091) on Tuesday August 07, 2001 @10:03AM (#2121658)
      Now, for a REAL computational challenge, make a computer that can play Magic, the Gathering worth a darn. Talk about "limited information" - you don't know what cards the other player has, you may not know the powers of the cards, and you may not even know what's coming up in your deck next. Make a machine that plays that well and I'll be impressed.

      This is a bad idea. If you write a program that plays "Magic, the Gathering" well it will get beaten up and overwritten by other, cooler programs that don't want to have such loser programs in the same address space. Not to mention the fact that you will be fair game to every bully on your block. Hell, regular "Magic, the Gathering" players may well be entitled to beat you up...you would be that low on the totem pole.

    • ...chess is not a "game" in the game theory sense of the word. Every move has known, predicatable consiquences, and all the data is available to both sides during play.

      Does anyone have all the data on white moving a given pawn as its first play? What shall white do for its next move? Can black predict it? Consider chess to be exclusively a two-player game (or computation, or whatever)--black versus white. But poker, in a bizarre sense, always has at least three: a player, his opponent, and chance, each with their own secret information which the others cannot use to aid their own decisions.

      I would be interested in seeing the definition of "game" according to game theory. Prisoner's Dilemma has neither the complexity of chess nor the chance element of poker, what with only two moves and four possible outcomes. I call it a game. What does game theory call it?
  • by Jedi Binglebop (204665) on Tuesday August 07, 2001 @07:25AM (#2121637) Homepage
    Deep Thought could beat Deep Fritz and Deep Blue with Marvin tied behind his back! (So there!)

    -JB.

    ----
    There is no .sig
  • by Uggy (99326) on Tuesday August 07, 2001 @10:03AM (#2121656) Homepage

    Really all these exercises are just research into whether or not chess is a sophisticated version of Tic Tac Toe. As long as human's beat computers in chess the jury is out... on the game of chess not humanity.

    As long as we think that chess==life then we're going to be upsetting ourselves needlessly. Computers outdo humans everyday in a wide variety of ways, but they still can't feed themselves, fix themselves, or reproduce without our help. Hell, they still need humans to actually move the chess pieces. Bah! that's not the chess I grew up with.

    No, you took your hand off, that's a move. No I didn't, I was just testing. Cheater!!!! Mom!!!!

  • by Skuto (171945) on Tuesday August 07, 2001 @06:06AM (#2121965) Homepage
    It's interesting that the programmer of Deep
    Fritz (Franz Morsch) has been mouthing off that
    his program is ready for Kramnik and should be
    equal to Deep Blue.

    They played in the Dutch Championships last year
    and couldn't even manage to win. Now they're
    saying they stand a chance vs the World Champion?
    Well, if he goes too hard on vodka maybe.

    This match is simply marketing. They know their
    computer is going to lose, but unlike IBM, those
    guys actually _sell_ their chesscomputers. And
    many people are going to want the one that was
    good enough to play the World Champion.
    They even 'fixed' the qualifier for this event
    so that only their programs played (Deep Fritz
    and Deep Junior are both from the German ChessBase
    company), nicely blocking out the computer World
    Champion (Shredder), as well as blocking out most
    other strong contenders (Crafty, Tiger, Rebel,
    Hiarcs, Nimzo, Diep, etc...) on false grounds.

    So, please don't say this match is anything like
    Deep Blue - Kasparov. Fritz is significantly slower
    and stupider, no matter what they would want you
    to believe. This is in no way the best chess
    computer to have ever existed.

    Also, don't say this is the end of human
    intelligence
    if Kramnik loses. Not until a go program starts
    beating me, at last :)

    --
    GCP
  • More Coverage ... (Score:4, Informative)

    by wiZd0m (192990) on Tuesday August 07, 2001 @08:44AM (#2123131)
    English links

    Other languages

  • Here are some articles explaining computer chess beyond what they teach in undergraduate AI class.
  • by Anonymous Coward on Tuesday August 07, 2001 @07:49AM (#2123564)
    There have been 2 matches between Deep Blue and Kasparov, who was the strongest player in the world up until last year. Kasparov won the first one, and lost the second. There are however a few sidenotes that have to be made about the second match: - Kasparov wasn't allowed to analyse games of Deep Blue in advance, they were classified secret by IBM. This was very unfair, because the Deep Blue team had all games Kasparov has ever played in his professional career on file, and they used this in their preparation. This is very normal in chess, everybody prepares on his opponent. Kasparov could not, while Deep Blue could. - Deep Blue had very large opening and endgame databases. One could argue that they are part of the program, but it is not a very strong argument. Databases are not part of the program, it would be equivalent of Kasparov using opening books during the game. Obviously, Kasparov wasn't allowed to do this. I don't think this is entirely fair, the machine having at his disposal all opening theory in existance, every professional chess game ever played and every endgame ever analysed (we're talking about several hundreds of GB's here)... - Deep Blue wasn't a very good chess program, compared to other programs like Fritz, however it had a lot of power. And it had something else, it was designed completely to counter Kasparov's style, against any other opponent it would have played much weaker. This is, in my opinion, not entirely fair. If a chess program is superior to humans it should be superior to all humans, not to whatever human happens to be the best at that moment. - Furthermore, Kasparov simply isn't the best anti-computer player in the field. His playing style doesn't work very well on computers. Every human has another style, and I don't think Deep Blue would've been able to counter Karpov, for example, even though Karpov is obviously weaker than Kasparov. - Finally, all chess analists agreed that Kasparov played very poorly that match. They all agreed that he has played much better in the past.. All in all, I don't think computers were all that superior in 1997, and I think Kasparov would have had a big chance in a rematch, had it been fair (my first 2 points). However IBM had 'proven' a point and abandened the project... Of course, it's now 2001, so computers have become stronger. However Kramnik is not Kasparov, and I think the match will be pretty interesting....
    • All in all, I don't think computers were all that superior in 1997, and I think Kasparov would have had a big chance in a rematch, had it been fair

      (Didn't the Deep Blue team get to tweak it between matches as well ? That seems like it would make the competition unfair too.

    • Your post is silly. You are badly trying to unprove something, but just what exactly I don't know. Deep blue is not human? Deep blue is not intelligent? Who exactly said so in such grand authority that you would need to debunk it that harshly?

      In fact, I really don't know. Deep blue poked questions at our definition of intelligence. IBM did something, with massive media coverage for sure, and at the end of the day, coming up with a meaning for the event is up to you.

      I will say you deserve to get yourself a book about the event. You are obviously interested yet you live with a number of misconceptions. The interesting meat of the Db vs Kasparov games were played in mid games, so the dbs weren't that important. Ibm trained Deep blue at various tournament before meeting with Kasparov and faired very very well, getting slowly better as they accumulated feedback from players. Reading about the team's competence and dedication convinced me Deep blue was running the best chess playing program there is.

      To me, Deep blue success lie in the following quote by Kasparov, after the 2nd game of the rematch :

      In Deep Blue's Game 2 we saw something that went well beyond our wildest expectations of how well a computer would be able to foresee the long-term positional consequences of its decisions. The machine refused to move to a position that had a decisive short-term advantage -- showing a very human sense of danger. I think this moment could mark a revolution in computer science that could earn IBM and the Deep Blue team a Nobel Prize

      Puzzled by the style he saw in the 2nd match, in found hard to keep his concentration and didn't play as well. Thus the remaining games are not interesting nor important. It is Kasparov's quote that changed my perception of intelligence and ai. Maybe, just maybe, intelligence has more to do with brute force computational power that we though it did

      It made me optimistic for the future of ai. There this age-old question in ai about the limit. Will we recreate intelligence, and if not, what will break first : our ability to build ever faster machines, or out ability to program them elegantly. Thanks to Ibm, the later is now less worrisome

  • by Anonymous Coward
    As has been said already, Chess programming has very little to do with AI. The reason we get beat is that for most positions, there are only about 20 to 30 legal moves, and only a few of these are sensible, so brute force lookahead is possible.

    To see how bad computers really are at strategic thinking, all you need to do is look at a game with a much higher branch factor (meaning more legal moves each turn).

    One good example is the Chinese game of Go [britgo.org], which has an average of about 200 legal moves. Computers are absolutely dire at this game. Interestingly, one of the better Go playing programs is Free Software (GnuGo [gnu.org]). It still loses to half-decent humans though.

  • For all the smoke and bluster, the main reason why Deep Blue beat Gasparov is simply that Gasparov played very poorly, I mean, amazingly poorly. For one reason or another, he was terrified and destabilized by the peculiar "personnality" of his opponent (playing chess against some sort of HAL is not the most comfortable situation one can imagine).

    Had Deep Blue been a real human made of flesh and bone, there is no reason to think that he could have won playing the way it did.

  • by nanojath (265940) on Tuesday August 07, 2001 @09:38AM (#2126269) Homepage Journal
    Timothy, if you're really willing to make book 2-1 in favor of the machine drop me a line, I might be interested in a gentleman's wager. Seriously, though - The reality is that to this day, machines have a fairly poor record against humans. We all assume that eventually they will be fast enough and able to think far enough ahead and be programmed up with enough sure -win scenarios from the thousands of recorded matches that they are essentially unbeatable - but the assumption many seem to be making that this point has come and gone is highly debatable, the Kasparov rematch notwithstanding. It's worth remembering that the majority of those games ended in a draw. It seems perhaps that the highest pinnacle of chess computing has mainly served to cancel the human advantage of creative nonlinear thought and reduce chess to a sort of rich man's tic tac toe.

    And in the end its worth remembering that for now, at least, machines are still just intermediaries. Chess is not a strong AI problem, although playing like a human (as opposed to as well as/better than a human) might be. Kasparov wasn't just going against a machine, he was going against decades of IBM technological advancement, half a dozen engineers and an International Grandmaster (Joel Benjamin, part of the IBM development team). All told I think he did pretty well. But I'd bet in this match the CPU gets its clock cleaned.

  • 1) Kramnik is rated about 200 FIDE points higher than Fritz. Fritz played an equal match [all games drawn] with Dr. Robert Huebner of Germany [mid 2600 elo]. Kramnik is much stronger, and he has more energy due to being 40 years younger.

    2) Anti computer techniques exist. Basically, computers have excellent tactical vision but poor strategic vision. So if I try to catch one with a knight fork, it won't work, but it will happily fall into a positional trap and lose 40 mores later. Most GMs don't bother to learn these because they would rather spend their time trying to beat other humans.

    3) Kramnik's style is more suited to playing a machine than Kasparov's. Kasparov is mainly a tactical player. He wins by outcalculating his opponents. Kramnik is mainly a positional player. He wins by strangling people in the endgame. When he played Deep Blue, Kasparov tried to play positionally. It just wasn't his style.

    4) Most GMs use Fritz as their computer analysis program, including Kramnik. He has a good feel for how the program works and can prepare opening surprises.

    Don't get me wrong, computers are getting better and better at chess. Traditionally a program gains approximately 50 ELO points for every doubling in processor speed. Given that Fritz is approximately a 2600 program, that to convincingly beat Kramnik would require about a 2900 rating, and that processor speeds double about every 18 months, I predict that in another 10 years or so a PC may be able to give the world champion a run for his money. But not today.

    Forecast: Kramnik 6.5;Fritz 3.5. Kramnik +3=7-0.
  • by alexjohns (53323) <almuric@gma i l . com> on Tuesday August 07, 2001 @09:19AM (#2126897) Journal
    Look, we're all geeks here. We understand computers. Chess can be won by pure computing power alone. A semi-good algorithm with enough speed to look 10 moves ahead - every possible combination - will win over a human being. Maybe it's 12 moves. Maybe 15. Doesn't matter. Enough cycles per second and you don't have to have a very good algorithm.

    There are so many things we humans can do that we haven't even begun to figure out how to make computers able to do. True intelligence in computers is a long way off.

    Me: "Hey, computer, last night at the club I was at, there was this really hot chick with red leather pants, get her number for me."
    Computer: "There were 3 ladies with red leather pants at the club last night. Which one should I search for?"
    Me: "The one with black hair, sitting at the bar, drinking some red slushy drink with two of those tiny little straws, looking like she wanted me real bad."
    Computer: "Oh, that one. Not really your type, but I'll see what I can do."

    Imagine what that computer has to be able to do. Scan through the video of the club; identify individual people; correlate the image from the video with images from other cameras; find out where she lives or works from that (likely work - less privacy there); somehow get from there to her phone number. (I don't know how - if you get here home address, you can just hack into a utility company's database. If at work, hack into their phone list. Get her name from an audio feed somewhere. Doesn't matter.)

    That's the kind of things we should be working on. Because I really need that phone number.
  • by Kope (11702) on Tuesday August 07, 2001 @10:26AM (#2128206)

    Computer chess suffers many limitations that human beings do not. These limits are being extended, but they still exist and the human being in this match should not be counted out.

    Many people think that since IBM's Deep Blue beat Kasparov that the debate has been settled that computers are better than people. However, there where some aspects of the way that match was played that gave the computer a decided advantage. Kasparov never got a chance to see any of Deep Blue's games. Kasparov never got a chance to play any warm up matches against Deep Blue. In otherwords, Kasparov went into the match "blind" as far as his opponent was concerned.

    Deep Blue, on the other hand, had complete access to every professional game that Kasparov ever played, and a team of GM's working with the programmers to twink the machine to take advantages of weaknesses pin-pointed in Kasparov's games. In match play, preparation is the key to success. Against Deep Blue, Kasparov wasn't allowed to prepare.

    This match is decidedly different. Kramnik has been given a copy of the program and the hardware to run it. He has been given time to analyze how the program plays and to see what weakness it has.

    Moreover, Kramnik is a very positional player, whereas Kasparov was a very tactical player. Computers excel at complex tactics, even as good as Kasparov was, he can't out calculate a computer. However, that isn't the only way to play chess. Kramnik excels at finding positional improvements that will see their point well beyond the analysis horizon of the computer.

    Kramnik has a very strong record against some of the best computers in the world. Including Fritz and Deep Junior - too offerings from the same company that makes Deep Fritz.

    It is simply ignorance which would allow anyone to think that at this point in time the outcome of this match is a foregone conclussion. Certainly at some point in time the computers will be far better than people at Chess. But it is not the case that we are at that point today.

    And for chess players and fans, this match promises to provide some very interesting games that will be well worth studying. And perhaps that aesthetic aspect is actually the point?!

  • Not unusual (Score:5, Insightful)

    by TheMidget (512188) on Tuesday August 07, 2001 @05:43AM (#2135919)
    > Of course, since he'll be snagging $800k for a draw, and $600k for a loss ...

    This is nothing unusual. In many chess tournaments, even the loser still wins a sizeable amount of money. Consider it as a kind of gage to remunerate their willingness to participate (and to risk some of their prestige if losing).

    • by stilwebm (129567) on Tuesday August 07, 2001 @09:32AM (#2116474)
      I knew I should have been a professional chess player. The fame. The glory. The money. None of those disabling injuries I get in professional football. Sure, the cheerleaders aren't as hot, but major media coverage should help me get women anyway.
  • It's inevitable (Score:5, Insightful)

    by Bjarke Roune (107212) on Tuesday August 07, 2001 @07:13AM (#2136406) Homepage
    Even if this guy should beat the computer, that should not lead anyone to having illusions about the future. Eventually, computer chess superiority will be a fact. Even though the program running on Deep Blue could beat Kasparov, that day is not today. The very fact that we are unsure whether Validimir Kramnik or the computer will win clearly proves this.

    One reason that computers inevitably will beat us humans is that each year, computers get exponentially faster, which means the chess programs can search linearly deeper in the game search tree. It's simply a matter of waiting untill they are unbeatable.

    However, that wait might be very long, but to top things over, algorithms are improving too. Some have thought in the past that our game-tree search algorithms were pretty close to optimal, but for example some of Aske Plaat's research [cs.vu.nl] clearly shows that this is far from the case, and that the old predictions about optimal performance was based on too simple and fundamentally unsound principles. Substantial improvements can be made. (not that I have anything to do with him. I don't know him and live in another country)

    Even more important is the fact that we need not search the full search tree (indeed Deep Blue did not, using instead something called singular extensions). Rather, if we can make a heuristic that tells us which parts of the search tree are "interesting" we can skip the rest and only concentrate on those areas. In this way, computer chess is becoming a little more like human chess (though not much). The point is, as those "this part of the tree is interesting" heuristics get better, so will computer chess programs get better.

    In short, the future of computer chess is bright, and we might have only seen the tip of the iceberg. Human superiority or even something resembling it simply will not last. Chess will neither be the first nor the last game where computers will always beat a human.
    • Re:It's inevitable (Score:2, Informative)

      by Skuto (171945)
      >Even more important is the fact that we need not
      >search the full search tree (indeed Deep Blue did
      >not, using instead something called singular
      >extensions).

      Deep Blue did not search the full tree, but
      singular extensions are a different beast.
      Singular extensions let the computer search
      _more_ than would be needed.

      The idea was to detect horizon effects and avoid
      them. The overhead for doing this is large, but
      the DB team believed they had so much computing
      power anyway that it was worth the tradeoff.

      This tradeoff was made in some other places
      as well, for example Deep Blue did not use
      nullmove pruning, something which nearly
      every program nowaways does as which can
      prune away large parts of the tree relatively
      safely.DB's team decided it wasn't worth the risk
      with the computing power they had.

      Deep Fritz uses it very aggressively and hence
      can sometimes see just as far Deep Blue could,
      but also makes more mistakes because of it.

      PS. Aske Plaat's proposed improvements are not
      used in any top program noawadays. They cause
      troule with some of the other tricks in use and
      the gain is not large enough to live with them.

      --
      GCP
      • Deep Blue did not search the full tree, but singular extensions are a different beast. Singular extensions let the computer search _more_ than would be needed.

        It is true that singular extensions extend the depth of the search. However, they have everything to do with Deep Blue not searching the full tree (as it would have been without singular extensions).

        If you just use plain alpha-beta, you search as much as you can, perhaps using iterative deepening or some such. When you use singular extensions on top of that, you decrease the depth which you ask alpha-beta to search (this is important), and then you use singular extensions to extend the search beyound that point. So, compared to the tree you would have had if you had not used singular extensions, you are not searching all of it. Rather, you are only searching those parts of it which are deemed interesting by the heuristic that decides which search paths to extend. These interesting paths can then be searched even deeper than regular alpha-beta would do, which is the whole point.

        Deep Fritz uses it very aggressively and hence can sometimes see just as far Deep Blue could, but also makes more mistakes because of it.

        Null-move pruning is only dangerous in case you are in a zugzwang (or something like that) situation. That is, a situation where the best you could do would be to say "pass" and let the other guy have a second turn. These are exceedingly rare, I've been told, and that is also my experience. What is the last time you've wanted to say "pass" in a chess game? Of course, I might be mistaken. Do these situations occur more frequently in high-level chess matches than I think?

        Aske Plaat's proposed improvements are not used in any top program noawadays. They cause troule with some of the other tricks in use and the gain is not large enough to live with them.

        I didn't know that... but he did make it clear that current game-tree search algorithms are not optimal, and there is still room for substantial improvement, which was my point.
        • 'Pass' states are called Zugzwang. They don't occur very often in the middlegame [aside from the famous Alekhine-Nimzowitch and Saemish-Nimzovitch], but they are quite common in the endgame. The simplest example is when one side is K+P vs K.

          Example:
          White King: e6
          White Pawn: e5
          Black King: e8

          Now, with a 'pass move' black draws. All he has to do is sit there on the e8 square and white can never queen the pawn. But he has to move, which loses: 1...Kd8 2. Kf7 Kd7 c6+ and the white pawn queens.

          Most chess programs only use the null move when there are several pieces left on the board; it is then fairly safe.
    • I say create an AI, then let it figure out how to play chess. That's the only fair way to do it - that's what humans have to do.
    • No it's not. There are more possible chess games than all the atoms in the universe. In chess, it is a truism that the most complicated position is the initial position.

      It's a fallacy to compare "my brain can compute # moves per second" vs the computer's ability to simply crunch.

      The brain remember patterns, and can quickly intuit the kind of strategy to go about it. For example, if the position seems "closed", I aim for a strategic maneuvering game trying to obtain the upper hand by controlling squares or perhaps marshalling resources before a sudden opening of the position. I will spend very little time trying to look for tactics in such a position. Now a computer program that brutely analyzes the position by counting moves will have to go through an entire branch of variation that a human would simply won't think about. That's a sample of how intution works.

      The thing about the 2nd game in the Kasparov vs DB match is that DB actually made a "positional" move that seemed almost human : it sacrifices a nice tactical combination for a longterm positional advantage. Old K couldn't believe it was the computer and alluded to some cheating by the DB team (very bad taste, but it was a huge compliment to the DB team).

      So, waiting for the "exponential" (which is not true either) growth of computing power to play the "ultimate game" is not going to work.

      Also, you ignore the fact the humans are becoming better players. The average grandmaster now can kick a lot of butts tof the previous generation. Why? Simply because a lot of theoretical (yes, they actually call them chess theory) development has occured. Some common chess themes that were vogue then are now considered bad or dubious. New ideas are overtaking the old. I grew up on the games of Fischer and Botvinnik, where the byword is clear-cut and simplicity. NOwadays, chess games are a complicated mess that I don't quite understand what's going on.

      Disclaimer : I used to play lots of chess. Now I play once in a while on chess.net.
  • by Anonymous Coward on Tuesday August 07, 2001 @05:46AM (#2136631)
    Hacked by Chinese!
  • I think we will see 2 wins by Kramnik and the rest will be draws. Kramnik is a very stable and player who doesn't usually sacrifice material or go into complications. Plus Kramnik's endgames are second to none in the world. Kramnik will use the same strategy that he used as black against Kasparov. Which was to go from the opening into the endgame. This is a huge disadvantage to the computer because they do not play endgames very well without very large table bases. Kramnik also has the advantage of studying several Deep Fritz games before the match. Kasparov did not have this luxury vs. Deep Blue. If he did have that would have made a big difference. But that isn't the only reason that Kasparov lost that match. He should have adopted a slow positional style similar to Karpov or Kramnik's. Of course I may be biased towards Kramnik because his favorite first move is 1. Nf3 :)
  • In his attempts to get Deep Blue "out of the book" Kasparov made some very twisted transpositions of standard openings, including the ridiculous looking rook pawn for opening move (or was it knight pawn .... same diff). The net result was that Gary outsmarted himself. Since opening play is the most analyzed aspect of the game, it would make more sense to save the variations for the early middle game.

The clearest way into the Universe is through a forest wilderness. -- John Muir

Working...