A HISTORY OF COMPUTER CHESS
Since the beginning of the mechanical age people have been fascinated by the possibility of machines replacing human functions. To some it meant a release from human drudgery, both manual and intellectual. To others a more philosophical challenge was in sight in the attainment of machine decisions, machine imagination, machine thought. In retrospect it is obvious that these two aims were related, the thinking machine of one age became the drudge-replacing automaton of the next. A brief look at the history of the calculator, from abacus to the modern electronic variety, soon reveals that as soon as a so-called 'intelligent' machine has been produced then the very definition 'intelligence' changes. 'Intelligence' seems to be a word applied to all functions that a human can achieve and machines cannot. Perhaps one day this process will restrict the word to such a limited range as to become meaningless.
For many years the fascination of this subject has been concentrated upon the advent of chess playing machines, and with good reason. Chess has always been respected as a formidable human accomplishment yet many aspects of the game (though not yet all) are susceptible to analysis consisting of many repetitive calculations, well suited to computers and their forerunners. This leads to a situation where man and machine can be pitted against each other on fairly equal terms. There is certainly never any lack of human players eager to undertake this challenge, which is often seen as one of defending the pride of the human race.
As yet our finest chess players still persist in beating our chess computer, despite the latter's horrifying amount of processing power. It seems these players possess an insight into to the game beyond the realms of mere number crunching, an insight that provides a new challenge to the designers of chess programs. When this challenge is met then it will provide the final chapter to a history that began (albeit in a dubious fashion) nearly two hundred years ago.
BARON VON KEMPELEN - TURK
It will probably come as a surprise to most people that the very first chess-playing machine was produced in the eighteenth century, long before the advent of computers, or even complicated mechanical devices. It was invented by the Baron Von Kempelen and was very successful, beating many of the best players of its time, and even winning against Napoleon (a fairly dangerous maneuver as he was not known as a good loser). The machine, called TURK consisted of a mechanical man that moved pieces on a board in response to an opponents move. It was very popular, toured many countries, and entertained most of the royalty of the day.
Unfortunately TURK had one drawback, it was a clever fake. It was a cunningly designed device with cabinets below in which a human player could hide from view. As the box was opened up, one side at a time, the human played moved to hide from the sight of spectators. Lever controls were provided to operate the machine's mechanical arm and the player could see the board through a veil in the mechanical man's chest. It had however no intelligence of its own barring several of the (smaller) chess players of the time hidden within. Fake though it was TURK did illustrate the public interest produced by any machine that could claim to think.
LEONARDO TORRES Y QUEVEDO
In the Polytechnic University of Madrid can be found, still working, the true ancestor of the chess playing computer. It is not very ambitious in its aims, but considering that it was built in 1890 and used only electro-mechanical devices then it is worthy of admiration. Its inventor was the Spanish scientist Leonardo Torres y Quevedo whose experiments and theories on automaton led him to produce this as an example of the possibilities of robots.
The object of the device was to checkmate a human component's king using only its own king and rook. It consisted of a board on which the three pieces moved along slots. Electrical connections made by the pieces in their various positions served to 'sense' the current board position and electromagnets provided the means of moving the chess pieces. A light bulb lit up if the human had made an illegal move and a device similar to an early gramophone produced the words CHECK and MATE where appropriate.
Decision-making was performed by a series of electromagnetic relay switches. It had no software control as such, the device being analogous to a modern microprocessor constructed to respond only to an instruction set of (simple) chessboard positions. The embedded rules determining which moves to make were not complicated, consisted of six conditions concerning relative positions of Kings and Rook, on which six actions could be taken. It could guarantee checkmate within 63 moves against any opponent.
ALAN MATHIESON TURING
We had to wait another fifty years before a step comparable to that of Torres was made. Alan Turing was both mathematician and philosopher whose short (and often unhappy) life founded both computer and artificial intelligence research. In 1951 Turing wrote what was probably the first chess program TURBOCHAMP. Unfortunately there did not exist a computer capable of running TURBOCHAMP. The first game that was played between a chess program and a human was executed by Turing who himself performed the program's calculations (without the aid of a calculator). The human opponent was Allick Glennis who was not particularly a good chess player but who managed to checkmate TURBOCHAMP after 29 moves. The game lasted three hours.
TURBOCHAMP was a rudimentary program by today's standards in that it could only look one move ahead; it had no concept of the difference between the opening, middle and end games, and had an elementary evaluation of position. It did however understand the rules of the game and used basic algorithms distinguishable from the modern variety only by the need to produce an answer within many fewer calculations. It is interesting to note that as Alan Turing was a poor chess player, TURBOCHAMP was probably an example of a program being able to out think its creator.
CLAUDE ELWOOD SHANNON
Claude Elwood Shannon was working on his theories of chess programming almost simultaneously with Alan Turing. He formalized the methods that can be used to consider a chess position into two strategies, generally known as strategy A and strategy B. These two methods form the basis of practically all-modern chess programs. Both strategies were developed on the basis of work done several years earlier by the mathematician Jon
Van Neumann. He developed the methods of MINIMAX, to evaluate the optimum path through a decision tree, as part of his general theories on game playing.
This is sometimes known as the 'Brute Force Method'. In its initial conception it simply involved the calculation of every possible move and every possible reply for a fixed number of 'half moves' ahead. This has been refined in later years to include alpha-beta cutoff in the MINIMAX search, and to perform heuristic ordering of evaluation of moves to improve efficiency. To work effectively this method requires computers of high processing power due to an alarming way in which the number of computations required rises as the 'look ahead' increases.
As Shannon realized that the computers of his day were incapable of utilizing strategy B as a subtler alternative. The essential difference is that heuristic 'plausible move generator' is used to cut down the number of moves considered at each stage and hence increases the number of 'half moves' ahead can be analyzed. This method has the disadvantage of the possibility of missing a vital move if the 'plausible move generator' is not of the highest standard. It does however provide the more modest computer the chance of finding a move reasonably sound for several moves ahead.
Shannon never actually wrote a full program to perform either of his strategies, but set down algorithms used from then on by many chess programs. He demonstrated a deep understanding of the limiting factors that were to pose the problems for chess programmers for many years to
LOS ALAMOS - MANIAC 1
A group at the Los Alamos Scientific Laboratory, New Mexico, developed one of the very early chess programs running on a computer in the early 1950’s. This was presumably a form of relaxation after their efforts in producing the first hydrogen bomb. The scientists, Wells, Walden, Kister, Stien and Ulam developed their program on the 30-ton IBM monster MANIAC 1. In trying to cut down the explosion of computations they cheated a little by programming for a 6 by 6 chessboard without bishops.
A fairly strong player despite the program being given an initial queen advantage firstly beat this program. It then went on to face a specially prepared challenger who had been taught to play chess one week earlier was thrown into the fray and was unsurprisingly beaten after 23 moves. History does not record the name of this challenger but she gained the doubtful honor of being the first to be outwitted at chess by a computer.
MODERN CHESS PROGRAMS
As true computers, recognizable as the ancestors of our current machines, were developed in the early 1950's the race to produce the ultimate chess program was on, and still continues today. In 1974 the internal skirmishes between chess computers were formalized at the first world computer chess championship at Stockholm. The top computers played each other under tournament rules (with a few amendments to cope with system failures). A Russian program KAISSA won the first of what was to be a regular event. Since then competition has also extended to a microcomputer event which tends to be more of a test of programming than processing power.
The race has always been a three-way challenge, between the computers themselves and between computers and chess players. The process of the computers and their programming can be traced through the increasing standard of players required to defeat them. From novice in the 1950's through to master in the 1980's it seems that the humans are fighting a losing battle. Perhaps so, but the final stages of the war may well last longer than expected.
Excerpts taken from “Commodore Amiga The Art of Chess” User Manual.