A Short History of Computer Chess

A-Jenery
A-Jenery
Jan 14, 2008, 12:00 AM |
2 | Other

 

Chess and computers was a marriage waiting to happen, and when it did, so we had the reality of computer chess.  The following; derrived from books and other sources of info, covers some of the earliest roots of computer chess; technological milestones in their own right that has led to the situation we have today, where average-strength, off-the shelf computer programs/chess computers regularly outplay good players, and where the strongest one's are able to beat even Grand Masters.

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 uses 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 automation led him to produce this as an example of the possibilities of robots.  The object of the device was to checkmate a human opponent'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 player 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 similar 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, consisting of six conditions concerning relative positions of Kings and Rook, on which six actions could be taken. It could guarantee a 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 who founded both computer science and artificial intelligence research.  In 1951 Turing wrote what was probably the first chess program TURBOCHAMP.  Unfortunately there did not exist a computer at that time capable of running TURBOCHAMP.
The first game played between a chess program and a human was overseen by Turing himself who performed the program's calculations without the aid of a calculator.  The human opponent was Allick Glenms who managed to checkmate TURBOCHAMP after 29 moves in a game that 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 Alan Turing himself 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 lan Turing.  He formalised 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 or chess computers.  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.

STRATEGY A.
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 the alarming way in which the number of computations required rises as the 'look ahead' increases.

STRATEGY B.
As Shannon realised that the computers of his day were incapable of utilising strategy A with much effect, he devised strategy B as a more subtle alternative. The essential difference is that a heuristic 'plausible move generator' is used to cut down the number of moves considered at each stage and so increases the number of 'half moves' ahead that can be analysed.  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 compute? - the chance of finding a good move for several moves ahead.  Shannon never actually wrote a full program to perform either strategy, but set down algorithms used from then on by many chess programs.  He demonstrated a deep understanding of the limiting factors which were to pose the problems for chess programmers for years to come.

Los Alamos - MANIAC 1
One of the earliest chess programs running on a computer was developed in the early 1950's by a group at the Los Alamos Scientific Laboratory in New mexico, presumably a form of relaxation after their efforts in producing the first hydrogen bomb.  The scientists; Wells, Walden, Kister, Stein and Ulam, developed the program on the IBM MANIAC 1 that weighed about 30 tons.  To reduce the number  of computations they cheated a little by programming for a 6 by 6 chess board without bishops.
This program was firstly beaten by a fairly strong player despite the program being given an initial queen advantage. It then went on to face a very specially prepared challenger.   A young member of the laboratory who had been taught to play chess only a week earlier was thrown into the fray and was unsurprisingly beaten after 23 moves.  The challenger was the first to be outwitted at chess by a computer.

Modem Chess Programs
As true computers, recognisable 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 first world computer chess championship took place in Stockholm.  The top computers available 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 become 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 progress of chess computers and their programming can be traced through the increasing standard of players required to defeat them.   From novices in the 1950's through to masters in the 80's, never mind the 90's and 00's; it seems that we are fighting a losing battle - and the chess player 'v' chess computer battle will probably last for ever.

 


More from A-Jenery
It can happen to any chess player...

It can happen to any chess player...

The Ghost In The Chess Machine

The Ghost In The Chess Machine