December 6, 2006

The future of chess

Now that the RAG Tournament featuring Vladmir Kramnik and Deep Fritz has concluded with the machine emerging victorious, it's time for some contemplation about the current state of chess and its future.

First off, credit where credit is due. The Fritz team put together an excellent program that defeated Kramnik quite soundly -- an achievement made all the more impressive by the fact that Kramnik's style is considered quite difficult for computers to handle. Fritz v.10 may be the best chess playing entity of all time (not including Hydra which hasn't been pitted against a world champion). Yes, Kramnik blundered away Game 2, but that, like fatigue, stress and over-confidence, are indelible parts of the human condition -- intangibles that don't apply to machines. Moreover, Kramnik never really threatened Fritz and lost quite soundly in game 6; he played for the draw in virtually every match and never assumed he could win.

And this is where we find ourselves at the end of 2006: the best chess playing humans, it would seem, are now unable to beat the expert chessbots. It's at the point now where the victory is in the draw. The day is soon coming where even this may become impossible, but a part of me believes that chess is too complex for today's computers to achieve consistent victories. Computer power and programming will have to be more powerful by an order of magnitude before computers can generate algorithms that will result in perfect play resulting in perpetual streams of victories.

This is assuming, of course, that chess could be solved in the strong sense. I'm not convinced this is possible. In the vast space of all possible games, perfect play in chess will lead to draws more often than not. The most solved that chess could ever become is in the weak sense where an algorithm can secure a win for one player, or a draw for either, against any possible moves by the opponent from the initial position only.

How complex is chess? Well, before I get to that let's look at tic-tac-toe and checkers for a frame of reference.

Tic-tac-toe has the potential for 765 different positions, or 26,830 possible games on the 3x3 grid. When taking into account both rotational and mirroring symmetry, there are 31,896 possible unique games. Consequently, it is very easy to write a computer program that can deal with all possible variations and play a perfect game. In fact, it's so simple that even humans can consistently play tic-tac-toe with perfect play (which is why every errorless game ends in a draw).

Checkers is a bit more complicated. It is played on an 8x8 grid with an estimated 10^(12) possible positions with other estimates reaching upwards of 5x10^(20) and 10^(18) positions reachable under the rules of the game.

There is a popularly held myth that checkers is a solved game, but it's not -- at least not entirely. Endgames up to 9 pieces (and some 10 piece endgames) have been solved. Not all early-game positions have been solved, but almost all midgame positions have been. It has been estimated that several more years of computer advancement is required before machines will completely solve checkers.

And then there's chess. An average chess position has 30 to 40 possible moves, sometimes with as many as 218. Subsequent game-tree possibilities explode exponentially with each potential step into the future. The number of legal positions in chess is thought to be between 10^(43) and 10^(50). It has an estimated game-tree complexity of 10^(123) -- yes, that's a 1 with 123 zeros behind it! To put this into perspective, there are more possibilities in chess than there are atoms in the Universe. Actually, to say that's putting it into 'perspective' is a bit of a sad joke. To the paleolithic human brain it might as well be infinite; we cannot even come close to comprehending what a vastly huge number that is.

So, a computer like Deep Fritz, which is able to calculate millions of moves each second, still has a rather profound game-tree horizon to deal with. It still cannot chart an algorithmic course to guaranteed victory. That being said, modern chess computers are powerful enough such that they will not allow themselves to be put into dangerous situations. While Fritz might have a formidable game-tree horizon to contend with, it is a horizon that is way off in the distance as far as humans are concerned. This is a tremendously demoralizing prospect from the perspective of human competitors.

Adding insult to injury, chess is a partially solved game (and powerful computers should be able to calculate these winning maps on their own). Retrograde computer analysis for all 3 to 6 piece and some 7 piece endgames have been solved (counting the two kings as pieces). It is solved for all 3–3 and 4–2 endgames with and without pawns. Chessbots also have access to the opening books (typically up to the first 12 moves), which human chess players have to memorize.

So what does this mean for the future of human and machine competitions? Given Fritz's excellent performance against Kramnik, and given that chessbots are improving much faster than their human counterparts, I believe that the era of meaningful human/machine interactions is behind us. Fritz made moves during the tournament that left other grandmasters scratching their heads wondering how and why it did what it did. In many respects, the internal machinations of the computer is beyond human comprehension. Consequently, even advanced chess as envisaged by Garry Kasparov, where humans pair-up with computer assistants, may be an obsolete idea as even the best human minds are already incredulous to the findings of the computer. A human collaborator may actually undermine the work of the machine.

In regards to human versus machine situations, the only option at this point is to start handicapping the computer. Otherwise, there's no point to these match-ups.

One thing I'd like to see are fairer time controls that take the slow human clock speed into consideration. I'm not proposing that players take weeks in between moves, but something fairer like giving the computer less time to ruminate. What's needed is a sliding ratio depending on the power of the machine (Anatoly Karpov has suggested a ratio of 2.15 on 1.40 (hours). I'd be inclined to give the machine even less time).

Also, computers should not be given access to the opening book, while humans should have access to the entire chess database. Other ideas include collaborative human teams consisting of multiple grandmasters, time-outs for the human player, and even the ability to take back a move.

The trouble is, however, that the developers of the chess playing computers are reluctant to handicap their machines. These events are, for all intents-and-purposes, money making ventures. IBM stock skyrocketed after Deep Blue's famous victory over Kasparov back in 1997.

That said, the developers run the risk of eating themselves up by putting an end to meaningful match-ups. It'll only be a matter of time before the grandmasters refuse to be humiliated by number crunching behemoths. Moreover, the advent of handicaps would offer an excellent opportunity for immensely entertaining tournaments and high quality chess.

