10 Years After Big Blue Beat Garry Kasparov

Jamie found another MIT Technology review story, this time about Chess, Supercomputing, Garry Kasparov, and trying to make sense of just what exactly it all meant when a computer finally beat a grand master. An interesting piece that touches on what it means to play chess, the difference between humanity and machinery and how super computers don't care when they are losing. Worth your time.

Comments

A chess player's take on this

[Zontar_Thing_From_Ve]

Back in the early 1990s, I used to play in chess tournaments. I wasn't very good though and I didn't play at a high level, but I did play in official tournaments that the USCF (United States Chess Federation) sanctioned. My goal at the time was to try to make grand master. I gave up because of 2 reasons. The first was that I wasn't very good. I had serious problems in the middle game. My opening play and end game play were sound, but inevitably I would get beat in the middle game through carelessness. The second reason I gave up was because I realized that computers were ruining chess. Keep in mind that I am talking 1990-1993 here (I stopped playing in tournaments in 1993). In the old days, if you learned a chess opening, the moves might go 7 moves deep or so in most openings where the moves for the white and black pieces were known and any deviations from these set moves got you "out of book" as they say. If you deviated on, say, move 4 in a 7 move sequence, the odds were that your move was bad because if it was so good, it would have been known and used by other players and then be part of the book. At this time being "in book" was already starting to change because of computer analysis. Then you could go 10 moves or more in many openings and still be "in book". The amount of time and memory required to memorize these much deeper opening sequences was overwhelming. One day I realized that it just wasn't worth it and I'd rather devote my time and brain power to other things that I actually had some talent for, like learning other languages.

Chess is said to be "solvable". My understanding is that it can be proven mathematically that chess has a finite series of moves. If this is correct, then at some point computers will be powerful enough to be able win every game because they'll be able to analyze every possible opening all the way to the end and only pick the moves that will win. No human will ever be able to duplicate this feat. So it is inevitable that computers will eventually be unbeatable. I think just a few weeks ago Slashdot had an article that a computer program has been designed that is now at the point where it cannot lose at checkers - ever. Checkers is quite a bit less complex than chess and it has only now been solved. Whether it takes 10, 20, 50 or more years to solve chess, the day will come when computers simply cannot be beaten at chess under the current rules.

Should we care? Well, maybe not. Computers are better than humans at a lot of things, like mathematical calculations, so it's inevitable that they will be better than humans at chess. The downside is that once all chess games are solvable, it will ruin chess at the professional level. It will make it almost impossible for any game to be postponed until the next day because once there is a postponement, a player could, in theory, simply use a PC to analyze his game and find a sequence of moves where he cannot lose if he plays them correctly. At that point, there's no more human element in the game - it's simply a matter who can more accurately remember computer analysis. Computers ruined chess for me in the early 1990s. Can you imagine how much worse things are now? And how much worse they will be when the day comes that everybody can use a PC to analyze his game and find a way to never lose? At that point, I suspect that either chess will change to Fischer Random Chess as mentioned in the article or people who would have played chess will simply move on and play the game of go instead. Go is beyond the ability of current computers to solve and even the best computer programs can't beat strong human players.

Re:the supercomputers advantage...

[feijai]

Sure. But Kasparov didn't have access to Deep Blue's "previous games", or indeed any information about the system at all. They kept him in the dark. IBM also insisted that there be no game breaks -- not an issue for Deep Blue of course -- but a very *big* deal for professional chess players. But most importantly, IBM's team of chess masters and coders modified the system between chess games after analyzing Kasparov's strategy the previous game. That is, he wasn't playing Deep Blue: he was playing Deep Blue being adapted in semi-real-time by a bunch of human experts. And crucially, IBM hid this fact, knowing that it'd be (rightly) considered highly suspect.

Re:Obligatory

[SoVeryTired]

Actually, backgammon was essentially 'solved' in the 80's by a program known as TD-gammon, which used Temporal difference learning along with self play. http://en.wikipedia.org/wiki/Temporal_difference_l earning

As far as I know, the major difficulty in writing a strong go playing program isn't the search space, but the fact that there are so many opposing aims that it's very hard to write a good heuristic. For instance, players have to decide wether to go for speed or security in their play. Deciding whether to expand territory quickly and risk invasion, or to build up a small stronghold is a major factor in the game.

The Best Chess

[Anonymous Coward]

... is Computer vs. Computer

They are fearless, uncompromising, untiring. The games are far more interesting than human efforts. Check out some Rybka vs. ZapZanzibar matches (the number 1 program vs. the number 2 program). Incredible play.

Re:Obligatory

[Dlugar]

As far as I know, the major difficulty in writing a strong go playing program isn't the search space, but the fact that there are so many opposing aims that it's very hard to write a good heuristic. For instance, players have to decide wether to go for speed or security in their play. Deciding whether to expand territory quickly and risk invasion, or to build up a small stronghold is a major factor in the game.

The major difficulty isn't so much in that there are opposing aims so much as the fact that there's no good evaluation function. In chess, you search the tree as far as you can, then you have some way of statically evaluating the leaf nodes without traversing the tree any further. In chess, you can use the number of pieces, or the number of squares controlled on the board, etc. But in Go, it's really hard to statically evaluate the board, because all of your pieces on the board might be capturable, and the only real way to tell is by continuing down the search tree.

As a result, recent advances in Go-playing programs have actually come simply because a new "evaluation function" has arisen: random play. When you get to the end of your search tree, to evaluate whether a move is good or not, you simply randomly play a bunch of games starting at that position, with random moves by both sides, and see what happens. It's a pretty dumb "evaluation function", and isn't really even very static (so it's much slower than, say, most chess evaluation functions), but it has still resulted in a reasonable increase in program strength.

Dlugar