A second interesting point in the game occurs on move 13. The move played by HAL is clearly a winning move, but Deep Blue would have found a move that forces checkmate one move sooner. Current programs always prefer the shortest checkmate. Thus, either HAL is not able to calculate as deeply as Deep Blue does or he chooses a move based on "satisficing" criteria; that is, HAL saw that the move guaranteed a win, and so did not bother to search for a better move. Human chess players commonly follow this practice, which is another piece of evidence pointing to HAL's human style of play.

So how do we now that HAL understands how humans think? When HAL plays his spectacular fifteenth move, he surmises, undoubtedly correctly, that Frank had overlooked this move. Further, HAL did not point out to Frank the other possible variations to checkmate -- only the most interesting line, the one that Frank would most appreciate. Although Frank need not have accepted HAL's queen sacrifice, a prosaic checkmate would have followed shortly anyway.

HAL's ability to play chess human style is what computer scientists in the 1960s might have expected. When 2001 was produced, the majority of artificial intelligence researchers probably believed that computers should play the way humans play: by using explicit reasoning about move decisions and applying large amounts of pattern-directed knowledge. It wasn't until the 1970s, after years of much hard work and little progress, that chess programmers tried a new strategy, which is still utilized in the 1990s. A brief history of computer chess and some of its key components is relevant to understanding how machines play today. Perhaps we should start with an even more basic question: Why develop a chess machine in the first place?


A Brief History of Computer Chess: The Early Days

In 1950, Claude Shannon, the founder of information theory, proposed that developing a chess machine would be an excellent way to work on issues associated with machine intelligence. In his article, "A Chess-Playing Machine," Shannon states the case for developing such a machine: "The investigation of the chess-playing problem is intended to develop techniques that can be used for more practical applications. The chess machine is an ideal one to start with for several reasons. The problem is sharply defined, both in the allowed operations (the moves of chess) and in the ultimate goal (checkmate). It is neither so simple as to be trivial nor too difficult for satisfactory solution. And such a machine could be pitted against a human opponent, giving a clear measure of the machine's ability in the type of reasoning."

In fact, the practical applications that could result from development of a world-class chess machine are numerous. Complex tasks that may be solved by technologies derived from Deep Blue include problems in chemical modeling, data mining, and economic forecasting.

Fascination with the idea of a chess-playing machine, however, began more than two centuries ago, long before anyone thought of using a computer to solve large-scale problems. In the 1760s Baron Wolfgang von Kempelen toured Europe with the Maezal Chess Automaton, nicknamed the Turk. The machine was nicknamed the Turk because it played its moves through a turbaned marionette attached to a cabinet. The cabinet supposedly contained "the brain" of the machine; it was later discovered that the brain was actually a chess master of small stature.

The first documented discussion of computer chess is in The Life of a Philosopher by Charles Babbage (1845). Babbage, whose remarkable ideas in mathematics and science were far ahead of his time, proposed programming his Analytical Engine -- a precursor of the computer -- to play chess. A century later, Alan M. Turing, the British mathematician and computer scientist, developed a program that could generate simple moves and evaluate positions. Lacking a computer with which to run his program, Turing ran it by hand. Konrad Zuse, a German computer science pioneer, in his Der Plankalkuel (1945), described a program for generating legal chess moves. He even developed a computer, although he did not actually program it to play chess.

In spite of these earlier precedents, it was Shannon's efforts that laid the groundwork for actual research, and he is generally considered the "father of computer chess." Shannon's work was based, in turn, on the findings of John von Neumann and Oskar Morgenstern, game theorists who devised a minimax algorithm by which the best move can be calculated.


Key Components of a Chess Program

The minimax algorithm can be thought of as consisting of two parts: an evaluation function and the minimax rule. An evaluation function for any chess position produces a number that measures the "goodness" of the position. Positions with positive values are good for White, and negative values are good for Black. The higher the score, the better it is for White, and vice versa. The minimax rule allows the evaluation function values to be used. It simply states that, when White moves, White chooses the move that leads to the maximum value, and when Black moves, Black chooses the move that leads to the minimum value.

In theory, the minimax algorithm allows one to play "perfect" chess; that is, the player always makes a winning move in a won position or a drawing move in a drawn position. Of course, perfect chess is just a fantasy; chess is far too vast a game for perfect play, except when there are only a few pieces on the board. In practice, chess programs examine only a limited number of moves ahead -- typically between four and six.

Although minimax is very effective, it is also quite inefficient. In the opening position in a chess game, White has twenty moves, and Black has twenty different replies to each of these -- thus there are four hundred possible positions after the first move. After two moves there are more than twenty thousand positions, and after five moves the number of potential chess positions is into the trillions. Even today's fastest computers cannot process this many positions. The alpha-beta algorithm improves the minimax rule by greatly reducing the number of positions that must be examined. Instead of exploring trillions of positions after five moves, the computer only needs to analyze millions.