TCS Daily


Man vs. Machine

By Arnold Kling - November 20, 2003 12:00 AM

"I was surprised to see Kasparov favored. Once he lost to Deep Blue, the last big match (Kramnik vs. Deep Fritz) was a draw. I know it is not as simple as Moore's Law, but hey, don't these machines improve their game more rapidly than the human players do?"
-- Tyler Cowen

 

The results of the latest match between Gary Kasparov and the top computer X3D Fritz ended in a draw, vindicating Tyler Cowen and Jeff Sonas, who believe that computers have not yet overtaken the top human player. Sonas argues that "Although computers obviously must be improving in recent years, the strongest humans seem to also be improving at about the same rate."

 

As a fan of Moore's Law, I am disappointed by the outcome of the latest chess match. As Cowen implies, the strength of the computers should be doubling each year or two. Yet they seem to be improving no faster than the best humans.

 

How Better Players Win

 

Cowen describes the following process by which computers beat humans at chess.

 

"The human grandmaster carries a significant advantage out of the opening or early middle game, where it is harder for the machine to calculate all relevant possibilities and positional judgment is at a premium. But as the game progresses, the machine plays perfect defense and the human cannot convert the advantage into a win."

 

The implication is that the computer only wins by wearing down the human opponent. In Cowen's view, the human is really the better player.

 

In fact, it is often the case in games between humans that the inferior player takes an early advantage and appears to be "worn down" by the better player. But that is the way games proceed between players of slightly uneven abilities.

 

Suppose that a really top player makes the correct move 80 percent of the time, and a slightly weaker player makes the correct move 75 percent of the time. If each player makes one move, then the inferior player comes out ahead if she makes the right move and her opponent makes the wrong move. The probability of this is (.75)(1 - .80) = .15, or 15 percent.

 

However, in a long game, the law of large numbers works in favor of the superior player. Over a series of many moves, the chances increase that the inferior player will make more mistakes than the superior player. The laws of probability ensure that the inferior player has a much lower likelihood of being ahead late in the game than early in the game.

 

In ordinary English, it is easier to play over your head for a short spurt than to keep it up. If you are an inferior player, then occasionally you will outplay a superior opponent for a few moves early in the game, gaining an advantage. After a while, though, you will begin to make the greater share of mistakes, so that eventually you lose. You will remember those games as games where you "blew it." In contrast, when your mistakes come early, and any streak of good moves that you make later in the game is in vain, you will remember yourself as having been "dead out of the opening."

 

Overall, then, there is nothing unique about the way that computers defeat humans. The process by which computers beat humans is the same as the process by which superior humans beat inferior humans. Sometimes, the human loser feels like he "blew it," and sometimes he feels like he was "dead out of the opening." Either way, the better player wins. The better player wins by making fewer mistakes, where a mistake is any move that is less than optimal for the given situation.

 

Search Depth

 

I am an incompetent chess player, but I have played tournament Othello. In Othello, the man vs. machine issue also has been controversial. The computers overtook me when they reached a search depth of 9 moves -- examining moves 9 moves ahead, which they have been able to do for fifteen years. Now, on my laptop, the Zebra Othello program can quickly compute a 20-move look-ahead.

 

The low point for humans in Othello was reached in 1997, when world champion Takeshi Murakami was trounced by a program called Logistello. Since then, I would argue that humans have been learning from computers, rather than the reverse.

 

In chess, Sonas charted the progress of computers here. He argues that computers are not going to reach the final milestone, of surpassing the very best human players.

 

My guess is that holding the algorithms constant, as the computers add search depth, they will overtake even Kasparov. However, I suspect that they could use better algorithms.

 

The top Othello programs rely on databases of previous games to evaluate positions. If a position at move 45 correlates with a win for White most of the time, then the program will give that position a good score for White and a bad score for Black. However, keep in mind that the program is looking ahead 20 moves, so that it is using its database of positions at move 45 at the 25th move!

 

The point is that the Othello programs use databases and statistics, not human logic and heuristics, to evaluate positions. My guess is that to really take advantage of Moore's Law, chess programs might have to do the same. Writers of chess programs should not throw away processing power on attempts at chess logic. Instead, they should try to maximize search depth, which is the critical factor in machine capability.

 

It may take another few years for computers to be able to out-search humans at chess. It is easier for a human to search deeply in chess than in Othello. In Othello, the flipping of pieces is harder to track. In chess, many top humans can play "blind" games, in which there is no board. To my knowledge, only Murakami has been able to play "blind" Othello.

 

The Bigger Game

 

In the grand scheme of things, chess and Othello are not important games. There are many human activities and capabilities that are more impressive. However, if computers keep doubling their capability every year or two, then eventually they will be able to match any of our skills -- or at least that would be the argument of Ray Kurzweil. From Kurzweil's perspective, chess is merely a battleground in the larger man vs. machine war that the computers are destined to win.

 

As an economist, I am inclined to bet that computers will gain prowess at a rate close to what Kurzweil projects. That view leads to Rational Exuberance about economic growth in the next few decades. Computer prowess at chess could be an indicator of how well that forecast will pan out. Kasparov's continued success may be good news for human chess players, but it could be bad news for those of us counting on the machines to deliver high economic growth!

Categories:
|

TCS Daily Archives