Former world chess champion Mihail Moiseevich Botvinnik introduces
his ideas on how to program a computer to play chess. Botvinnik was to later refine his ideas in his 1984 work Computers
in Chess: Solving Inexact Search Problems.
I have to confess that I was somewhat unfamiliar with his ideas
when I put together A Proposed Heuristic for a Computer Chess Program. I'm not sure that I understood exactly what Botvinnik
was trying to say the first time I read his work, which read like a collection of ideas. In addition, the discussion
boards I visit rarely mention specific details of his work or the possibility that the concepts he discusses are worth time
and effort investigating. A Proposed Heuristic and Computers, Chess and Long-Range Planning
are similar on a superficial level, once one gets over Botvinnik's extremely difficult to understand notation. This is not
surprising, since both works approach the concept of long range planning, and both spend considerable amounts of time looking
at the potential ability of the pieces to realistically accomplish objectives in the future. Each paper considers the restrictions
of the present pieces on the board when determining the 'attacking potential' of such pieces. Botvinnik struggles with
the concept of search focus throughout his entire paper. He outlines a process for generating lines of analysis,
but he fails to communicate exactly how to perform the search without falling into a trap of recursion.
[preface to the Russian version] "One cannot say that Botvinnik's method is completely worked out.
There are positions in which his algorithm appears to offer no clear prescription for the choice of a move. A whole string
of questions remain that can be solved only when Botvinnik's ideas have been realized in a program and run on a machine."
p.xi"An Algorithm [Botvinnik refers his work by the title
of the Russian version of this book, An Algorithm for Chess] is a hypothesis about the intuitive thought process
of a chess master. Like any hypothesis, An Algorithm needs to be tested by experiment; in this case, an experimental
test means writing a program and running it on a machine. This task has been taken on... by a young mathematician and first-class
chess player, V. Butenko."
For Botvinnik, there is only one approach he can see (as a chess player) to writing a successful
computer chess program, and it is contained in his book. It is not presented as a completed idea, and he admits that it needs
to be completed and tested. Botvinnik implies that he will be participating more in the development when the initial coding
is complete.
Perhaps since his time is best spent running his chess school (probably a good idea) it would not
make sense for him to learn to program and put the ideas together himself.
p.xii"As a chess player I see no way to solve the problem of choosing
a move in a chess game but via the path sketched out in An Algorithm . I hope that this edition of An Algorithm
will give new impetus to the testing of this hypothesis and will hasten the accomplishment of the tasks laid down by Shannon
in 1950."
Botvinnik notes that the working chess programs circa 1970 all use Claude Shannon's ideas, which
he is critical of. He also seems to miss the concept that Shannon's evaluation 'number' also functions as a heuristic to focus
the search efforts of the machine. Neither applies the concepts of system dynamics.
p.2"If the rule for excluding weak moves is well founded, the processing of the information is more
fruitful and the scan of alternatives is deeper... At the outset, we must acknowledge our debt to Shannon's insight. All computer
programs for playing chess published by mathematicians in recent years are basically no different from those established in
principle by Shannon... The use of the given weighting function to evaluate a position [the approach specified by Shannon]
is also a doubtful procedure. Shannon proposed the inclusion of numerical 'weights' for the material relation of forces, open
lines, mobility of the pieces, advanced and doubled pawns, control of the center, and so on, which are listed in every manual
for beginners. We should note, as the authors of the textbooks usually do, that it is far from necessary to take account of
all these factors at all times and that their calculation yields only a sketchy estimate of the [winnability of the] position.
To sum up, the mathematical goal of a game of chess, according to Shannon, is a number - the value of the weighting function."
Botvinnik condemns man for the weak chess-playing ability of computers, circa 1970. We must master
both chess and programming in order to construct a good chess program. Perhaps we also need to master system dynamics, the
construction of an effective model, and borrow concepts from the study of ecosystems. Having a good strategic plan would also
help.
p.5"The machine may play chess badly, like a beginning amateur, but the machine is not guilty. Man
is guilty. He has not yet succeeded in teaching the machine, in transferring his experience to it... To write a finished program,
one must master both chess and the art of programming."
Botvinnik is determined to create a chess program in the image of the human mind. But the machine
1. lacks the accumulated experience of that mind, 2. lacks the human ability to perceive stress in a position, 3. lacks the
human ability to construct resilient positions, and 4. lacks the human ability to model feedback structures. Can we therefore
represent experience by an 'algorithm'? It would seem easier to do with a generalized dynamic heuristic which gathers information
from the pieces in their present position on the board and their interactions.
p.7"Man solves inexact problems by relying on his accumulated experience and on intuition. The following
method for creating an exact program for the solution of inexact tasks therefore suggests itself: the program must be
modeled on human thought processes... It seems to me the only real way."
This opinion is in sharp contrast to Shannon, who has declared, "It is not being suggested that
we should design the strategy [of the evaluation function and search] in our own image. Rather it should be matched to the
capacities and weakness of the computer." One has to add that all existing chess programs use Shannon's approach, and none (so far) use Botvinnik's approach.
For Botvinnik, chess is a game where certain intangible parameters related to material and positional
advantage are exchanged and fought for by the players. Perhaps this is the concept we need to teach the machine.
p.9"In my opinion, the process of playing chess (and probably any game) consists in a generalized
exchange. By this term we mean an exchange in which (in the general case) the values traded may be tangible or positional
('invisible,' situational). The goal of a generalized exchange is a relative gain of these tangible or positional (situational)
values. There are not and cannot be other goals. In the end, this generalized exchange process in chess must lead to the winning
of infinitely great tangible value (i.e., to mate)."
What are the fundamental units of positional play, Botvinnik wonders. Perhaps we can use a
reference such as How to Measure Anything (Hubbard, 2007) and figure out how to measure the 'intangible' elements of positional evaluation.
p.9"The tangible value of the pieces in chess is well known to all beginning chess players. But
what of the invisible, conjunctural (positional) value of the pieces? This value depends on the position of the piece and
on the role of the piece in the general combat taking place on the board. The positional value of a piece is subject to sharp
changes"
Botvinnik declares that it is essential for a chess program to answer three questions:
p.10"We shall assume, moreover, that the algorithm imitates the mode of play of the human, that
is, it defines a scan and an evaluation of the available moves. The scan, however, is controlled... What must the algorithm
now envisage? As a minimum, it must envisage a solution to the following three problems: 1. How to limit the number of
alternatives... 2. When to stop computing a variation... 3. What move to make if the analysis of variations
gives no clear answer.. The solution of these three problems is essential, even though we may later find that it is not
sufficient."
The value we should place on a piece is related to its ability to attack our opponent's pieces.
Moves to support our own pieces have value in the sense that they negate an opponent's ability to attack, even if
a surprise move is played that we did not expect. If there is no potential for an enemy to attack, then defensive supporting
moves have little value at present.
The Russian school of chess teaches basic principles of the game, including the importance of analysis
of variations, that the attacker is the one who wins, and that an advantage is gained in a position insofar as it supports
an attack (see works by Kotov Play Like a Grandmaster by Kotov for a more thorough explanation of this). Therefore it is not surprising that the principles of analysis of variations
and of the lines of attack feature prominently in Botvinnik's computer program. It is, in his mind, a validation of the concepts
taught at the Russian school of chess. These concepts are correct, period, and so they must form the foundation for a
computer chess program, period.
p.13"An attacking piece has an intangible value or values in addition to its tangible value; its
total value is the sum of the tangible and intangible values. The intangible value of an attacking piece reflects its ability
to annihilate an enemy piece."
This attack must take place via squares on the chessboard, and these squares in turn are attacked
by other pieces. We can negate a piece's ability to attack by denying it the mobility through a square. Here is where we must
yield to system dynamics and conceed that the situation is fairly complicated.
p.14"The Path of a Piece: An attack must have real features. There must be an object of attack and
a path, made up of actual squares, over which the attack is to be carried out. These squares are of two types: 1) squares
where the pieces come to rest, which we shall denote by a, and 2) squares over which
the pieces pass, denoted by b. There must always be a-squares;
there need not be b-squares. When the King, the Knight or the Pawn makes a move
(except for castling and the initial two-square move of the Pawn) there are no b-squares.
Similarly, there are none when the Queen, Rook or Bishop moves to an adjacent square."
Positional play begins by noting the paths that pieces take to attack other pieces, and the presence
or availability of still other pieces to support or hinder such attacks.
p.22"If the attack path is unsafe (closed) the master... looks about him: can he bring other pieces
into the game, to better the attack paths (the functions) against the enemy pieces and lessen the attacks against his own
pieces? This is what 'positional' play amounts to.
I believe that this part of the theory (on positional warfare) is radically different from
what has been presented up to now."
Play may proceed to attack these "mobility paths" which enable pieces to attack or pressure other
pieces. While it will be difficult and expensive time-wise to determine 'for certain' whether a piece can trace mobility through
certain squares, we can, if we wish, use a quick heuristic to estimate such mobility towards a remote target.
p.23"Play directed at changing a [future piece mobility] path has the same character, and proceeds
by the same formulae, as play for annihilation, with the distinction that now the object of attack is not an enemy piece itself,
but a change in the attack-functions [piece mobility]."
Botvinnik's design directs the chess program to build an analysis tree similar to the
way a chess master conducts his analysis when playing a chess game. He wonders out loud if there is a way to construct
a 'positional evaluation' in the style of Shannon, which reduces each position to a number, rather than an analysis tree.
If this is possible, he reasons, it might be an improvement on his algorithm.
p.23"One possibility for improvement [Botvinnik is in the middle of explaining his algorithm] that
comes to mind is the use of modern mathematical methods to define moves most likely to lead to success. Then to every 'positional'
move there would correspond a weighting function (a number) which would allow the definition of the most useful move, by a
more perfect method than the chess master now uses."
Botvinnik decides to place the pieces on the board in one of 4 categories. Type IV pieces are
not within a reasonable attack window of any piece. Type III pieces lie within an attack window, but are currently safe. Type
II pieces are subject to imminent capture, and Type I pieces have already been captured and removed from the board. Positional
play for Botvinnik lies in moving pieces from type IV to Type III categories, and vice versa, via careful maneuvering. It
is assumed that tactical play will handle the maneuvering to place pieces in jeopardy (Type II) and eventual capture (Type
I).
p.24"Positional play consists in converting Type IV values [pieces not in the line of sight of enemy
pieces] to Type III [pieces within the realistic future mobility 'horizon' of enemy pieces] (and the reverse)."
Botvinnik thinks that his algorithm describes how a chess master plays a game of chess. But he overlooks
the fact that a chess master is using heuristics to focus his attention on likely moves in order to build the analysis tree.
We would need to come up with a machine-version of this process, and would need to do so without access to the chess master's
lifetime memory of positions and observations of interactions between the pieces. We would also have to do so without involving
any further search, as we would then fall into a trap of recursion where our efforts to define likely moves rely on further
efforts, in a way that does not terminate. Our heuristic for focusing search efforts will need to be be effective in
all types of positions. Perhaps it will begin with a general-purpose diagnostic test, or tests. We can develop a set of vital
diagnostic tests, and focus our search efforts to improve the scores of the weakest, vital diagnostic test. For example, if
our King ends up in the middle of the board, we recognize this and reward our machine to return the King to a safe spot. Sustainable
development cannot happen with any of our vital diagnostic tests that score in the "red" zone.
p.26"The reader is now familiar with the principles involved in constructing and analyzing a mathematical
map of a chess position. I believe that the chess algorithm presented in this book and based on these principles represents
the thought process of a chess master during a game"
p.40-52 Here Botvinnik works out an example, using the position in the diagram below.
