http://www.turingarchive.org/browse.php/B/7
http://books.google.com/books?id=x7mMr4twnloC&pg=PA569
Digital Computers applied to Games.
When one is asked 'Could one make a machine to
play chess?,' there are several possible meanings which
might be given to the words. Here are a few:-
i) Could one make a machine which would obey the rules
of chess, i.e. one which would play random legal
moves, or which could tell one whether a given move
is a legal one ?
ii) Could one make a machine which would solve chess
problems, e.g. tell one whether, in a given position,
white has a forced mate in three ?
iii) Could one make a machine which would play a reasonably
good game of chess, i.e. which, confronted with an
ordinary ( that is, not particularly unusual) chess
position, would after two or three minutes of
calculation, indicate a passably good legal move?
iv) Could one make a machine to play chess, and to
improve its play, game by game, profiting from its
experience?
To these we may add two further questions, unconnected
with chess, which are likely to be on the tip of the
reader's tongue.
v) Could one make a machine which would answer questions
put to it, in such a way that it would not be possible
to distinguish its answers from those of a man?
vi) Could one make a machine which would have feelings
like you and I do?
The problem to be considered here is iii), but to
put this problem into perspective with the others
I shall give the very briefest of answers to each
of them.
To i) and ii) I should say "This certainly can be
done. If it has not been done already it is merely
because there is something better to do".
Question iii) we are to consider in greater detail,
bu the short answer is "Yes, but the better the standard
of play required, the more complex will the machine be, and
the more ingenious perhaps the designer".
To iv) and v) I should answer "I believe so. I
know of no really convincing argument to support this belief
and certainly of none to disprove it".
To vi) I should say "I shall never know, any more than
I shall ever be quite certain that you feel as I do".
In each of these problems except possibly the last,
the phrase 'Could one make a machine to....' might equally
well be replaced by 'Could one programme an electronic
computer to....'. Clearly the electronic computer so
programmed would itself constitute a machine. And on
the other hand if some other machine had been constructed
to do the job we could use an electronic computer ( of
sufficient storage capacity), suitably programmed, to
calculate what this machine would do, and in particular
what answer it would give.
After these preliminaries let us give our minds to
the problem of making a machine, or of programming a
computer, to play a tolerable game of chess. In this
short discussion it is of course out of the question to
provide actual programmes, but this does not really matter
on account of the following principle:-
If one can explain quite unambiguously in English,
with the aid of mathematical symbols if required, how a
calculation is to be done, then it is always possible to
programme any digital computer to do that calculation,
provided the storage capacity is adequate.
This is not the sort of thing that admits of clear
out proof, but amongst workers in the field it is regarded
as being clear as day. Accepting this principle, our
problem is reduced to explaining 'unambiguously in English'
the rules by which the machine is to choose its move in
each position. For definiteness we will suppose the machine
is playing white.
If the machine could calculate at an infinite speed,
and also had unlimited storage capacity, a comparatively
simple rule would suffice, and would give a result that in
a sense could not be improved on. This rule could be
stated:-
Consider every possible continuation of the game
from the given position. There is only a finite number
of them ( at any rate if the fifty-move rule makes a draw
obligatory, not merely permissive). Work back from the
end of these continuations, marking a position with white
to play as 'win' if there is a move which turns it into
a position previously marked as 'win'. If this does not
occur, but there is a move which leads to a position marked
'draw', then mark the position 'draw'. Failing this, mark
it 'lose'. Mark a position with black to play by a similar
rule with 'win' and 'lose' interchanged. If after this process
has been completed it is found that there are moves which
lead to a position marked 'win', one of these should be
chosen. If there is none marked 'win' choose one marked
'draw' if such exists. If all moves lead to a position
marked 'lose', any move may be chosen.
Such a rule is practically applicable in the game
of noughts and crosses, but in chess is of merely academic
interest.
Even when the rule can be applied to it is not very
appropriate for use against a weak opponent, who may make
mistakes which ought to be exploited.
In spite of the impracticability of this rule it
bears some resemblance to what one really does when playing
chess. One does not follow all the continuations of play,
but one follows some of them. One does not follow them
until the end of the game, but one follows them a move or
two, perhaps more. Eventually a position seems, rightly
or wrongly, too bad to be worth further consideration, or
( less frequently) too good to hesitate longer over. The
further a position is from the one on the board the less
likely is it to occur, and therefore the shorter is the
time which can be assigned for its consideration. Following
this idea we might have a rule something like this:-
Consider all continuations of the game consisting
of a move by white, a reply by black, and another move
and reply. The value of the position at the end of each
of these sequences of moves is estimated according to some
suitable rule. The values at earlier positions are then
calculated by working backwards move by move as in the
theoretical rule given before. The move to be chosen is
that which leads to the position with the greatest value.
It is possible to arrange that no two positions have
the same value. The rule is then unambiguous. A very
simple form of values, but one not having this property,
is an 'evaluation of material', e.g. on the basis
P = 1
Kt = 3
B = 3 1/2
R = 5
Q = 10
Checkmate +/- 1000
If B is black's total and W is white's, then W/B is
quite a good measure of value. This is better than W-B
as the latter does not encourage exchanges when one has
the advantage. Some small extra arbitrary function of
position may be added to ensure definiteness in the result.
The weakness of this rule is that is follows all
combinations equally far. It would be much better if the
more profitable moves were considered in greater detail
than the less. It would also be desirable to take into
account more than mere ' value of material'.
After this introduction I shall describe a particular
set of rules, which could without difficulty be made into
a machine programme. It is understood that the machine
is white and white is next to play. The current position
is called the 'position of the board', and the positions
arising from it by later moves 'positions in the analysis'.
'Considerable' moves i.e. Moves to be considered in the
analysis by the machine.
Every possibility for white's next move and for
black's reply is'considerable'. If a capture is
considerable then any recapture is considerable. The
capture of an undefended piece or the capture of a piece
of higher value by one of lower value is always considerable.
A move giving checkmate is considerable.
Dead position.
A position in the analysis is dead if there are no
considerable moves in that position i.e. if it is more than
two moves ahead of the present position., and no capture or
recapture or mate can be made in the next move.
Value of position
The value of a dead position is obtained by adding up
the piece values as above, and forming the ratio W/B of
white's total to black's. In other positions with white to
play the value is the greatest value of:A) the positions
obtained by considerable moves, or B) the position itself
evaluated as if a dead position, the latter alternative
to be omitted if all moves are considerable. The same
process is to be undertaken for one of black's moves, but
the machine will then choose the least value.
Position-play value
Each white piece has a certain position-play
contribution and so has the black king. These must all
be added up to give the position-play value.
For a Q.,R.,B. or Kt., count
i) the square root of the number of moves the
piece can make from the position, counting a capture as
two moves, and not forgetting that the king must not be
left in check.
ii) (if not a Q) 1.0 if it is defended, and an
additional 0.5 if twice defended.
For a K, count
iii) for moves other than castling as i) above.
iv) It is then necessary to make some allowance for
the vulnerability of the K. This can be done by assuming
it to be replaced by a friendly Q on the same square,
estimating as in i), but subtracting instead of adding.
Count v) 1.0 for the possibility of castling later
not being lost by moves of K or rooks, a further 1.0 if
castling could take place on the next move, and yet another
1.0 for the actual performance of castling.
For a P, count
vi) 0.2 for each rank advanced
vii) 0.3 for being defended by at least one piece
(not P)
For the black K, count
viii) 1.0 for the threat of checkmate.
ix) 0.5 for check.
We can now state the rule for play as follows.
The move chosen must have the greatest possible value,
and, consistent with this, the greatest possible position-
play value. If this condition admits of several solutions
a choice may be made at random, or according to an arbitrary
additional condition.
Note that no 'analysis' is involved in position -play
evaluation. This is in order to reduce the amount of work
done on deciding the move.
The game below was played between this machine and a
weak player who did not know the system. To simplify the
calculations the square roots were rounded off to one decimal
place, (i.e. the table below was used). No 'random choices'
actually arose in this game. The increase of position-play
value is given after white's move if relevant. An asterisk
indicates that every other move had a lower position-play
value.
Number 0 1 2 3 4 5 6 7 8 9 10 11 12 13
Square
Root. 0 1 1.41.72.02.22.42.62.83.03.23.3 3.5 3.6
White (Machine) Black.
1. P-K4 4.2* P-K4
2. Kt-QB3 3.1* Kt-KB3
3. P-Q4 3.1* B-QKt5
4. Kt-KB31)2.0 P-Q3
5. B-Q2 3.6* Kt-QB3
6. P-Q5 0.2 Kt-Q5
7. P-KR42) 1.1* B-Kt5
8. P-QR42) 1.0* Kt*Kt ch.
9. P x Kt B-KR4
10.B-Kt5 ch 2.4* P-QB3
11.P x P O - O
12.P x P R-Kt1
White (Machine) Black
13. B-R6 -1.5 Q-R4
14. Q-K2 0.6 Kt. - Q2
15. KR-Kt13)1.2* Kt - B44)
16. R-Kt55) B-Kt3
17. B-Kt5 0.4 Kt X KtP
18. O-O 3.0* Kt - B4
19. B-B6 KR - QB1
20. B-Q5 B x Kt.
21. P x B2)-0.7. Q x P
22. B-K36) Q-R6ch.
23. K-Q2 Kt. - R5
24. B x RP7) R - Kt7
25. P - B4 Q - B6ch.
26. K - B1 R - R7
27. B x BPch. B x B
28. R x KtP ch5) K x R
29. B - K38) R - R8 mate
Notes: (O-O indicates castling)
1) If B-Q2 3.6* then P xP is foreseen.
2) Most inappropriate moves from a positional point of view.
3) If O-O then BxKt, BxB, QxP.
4) The fork is unforeseen.
5) Heads in the sand!
6) Only this or B-K1 can prevent Q-R8 mate.
7) Fiddling while Rome burns.
8) Mate is foreseen, but 'business as usual'.
Numerous criticisms of the machines play may be made,
It is quite defenceless against 'forks', although it may
be able to see certain other kinds of combination. It is
of course not difficult to devise improvements of the
programme so that these simple forks are foreseen. The reader
may be able to think of some such improvements for
himself. Since no claim is made that the above rule is
particularly good, I have been content to leave this flaw
without remedy; clearly a line has to be drawn between
the flaws which one will attempt to eliminate and those
which must be accepted as a risk. Another criticism is
that the scheme proposed, although reasonable in the middle
game, is futile in the end game. The change-over from the
middle game to the end-game is usually sufficiently clean
cut for it to be possible to have an entirely different
system for the end-game. This should of course include
quite definite programmes for the standard situations,
such as mate with rook and king, or king and pawn against
king. There is no intention to discuss the end-game
further here.
If I were to sum up the weakness of the above system
in a few words I would describe it as a caricature of my
own play. It was in fact based on an introspective analysis
of my thought processes when playing, with considerable
simplifications. It makes oversights which are very similar
to those which I make myself, and which may in both cases
be ascribed to the considerable moves being rather
inappropriately chosen. This fact might be regarded as
supporting the rather glib view which is often expressed,
to the effect that 'one cannot programme a machine to play
a better game than one plays oneself'. This statement
should I think be compared with another of rather similar
form. 'No animal can swallow an animal heavier than
himself'. Both statements are, so far as I know, untrue.
They are also both of a kind that one is rather easily
bluffed into accepting, partly because one thinks that
there ought to be some rather slick way of demonstrating
them, and one does not like to admit that one does not
see what this argument is. They are also both supported
by normal experience, and need rather exceptional cases
to falsify them. The statement about chess programming
may be falsified quite simply by the speed of the machine,
which might make it feasible to carry the analysis a move
farther than a man could do in the same time. This effect
is rather less than might be supposed. Although electronic
computers are very fast where conventional computing is
concerned, their advantage is much reduced where enumeration
of cases etc. is involved on a large scale. Take for
instance the problem of counting the possible moves from
a given position in chess. If the number is 30 a man
might do it in 45 seconds and the machine in 1 second.
The machine has still an advantage, but it is much less
overwhelming than it would be for instance where calculating
cosines.
In connection with the question, numbered iv) above,
as to the ability of a chess-machine to profit from experience,
one can see that it would be quite possible to programme
the machine to try out variations in its method of play
(e.g. variations in piece value) and adopt the one giving
the most satisfactory results. This could certainly be
described as 'learning', though it is not quite representative
of learning as we know it. It might also be possible to
programme the machine to search for new types of combination
in chess. If this product produced results which were
quite new, and also interesting to the programmer, who
should have the credit? Compare this with the situation
where the Defence Minister has given orders for research
to be done to find a counter to the bow and arrow. Should the
inventor of the shield have the credit, or should the
Defence Minister?