Computers in Chess

The notion of an inexact problem was introduced by the author several years ago [1], but no precise definition was then given. We now say that an enumerative task is inexact if it solves a problem by minimax methods on a truncated search tree (see the Glossary of Terms). The concepts of minimax procedure and search tree are well known; the concept of the truncated search tree may need explanation. Problems soluble by the formation of a tree of all possibilities (elementary actions) may differ in difficulty and may give rise to search trees of different sizes—small, large, or even infinitely large. If the resources of our information-processing device (speed and memory) are so limited that we cannot form the tree and search it exhaustively, we must either abandon the task or be content with an inexact (i.e., approximate) solution. If an inexact solution is acceptable, we limit the depth of the variations; the use of a depth-truncated tree and the acceptance of an approximate solution make the enumerative problem inexact. The definition of an inexact problem is therefore inextricably bound up with the general method of solution and with the resources of the information- processing system being used. If we can apply the minimax procedure to the complete tree, the problem is exact. (Problems may of course be solved exactly by other methods, e.g, by the use of equations or exact algorithms, and they may be inexact under other definitions, as when approximate solutions to equations are used. However, we shall use the narrow definition of an inexact task, as given above, and will not consider inexact tasks not conforming to it.

When the search tree is large it must be truncated. We may truncate near the root or further away. We can do the latter if the tree is narrow (Fig. 5). In a wide tree we must truncate near the initial position, i.e., the limiting depth of the variations is small.

When we meet an original situation and wish to use a decision-making program, we apply some of our historical experience indirectly, in the development of our algorithm and in the structure of the program. We form a deep and narrow tree of suitable size, expending substantial resources in time and memory. Usually, however, we also have direct historical experience, accumulated over the centuries and specifically related to the concrete problem that is to be solved. If we apply this experience, we can save our resources and obtain a faster and deeper solution. A specialist solving a problem always uses his knowledge and experience if the situation permits.

We have set forth the general postulates on which the solution of an inexact problem should be based. We shall illustrate their application by a concrete example—the development of a chess-playing program for an electronic computer. Chess, as we have already noted, is a typical inexact game—a model of a multi-level control system with a single information processor.

Even before the work on the program began, it was decided that the first trials would be made on chess problems. The solution of a problem by the program would be a very profitable experiment, and at the same time not too complex. One of the bases for a chess master’s strength is the calculation of variations; after this master capability had been formalized in the form of a program, it was subjected to an experimental trial by endgame studies. Some eleven compositions were prepared, but it turned out that we secured the information needed after only three experiments.

The First World Championship contest among chess playing programs took place in Stockholm in 1974, under the aegis of IFIP (the International Federation for Information Processing). The winner was the Soviet program KAISSA.