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.