New! Chess 2.0! (Not really.)

By Jim Rossignol on January 27th, 2010 at 3:08 pm.


This large and splendid article by chess hyperbrain Garry Kasparov (pictured), in which he talks about the evolution of computer chess, seems deeply relevant to all of computerised gaming.

Like so much else in our technology-rich and innovation-poor modern world, chess computing has fallen prey to incrementalism and the demands of the market. Brute-force programs play the best chess, so why bother with anything else? Why waste time and money experimenting with new and innovative ideas when we already know what works? Such thinking should horrify anyone worthy of the name of scientist, but it seems, tragically, to be the norm. Our best minds have gone into financial engineering instead of real engineering, with catastrophic results for both sectors.

It’s worth reading, anyway.

Dave Tosser says: The problem with chess is that it isn’t owned by a corporation. Because it’s old, and therefore rubbish, it receives none of the ancillary bonuses of feature creep or online-ification that modern games benefit from. What the chess market needs is a new chess, developed and marketed by a successful large company to deliver the additional features chess needs (co-op, achievements, micro-payment DLC).

, , , .

58 Comments »

  1. Ian says:

    When ARE we getting Chess 2, anyway? After the first one ended with a such a cliffhanger (with the King looking to be in an inescapable position, facing certain death) I was hoping we’d get a second one to continue the story.

  2. MrCraigL says:

    Dave Tosser is my hero!

    • Bhazor says:

      Smoking a cigar with a tasch like that does require a great deal of bravery.

  3. Mike_in_Ohio says:

    Chess really is THE ultimate strategy game… I suck at it but still continue to play it…

    (besides I get to play online with those sexy chicks in the U.K)

    http://www.chess.com

    hooyah!!!!

    LOL

    • Psychopomp says:

      At the risk of sounding like a weeaboo, I actually prefer Shogi to chess.

    • Yak Jazz says:

      I thought weaboos were the anime/cosplay nerds? Shogi rocks. It’s got bugger all to do with how vapid contemporary Japanese media culture is.

    • tekDragon says:

      Go gives chess a good run for it’s money. Computers are still completely terrible at playing Go in large part because brute force approaches still fail.

  4. Mepus says:

    No, that would be GO.

  5. Meat Circus says:

    Kasparov’s a bit of an arse and a massive luddite. He loves expounding off on things like game theory, despite apparently knowing little-to-nothing about them.

    The reason, Garry dearest, that brute-force methods work so well against Chess is that Chess is in a game-theoretic sense, trivial. Given a sufficent amount of time and space, an optimal move is always possible to determine.

    If Kasparov weren’t such a rigidly mechanistic thinker, he might turn his attention to more interesting, non-game-theoretic-complete games. Like Backgammon, Go or Poker.

    I bet he’d be /really/ shit at No Limit Texas Hold’em.

    Essentially, Chess is a solved problem, and Kasparov’s really bitter because he helped IBM solve it by losing to an oversized pocker calculator. Sorry about that. Tough.

    • Premium User Badge

      AndrewC says:

      Careful there, Meat, he’s already worked out this thread to comment 50.

    • Meat Circus says:

      That’s fine. I’ll play move 51: Shotgun beats Angry Russian.

      Check and mate, muddy funster.

    • brog says:

      Meat Circus: Your examples are poor.

      - Go, being also a perfect-information game, is susceptible to the same methods as Chess. It’s trivial for the same reasons. It so happens that the game tree has a wee bit of a higher branch factor, so you need a computer a few orders of magnitude more powerful to solve it, but the methods are the same.

      - Backgammon and Poker are much simpler to solve game-theoretically. Because they’re games with chance and (in the case of Poker) hidden information, there is no unique optimal strategy; instead, game theory tells you that the optimal play is to randomly choose between move A with a 20% chance and move B with an 80% chance (or something similar). These odds are much easier for a computer to solve than the complex game tree of Chess, and as such computer players can play these games optimally and come out ahead of humans (over time, obviously not in every individual play because of the element of chance).

    • Sam says:

      Actually, Meat, if you read the article itself, you’ll see that Kasparov is mainly upset because he wanted to see new and interesting solutions to the computer chess problem – which hasn’t happened since chess was “solved” by constructing an algorithm that could beat Garry Kasparov.
      He actually does mention a later experience of playing another grandmaster in a special game where both were allowed to use a chess program to assist them – apparently it was an interesting experience.

      So, he’s hardly a luddite.

    • A-Scale says:

      You are an ignorant and insufferable ass, Meat Circus.

    • sebmojo says:

      You are an ignorant and insufferable ass, Meat Circus.

      Thank you A Scale, quoted for great truth.

    • mastrblastr says:

      seriously meat circus, why are you such a hater. thought the article was very well written and attacked a lot of interesting points. Recommend the read to everyone

  6. aldo_14 says:

    I’m still waiting for Ubisoft presents Cheryl Coles Chess Hero 2010 Sponsored by Starforce, with not one but 10 different chess pieces* and not one, not two, not four, but three(!!!) challenging opponents**.

    *pieces sold seperately
    **opponents 2 and 3 will be patched in post release for legitimate purchases at a minimal fee, presuming Dave from accounts says ok and Generic Steve the Discount Foreign Programmer’s fingers haven’t fallen off from making iPods.

  7. Mike_in_Ohio says:

    Yeah I do believe he would suck at Texas Hold’em…

  8. The Archetype says:

    @Meat Circus: But from a non-game-theoretical point of view metyhods besides brute froce might be useful. For example, studies have shown that chess players don’t so much plan tere moves out turns in advance as recognize patterns they’ve seen before in the board positions and respond accordingly. Building a program that could do that would at the least potentially help us understand how the brain recognizes patterns better, and could potentially be helpful in other areas where pattern recognition is needed.

    And of course, an AI that plays like a human would be more fun to play against.

  9. Mike says:

    Brute-force programs play the best chess, so why bother with anything else? Why waste time and money experimenting with new and innovative ideas when we already know what works? Such thinking should horrify anyone worthy of the name of scientist, but it seems, tragically, to be the norm.

    What?

    First of all – scientists aren’t here to solve the problems of chess. They’re here to progress understanding of the world in general. We do have a solution to chess that will always work – compute every known solution and run it. There are various ways of balancing it but it’s not really very interesting. Interesting problems generate interesting solutions, and interesting new techniques that advance our understanding of AI and human-computer interaction.

    But Chess is not the only game out there, and many places show off more interesting challenges. A student I know is currently working on an AI project that aims to abstract DEFCON into a boardgame, solve the boardgame in realtime, and then apply the rules to each individual naval battle/air engagement. Chess can only offer so much. If it offers interesting challenges, those challenges will be met.

    Phew. Anyway, interesting link.

    • Meat Circus says:

      Quite. I bet it would be massively more interesting to try to create a program that can beat humans at Poker, or Backgammon, or Diplomacy or Nomic or any game where strategy is about something other than who can space-efficiently prune a decision tree to the greatest depth.

      If Deep Blue were human, I think he’d call Kasparov a sore loser.

    • Caiman says:

      Meat, your criticisms are like saying that art isn’t inherently interesting because, given enough computing power, every possible combination of colour and pattern could be iterated onto a piece of canvas and there would be no originality, no inspiration. Kasparov is clearly looking at why playing a computer at chess is inherently much less interesting than playing a human. You can extend the same analogy to playing an FPS shooter against humans or bots.

    • veerus says:

      Meat Circus, you make it sound like there are no poker bots out there. There have been a few “man vs machine” poker matches. The latest one that I’ve heard of was a year and a half ago and the computer did win.
      http://www.poker-academy.com/man-machine/2008/

  10. Premium User Badge

    Fede says:

    I think the problem is (was?) that chess is in a middle ground, too complex to be solved by being reduced into smaller and simpler problems (the way connect four has been solved in 1989), but not enough complex to be too far ahead of brute force approaches.
    So brute force was necessary but also sufficient to solve the problem (defeating the strongest humans).

    More complex games will help programmers search for better ways. I have seen it happen in go: programs have gained a good amount of strength in the last 4 years because they shifted from brute force to monte-carlo methods. Maybe go isn’t yet complex enough and this new method will some day be enough to defeat the best human players, but then there will always be (or a new one will be created, eventually) a more complex game or system where the AI will need new tecniques to beat humans, instead of just brute force.

  11. Berzee says:

    Garry Kasparov makes many not-quite-right metaphors. It distracts me.

    Just thought you’d all like to know that.

    • Berzee says:

      For example, asking how many moves a grandmaster sees ahead is “the equivalent of asking Lance Armstrong how many times he shifts gears during the Tour de France.”

    • Snuffy (the Evil) says:

      Lance Armstrong doesn’t know how many times he shifts gears because different gears are better for different situations. Is the road wet? Is this section uphill? What position am I in? Et cetera. It’s the same with chess, as different situations and factors affect how many moves a chess player can look ahead. For example, at the beginning of a game, you have all kinds of time and no pressure to make a decision, but you won’t be thinking as clearly when it’s just your king and a rook against the world.

  12. David Arcila says:

    It’s good to see such a great article :) Thanks for sharing it RPS

  13. Jahkaivah says:

    Hopefully the Devs will get round to nerfing Pawn Spam.

    • Malibu Stacey says:

    • Malibu Stacey says:

      err that was meant to say

      [insert obligatory Queen/Rook/Knight/Bishop is overpowered comment here]

      but used greater than/less than instead of square brackets & got owned by the XHTML parser =(

  14. Alexej says:

    Queen is overpowered, can’t ever get rid of her.

  15. Weylund says:

    That’s because Queen is the Champions. (Sic.)

    Chess, as an AI problem, is kind of boring compared to much more fluid and dynamic stuff, like language understanding and how to make a guy who shoots reeel gud and keels the bad giyz.

    Seriously. I work in AI and both of those are far more interesting to me than applying more abstract but potentially more powerful methods to Chess than brute force. Shoot, if I wanted to build an AI to play something where I could see thirty moves into the future just by doing the math, I’d build an AI to do my laundry.

  16. Yfel says:

    Backgammon is actually harder to play (computationally) than Chess, although still being easier than Go. Because of the uncertainty, it needs to maintain various hypotheses, run the usual minimax + alpha beta pruning for each of those, and then select the move that maximizes the expected utility. To make matters worse, Backgammon also has a fairly high branch factor.

  17. CloakRaider says:

    Dave Tosser is so right, it’s unbelievable.
    I’ve always thought that Chess also needed in-game advertisements. Like, an advert per square. We’ll make millions.

  18. Jimbo says:

    I always get Kasparov and Legolas mixed up too.

  19. Quirk says:

    What Brog said.

    You’re failing to see that any game with a statespace falls to similar methods (which you can call “trivial” if you like). And backgammon in particular is straightforwardly simpler than chess. A human may gamble in backgammon or poker on an approach which is probabilistically less likely to succeed, but win anyway; but we can say, identically, that the weaker player can gamble on the unlikely outcome and win sometimes. This does not increase the depth of skill in the game; it just makes it harder to measure any skill at all. Poker is more challenging with its more complex betting, but it’s beginning to crumble now too.

  20. Tusque d'Ivoire says:

    Isn’t that Yuri Gagarin in the picture?

  21. Riesenmaulhai says:

    Kasparov has some weird understanding of science. You can’t just through a lot of money after problem X and after several years it’ll eventually get solved.
    Sure, he’s right in principle: Why not try to model human reasoning when writing chess programs? You might end up learning a lot of useful stuff about human cognition in general*. But then again: How exactly would you want to do that if you don’t know how humans actually reason (and I’m trying to find out for seven semesters already)?
    Despite the fact that Kasparov was actually really pissed about chess AI since the day it has beaten him.
    Of course you can say it’s been cheating, Garri, but it is better in YOUR game nonetheless. Get over it.

    * Perhaps you’d just learn about modeled human cognition. Who knows.

    • Weylund says:

      “* Perhaps you’d just learn about modeled human cognition. Who knows.”

      Often, yes. It’s fascinating to examine AI code (even, maybe especially, your own) and look at the pre-concepts and decisions that built it. Even fundamental applications of theory show the strokes of the maker.

      (I think my favorite thing about the CAPTCHA is that you lose your post if you forget to do it. Way to go with the negative reinforcement, guys.)

    • Tusque d'Ivoire says:

      concerning the CAPTCHA (i was really looking forward to what you were going to say about the psyche of its creator) that must be your browser. opera did just fine summoning my text again, when i forgot to captcha. (btw there is no reply to a reply. which i like.)

  22. Sir_Darc says:

    I’m really confused here… did Meat Circus actually read through the article? There’s no bitterness about Deep Blue, he talks about Poker in the last few paragraphs as being the next big thing in computing challenges, and seems to have a very balanced look at how things have developed over the past few decades. I thought the article was quite insightful.

  23. Premium User Badge

    Sagan says:

    Great article. Reminded me that I wanted to read up on Poker AI. And on generic AI that learns to play games. I know there was research in that area, and I would really like to know how far they got and where they failed.

  24. Tei says:

    I have read a few AI books and a few books about how the human brain work, and I think meat is a bit wrong.

    The thing is that chessmaster don’t see individual games, but “strategies”. The building blocks are bigger. Where poor players and machines are forced to think about the game in small blocks. Also, for a chessmaster the way the machine play is predictible, hence, he can build a trap that will ultimatelly win.

    Of course, you can cheat. You can make a AI play like a human, adding lots and lots of “historical games”, so the machine can “remenber”( replay ) a human strategy. Thats to me somewhat like cheating… in the sense, is not the machine the “creative force”.

  25. Biz says:

    chess is just a nice marketing gimmick. the public think it’s some huge achievement to win a game against the world’s best when the game can be easily reduced to iterating through board positions. obviously computers will win at those games.

    i’d like to see the day a computer can beat me at even the simplest of RTS games. (without cheating of course).
    that will be a true advancement in AI

  26. Premium User Badge

    Carra says:

    Interesting read.

    What I always find interesting about “Deep Blue vs Kasparov” is that it was all about man vs machine. While obviously you needed a bunch of excellent programmers to win.

    And indeed, the way in which Deep Blue did beat Kasparov was probably not how they imagined it fifty years ago. It’s basically iterating an entire tree for x seconds to find your best move. Lots of calculation but no intelligence (except from the programmers who wrote it).

  27. Lightbulb says:

    But isn’t that what a grandmaster is doing in a sense? By employing previous strategies they are using past experience.

    The difference is the creativity to do somethign different.

    However the most interesting thing I think is the idea of Human’s+AI’s vs Human’s + AI’s. Makes me think of the Culture books by Ian M Banks…

  28. golden_worm says:

    The computer assisted and freestyle methods of competition have an interesting extrapolation. If the system used was powerful enough it could suggest three optimal moves each turn. They could be labelled rock, paper and scissors. Each player takes a turn to select the method they think will counter their opponent.qq

  29. Moonracer says:

    It would be nice to see a digital chess game that actually had different game modes. I once played a RL game where all the pawns had the same movement ability as kings. You can’t change the rules like that in a digital game.

  30. Tony M says:

    I think what Kasparov is saying (and some readers are missing) is this:

    They have designed a computer program that beat the best Chess players. Well done, Kudos to the guys who achieved that.

    Now that thats been done, a more interesting avenue of study is to try and create an AI that thinks about chess the way humans do. Looking for patterns etc. This kind of AI would make the same kinds of mistakes that human players make, and the same leaps of intuition based on visual patterns etc. It could even learn based on previous mistakes.

    Kasparov is saying thats a more interesting and fruitful avenue for future research into chess AI rather than just refining the brute force calculator algorithm that we’ve been using for years.

    Gaming analogy: Which is the better FPS bot: A bot with 360 degree vision and perfect aim who can beat any human opponent, or a bot that plays like a real human?

    Tony

    • bill says:

      It’s interesting that the FPS bot needs to be programmed in a totally different way to the way RTS games are.

      FPS bots need to be programmed to act like players, with their flaws and behaviours.

      Right now, RTS bots are mostly designed to play like RTS players, but I think that’s totally the wrong way to go. AI wars is heading in the right direction by trying to make AI units that act like the units they are supposed to be, and therefore allow the armies to act like the armies they’re meant to be.

      In short, FPS bots need to be players. RTS armies need to be armies. Chess AI needs to be skynet.

  31. Fun play online says:

    I agree with Kasparov, of course. The old method sucks and it’s long dated.

  32. Bret says:

    You know, considering how few computers there were when Mr. Chess made Chess, I figure he’d never expect this sort of adaptation. Interesting, really.

  33. Boldoran says:

    Kasparov social skills may not be as far developed as his chess skills but what he says is worth listening to.


    Like so much else in our technology-rich and innovation-poor modern world, chess computing has fallen prey to incrementalism and the demands of the market. Brute-force programs play the best chess, so why bother with anything else? Why waste time and money experimenting with new and innovative ideas when we already know what works?

    This is spot on and is also applicable to many other areas (transportaition, energy production, game-development, …).

  34. Backgammon says:

    Thanks for the reference. From where I see it, chess and backgammon are not so different in the influence computer had on them. I especially identified with this quote:

    “Instead of a computer that thought and played chess like a human, with human creativity and intuition, they got one that played like a machine.”

    That’s what I had to say about The Backgammon Master and the Computer

  35. party gowns says:

    I hope that we will see more from you.