The idea of a machine which could play chess was first proposed by the mathematician Charles Babbage more than a hundred years ago. Babbage is better remembered for his work on machines that perform automatic mathematical computation. He designed a number of such machines, but was unable to realise his more ambitious projects. Nonetheless he understood clearly all the fundamental principles of a modern computer, and believed that his analytical engine would be capable of playing a real game of chess.
The first genuine machine was made by Signor Torres Quevado in about 1890. It could play the end game of the rook and king against a lone king and, providing the opponent did not cheat, it could always win from any starting position. Despite the simplicity of this machine no further development occurred until the advent of the electronic computer.
The first paper to describe explicitly how to program a computer to play chess was by Shannon (27). In it the concept of the minimax tree search was introduced. By 1951 Dr W. Prinz, using the first Manchester University Computer (MADM; 1 millisecond cycle time), had developed a program which could solve a restricted set of Mate in Two problems (18). As a specific program to solve the problem is given in this book, it is interesting to compare the designs. The pioneer program's restrictions were:
Such restrictions save time but were primarily because the machine had limited memory and was difficult to program efficiently. The first chess problem it solved is shown below.
It took the program about twenty minutes to show that the only correct move is R-R6. Almost half the time was spent in testing for self-check, because this was implemented badly. It was done by first examining all squares connected to the king's square by a knight's move (despite the fact there are no knights on the board) to see
A similar test was made for bishops, rooks, etc.
Most of the remaining time was spent in transfers between the limited main store and the large (?) backing store. Prinz commented that improved programming technique could probably save most time in this area by reducing the number of transfers, but modern computers are sufficiently large to overcome this problem. The conclusion drawn was that the method was too crude to compete on reasonable terms with a competent human being. This is too modest, since modern machines are about 1000 times faster and could, therefore, execute Prinz's program in the order of five seconds on average. The main reason chess programs are so good nowadays is because of the enormous speed of execution, not because of improved programming techniques which has only gained factors of five at most (notably the alpha-beta algorithm which is not applicable to mating problems).
The next program of any note was Bernstein's (this program is discussed in Chapter 4). Written in 1955 for an IBM 704 (with a speed of about 10,000 operations/second, i.e. about 10 times faster than MADM), it was the first satisfactory program deriving most of its power from the ability to search ahead 4 plys within eight minutes.
There then occurred a distinct split in the development of chess playing programs. Since that time programs have either been (a) pragmatic, concentrating on playing a powerful opening and (hopefully) winning in the middle game, or they have been (b) philosophic employing explicit plans and goals for choosing their moves.
The philosophic approach is obviously more applicable in the end game, where situations occur for which brute force lookahead is not the best technique. The first program in this tradition was in 1958 by Newell, Simon, and Shaw (17), who tried to solve the opening, middle, and end games in one. The program never played a game. Nevertheless it was significant in that it used (for apparently the first time) the alpha-beta algorithm, a standard component of every modern tree-searching program.
Between 1960 and 1966 the pragmatic programs became more and more sophisticated, but the biggest improvements came in hardware. Large stores, and speeds of 200 to 1000 greater than MADM became readily available and, by 1967, Greenblatt beat about 80% of non-tournament players and had actually won a trophy in an amateur tournament (28). The machine used was a PDP6, with an approximate speed of 200,000 operations/second.
The program has seven major components, all of which are improvements on Bernstein's program. These are:
Greenblatt's program was exhibited at the 1968 IFIPS held in Edinburgh. It was a major attraction, drawing large crowds who cheered the program on to a win against the majority of its opponents. A special match was arranged between the program and one written by John Scott for the ICL 1909/5 (29). An analysis of this game was made by I. J. Good (30), with the comment that Scott's program had a chance to draw at the 58th move, but made a bad move and then resigned. Because it was generally agreed that Greenblatt's program was the best to that date, Scott's program had done well to last so long. Both these programs were powerful opening and middle game players but became, from recorded games, relatively weak should they reach an end game. It seemed to the author that if it were possible to playa vigorous swapping strategy in order to reach an end game quickly then, even with a queen advantage, neither program would be actually able to realise the mate.
Mainly as an on-line demonstration, the Algol program (Chapter 3) was extended to actually play the game. Most of the effort went into the communication language, e.g. the program types the normal chess notation (P-K4 etc.) when making a move; it types Eh? when an illegal move is attempted by the opponent and so on. To make it play quickly the program looked ahead only 3 plys. This is too shallow to allow it much chance of winning (in fact it never beat anyone), but what it tried to do was last as long as possible by forcing and accepting equal or better swops with a weighting on the more powerful pieces, e.g. it would always take the opponent's queen unless illegal, swap a rook for a bishop or knight etc. If no swaps or captures were present it attempted to maximise (the number of moves it could make/the number the opponent could make), but got extra points if the move also attacked an enemy man. The result was a program which responded almost immediately but lasted, on average, only 20 moves. To curb it slightly the queen was inhibited until the sixth move and the program always castled as soon as it was possible.
John Scott kindly agreed to play with this hairy program. As neither program learns then only two games are possible. The game where Scott's program played White was as follows:
SCOTT AUTHOR
1. P-Q4 N-QB3 (attacks pawn)
2. P-K4 P-K3 (Q and B freed)
3. P-Q5 B-QN5 ch (restricts opponent)
4. P-QB3 B-QB4 (cheat)
5. P-QN4 N*P (inevitable)
6. P*N Q-B3 (can't wait)
7. P*B? Q*R (next set inevitable)
8. B-Q3 Q*P
9. N-KB3 P*P
10. KP*P Q*QP
11. N-QB3 Q*P
12. B-Q2
(The cheat at move 4 was that the bishop wanted to check again, but I made it take its second choice and left the country at move 12.) Scott's program would undoubtedly have weathered this storm, but it now has less chance of a quick win in the middle game.
A philosophic program was written by Barbara Huberman to specifically play end games (31). It was a research project on translating book descriptions of problem solving methods into program heuristics. It is well known that the following minimum combinations of pieces have a certain win against a lone king:
The K,Q can be considered equivalent to the K,R.
Huberman followed descriptions (by Capablanca and Fine) of how to execute all but the case of K,N,N,N. The cases of K,R and K,B,B are feasible using the minimax technique. This is not true for the K,B,N. The difficulty here is that bishops and rooks can force mate on any size of board but the knight has a limited mobility (from a centre square there are five squares which each require four moves to be reached by the knight).
Consequently the K,B,N mate is not possible on a board of side > 8. Even allowing for the black king being against a side there is no way in which the K,B,N can be arranged and played that will systematically force the black king along the edge of an infinite board. Because of this weakness the actual mating can take up to forty moves. Huberman's model for the problem was a forcing tree co-ordinated with two functions (better and worse) which were able to compare positions. Roughly speaking the program had two sub-goals (apart from not losing a piece, giving stalemate, etc). First drive the king away from the centre and second, when the king is at the edge, drive him towards a corner of the bishop's colour.
Huberman's program is the only one which can perform this mating sequence for any starting position. It would be a useful addition to Greenblatt's program, being easily extended to solve other end games and hence giving the more general program a selection of sub-goals equivalent to winning the game. The problem of K,N,N,N is unlikely to occur; nevertheless it is of interest to the theorists. One surprising fact is that the combination can systematically drive the black king along the edge of an infinite board, and therefore the mating sequence is much easier to program.
A final example, to illustrate the importance of good communication with a game playing program, is the CDC 6600 CHESS by D. Slate and L. Atkin. The following output was the result of a player who did not know the program and, in effect, the program taught him how to communicate correctly. Having done this it could teach him how to play chess.
BOARD IS SET UP DO YOU WANT WHITE NO MY MOYE-P-K4. P-K4 YOUR MOYE-P-K4 MY MOYE-B-B4. N-B3 AMBIGUOUS MOYE. ENTER MOYE. N(KNl)-B3 YOUR MOYE-N(KNl)-B3 MY MOYE-N-QB3. N-B3 YOUR MOYE-N-B3 MY MOYE-N-B3. N-N5 AMBIGUOUS MOVE. ENTER MOVE. KN-N5 SYNTAX ERROR. ENTER MOVE. N(KB3)-N5 YOUR MOVE-N(KB3)-N5 MY MOVE-P-Q4. P*P YOUR MOVE-P*P MY MOVE-N*P. N*N YOUR MOVE-N*N MY MOVE-Q*N(Q4) N*P AMBIGUOUS MOVE. ENTER MOVE. N*KBP ILLEGAL MOVE. ENTER MOVE. N*P(KB2) ILLEGAL MOVE. ENTER MOVE. K *P(KB7) YOUR MOVE-K*P(KB7) MY MOVE-Q*N. B-N5 YOUR MOVE-B-N5 MY MOVE-Q*P(B7)CHECKMATE. ***COMMENT DAMN YOU SYNTAX ERROR. ENTER MOVE. ***COMMENT.DAMN DAMN DAMN SYNTAX ERROR. ENTER MOVE.
Most programs can only type out their moves, but the 6600 is equipped with a display on which it can draw a fair representation of a checker board and chess men. This ability required a major programming effort, but it adds to the attraction of playing the machine. When a man is about to be moved he is blinked on the display, moved, and blinked on his new square; the move is also shown at the bottom of the board in the usual chess notation and, finally, two clocks are also displayed should anyone wish to play tournament rules. This program was featured in a television programme against D. Levy, the Scottish champion. To aid filming, the program was set to a shallow depth and replied quickly. Despite this Levy had some problems before defeating it. Immediately after filming the program was reset to operate at its full power (full power means that searches of down to 12 plys are common) and played the following game against Stewart Reuben, a county class player. The example is chosen to show the power of chess programs at the end of the 1960s; not world class as some people had predicted, but nevertheless impressive.
WHITE BLACK
Stewart
Reuben CDC 6600 Nimzo-Indian Defence?
1. P-Q4 N-KB3 36. R-R3 P*B
2. P-QB4 N-B3 37. R *p ch K-R3
3. N-QB3 P-K3 38. N-N4 N-B6
4. B-N5 B-N5 39. R-B3 K-N2
5. P-K3 B*N ch 40. R-Bl P-R4
6. P*B P-KR3 41. N-Q3 N-K5 ch
7. B-R4 P-KN4 42. K-Ql R-B6!
8. B-N3 P-Q3 43. N-Bl R*KP
9. B-Q3 P-K4 44. K-B2 P-Q5
10. P-KR4 B-N5 45. R-Ql P-N4
11. Q-R4 K-K2! 46. R-Q3 R*R
12. P-Q5 N-QNl 47. N*R K-B2
13. P-B5 QN-Q2 48. K-N2 N-B6
14. P*P ch P*P 49. N-B5 P-K5
15. Q-N4 Q-B2 50. K-B2 P-K6
16. P-QB4 N-B4 51. N-N7 P-K7
17. B-B2 N-R3 52. K-Q2 P-R5
18. Q-B3? N*P 53. P*P P*P
19. Q-Q2 N-N3 54. N-Q6 ch K-K3
20. B-N3 N*P 55. N-B4 P-B4
21. Q-B3 N-R4 56. N-R3 K-K4
22. Q*Q ch N*Q 57. N-B4 K-Q4
23. R-Bl N-N4 58. N-R3 P-B5
24. N-K2 N*B 59. N-B2 K-K5
25. P*N KR-QBl 60. N-R3 K-Q4
26. K-Q2 B-B4 61. N-B2 P-B6?!
27. P*P P*P 62. P*P K-B5
28. R-R5 R*R 63. P-B4 P-Q6
29. N*R P-B3 64. N-K3 ch K-N6
30. P-B3 P-Q4 65. N-N2 P-R6
31. P-B4 R-QBl 66. K*P P-R7
32. N-Q3 B-N3 67. P-B5 P-R8/Q
33. R-R6 NP*P 68. P-B6 Q-KB8
34. R*B K-B2 69. Resigns
35. R-R6 K-N2