Statistics for the Chess Computer and the Factor of Mobility
Proceedings of the Symposium on Information Theory, London, 1950. Reprinted (1988) in Computer Chess Compendium, pp. 113-117.
Shannon has argued that the problem of providing a programme for a chess‑playing computer is of theoretical interest, and its use might lead to a wide range of practical developments. The problem is also interesting psychologically. If the human and the mechanical players are to play the same game, they will each have to be directed by concepts which have a certain equivalence. But the concepts used by the skilled human chess‑player are both subtle and complex, and for the purpose of programming a computer they will have to be reduced to their simplest form. Chess‑masters are, as a class, men of considerable general intellectual ability, and come from the ranks of professional in mathematicians, scientists, lawyers, etc. They have in addition a special ability. Very few chess‑masters, who began the game early, did not show unusual excellence at it at a very early age. The specific chess ability begins to show itself, given the opportunity, at about the age of eleven. Furthermore, there are few, if any, chessmasters who cannot play blindfold, and play many games at once, achievements which are entirely beyond the powers of the ordinary player. The order of intellectual activity which we are required to reduce to simple terms is therefore of a superior kind.
Shannon has suggested that one practical strategy of the chess computer would be for it to combine a deeper analysis of forcing variations with a two‑ three‑move analysis of development in more quiescent positions. Both are necessary if the machine is neither to fall into simple tactical, traps, nor to fail to develop its pieces in an adequate way. The present investigation is confined to the latter aspect of play. Statistical data have been taken from the games played in the following tournaments: St. Petersburg 1914, New York 1916, London 1922, Hastings 1922, Keoskemet 1927, Capablanca‑Alekhin match 1927, Alekhin‑Euwe match 1933.
It would simplify the problem of programming the computer if it could be provided with only a few parameters for the measurement of a given chess position. The total value of a position would then be the weighted sum of the values of these parameters, i.e. the directive for the machine would be a discriminant function which could be calculated by the statistical analysis of chess positions of known value. Shannon has given a list of fifteen features which should be evaluated by the machine. It is submitted that this list could be simplified. The three noteworthy parameters appear to be those of material, structure and function. Structure is inherent in the pawn formation, which changes only slowly during the course of a game. It is far from easy to provide any single scale of measurement for its evaluation. Material, on the other hand, is easily measurable. For practical purposes we can adopt Shannon's scale of 9 for Q, 5 for R, 3 for B or S, I for P. If the value of a game is +1 in the case of a win for White, 0 in the case of a draw, ‑1 in the case of win for Black, then the value of a chess position of a defined kind, Shannon's f(P), is (w ‑ b)/(w + d + b), where w, d and b are respectively the number of White wins, draws and Black wins which have been obtained from that kind of position. From the games analysed an advantage of one pawn has at the 20th move if positive i.e. in favour of white, a value of +0.27, if negative, i.e. in favour of Black, a value of ‑0.21.
Material gains are therefore, as we could have guessed, highly decisive. They are, however, attained as a rule only after a considerable number of moves and with difficulty. Out of 350 master gaines, only in 98 cases had a material advantage been won by the 20th move. This factor by itself will be of value to the machine towards the end of the game in administering the coup‑de‑grace, and in ordinary situations in preventing it from falling into crass error. For move-to‑move guidance, advantages measurable in smaller units will be evaluated. This, the strategic advantage, is involved in the functional factor.
This factor appears to be largely identical with mobility. Its value is recognised by chess experts, but it is often inaccurately judged. On the simplest view it is fundamental. The outstanding characteristic of a chess position is that it is a dynamic situation with a definite and limited number of degrees of freedom (the total number of legal moves). The game cannot be finally won without administering mate, when the opponent's degrees of freedom are reduced to zero. A series of checks, known by chess‑players to be highly dangerous, is so because it reduces the opponent's mobility to the lowest possible level short of paralysis, and often eventually compels a disastrous move.
If the degrees of freedom available to each opponent are charted through the course of a game, a double curve is obtained whose rises and falls correspond closely with the strategic advantage. Means taken from 78 arbitrarily selected games which ended with a decision on or before the 40th move shows the following state of the parties:
These fiagures show (1) a rise in the degrees of freedom as pieces are developed, followed by (2) a fall as pieces are exchanged, and (3) a consistent and increasing difference to the advantage of the winners.
Shannon’s f(P) has its limits +1 and ‑1. We can define an advantage in mobility, M, as (dFw – dFB), which has the same limits. It has been found from a total of 380 games from the tournaments mentioned above, i.e. including all those which proceeded as far as the 20th move without one or other player having won an advantage in material, that there is a close relation between f(P) and M. This is shown in the following table:
If graphed these points approximate to a straight line, and to the equation f(P) = +.086 + 1.658M.
We may use the value of M to predict the value of f(P), and are then intersted to know its efficiency. If wins for White, wins for Black and draws are in equal proportions (as is very nearly the case), a random classification of a series of games will result in a misclassification rate of 89 points per hundred. If games ar ranked by the value of M at the 20th move, the misclassification rate drops to 63 points per hundred, and if both the values of a material advantage and of M are combined by simple addition, the rate drops still further to 55 points per hundred. Efficiency is therefore rather low. It is rather doubtful whether it could be much improved without the intrusion of a subjective element. The players themselves “misclassify” their games, as it is far from infrequent for a player to lose from a theoretically drawn position, even in a fairly advanced stage of the game, or to draw or lose from a theoretically won position. The frequency with which this is actually observed depends on the care and skill of the subsequent analysis to which tournament games are usually subjected when play is over. Much depends, therefore, on the annotator. With a highly skilled and interested analyst like Alekhin, one finds that, in his judgement, the "misclassification" produced by errors in approaches in the tournament games he has annotated to 40 points per 100.
To summarise the effect of these arguments, it does seem possible that a chess computer which was programmed, beyond immediate tactical tasks, to maximise the mobility difference between itself and its opponent over a series of moves, might play a strategically tolerable games of chess. The mobility factor by itself might be a sufficient measure of all the factors (Rook on open file etc.) listed by Shannon as requiring evaluation under his headings (3 and (5). Moreover the concept of mobility overlaps with other concepts much used by chess players. Control of space, when defined as the number of squares the opponent's half of the board whose use can be denied him for Llt least one move, proves to be correlated with mobility by a coefficient of +0.83, i.e. the two concepts are nearly identical. "Development" is largely tantamount to the acquisition of increased mobility for all pieces together and for each piece separately. "Initiative" is nearly always in the hands of the player with the advantage in mobility, and "having the attack" scene to consist in having the opportunity for its aggressive application. "Combination", though nowhere very precisely fined by chess authors, seems to be the same thing as the exchange of one sort of advantage for another, e.g. when superior mobility enables a rapid concentration of attack on a piece which cannot be so quickly defended, or when a sacrifice in material buys an open file bearing on the opposing King.
The speculation may be offered that many other games, from draughts to war, may be found by appropriate analysis to involve the same concept, i.e. that advantage lies in creating a difference in mobility. For the more restricted problem of programming a chess computer, however, these preliminary investigations also suggest that a digital computer may prove an iefficient instrument, and that an analogue machine, or a combination of digital and analogue machines, will provide better result.
Reference
Shannon, C. E.,: "Programming a Computer for Playing Chess". Phil. Mag., 41 256‑275 (1950).