Copyright (c) 2013 John L. Jerz

Computers in Chess: Solving Inexact Search Problems (Botvinnik, 1984)

Home
A Proposed Heuristic for a Computer Chess Program (John L. Jerz)
Problem Solving and the Gathering of Diagnostic Information (John L. Jerz)
A Concept of Strategy (John L. Jerz)
Books/Articles I am Reading
Quotes from References of Interest
Satire/ Play
Viva La Vida
Quotes on Thinking
Quotes on Planning
Quotes on Strategy
Quotes Concerning Problem Solving
Computer Chess
Chess Analysis
Early Computers/ New Computers
Problem Solving/ Creativity
Game Theory
Favorite Links
About Me
Additional Notes
The Case for Using Probabilistic Knowledge in a Computer Chess Program (John L. Jerz)
Resilience in Man and Machine

botvinnik4.jpg

Botvinnik explains his ideas for a computer chess program in this 1984 work

p.v One might expect that PIONEER [the name of the software program created by Botvinnik's team to implement his ideas] would have made substantial advances - unfortunately it has not. There are reasons: the difficulty of the problem, the disenchantment of the mathematicians (because of the delays and drawing out of the work), and principally the insufficiency and sometimes complete lack of machine time... our group of mathematicians works at the Institute for Electroenergy
 
p.16 As soon as the search tree is truncated, the exact goal of the game loses all meaning. It is necessary to introduce an inexact goal in the truncated tree; else the game becomes aimless and cannot be strong. The goal of an inexact game permits the formation of a deep and narrow [analysis] tree... To attempt to solve an inexact problem without having formulated the goal of the corresponding inexact game is to waste time. This goal is the basis of a strong algorithm for the solution of an inexact problem, and the basis for development of a deep and narrow tree... The goal of a game says what our aim is; only when we know this can we identify courses of action that cannot lead to our target, and exclude them from the tree. Knowing the goal lets us define the lines along which the search is to occur.
 
p.38 The positional estimate should not be a general-purpose affair; it should be specific to each given situation. A general-purpose estimate might, for instance, be applicable to 67% of the positions encountered, and wrong in 33%; the current position might fall in the latter group. We must give Capablanca due recognition in this respect; in a polemic [polemic: A controversial argument, especially one refuting or attacking a specific opinion or doctrine] with Znosko-Borovsky, author of The Theory of the Middle Game in Chess, Capablanca pointed out that the basis for a positional estimate is the control of fields [apparently, this is an uncited reference to Capablanca's book A Primer of Chess, p.115, 116, 117 - JLJ]. Control of fields does not mean control of the whole board, but control of only those fields that may be used in the impending play. Therefore, one must strive for control of the field consisting of those trajectories in which the pieces can move, but have not moved yet.
  At the node in the search tree where we find ourselves at a given moment, we must unravel all those sheaves of trajectories which have not yet been developed and determine which player has control of the majority of the fields consisting of  the trajectories not yet used in the play. This allows us to forecast the result of the play - the result of a search which, in particular, had to be renounced at the terminal nodes of the variations for lack of resources.
 
p.38 We shall show later that the positional estimate allows us to solve the question of priorities... Thus the positional estimate, with the development of the sheaf of trajectories, should be produced at every node in the search tree . We may assert that the squares under control define the usable mobility and maneuverability of the pieces. Better maneuverability of pieces often also determines the positional superiority.
 
p.39 It was assumed that the control of squares involves only those pieces that lie at a distance of one move from the controlled square (and a blockading piece must lie on the square itself).
 
p.39 To sum up: The positional estimate is computed at every node of the search tree. The procedure is substantially more complex than the procedure for computing a material score. All sheaves of trajectories included in the play but not yet used (in whole or in part) are taken into account in computing the positional value.
 
p.39 The positional estimate at a given square in a trajectory is computed only up to, but excluding, the first square at which it ceases to be positive, and this determines the movement of a piece along its trajectory... we see that we may get a first approximation on those trajectories on which the pieces have not yet had time to move.
  Thus the basic factor in the positional estimate is proportional to the ratio Kw / Kb, where Kw and Kb are the numbers of squares controlled by White and Black, respectively.
 
p.64 [Botvinnik describes the capabilities of two computers playing a 1977 demonstration game] KAISSA used a computer with a speed of 3 [million] operations per second, CHESS 4.6 had a speed of 12 [million] operations per second. KAISSA could calculate variations to a depth of 5 plies; CHESS 4.6 could go to 6... In the end [game], KAISSA extended the length of a variation to nine plies and CHESS 4.6 went to twelve.
 
p.67 Since 1964, when the author began to seek support for his algorithm, there have been many critical remarks; these are worth reviewing. It has been said that this is all fantasy: it conflicts with the accepted canons; it demands more resources than does a full-width search; it would require decades for development.. and so on.
 
p.105-106 [section written by Tsfasman and Stilman] The concept of the positional estimate plays an important role in chess programs... The positional estimate proposed by Botvinnik is based on the control of squares in trajectories... We must first define the nonfrozen trajectories of the pieces... Then for each trajectory... we develop a list of pieces lying one move away and compute the outcome of the optimal exchange on the given square. The square is traversable if the result of the exchange is advantageous to the side possessing the trajectory. If the given square is traversable and belongs, say, to White, Kw is increased by 1... This unravelling of all non-frozen trajectories in the included fields is a time-consuming process.

Enter supporting content here