But as far as the advancement of chess is concerned, it is time for humans to take a backseat to the computers. Chessbots have moved beyond us now and are playing the most sophisticated matches in the history of the game.

But that doesn't mean that you and I can't still enjoy the game, or that human versus human tournaments are obsolete. There's still a lot of chess that needs to be played.

7 comments:

Anonymous said...

I take some solace in the fact that computers rely on the benefit of hundreds of years of accumulated human chess knowledge. These programs still own their ability to evaluate positions to the human programmers. Not that Fritz isn't sophisticated, but it is brute force that ultimately allows it to win.

Also, that humans can still draw the computers is quite impressive. As you point out Fritz is searching millions of moves per second, while the human looks at a tiny fraction of that amount. And even in this recent event, Fritz did not play correctly in every case.

Anonymous said...

Last game was the coolest of the contest. We saw what 'post-human' chess looks like. All the GM's were sure Black (Kramnik) had the advantage but...

From the match report:
http://www.chessbase.com/newsdetail.asp?newsid=3524

"The move and manoeuvre Deep Fritz plays has certainly never been seen before."

"The manoeuvre Bc1-g5-f4-c1 (with Ra1-e1 incerted) caused some amusement in the commentary boxes in Bonn, but as with Rf1-e1-e3-g3 the GMs slowly started to see meaning in the "madness". "

"19.Nb1. Amazing: a mirrored knight retreat on both sides. Once again the GMs doing live international commentary broadcasts were surprised and amused by the computer moves, but slowly started to find reasons for it."

"The commentators who had given Black a substantial advantage (while Deep Fritz persistantly saw White in the lead) now slowly started to have doubts about Kramnik's position."

"21.Na3. This was not the move the GMs anticipated (...Nd2 was the reason given for 19.Nb1). Deep Fritz is still playing moves that take a while for humans to appreciate."


I take solace in the fact that computers cannot even beat an average human player at 'Go'. I guess I'm a lot more fascinated by 'Go' now, rather than 'Chess'.

Sure Chess is a deeply complex and amazing game and all, but the fact that is was mastered through largely brute force methods shows that it's not a true test of real intelligence in the way, for instance, that 'Go' has to be.

Anonymous said...

Handicapping computers makes no sense. They increase in ability exponentially, so whatever handicap is proposed won't help against the next iteration of computer players. We want to see the "profound" ideas they can come up with. They will be able to do this in shorter and shorter periods of time. You could reduce them to X clock cycles but it's a given you can make a computer play as poorly as you want. It's not interesting.

As for opening books, it's silly to get rid of those just because they are the product of human work; the whole chess engine is a product of human work. Besides that, it's only a matter of time before they can calculate from the get-go, or they can simply do their own "opening preparation" in the months leading up to the match, developing their own openings.

Taking back a move? What's the point? If you want the computer to play worse, just chop down its abilities to taste. If you want the human to play better, it'll simply be an exercise in boredom for the onlookers, as grandmasters are toyed with the way casual players are toyed with already. Take back that move? Okay. It still wins. Take back another? Okay. Try something else. Woops, it's still winning. Okay, use multiple levels of undo until we find something that works finally. That's not a game, that's trial-and-error as directed by the computer.

These suggestions are the sounds of desperation from a generation of players whose profession has been rendered obsolete. Interest wanes and now they'll have to do something else for a living.

I saw this coming long ago. At the time of Deep Blue it was still mostly theoretical (if inevitable) but now a reasonably-priced desktop system can beat the human world champion, and soon your cell phone will be able to. Spending 15 years now to become a grandmaster will just see you lose to a computer 1,000 times the speed of what we're using today. (Stated another way, that computer will be able to do all the calculations that today's computer would do in the entire game -- 2 hours and 40 minutes -- in under 10 seconds.) Not a good investment of time.

A fun exercise would be to run a chess engine on Amazon's EC2 and see just how many ply you could get by using lots of nodes.

Anonymous said...

I totally disagree with the notion that computer chess is displacing human vs human events. I see more and more people playing chess and using computers (as tools) than ever. The tournament stakes are getting higher and higher because human players want to test themselves against each other, not some lifeless machine that crashes when the electricity switch is pulled. What's interesting is to try and uncover the "style" of various computer programs and to find out why they're making certain moves. Beyond that, it's important to chart one's own path and not play follow the leader. As far as I know computers don't play the same openings and reach the same positions over and over again, proving that chess is, for all intents and purposes, infinite in possibilities.

Anonymous said...

As a postscript, I believe that they have now completely solved checkers.

There will still be the demand for human vs human. Chess is not always about the best moves, its also about the psychology, which is part of the reason a human player will lose if he 'plays to draw'

Amber said...

@Ryan:

[...] that computers rely on the benefit of hundreds of years of accumulated human chess knowledge [...][...] it is brute force that ultimately allows it to win

Now there is your classic exacerbated contradiction. I'm not sure what point Ryan actually tried to make, but it would seem he invalidates both.

FWIW: i happen to have some experience in computer chess and I find that invariably I win more by tossing 'chess knowledge' in favor of evaluation speed, in effect shifting that game horizon.

Unknown said...

There is no point in trying to beat a super computer in chess cause they have far more advanced processing power then human beings.the point is how human beings can use the help of these super computers when the play with human beings.so that ultimately the human brains will develop more and produce excellent games which has not been seen ever before..so no need to worry about the computers power.they should be like that only.the difference is as simple as the difference between a war and a game ! why people are worried i cant make out!