COMPUTER CHESS
by Dan and Kathe Spracklen

Dan and Kathe Spracklen are the authors of Sargon, the most popular chess playing program for home computers.

Ever wonder how a computer can play a game of chess? Just think about it. Chess is a strategy game. You have to study the board and plan how to maneuver your pieces. Finally, after devising a complex strategy, you play the decisive move-checkmate! How can a computer study a chess board? How can it make plans? How can it checkmate?
    Taken all at once, the problem might seem unsolvable. But the job can be broken down into three main parts:
    1) The mechanics phase: describing a chess board and pieces in a way the computer can understand and teaching it how to move the pieces according to the rules of chess.
    2) The search phase: looking ahead at what can happen as the game progresses. The computer still can't make real plans the way a human does, but instead must look at thousands of possibilities-many times more than the human mind can handle.
    3) The evaluation phase: sizing up the merits of a particular position on the chess board. It wouldn't do any good for the computer to look at all those positions if it didn't know which ones were better than the others. Sure, it might know when the other guy is checkmated. But if mate isn't in sight how does it know what to do?
    We'll take a look at how the Sargon chess program handles each of these phases, then discuss some of the computer chess player's limitations and how they might be conquered.

    In this famous game between two past world champions, White mounts an attack against Black's King. Nine moves later, faced with inevitable mate, Black resigns. How can a computer simulate this complex activity of the human mind?

Setting Up the Board
A human can look at a chess board and see black and white squares with pieces sitting in various places. A computer can only deal with numbers. To the computer, the chess board is an area of memory-64 locations set aside to represent the real board. A value of zero in a particular location indicates that the square is empty. A chess piece must also be a number for the computer. For instance, we might assign the following codes to the chess pieces:

1- White Pawn 2 - White Knight 3 - White Bishop 4 - White Rook 5 - White Queen 6 - White King

7 - Black Pawn 8 - Black Knight 9 - Black Bishop 10 - Black Rook 11- Black Queen 12 - Black King

Thus the chess board and pieces would look like this:

    Moving the chess pieces, then, becomes an arithmetic process. If we number the board squares from 1 to 64, moving a White Pawn up two squares can be accomplished by adding 16 to its starting location. A Rook can be moved one square to the left by subtracting 1 from its current square number. Other pieces can be moved by simple addition and subtraction operations as well.

    Unfortunately, there is a problem associated with this simple scheme. Take, for example, a Black Rook standing on square 57. It can't move to the left because it's already at the left edge of the board. If we try to move it one square to the left by subtracting 1 from its current square number, we get square 56. That's a valid board square under this system, but it's not a legal Rook move so a border is added to the board. The extra locations are filled with a new code:

-1 = Off Board

    Using this new code solves the problem. Moves are still addition and subtraction operations, but the amounts added and subtracted are a little different from the other numbering. You might notice that the border is two squares wide. That's because Knights can jump that far. With the border, the board now looks like this:

Looking Ahead
In trying to decide on a strategy, a human chess player tries to combine general concepts such as putting pressure on a weak point with specific variations ("If I go here, then he'll go there"). The number of specific variations a human can handle is quite limited; the rest must be left to intuition and experience. The computer, with its vast calculating capability, can look at many thousands of variations while making a single move choice. It is this calculating power that first frightened human chess masters and still overwhelms the novice to intermediate player when faced with a computer opponent. But why can't computers outcalculate the masters and look ahead to a won position from the earliest moves of the game? The answer to this question is the fundamental problem of computer chess. Let's look again at the position from the Alekhine-Lasker game shown at the beginning of this article. The game continued as follows:

1. Q-Q6 2. R(KB1)-Ql 3. Q-N3 4. Q-N5! 5. N-Q6 6. P-K4 7. R-Q3 8. N-B5ch 9. QXP!

N(K4)-Q2 R(Rl)-Ql P-N3 K-R1 K-N2 N-KN1 P-B3 K-R1 Resigns

In this final position, if Black does not take the Queen, White will mate with Q-N7. If Black does take the Queen, White mates with R-R3.
    You might think a computer capable of examining thousands of positions per move would certainly be able to look nine moves ahead and find the winning line. But you'd be wrong! Here's why it can't. In the starting position, White has


for a total of 44 legal moves.
    Suppose we start the look-ahead search by trying P-QR3. In the resulting position, Black has


for a total of 35 legal moves.
    If we assume that each of White's possibilities will give Black the same number of legal responses, the computer would have to examine about

positions just to look one full move ahead. To look nine moves ahead would require examining approximately

44 x35 x44 x35 x44 x35 x44 x35 x44 x35 x44 x35 x44 x35 x44 x35 x44 x35

