Artificial Intelligence Project - MIT & MIT Computation Center: Memo 41 - A Chess Playing Program - A. Kotok

The material below the line was reconstructed by me, the original author, from scanned images of a poor copy of this paper. I corrected typographic errors and reformatted the document to HTML. Otherwise, to the best of my ability, it remains as written. The date of the publication of Memo 41 is obscure. All the material after the Abstract was the body of my thesis (PDF), submitted in May 1962 to MIT in partial fulfillment for the degree of Bachelor of Science in Electrical Engineering. It refers to a number of appendices which were not part of Memo 41.

For completeness sake, it should be understood that this report, while written by me, represents joint work of "the chess group", which consisted of me, Elwyn R. Berlekamp (for the first year), Michael Lieberman, Charles Niessen, and Robert A. Wagner (for the third year). We are all members of the MIT Class of 1962.

Alan Kotok
MIT CSAIL
Cambridge, MA
3 December 2004


ABSTRACT


This paper covers the development of a chess playing program. The preliminary planning led to the decision to use a variable depth search, terminating at either an arbitrary maximum, or at a stable position. Two schemes of controlling material balance are discussed. Of major significance is the use of the "alpha-beta" heuristic, a method of pruning the tree of moves. This heuristic makes use of values obtained at previous branches in the tree to eliminate the necessity to search obviously worse branches later.

The program has played. four long game fragments in which it played chess comparable to an amateur with about 100 games experience.

INTRODUCTION


This thesis describes a chess playing program for the IBM 7090 computer. Although chess programs have been previously written, none of these played what could be considered "good chess". Before commencing work on our chess program, we studied the report published by Newell, Shaw and Simon covering previous attempts, such as the Los Alamos program, and Bernstein's program at IBM.

PRELIMINARY INVESTIGATION


The chess group, consisting of Messrs. Berlekamp, Niessen, Lieberman and Kotok, inherited routines for generating and making legal moves. With these as a basis, we decided to write a three move mate solving program for the purpose of familiarizing ourselves with the existing routines, and to come in contact with many of the problems we would later face in the actual general playing program. The three move mate program was completed in the spring of 1960. It was given problems from actual games, and successfully solved many of them. The three move mate program was written for the IBM 704, which was removed from the MIT Computation Center in the summer of 1960. Due to incompatibility with the incoming 709, the project was dropped at the end of the spring term of 1960.

In the fall of 1960 the chess group, without Mr. Berlekamp, began planning for the general chess program. It was decided to retain the original McCarthy/Abrahams move routines, and to continue coding in FORTRAN and FAP. The program was to be a variable depth search with a "stable position" termination. An evaluation was to be made at the terminal points of the move tree. This evaluation would be a weighted sum of such criteria as material balance, center control, pawn structure, "tempo" advantage, and development.

Moves on each level were to be proposed by "plausible move generators" which would propose moves to fulfill various goals. As the tree was searched, a backing up process would take place, in which the move declared best at each level by the evaluation would have its value brought up to the next higher level.

This procedure, also called mini-max, leads to a "principal variation" which is that set of moves which the machine considers most likely to happen. The evaluation always assumes that a player will always make the best move available to him at a given time.

It was, of course, recognized that any evaluation could not be perfect, since chess is a game in which the only way a position can be perfectly evaluated is to look to the end of the game, and see whether it leads to a win, draw, or loss. The only sound basis for an evaluation is that chess masters have, over the years, accumulated knowledge concerning the play of the game. For instance, a position in which a piece is "en prise" is considered bad, while having rooks on open files is considered good, even though the rules do not state anything about such things.

Since none of the members of the chess group are more than amateurs, we consulted books by masters to find out how much better it is to control the center than to have a strong pawn structure. These books are amazingly elusive on such details. Although many tips were given concerning the play of the game, relative importance of various strategies was uncertain.

We therefore considered having the program play for a while, and adjust the weights of the evaluation criteria to optimize its position. Although such a scheme seemed desirable, it was decided not to include any "learning" in the program due to the unavailability of suitably large amounts of computer time.

ORGANIZATION OF THE CHESS PROGRAM


Work on the chess program itself began in the spring term of 1961. The program is written in subroutine form, using the Fortran Monitor System of linkage. Where possible, programs are written in FORTRAN, and where it becomes too clumsy, or inefficient, FAP is used.

The actual implementation of the above mentioned "plausible move generators" has never been accomplished. Instead, we have a program, called REPLYS, which scans the legal move table, updates, evaluates, and reverts each move and orders them according to a single ply evaluation. (A ply is a half-move, i.e. a move by only one side.) The number of moves actually chosen is a function of the current depth in the tree.

Evaluation functions were written for material balance, center control, and development, since we intended to concentrate our efforts on openings until the program was thoroughly debugged.

