ICS 180A, Spring 1997:
Strategy and board game programming

Lecture notes for April 1, 1997
A brief history of computer game programs

1950

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 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.

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.

1951

Alan Turing describes and hand-simulates a computer chess program of type B. Play best described as "aimless"; loses to weak player.

1956

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.

1957

Type B program implemented on IBM 704 (42Khz, 7K words). Does full chess 4-ply in 8 min. Passable amateur.

1958

Newell, Simon and Shaw introduce alpha-beta pruning, a general game-search technique which effectively doubles the length of move sequences one can examine.

1959

Arthur Samuel begins experimenting with automatic learning techniques to improve the play of a checkers program.

1962

Alan Kotok's B.S. thesis project from M.I.T., a program called MacHack for IBM 7090 computers, examines 1100 positions/minute.

1967

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.

1968

Zobrist writes the first Go program. It plays like a complete beginner.

1971

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.

1973

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.

1975

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.

1977

Belle, first special-purpose chess hardware, built by Condon & Thompson at Bell Labs.

Chess 4.6 beats a grandmaster (Stean) at speed chess.

1979

BKG, written by Hans Berliner, beats the world backgammon champion in a match.

1982

IAGO plays Othello at world-championship level (according to then-human champion Jonathan Cerf) but does not actually play against championship-level human competition.

1988

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).

1989

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.

1992

Chinook checkers program loses a match to the human world champion, Marion Tinsley, 4-2 (with 33 draws).

1993

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.

1994

Tinsley forfeits match to Chinook due to illness. Chinook becomes world checkers champion.

1996

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.

1997

Kasparov - Deep Blue rematch to be held this quarter.