Origin of a Specie

A computer—above all else—computes. The part of the translation chain between voltage levels and mathematical computation was the easiest part to write. From there, things became harder.

Their work began with a “simple” challenge first issued in 1950: trans­late chess into computation.⁵ Looking back, it may be hard to remem­ber just how young the computing world was in 1950, but when Claude Shannon, a prominent communications researcher at Bell Labs, proposed chess as the first not-strictly-computational task that anyone ever asked a computer to solve, he had to explain that he planned to write a set of instructions that would “program” the computer to play chess, rather than to build a special chess-playing machine.⁶

Shannon approached the challenge through game theory. Several years earlier, a group of mathematicians and mathematical economists led by John von Neumann had shown how to translate games like chess into mathematical constructs called “game trees.” They had also explained the algorithmic steps needed to “solve” the mathematical equation implicit in the game tree, and to devise the optimal moves to make under any possible circumstance.⁷ If Shannon could implement von Neumann’s algorithm, he could teach his computer to play perfect chess. But there was a problem. While the game-theoretic algorithms were theoretical breakthroughs, and the game tree model gave Shannon a sturdy plat­form upon which to base his work, von Neumann’s pointers to chess­playing perfection suffered from a glaring lack of efficiency.

He decided to forego optimality, to settle instead for a program that would make pretty good moves much of the time. He augmented his computational algorithm with heuristics, shortcuts that embody tidbits of wisdom in an attempt to do pretty well, while making relatively few mistakes. Heuristics were radical at the time. Back when computers per­formed only computational tasks, tolerance for errors was limited. Programs that returned the wrong answer—even if only on rare occasions—were “bad.” Shannon’s consideration of computer chess taught him an immediate lesson about the evolution of the interface: If it was going to grow upward in any meaningful way, it would have to take risks. It would need principles that allowed it to issue educated guesses, even at the expense of an occasional mistake. His inquiry gave birth to the concept of heuristic programming.

Sound esoteric? Well, it was in 1950, but today it’s not. In fact, heuris­tic programming lies at the cutting edge of e-commerce. Heuristics are what allow Amazon to guess what books you may want to buy based on your past purchases. They’re what allow Yahoo! Music to know that I (and perhaps I alone) enjoy segueing from Yoko Ono to the Weavers. They’re also what allow the same program to posit erroneous connec­tions, such as suggesting that if I like Simon and Garfunkel, I’d proba­bly also like Mary J. Blige.

But Shannon had no way of knowing where his inquiry would lead some fifty years in the future. He wanted to integrate heuristics with algo­rithms to teach his computer how to play chess. He started by studying the game-theoretic algorithm for chess perfection. The underlying idea was fairly straightforward: Think about all of White’s possible openings. Now think about all of Black’s possible responses to each of White’s pos­sible openings.

Shannon saw two possible shortcuts that kept at least some of mimimax’s flavor: he could either look ahead only a few moves (rather than all of them), or he could consider only selected openings and responses (rather than all of them). Strategies of the first sort represent “brute force searches” of the game tree. They don’t really need to think about what they’re doing. The key lies in bookkeeping. They simply con­sider every possible alternate path until they run out of either time or memory space. When they reach a “horizon” lying several moves in the future, they apply heuristic information encoded by a programmer who knows something about chess to estimate the probability that each point on their horizon will lead to a win, apply the minimax algorithm to those estimates, and make the move that appears to be best. Strategies of the second sort define “selective searches.” They embody a good deal more heuristic information.

Shannon’s inquiry into chess programming led him to define both cat­egories of search strategies. Over the years, a number of researchers fol­lowed his lead, expanded his concepts, and turned them into powerful, generally useful algorithms. How general? And how useful? The current incarnation of these algorithms powers every commercial search that the Web has ever seen. Google, Yahoo!, Lycos, Alta Vista, HotBot, and even Lexis/Nexis—all can trace their intellectual underpinnings back to Shannon’s initial inquiry into computer chess. The evolutionary processes that he unleashed in his desire to find a not-strictly- computational use of his computer laid the groundwork for the infor­mation sector to absorb reference lookups into the realm of computing.

But again, Shannon wasn’t looking to revolutionize library science. He just wanted to play chess. And the truth is, he wasn’t even really inter­ested in that; his primary interest lay in using his computer to model human decision making. As a result, he outlined the pros and cons of both brute force and selective searches, programmed his computer to play pretty poor chess, and wrote an important and influential article about the experience. But his article had thrown down more gauntlets than he may have realized. At least two important groups of challengers arose to pick them up: the chess programmers and the AI researchers.

The chess programmers more or less missed Shannon’s point.

But they were wrong. And not because they were slouches at chess. They were just wrong. Take Mikhail Botvinnik, for example. Botvinnik was the greatest chess player of his time; he held the world championship for fourteen of sixteen years between 1948 and 1963. He was also a chess programmer. He developed a technique that he called the “chess master’s method,” and taught it to his computer, which he named PIONEER. Regrettably, PIONEER never learned how to play competi­tive chess. But Botvinnik was not beyond taking advantage of a lucky coincidence. His chess master’s method actually embodied some sophis­ticated, generalizable approaches to reasoning and decision making. Botvinnik put these approaches to use in his day job; the reconfigured PIONEER planned maintenance repair schedules for power stations across the Soviet Union.⁸ Nevertheless, Botvinnik’s experience did demonstrate an important type of software evolution: he helped to convert scheduling into a computational task and thereby moved the translation frontier upward.

But it was Hans Berliner, a correspondence chess champion and a Pro­fessor at Carnegie Mellon, who proved to be the most important of the chess programmers. Berliner extolled the virtues of selective strategies and derided the simple fools who advocated brute force approaches. He emerged as the most articulate priest of computer chess, developed several chess programs embodying his ideas, and entered virtually every available computer chess tournament. His programs never won, but defeat is effective in focusing the mind. After one-too-many brute force programs defeated his selective searchers, Berliner experienced an epiphany; in the mid-1970s, he began extolling the virtues of brute force approaches and deriding the simple fools who advocated selective searches. As luck would have it, he was right this time. By the mid-1980s he had assembled a team of students who stood Shannon’s original idea on its head. They built dedicated chess-playing machines named Hitech and Deep Thought.⁹ And Deep Thought was an excellent chess player. In fact, it was a good enough chess player for IBM to hire it and rename it Deep Blue. Deep Blue’s evolution continued at IBM, as it drew more and more chess knowledge out of the human environment, across the software interface, and into the computing environment. In 1997, Deep Blue met world chess champion Gary Kasparov for the second time— and won the match.¹⁰

And so, nearly fifty years after Claude Shannon set out to translate chess into a computational problem to enable software to evolve into the realm of chess, Gary Kasparov found himself losing a match to a fully evolved chess machine. Even those who missed Shannon’s basic point managed to make an important contribution to software’s evolution. That left only those who joined Shannon’s original quest to model human decision making: the pioneering researchers of AI.