Kramnik Defeated

Vladimir Kramnik lost the sixth game of his match against the computer prgoram Deep Fritz today. He thereby lost the match by a score of 4-2.

The finla game saw the super sharp Najdorf Variation of the Sicilian Defense. This was in stark contrast to the careful positional play of the earlier games. The computer managed to prove, once again, it’s general superiority in tactical positions. The machine played the opening in somewhat bizarre fashion, and did not appear to have much advantage out of the opening. But it was able to keep up the pressure, and seized on a few sloppy moves by Kramnik to bring about a winning endgame. An impressive game by the machine.

I don’t know how many of the matches we will see in the future. Certainly the point is made that the top computers now play chess better than the top humans. The New York Times has a good summary of things:

Today’s outcome may end the interest in future chess matches between human champions and computers, according to Monty Newborn, a professor of computer science at McGill University in Montreal. Professor Newborn, who helped organize the match between Mr. Kasparov and Deep Blue, said of future matches: “I don’t know what one could get out of it at this point. The science is done.”

Mr. Newborn said that the development of chess computers had been useful.

“If you look back 50 years, that was one thing we thought they couldn’t do,” he said. “It is one little step, that’s all, in the most exciting problem of what can’t computers do that we can do.”

Speculating about where research might go next, Mr. Newborn said, “If you are interested in programming computers so that they compete in games, the two interesting ones are poker and go. That is where the action is.”

I’m not sure if Go really holds much interest from a computer programming standpoint, since it is ultimately the same sort of game as chess. But a computer that can play poker well would be a bit creepy!

Comments

  1. #1 Blake Stacey
    December 5, 2006

    The computer managed to prove, once again, it’s general superiority in tactical positions.

    “It is general superiority”?

    I think the appeal of programming computers to play go is that while the rules are even simpler than chess, the search space explodes so rapidly that brute computation is just useless. The standard party line is that playing go requires more of the skills that humans have and modern computers don’t; we could “solve” chess without radically new ideas of computer science or artificial intelligence, just lots of processing power and hefty helpings of cleverness.

  2. #2 Davis
    December 5, 2006

    I’m not sure if Go really holds much interest from a computer programming standpoint, since it is ultimately the same sort of game as chess.

    The Wikipedia page on computer Go — http://en.wikipedia.org/wiki/Computer_Go — has some interesting information on the matter. The claim is made there that “It is a widespread opinion that techniques learned in the course of developing a strong Go program would transfer, to a greater degree, to more general problems in artificial intelligence, than has been the case with chess.”

    And speaking only as an extreme amateur both in Go and in chess, I’m not sure I’d consider it the same sort of game.

  3. #3 Alpha Chen
    December 5, 2006

    Check out this report on computer go. It’s a bit dated, but a pretty good explanation of the difference between programming go versus chess.

  4. #4 Tyler DiPietro
    December 5, 2006

    The standard party line is that playing go requires more of the skills that humans have and modern computers don’t; we could “solve” chess without radically new ideas of computer science or artificial intelligence, just lots of processing power and hefty helpings of cleverness.

    The problem is more of the programming paradigm than how the game is rigged against the programmer (pardon the pun). A computer can use Combinatorial Game Theory to analyze every move several turns in advance, a human player struggles to see enough while overall seeing less than a single turn ahead. It would be interesting to see a computer Chess A.I. that dropped the typical analytic method and went with pure pattern recognition.

  5. #5 u221e
    December 5, 2006

    A few things…

    First of all Fritz 10 isn’t even the best chess playing program out there, both from performance and usability standpoints (why the hell is there no analysis mode in Fritz? How completely useless…)

    For instance if you take a look at the current rankings here:
    http://www.husvankempen.de/nunn/40_120_ratinglist/ratinglist/rangliste.html

    You can see Fritz 10 is down almost 200 Elo points to Rybka.

    Who buys these programs anyway, when GNU Chess alone can beat more then 99% of the population?

  6. #6 tomh
    December 6, 2006

    I’m not sure if Go really holds much interest from a computer programming standpoint, since it is ultimately the same sort of game as chess.

    You’re obviously not a go player.

  7. #7 Johan Richter
    December 6, 2006

    Jason meant that GO and Chess are both two-player zero-sum games of complete and perfect information. From a mathematical point of view that indeed makes them the smae kind of game, regardless of differences in playing strategy.

  8. #8 Noodle
    December 6, 2006

    “From a mathematical point of view that indeed makes them the smae kind of game, regardless of differences in playing strategy.”

    Yes, but that difference in strategy is all the difference in the world, programmatically speaking, which is more to the point given Jason’s comment:

    “I’m not sure if Go really holds much interest from a computer programming standpoint, since it is ultimately the same sort of game as chess.” [emphasis mine].

    It’s a complexity thing. The potential variantions, and their implications to game play by computers, are far, far greater in Go than in chess.

    Computer scientists have shown that they can regularly beat chess masters. The best Go programs still cannot match the best Go players.

  9. #9 tomh
    December 6, 2006

    Computer scientists have shown that they can regularly beat chess masters. The best Go programs still cannot match the best Go players.

    The best go programs can barely play with a decent amateur player. Professional go players are light years beyond amateurs and go programs don’t even have them on their radar.

  10. #10 frank schmidt
    December 6, 2006

    Given the faster processing speed of a computer, one way to overcome its inherent advantage would be to reduce the time allowed on its clock so that an average move would allow a similar number of decisions.

  11. #11 Michael Kremer
    December 6, 2006

    “I’m not sure if Go really holds much interest from a computer programming standpoint, since it is ultimately the same sort of game as chess.”

    In the sense in which Go is “ultimately” the same sort of game as chess, chess is “ultimately” the same sort of game as tic-tac-toe. Nonetheless, the challenge of producing a chess algorithm that can beat all human players has been a lot more interesting than the same challenge for tic-tac-toe. For reasons that others have pointed out above, with improvements in technology, computing speed and so on, Go is now a more interesting challenge than chess, because brute-force calculation can get you much further in chess (given current technological abilities and limitations) than it can in Go.

  12. #12 Jason Rosenhouse
    December 6, 2006

    Johan-

    Yes, that’s exactly what I had in mind.

    Michael-

    Your analogy is well-taken. Tic-tac-toe is the same kind of game as chess. But it’s a game with such a small tree that a computer can play the game perfectly. Chess has a vastly larger tree and requires a far more complex evaluation function, but processing power is now at the point that the computer can analyze enough of the tree at any given point to defeat the strongest human players.

    It’s certainly true that the best Go computer programs are very weak indeed relative to the best human players. But 25 years ago that was true of computer chess programs as well. I suspect the weakness of Go programs has more to do with the lack of effort that has been put into the problem relative to chess.

    On the other hand, it might be that Go is combinatorially so huge, and the number of moves ahead you have to look so large, that the processing power just isn’t there to produce a strong Go program. My off the cuff remark was not intended as a scholarly assessment of the literature of the area, but merely as a knee-jerk reaction. I certainly agree that Go is now a more appealing target for programmers than is chess.

  13. #13 Mustafa Mond, FCD
    December 6, 2006

    There’s always a chance that the computer will fail the doping tests…

  14. #14 Joe Otten
    December 7, 2006

    Do we know of any interest in computer players without an opening library? If the opening has to be computed from scratch that would be a new challenge for good human players, and may (?) result in new opening theories.