ICS 180A, Spring 1997:
Strategy and board game programming
Claude E. Shannon writes the first article on computer chess: "Programming a computer for playing chess", Philosophical Magazine 41:256-275. He writes "Although perhaps of no practical importance, the question is of theoretical interest, and it is hoped that a satisfactory solution of this problem will act as a wedge in attacking other problems of a similar nature and of greater significance". Modern chess programs still follow the lines laid out by Shannon.
Shannon notes the theoretical existence of a perfect solution to chess and the practical impossibility of finding it. He describes two general strategies, both based an a heuristic "evaluation function" for guessing whether a position is in favor of one person or the other:Shannon Type A - expand all sequences of possible moves out to a fixed "horizon" (number of levels), combine the evaluations of these sequences in a simple tree computation ("minimax"), use the combined evaluation to choose the best move.Shannon thought that type B was clearly better but debate still continues today (you can find proponents of both sides on rec.games.chess.computer). Shannon's evaluation combines terms for material (P=1, N=B=3, R=5, Q=9) and positional advantages, similar to modern evaluation functions.
Shannon Type B - only perform selective expansion of certain lines, using knowledge to prune uninteresting branches. For example, Turing's 1951 program only expanded lines involving captures.
Alan Turing describes and hand-simulates a computer chess program of type B. Play best described as "aimless"; loses to weak player.
Type A program (for simplified 6x6 chess variant) implemented on MANIAC-1 (11Khz, 600 words of mem) computer at Los Alamos. Does 4-ply search in 12 min. Beats weak players.
Type B program implemented on IBM 704 (42Khz, 7K words). Does full chess 4-ply in 8 min. Passable amateur.
Newell, Simon and Shaw introduce alpha-beta pruning, a general game-search technique which effectively doubles the length of move sequences one can examine.
Arthur Samuel begins experimenting with automatic learning techniques to improve the play of a checkers program.
Alan Kotok's B.S. thesis project from M.I.T., a program called MacHack for IBM 7090 computers, examines 1100 positions/minute.
Greenblatt chess program (MacHack 6) on DEC PDP-6 (200Khz) evaluates about 10 positions/second. It competes in 4 amateur chess tournaments, wins 3 games, draws 3, loses 12.
Zobrist writes the first Go program. It plays like a complete beginner.
The "Technology" chess program wins 10 pts out of 26 in six tournaments. Is this the first chess program written in a high-level prgramming language? It runs on a PDP-10 (1Mhz), and examines 120 positions/second.
Until this point, most or all chess programs have been of type B. Programmers Slate and Atkin, revising their overly complicated chess program in preparation for the 1973 Computer Chess Championships, return to a type A search routine. Their program Chess 4.0 wins, and other programmers start to switch from type B to type A. On a CDC 6400 a later version (Chess 4.5) processes from 270 to 600 positions/second.
Robert Hyatt begins developing Cray Blitz, for a long time the fastest program and from 1983-1989 the world computer chess champion. As of 1983 it was searching 40-50K positions/second, only a little slower than current programs on fast pentiums. Hyatt is still very active today in computer chess with his free program Crafty.
Belle, first special-purpose chess hardware, built by Condon & Thompson at Bell Labs.
Chess 4.6 beats a grandmaster (Stean) at speed chess.
BKG, written by Hans Berliner, beats the world backgammon champion in a match.
IAGO plays Othello at world-championship level (according to then-human champion Jonathan Cerf) but does not actually play against championship-level human competition.
Deep Thought, predecessor of Deep Blue, created by a team of Carnegie-Mellon U. graduate students. The basic version of Deep Thought's chess engine contained 250 chips and two processors on a single circuit board and was capable of analyzing 750,000 positions per second or 10 half moves ahead. That same year Deep Thought became the first computer to defeat a Grandmaster in a tournament (Bent Larsen, who had at one time been a contender for world champion, being defeated by Bobby Fischer in a preliminary championship round).
An experimental six-processor version of Deep Thought, searching more than two million positions/second, played a two-game exhibition match against Gary Kasparov, the reigning world champion, and was beaten.
Chinook checkers program loses a match to the human world champion, Marion Tinsley, 4-2 (with 33 draws).
Deep Thought defeated Judit Polgar, at the time the youngest Grandmaster in history and still the strongest female player in the world (ranked in the top 20 grandmasters), in another two-game exhibition match.
Tinsley forfeits match to Chinook due to illness. Chinook becomes world checkers champion.
IBM's new chess machine Deep Blue (a 32-processor parallel computer with 256 VLSI chess engines searching 2-400M moves/second) beats reigning world champion Gary Kasparov in the first game of a six-game match, but loses the match.
Kasparov - Deep Blue rematch to be held this quarter.