The coordinating routine written in the spring of 1961, called TREE, employed the above mentioned mini-max scheme. REPLYS was set to cut the search at a depth of eight plies, or whenever the situation was stable, whichever came first.

The program was tested late in the spring of 1961. The 709 took about 5 to 20 minutes per move, depending on the complexity of the situation. Although the machine did not do too badly, we noted that it was looking at many irrelevant positions. We therefore attempted to find a method of pruning the move tree, without discarding good as well as bad moves.

Prof. McCarthy proposed a heuristic for this purpose, called "alpha-beta". It operates as follows: Alpha is a number representing the value of the best position which white can reach, using a pessimistic evaluation. Beta represents the best position white can reach, using an optimistic evaluation, due to the fact that black can hold him to this position. Under normal circumstances, alpha starts at -infinity, and beta at +infinity. At each level, optimistic and pessimistic evaluations are made, and compared to alpha and beta in the following way. If a white move is optimistically less than alpha, it is discarded, since a better alternative exists elsewhere. Likewise, if a white move pessimistically is better than beta, it too is discarded, since black had a better alternative previously; furthermore we revert two levels since no other white moves are worth considering at that position. The reverse strategy is applied for black.

The "alpha-beta" version of TREE was written during the summer of 1961, and was first put to use during the fall of that year. Also, we were joined by Mr. Wagner in the fall term of 1961.

After testing in the fall of 1961, it was decided that the material balance programs were insufficient. We therefore decided to replace the scheme then in use with a new, updated scheme. The programs then in use, and, as it happens, in use now, completely re-generate the material balance function at each position.

The material balance evaluator consists of two subroutines, SWAP and LTRADE. SWAP's function is to list all attacks and defenses on each occupied square. Secondary attackers which reside behind primary attackers (or defenders) are included. The pieces are listed in the order in which they would be played. Lowest valued pieces come first, unless the order is disturbed by the necessity of a higher valued piece to move first due to position. Pieces pinned to the king and queen were not recognized, leading to embarrassing evaluations. Likewise, discovered attacks were not considered.

LTRADE then simulates trade-off of all attacked pieces, and chooses the line most profitable for the side to move. The opponent is given the option of having a given piece taken, or moving the piece away. After all possible trades have been made, the program computes whether it is to the advantage of the machine to initiate an exchange, and if so, what the probable gain would be.

This scheme is both time consuming, and occasionally inaccurate. It was therefore decided to write a new evaluator for the material balance, which kept an updated set of tables, in a list structure format, from which the outcome of a given exchange could be found at a glance.

After a few months of planning and programming, the new list structure program was found to be impractical, due to excessive complication in the update procedure. Furthermore, the values which were to be included in the list were found to be no more accurate than the ones which the above scheme produced. The project was therefore abandoned.

DESCRIPTION OF COMPONENT SUB-PROGRAMS


The chess program is organized into a non-recursive hierarchy of sub-programs. Listings are to be found in Appendix 1.

ADMINISTRATIVE ROUTINES

(MAIN)

This is the highest level program. The on-line main program has the job of handling input/output, and timing. It determines the opponent's move by looking at the console keys, and picks the appropriate move from the legal move table. It then calls TREE which actually makes the move, after which (MAIN) prints out the machine's reply.

TREE

Tree is the second level of control. Tree has the responsibility of constructing the tree of legal moves. It calls REPLYS to generate a list of plausible moves, and enters those in the LISP table, which is the actual tree. The moves are then chosen in order of decreasing value, and updated. A new list of plausible moves is then generated for the opponent. The optimistic and pessimistic evaluators are called, and the alpha-beta tests are made, as described above. In the event that no replies are generated, due to stability, or excessive depth, a static evaluation is made and assigned to the position. The last move is then reverted, and the search proceeds down the next most likely branch of the tree. When all desired positions have been examined, the "best" move is returned as the answer.

PLAUSIBLE MOVE GENERATION

REPLYS

This program supplies lists of plausible moves to TREE. It updates each of the legal moves, evaluates the position and reverts. The number of moves presented is a function of the present ply. Current values in order of increasing ply are: 4 3 2 2 1 1 1 1 0 0. These are input parameters to the program.

EVALUATION ROUTINES

EVAL

Eval is the static evaluation program. Its function is to call all the subsidiary evaluation programs and to apply suitable multipliers, and hence form a weighted sum. Material values are: pawn 1, knight and bishop 3, rook 5, queen 9, and king 1000. These values are normally multiplied by 60 when combined with the other functions. Should one side be ahead at least 4 points, the material multipliers are adjusted to make trading off advantageous.

LTRADE

This program, described in more detail above, provides the projected material gain, considering all attacks and defenses.

ICENTR

