How did Claude Shannon propose that a computer could play chess?

Before any computer had played a single game of chess, Claude Shannon wrote down how one could. His paper, "Programming a Computer for Playing Chess," is short and readable, yet it lays out the method that chess programs used for decades: give the machine a rough way to judge a position, let it imagine the moves ahead, and have it assume the opponent will always answer as well as possible.

Shannon was a mathematician and engineer at Bell Telephone Laboratories in Murray Hill, New Jersey, already famous for founding information theory, the mathematics of sending messages efficiently. He first presented the chess work at the National IRE Convention in New York on March 9, 1949. (The IRE, the Institute of Radio Engineers, was a professional society for electrical engineers.) The written version appeared in the journal Philosophical Magazine in March 1950.

Why chess?

Shannon was not really interested in a chess machine for its own sake. He said so at the start: the practical value was small, but solving chess might open the door to machines that design circuits, route telephone calls, translate languages or carry out logical deduction. All of those involve judgment and trial and error, not just arithmetic.

Chess, he argued, was the ideal test bed. Its moves and its goal are perfectly clear. It is neither trivially easy nor hopelessly hard. And people generally agree that playing it well requires thought, so a successful program would force us either to accept that machines can think in some sense or to narrow what we mean by thinking.

The problem of too many moves

In principle, a computer could play perfect chess by examining every possible continuation to the end of the game. Shannon showed why that is out of the question. A typical position offers about 30 legal moves, so one move by each side gives about a thousand possibilities. Over a game of roughly 40 moves, that adds up to around 10 to the power of 120 different variations. Even checking one variation every millionth of a second, the first move alone would take more than 10 to the power of 90 years.

So the goal was not perfect play. It was skillful play, perhaps as good as a strong human.

Shannon's recipe: score, then search

The first ingredient is an evaluation function, a formula that gives any position a number: positive if it looks good for White, negative if it looks good for Black. Shannon's example counted material using the values chess players already knew (queen 9, rook 5, bishop and knight 3, pawn 1), subtracted a little for weak pawn structures, and added a little for mobility, meaning how many moves a side has available. He stressed that it was crude and only made sense in quiet positions, not in the middle of an exchange of pieces.

The second ingredient is look-ahead. The machine considers each of its moves, then each reply, and so on to a fixed depth. At the end of each line it applies the evaluation function. Then it works backward: on the opponent's turn it assumes the reply that is worst for the machine; on its own turn it picks the best. Taking the minimum on one side and the maximum on the other is why the method is now called minimax.

Here is a tiny worked example with two candidate moves for White and two replies for Black:

Move A can lead to +3, but a careful Black will answer with Reply 2, leaving White at -2. Move B guarantees at least +1. Minimax chooses Move B: not the move with the best possible outcome, but the one with the best outcome against good defense.

Type A and type B

Shannon saw that searching every move to the same depth, which he called a type A strategy, would be slow and weak. Looking three moves ahead for each side would mean about a billion evaluations per move, more than sixteen minutes each even at a very optimistic speed.

He proposed a smarter type B strategy, modeled on how strong players think. Follow forcing moves, such as checks and captures, further than quiet ones. Stop only when the position has settled down. And screen out obviously pointless moves early, while taking care not to discard moves that merely look bad at first glance. He added touches that later programs adopted too: a stored book of standard openings, and a small random element so the machine would not repeat the same losing game.

He was frank about the weak spot: such a machine would not learn from its mistakes. Only a better program could improve it.

How do today's chess programs differ from Shannon's plan?

For most of the next fifty years, chess programs followed Shannon's blueprint closely: an evaluation function written by people, plus minimax search. Early programmers favored his selective type B approach, but by the 1970s faster hardware and better search techniques made deep type A style search stronger. IBM's Deep Blue, which beat world champion Garry Kasparov in a six-game match in May 1997, still belonged to this family of programs that combine a scoring formula with a deep search.

The big change came recently. In 2017 DeepMind's AlphaZero learned to judge chess positions with a neural network instead of a hand-written evaluation function, and in a 100-game match it beat the leading conventional program, Stockfish, without losing a game. It also replaced classic minimax with a different, sampling-based search.

In a sense, AlphaZero answers the weakness Shannon pointed out in 1949. His machine could not learn; AlphaZero's judgment of positions is entirely learned. Yet the bones of his plan are still visible: a way to judge positions, and a search through possible futures that assumes a capable opponent.