Much of our country's computing power is spent playing games. Here's why. . . .
Shannon's trees
In 1950, Claude Shannon proposed a way to make the computer win at checkers, chess, and other complicated games.
To understand his method, let's try to make the computer win a game of checkers. As in all checker tournaments, one player is called BLACK, and the other is called WHITE (even though his pieces are actually red). BLACK makes the first move. When a player can jump, he must. The game ends when one of the players can't move (either because he has no pieces or because his pieces are blocked).
To simplify the game, we'll play on a 4-by-4 board, instead of the traditional 8-by-8. Each player has two pieces instead of twelve.
This diagram shows 63 possible positions:
Position #1 is the initial position, from which black will move. The three arrows coming from position #1 represent the three legal moves he can choose from. Depending on which move he chooses, the board will wind up in position #2 or #3 or #4. Which move is best?
If he moves to position #2, white will reply by moving to position #5 or #6 or #7.
If he moves to position #3, white will reply by moving to position #8 or #9 or #10.
If he moves to position #4, white will reply by moving to position #11 or #12 or #13.
The diagram shows all possible ways the game's first five moves could go. Throughout the diagram, w means white man, b means black man, w' means white king, and b' means black king. The diagram's called a tree. (If you turn it upside down, it looks like the kind of tree that grows in the ground.) The arrows are called the tree's branches. The tree's depth is 5. Which position should black choose: #2, #3, or #4? The wisdom of your answer depends on how deep you make the tree. In this particular game, a depth of 5 is satisfactory; but in 8-by-8 checkers or chess you might have to dig deeper. Theoretically, you should keep digging until you reach the end of the game; but such a tree might be too large to fit in your computer's memory. For chess, Shannon estimated that a complete tree requires 10120 branches. Einstein estimated that the number of electrons in the universe is only 10110. If Shannon and Einstein are both right, the tree can't fit in the universe!
Having constructed a tree of depth 5, look at the bottom positions (#42 through #63) and evaluate them, to see which positions look favorable for black. You should consider many factors: which player has control of the center of the board? which player can move the most without being jumped? and so on. But to keep matters simple, let's consider just one factor: which player has the most men? Consider a king to be worth 1« men.
Subtract the number of white men from the number of black men: the result of the evaluation is a number, which is called the position's value. If it's negative, black is losing; if it's positive, black is winning; if it's zero, the game is heading for a draw.
For example, consider position #42. Since black has one man and white has two, the value is 1 minus 2, which is -1. That's why I've written ``v=-1'' underneath that position. The value of each position at depth=5 is computed by that method.
For the positions at depth=4, use a different method. For example, here's how to find the value of position #29. That position has two possible outcomes: #46 and #47. Which outcome is more likely? Since the move will be made by black, and black's goal is to make the value large, he'll prefer to move to #46 instead of #47. Since the most likely outcome is #46, whose value is «, assign position #29 a value of « also.
Here's the rule: to compute the value of a position at depth=4, find the maximum value of the positions it points to. (The value of position #29 is the maximum value of positions #46 and #47, which is «.)
To compute the value of a position at depth=3, find the minimum value of the positions it points to (since it's white's turn to move, and white wants to minimize). For example, the value of position #18 is the minimum value of positions #31 and #32, which is 1«.
Compute the values for depth 2 by maximizing, and the values for depth 1 by minimizing. Finally, you get these results:
The value of position #2 is -1.
The value of position #3 is 0.
The value of position #4 is -1«.
Since black wants to maximize values, black should move to position #3. If white is also a good player, the game will probably gravitate toward position #53, a draw. If white is a poorer player, black will win.
That method of choosing the best move was proposed by Shannon. Since it makes heavy use of minimums and maximums, it's called the minimax method.
Samuel's checkers
After Shannon, the next person to become famous was Arthur Samuel. He spent a long time (twenty years, from 1947 to 1967) trying to make the computer win checkers. He used Shannon's minimax idea, but made many improvements.
His first spectacular success came in 1962, when his program won a game against Robert Nealey, a former Connecticut checkers champion. After the game, Nealey said ``The computer had to make several star moves in order to get the win. . . . In the matter of the end game, I have not had such competition from any human being since 1954, when I lost my last game.''
Later, the computer played six more games against Nealey. Nealey won one of them; the other five were draws. In 1965 the computer played four games against W.F. Hellman, the World Champion. The games were played by mail. Under those conditions, Hellman won all four. But in a hastily played game where Hellman sat across the board from the computer, the result was a draw.
In 1967 the computer was beaten by the Pacific Coast Champion, K.D. Hanson, twice.
In short, the computer wins against most humans and draws against most experts, though it loses to the top champions. To bring the computer to that level of intelligence, Samuel improved Shannon's method in three ways. . . .
1. When choosing among several moves, the computer analyzes the most promising ones more deeply.
2. After computing the value of a position (by examining the positions under it), the computer writes the value on a piece of tape. If the position recurs in another game, the computer looks at the tape instead of repeating the analysis.
3. To compute the value of a position, the computer examines many factors in addition to the number of pieces each player has. The computer combines the factors, to form combination-factors, and then combines the combination-factors to form a single value. The relative importance given to each factor is determined by ``experience''. Samuel experimented with two forms of experience: he had the computer play against itself, and also had it analyze 250,000 moves that occurred in checker championships.
Chess
While Samuel was programming checkers, other programmers tried to write a similar program for chess. They had a hard time. In 1960 the best chess program that had been written was beaten by a ten-year-old kid who was a novice.
Greenblatt The first decent chess program was written in 1967 by Richard Greenblatt and his friends at MIT. It actually won a game in a chess tournament.
But in most tournaments, it lost. In 1970 and 1971, it lost every game in every tournament it entered.
Slate & Atkins In 1968, Atkins & Gorklen, undergraduates at Northwestern University, wrote a chess program. Inspired by their program, David Slate, a graduate student in physics there, wrote a chess program also. In 1969, Slate & Atkins combined the two programs, to form a better program, Chess 2.0.
During the next several years, they continually improved the program. Their most famous version was called Chess 4.7.
Their program is playing chess against human experts ___ and winning! Their computer has scored several triumphs in tournaments designed for humans.