The center control evaluator gives points for controlling the 16 center squares. Looking from either side, these values are:
8 8 4 4
4 8 8 4
2 4 4 2
1 1 1 1

The center control points are each worth 1/60 of a pawn. After the game passes the twentieth full move, the center control function is decreased in importance until the 30th move, when it is discarded.

IDVLOP

The development function, gives points for each developed piece. These range from 1 point per pawn, to 3 or 4 points for other pieces. Development points are weighted 1/15 of material points. This function is also eliminated as the game progresses.

JPAWNS

The pawn structure function, considers the following situations, with approximate point values:

open file
+8
isolated pawn
-1
backward pawn
-5
doubled pawn
-3
passed pawn
+10


These points are weighted 1/20 of material points.

SERVICE ROUTINES

UPDATE

Updates any legal move and records all relevant information on a push-down list. It then generates all legal replies available to the other side, using the general purpose move routines UPREV and PUTCH.

REVERT

Takes back the last updated move. This is actually another option of the the updating routine UPREV.

PUTCH

A lower level routine used in making moves. It keeps tables of almost legal moves and piece bearings updated. This table does not include castling, and "en passant" moves.

SWAP

Generates the list of all attacks and defenses on occupied squares, listed in the order in which the pieces would be played.

PINS

Generates the list of all pieces pinned to Kings and Queens. Includes the pinning direction, so that SWAP will only consider a pinned piece as an attacker or defender along the line of the pin.

INPUT/OUTPUT ROUTINES

PRINT

The major output routine. It handles most of the printing, both on and off line. It, and its subroutines, print the chess board, legal move table, principal variation, move tree and log of all moves tried, plus other information useful in debugging.

INITIA

Reads in any chess board position. Its input language is as follows:

The chess board is scanned, from left to right, starting at white's Queen Rook 1. Digits represent numbers of unoccupied squares. Pieces are represented by the normal chess notation, in its most explicit form; e. g. KBP for King Bishop Pawn. Black pieces are preceded by asterisks. After exactly 64 squares are specified, the character "." (period) signifies the end of the specification and that white is to move. "*." indicates black to move. Additional features include the ability to indicate promoted pawns, by stating the type of piece, followed by the name of the pawn which it promoted, in parentheses, e.g. Q(KNP). Also, it is possible to indicate that a piece has previously moved (for rooks, kings and pawns) by suffixing (M) to the piece name. Comments must begin and end with slashes.

The input is on IBM cards, punched in columns 1 through 72, taking as many cards as necessary. In case of errors found by INITIA, a comment will be printed, the remaining part of the problem will be skipped, and the next problem will be used.

All tables are initialized, and the program is set to commence with the legal move table generated for the side indicated. An example of an INITIA input will be found in Appendix 2.

RESULTS


As of this date, the machine has not completed any chess games. We have, however, played 4 lengthy fragments of games, and also have investigated many individual positions.

For our first long machine run, we chose an undergraduate student, Milton Garber, who held second place in his dormitory chess tournament. A record of this, and other game fragments is to be found in Appendix 3.

The second game was also played against Mr. Garber. In the record of this game a column indicating the principal variation is included. These are the moves the machine considers most likely to happen in succeeding plays, based on the evaluation and mini-max process.

In seventeen moves, the machine guessed correctly only thrice, including only one case where it predicted correctly more than one move ahead.

Figure 1 consists of a set of representative output for a single move. The first page is a printout of the chess beard, and a list of the opponent's legal replies, labeled MAVAIL. The second page contains the principal variation, beginning with the value of this variation, and the number of positions examined at the approximate rate of 1100 positions per minute. The principal variation itself commences with the machine's move.

The following pages contain the actual move tree. The moves listed therein are moves which were considered plausible by the reply generator. Move were considered in the order top to bottom, however all moves on level one were generated simultaneously, and all level two replies to each level one move are generated together, etc. The "value" column contains a value on each terminating position. Values of 131071 indicate positions discarded for alpha-beta cutoff. Terminating positions which have no values have not even been examined, since the alpha-beta heuristic found previous moves on that level to be either too good, or too bad.

A third game fragment was played against an amateur with little chess experience, in particular, he knew the game, and had played some before he came to MIT. The game progressed 34 moves before time expired, with the result that the machine was ahead 1 rook, 2 knights and 2 bishops.

From our analysis of the results, we have found that in its present state, the program is comparable to an amateur with about 100 games experience.

Most of the machine's moves are neither brilliant nor stupid. It must be admitted that it occasionally blunders. These blunders can often be traced to wrong multipliers in the evaluation, and occasionally to situations where discovered attacks, forks, etc. cause confusion. It is rare, however, not to find the correct move in the list of plausible moves.

This study is far from complete, but we feel that our efforts are proving fruitful. Hopefully this work will be continued.

Valid XHTML 1.0!