Static evaluation functions

Shannon [81] proposed that a move be selected by considering potential moves by White, replies by Black, counter-replies by White, etc. until relatively static terminal positions were reached. This examination of move sequences is commonly referred to as the look-ahead procedure and will be discussed at length shortly. Shannon proposed that each terminal position be evaluated in a mechanical way. He suggested a crude evaluation function which examined the material balance (9,5,3,3,1 for queen, rook, bishop, knight, and pawn, respectively), the relative mobility for each side (number of available legal moves), and pawn structure (penalties for doubled, backward, and isolated pawns). In his appendix he suggested additional factors for consideration such as control of the center, pawn structure adjacent to the king, passed pawns, centralized knights, knights or bishops in a hole, rooks on open files, semiopen files, or on the seventh rank, doubled rooks, attacks on squares adjacent to the enemy king, pins, and other factors. The idea was to weigh each of these factors according to its importance and then add all items together to determine the value of the terminal position. Once these values have been determined, the machine can select a move which would "lead toward" the most desirable terminal position.

Other factors for a general evaluation function have been suggested by Shannon's successors. Greenblatt and his associates at MIT [48] have included a "piece-ratio change" term that encourages piece exchanges when the machine is ahead in material and discourages piece exchanges when it is behind. The MIT group also included a king-safety term that encourages the king to remain on the back rank when queens are on the board. Church (see Chapter 6) has suggested that the king safety term should include the number of moves required before the king can castle. Turing [96] suggested a king-safety factor that "imagines" a queen on the king's square and subtracts points for the number of legal moves which the queen would have from that square. It is important to realize that king safety becomes less important as the number of pieces on the board diminishes and that in the end game the king-safety term becomes a hindrance. In the end game, for example, the Northwestern program (see Chapter 4) adds evaluation points if the opponent's king is close to the edge of the board.

In writing an evaluation function for a chess program, it is essential that efficient computer instructions be employed because this aspect of the program is used repetitively (i.e., ten thousand to 100 thousand times during each move selection). For this reason it is probably best not to include every conceivable evaluation term in the function since each new term means a small increment in the time which is required to evaluate each terminal position. A good evaluation function is one that assesses the critical aspects of the position in question and does this as efficiently as possible. For each new term which is added to the evaluation function one must ask if the chess information gained is worth the cost in computation time that this additional assessment will require. The time requirement is important, of course, because computers play chess using the same tournament rules as humans, such as requiring 40 moves in the first two hours of play.

The structure of the evaluation function is dependent on the type of look-ahead procedure which is employed. In a program such as Berliner's [12], the emphasis is on evaluating a small number of terminal positions (e.g., 500) in a very thorough manner and therefore a highly complex evaluation function is necessary. In programs in which a very large number of terminal positions are examined, the evaluation function must be very fast and thus simplistic. For example, the "Technology" chess program by Gillogly at Carnegie-Mellon [46] examines only the material advantage (or disadvantage) for each terminal position and looks at as many as 500,000 terminal positions before selecting a move in tournament play. At present it is not clear which strategy will eventually lead to the best machine chess although our present best model, the human, clearly uses the former approach rather than the latter.

Our experience in computer chess over the past few years seems to indicate that future chess programs will probably benefit from evaluation functions that alter as the general chess environment changes. Such "conditional" evaluation functions will consider the type of opening, the stage of the game, the pawn structure, and the king defenses and then construct an evaluation function appropriate to the particular position. Computer programming techniques that use a hierarchical structure involving "discrimination nets" and "decision tables" are useful for this purpose. This modification would make the machine's evaluation procedure more similar to human analysis.

+1 0

Post a comment