Slashdot Mirror

← Back to Stories (view on slashdot.org)

Kramnik Ties Fritz; Machines Not Yet Our Masters

Posted by michael on from the gnuchess-has-got-my-number-though dept.

Maltov writes "World Chess Champion V. Kramnik ties his match against the software Fritz. Details here. You can also check out a picture gallery and a short history of computer chess."

18 of 161 comments (clear)

  1. We can at best hope a tie.. by Tester · · Score: 4, Interesting

    If two chess players play perfectly, then the game will always result in a tie. That's one of the big problems with chess as a man-vs-machine benchmark... If both become too good, they will tie all the time.. We might have to move to another game that might be much harder from a computational point of view. (I've been told that the Japanese (or is it Chinese) game of Go is one such game)...

    1. Re:We can at best hope a tie.. by Kircle · · Score: 5, Interesting

      If two chess players play perfectly, then the game will always result in a tie

      Here's an interesting quote from MSNBC:

      Friedel pointed to two weaknesses in Kramnik's play characteristic of humans. "Once in 200 moves a human will make a blunder, and that's all Fritz needs. And [Kramnik] was seduced by beauty." He added that Kramnik "understands 100 times more about chess than any computer, but tactically Fritz is a monster."

      --

      -- Kircle

    2. Re:We can at best hope a tie.. by pVoid · · Score: 3, Interesting

      The combinatorics behind chess, ie the number of distinct games is so high it would make a 128 bit UUID blush... and UUIDs are unique in time and space...

      I wouldn't hold my breath for the "guaranteed tie" level of gameplay to come any time soon...

    3. Re:We can at best hope a tie.. by targo · · Score: 5, Interesting

      The problem with this is that defining "perfect play" is next to impossible in chess. Different players have very different playing styles, and if player A is strong against player B, and B is strong against C then it doesn't necessarily mean that A could defeat C.
      Computers are strong in tactical play, humans in positional; people have argued for ages, which is better, so far both styles have their proponents among grandmasters.
      And we can't really find an answer to this question unless we compute the entire game tree of chess, but this is impossible, even if you used all the atoms in the Universe to track the nodes in your tree.

      Btw, the concern that chess as a game will exhaust itself and in the future grandmasters will always tie, has been expressed many times in the past. So far they have all been proven wrong, usually when some prodigy (Tal, Fischer, Kasparov) has come forward and brought new innovations with him. Computer chess is in a similar position, bringing many new ideas to the chess world, and countless new chess theories have been created by analyzing how computers play.
      So I am quite optimistic about the future of chess, there is certainly no end in sight for now.

      --
      When men used to be men
    4. Re:We can at best hope a tie.. by Anonymous Coward · · Score: 1, Interesting

      If both become too good, they will tie all the time

      More realistically, "man" will stay more or less the same strength, and "machine" will continue improving. We'll see machines either winning or tieing, never losing. Actually if man doesn't improve at all we will start to see *less* drawn games as the ELO gap widens between man and machine.

    5. Re:We can at best hope a tie.. by Moridineas · · Score: 4, Interesting

      Very well said. To add a couple things:

      On the average chess has a branching factor of about 40 (or 35--reports vary). This means that on average for each players turn there are that many possible moves. So to build a game tree, that's how fast the tree will grow.

      Go on the other hand as you state, starts with an empty board, and so even if you're playing on a child sized board of 9x9 (standard sized boards are a good bit bigger than this, I forget the size, at least 13x13 i believe) you have 81 possible moves at first. And you do make a good point that this branching factor drops dramatically as the game advances.

      there's nothing inherent to Go that makes it a better game, "harder", or anything of the sort--no magic reason for why computer AI's suck. It's simply a ton less energy being put into Go (when was the last time you heard of a MASSIVE super computer being built for Go?) and the massive branching factor.

      My personal feeling is that within 20 years Go AI with be at a similiar level as we are at with chess today--just my own guess.

    6. Re:We can at best hope a tie.. by legLess · · Score: 5, Interesting
      Blockquothe the poster:
      In the begining two-thirds of a game of Go most of the stone placements are "random". Yes some players attempt to mark out a territory but that can be self-defeating,
      100% pure bullshit. Strong players make no random moves, period, especially in the opening. Professional games are sometimes decided by 1/2 stone (black moves first, and in an even game - i.e. no handicap - the territory advantage of this move - 5.5 points - is added to white's score at the end of the game; this also prevents ties); a botched or "random" opening move is suicide.
      In Go there are only a few "true" patterns to worry about.
      Incorrect. If this were even remotely true the game would be trivial.
      The Line (easy to deal with if you know the rules). The Box (a way to control an area).
      Lines of stones are tremendously strong, if inflexible. Boxes are a very inefficient way to surround territory, open to many attacks, and very limited in possibilities.
      And The Spiral, when a contested area "spirals" out of control. The Go game becomes a miniture Mandlebrodt set that can loop off into infinity,
      Is this a concept of your own invention? I've yet to encounter it myself.
      One method of playing Go is to work your opponent into a corner that he cannot leave
      Yeah, this is the time-honored "shooting yourself in the fucking forehead" technique. The corners are by far the easiest territory to surround and control, because you don't need to defend at the edges. If one player in a more-or-less evenly-contested go game captures all 4 corners his victory is assured.

      You need to learn more about the game, I think, before you try to explain it to others.
      --
      This isn't as much "normalization" as it is "don't take so many drugs when you're designing tables."
  2. Machines Not Yet Our Masters? by skydude_20 · · Score: 4, Interesting

    Is it just me, or did someone forget the current score: Machines (1-0-1), Humans (0-1-1).

    --
    Jesus saves souls and redeems them for valuable cash prizes
  3. Actually, he's right by etymxris · · Score: 1, Interesting
    It doesn't matter. Only one of two outcomes is possible:

    1. White can force a win or
    2. Black can force a draw

    If White can force a win, then, in a match of 8 games, each side will have four wins. If Black can force a draw, then in a match of 8 games there will be eight draws.

    But as other people have said, determining whether a draw or win can be forced is computationally infeasible. So the game will be interesting for a while.
    1. Re:Actually, he's right by etymxris · · Score: 2, Interesting
      Why do you assume that "Black can force a win" is not possible? I have not heard of anyone proving that chess with perfect play is not a loss for white.


      Perhaps I was being sloppy. I was thinking that since the board is roughly symmetrical, if either could win, it would be the one with the first move.

      In any case, it doesn't matter. As long as the outcome is always one of the following possibilities, any fair match of an even number of games will ultimately result in a draw:

      1. White can force win
      2. Black can force win
      3. Both sides can force a draw

      Even allowing for a strange state of affairs where Black can force a win, the above three possibilities absolutely limit any deterministic board game like chess, go, tic-tac-toe, etc. Either one of the sides can force a win, or both sides can force a draw. If e.g. Black can't force a draw, then either Black or White can force a win.

      If White can always force a win, then every match of eight games will end 4-4. If Black can force a win, it will also be the case that every match of 8 games will end 4-4. If either side can force a draw, then every match of 8 games will end in 8 draws.

      Realizing this is very simple if you just imagine that chess was as easy as tic-tac-toe. Adults don't play tic-tac-toe because they know a game played perfectly on both sides always results in a draw, and the perfect game is really easy to play.
  4. Was the match 'fair' this time? by Ryu2 · · Score: 5, Interesting

    One oft-quoted complaint by Kasaarov, of the last man-vs-machine match against Deep Blue, was that Deep Blue was programmed with the moves of all of Kasparov's past championship games so it could ostensibly analyze the strategies used by Kasparov beforehand, while Kasparov was not allowed to look at Deep Blue's previous games.

    Anyone know if this was ever an issue in this current tournament?

    --
    There's 10 types of people in this world, those who understand binary and those who don't.
  5. Hardware and OS it was running on? by Ryu2 · · Score: 3, Interesting

    Anyone know? Not trying to start a flame war here, rather, just curious.

    I know that Fritz is supposed to be much more intelligent in its search-tree pruning than Deep Blue was, and not require so much computational power.

    --
    There's 10 types of people in this world, those who understand binary and those who don't.
  6. Computers playing with humans by Anonymous Coward · · Score: 3, Interesting

    One kind of chess that has been experimented with a bit is where humans play each other, but each has the aid of a computer during the game. Shirov and Anand played a short match like this last year (or the year before), and it seems like an interesting concept. You have the normal human strenghts in judgement, strategy, and intuition coupled with a tool that can process millions of tactical possibilities.

    The average slashdotter seems pretty certain of the day when programs, these unbeatable machines, will be able to simply trounce the best humans in one on one competition. But what about a future match with the best chess computer against a top notch grandmaster with his own pc, even a weaker program? Do you people honestly think that human knowledge will simply be obviated by brute force processing power?

  7. Not correct by ucblockhead · · Score: 3, Interesting
    The number of possible moves in go has nothing to do with its difficulty.
    It has everything to do with difficulty. Nearly all game playing programs use some variation on the min-max algorithm, which creates a tree of possible moves for some number of moves ahead. More possibilities per move means a larger tree, means more computation per each move of lookahead.
    --
    The cake is a pie
  8. Westerner alert! by thefirelane · · Score: 5, Interesting

    Hello, sorry, but... Go has not been analyzed and picked apart enough for us to say that it us much more difficult than chess.

    Perhaps with the belief among computer chess researchers that chess has been solved will Go soon undergo the same nitpicking that chess has

    This game is much more popular than chess in China, Japan, and Korea. Somehow, you seem to assume that these regions are all completely deviod of any programming, AI, or mathematical talent.

    These people are obviously just sitting around waiting for us Westerners to solve chess so we can move onto their little problem.

    As for your 'points'... they cry of a lack of deep understanding of both Go, and AI
    1. Go pieces can be removed from the board, by capturing. Thus opening up more combinations

    2. Even if it weren't possible, and a stone was plunked down each time, you'd still have (19x19)! possible moves (a lot, as stated earlier)

    3. When chess pieces are removed from the board, it collapses the search tree. On a Go board, it expands it.

    4. There are 4 'cells' Remember, in a Ko battle, a space can be empty, but unplayable.

    5. The whole cells argument is pretty nonsensical anyway? You are basically discussing bit-depth... in which case, would a black and white face be easier for a computer to recognize than a grayscale, how about color?

    6. Facial recognition really has nothing to do with Go in a practical sense. Facial recognition is categorization based on large differences. In go, you have to select the best move based on extremely small differences in extremely similiar layouts.

    7. As far as the "million game database" This just will not work, as playing against a human, they'll just do a profitable, but nonsensical move. It is the same thing that happens when studying Joseki. People will know the Joseki, but without an understanding of the principles behind it, it will be useless to them as they will not be able to respond to non-standard moves (GNU Go has a Joseki database I believe).


    ---Lane

    1. Re:Westerner alert! by comic-not · · Score: 2, Interesting

      It is the factorial. See, the first stone has 19x19 = 361 possible places, the second has one less (because of the previous stone occupied that) so two moves has 361*360. Repeat this until the board is full and you get 361! possible plays (this assuming that no pieces are removed and no positions are unplayable). For calculating large factorials just remember that


      x! = exp(sum(i=1,x)ln(i))


      so the above number is about exp(1768.75) is about 1.438e768 which means that we need a quantum computer with 2552 qubits to represent all the possible states of Go. Now imagine a Beowulf cluster of those ...

      --
      Existence usually comes as a surprise (Idem)
  9. Chess vs. Magic.... by wowbagger · · Score: 3, Interesting

    Go and chess are both computations: In both games there are no unknowns but the strategy of the other player. You may not know that the other guy is going to castle, but you know that he CAN castle. Therefor, you can theoretically work out the optimal series of moves from any given state.

    Games like backgammon and poker have unknowns - you may know what is in your hand, but you don't know what is next up, nor do you know what the other player has. As a result, given the state you can see, you CANNOT compute a single optimal set of moves - all you can do is probablistically state "most of the time, this would be the best move".

    Add to that bluffing - in poker you can bluff the other guy into losing when he should have won.

    Now, consider card games like Magic: The Gathering . Not only do you not know what the other guy's next draw is, nor what he has in his hand, you cannot even for certain limit the set of what he can draw very much - "Does he have a Force Of Nature? He might, or he might not."

    In addtion, since each card can change the behavior of the other cards, the combinatorial growth of the game state is extremely large. You might be winning, then the other guy plays a card that completely changes how your cards act.

    Given the above, much of the game is decided before you even sit at the table - how you construct your deck may decide the game, even before you see your opponent. AND you might change your deck, based on what you observe of the opponent's strategy.

    Given the above, what I would like to see would be a computer program that could, given a set of N cards, compose a deck of M card (where M < N), play that deck against an opponent, then compose a new deck from the same N cards that answers the strategy of the opposing player.

    When we can do that, THEN I'll believe we have real A.I.

    --
    www.eFax.com are spammers
  10. Go and Chess programs: its the branching factor by MarkWatson · · Score: 5, Interesting
    Sorry if this is a little off topic, but I have written two fairly widely used Go and Chess programs (the free chess program that Apple distributed on their demo cassette tape the first year or so they sold the Apple II, and my ancient commercial Go program Honnibo Warrior).

    Anyway, the other posts concerning the search branching factor difference in the two games are right on.

    Typically, there are a few hundred possible legal moves in any Go position. It is simple to write an alpha-beta search that does well in chess because of the relatively small branching factor (the free Java AI web book on my site has an example).

    Really, Go is an ideal testbed for AI, but currently the best Go programs are good engineering projects, but not really good AI projects. I would consider a great Go project to include these features:

    • Have a library of all available historical games (lots! I have a book of ancient famous Go games - very cool!!!) and the ability to search for opening patterns, etc. - the ability for both self analysis and the analysis of other games)
    • ability to play off-line training games against all available Go programs
    • use genetic programming to evolve new operators for statically ranking moves based on pattern matching
    • tutoring mode where a human player could criticize the program's moves - these criticisms would become a permanent part of the data maintained by the program and be used for off line machine learning

    -Mark