different positions. Though this is an unthinkable task for the computer, Alekhine surely saw the outcome of his plan. With the limited calculating power of the human mind, he could perform the needed look-ahead-a task beyond the vast calculating power of the electronic brain.
    Undoubtedly the reason Alekhine succeeded was that he didn't have to consider all 44 legal moves in the first position. For example, a mating attack seldom begins with 1.P-QR3. This process of elimination, called forward pruning, is the basis of one solution to his dilemma. Typically, 7 to 9 moves might be chosen from the 30 to 40 possibilities. The problems of forward pruning are twofold: on the one hand,

7x9x7x9x7x9x7x9x7x9x7x9 x7 x9 x7 x9 x7 x9

is still an unmanageable number; on the other hand, one of the moves not looked at might well be the best line of play.
    Another approach to the explosion problem is to take advantage of some of the mathematical properties of the search to rule out examining certain branches. Called alpha-beta pruning, this technique uses the assumption that if the computer can, for example, force the win of a Pawn along some line of play, it will not choose instead to lose a Bishop. These "loser" lines can thus be cut short. The principal advantage of alpha-beta pruning is that it produces the same move that the computer would play with no pruning of any kind, and it does this in about the square root of the time it would take the non-pruning search. With alpha-beta pruning, the Alekhine-Lasker position is still out of reach, but the level of play is strong enough to give tough competition to all but the expert or master-strength player.

Positional Judgment
Each time the computer evaluates a new position, it must assign a numerical score indicating how "good" the position is. Checkmating the opponent is infinitely good; being checkmated is infinitely bad. In between is the hard part. The Sargon program's evaluation function is heavily dependent on the material balance. Many times, chess masters will willingly give up a Pawn in exchange for an advantage in position. By contrast, Sargon will give up nearly every positional advantage it possesses in order to win a Pawn or avoid losing one. If material and position were weighted more evenly, the program would give up Pawns inappropriately and thus lose for lack of material.
    Quantifying chess concepts like mobility, attacking potential or piece placement is far more difficult than encoding pieces and moves. The rules of chess are fixed and inviolable, but the principles for good chess play are full of conditions and exceptions. Computer chess programs are boxed in by two interrelated difficulties. On one hand, the explosion in move possibilities limits how far ahead the program can calculate; on the other hand, evaluating the positions the computer can reach is a shaky approximation at best. The two problems are interrelated, since improving the evaluation might well take so much processor time that the depth of search is cut short.
    One easy solution is to wait patiently for computers to become faster. Although this will surely happen, we should realize that a computer running about thirty-six times as fast as current machines would only get about one move deeper in the look-ahead.
    A more tractable approach is to concentrate on improving the evaluation function (while keeping a close watch on the time it consumes). For instance, a chess player's "sense of danger" will certainly be aroused by an unprotected King. Programming a "sense of danger" could involve nothing more than reducing the evaluation score for the same situation. Gaining a better understanding of the worth of a Pawn, compared to certain positional criteria, could produce a marked improvement in the machine's play.

IMPROVING A CHESS CLASSIC When we wrote Sargon III, the sequel to our Sargon II chess program for microcomputers, we included the following two substantive changes that greatly enhanced its overall chess-playing abilities. • Rank and file. An improved mathematical model represents the board, employing a grid system with square designations that can be broken down into two parts: the rank (row of the chess board) and the file (column of the board). Such a system greatly simplifies encoding chess strategy. Where previously the program had to calculate the new square number before it could look at the board array to see what was stored at that square, in Sargon III the square value itself tells if a piece has attempted to move off the board. • Capture search. Speed is the greatest single limiting factor in the look-ahead process. The more quickly a given position can be created and evaluated, the more positions can be examined and the deeper the search can explore. Sargon II stopped at every move to be evaluated and took a long, hard look at the possible piece exchanges and the expected outcome of each; called a "static exchange evaluator," this process could examine about twenty-three positions per second on the Apple II. Sargon III uses a faster, more accurate method, the "capture search," which determines the value of trades by actually making them on the board. Once it reaches a position that it would like to evaluate, this process generates a restricted set of moves: captures only. It keeps generating captures until 1) there are no more captures possible, or 2) the remaining captures available lose more than they gain. This, with other improvements in the search, means that Sargon III on the Apple II can evaluate some 250 positions per second.     Sargon III's evaluation function benefited from the revised method of storing the board in memory and from the improved method of examining exchanges. But improvements in positional analysis cannot be summed up in one or two sweeping changes that make everything simpler or faster. It is always difficult to translate abstract human knowledge into a mathematical formula. ("Keep up pressure in the center," the master says. But how do you describe "pressure" to a computer?) In the end, refinements are the sum of more and more little pieces of knowledge finally translated into algorithms.     Guided mostly by your comments and letters about Sargon II, we also addressed the questions of how the program presents itself to the user, what you can do with it and how easily you can do it. Since we made a great many changes in this respect, you might say this is the part of the program that you improved. D. AND K. SPRACKLEN

---

Return to Table of Contents | Previous Article | Next Article