Chess (Program)

From Chessprogramming wiki
Jump to: navigation, search

Home * Engines * Chess - The Northwestern University Chess Program

Chess 4.6 Chesstor, ACM 1978 [1]

Chess,
the Northwestern University Chess Program by primary authors Larry Atkin and David Slate was the dominating program in the 70s, winning eight times the ACM North American Computer Chess Championships and the second WCCC Toronto 1977. The version Chess 4.0 from 1973 was a complete re-write and paradigm shift from Shannon type B to type A. Chess ran on Control Data Corporation's line of supercomputers, CDC 6600 and CDC Cyber, Chess 4.x was completely written in COMPASS, the CDC assembly language.

Photos

CHAOS Chess 4.0 Rubin Slate.WCCC 1974.jpg

Ruben and Slate, WCCC 1974 [2]

3-3a.NACCC-Minneapolis.Chess 4.4.Slate-David Atkin-Larry.1975.102645412.MONTY NEWBORN.src.lg.jpg

Slate and Atkin, ACM 1975 [3]

History of Development

Chess 1.0

In spring 1968 Northwestern University engineering students Larry Atkin and Keith Gorlen launched a chess program in their spare time.

Chess 2.0 - 3.6

By mid 1969, physics graduate student David Slate, who already started his own effort of a computer chess program, joined the team to develop Chess 2.0, which was gradually refined to Chess 3.6 during the following years by Slate and Atkin. While Gorlen left the team in 1970, he still contributed a few ideas for some time. The development and architecture of the early program is described in Larry Atkin's Masters Thesis [4] .

Chess, until 3.6, was a Shannon Type B kind of program, using a plausible move generator to select "best-n" moves. Due to their early success and obligation to prepare for the annual ACM event, the authors more and more stumbled over their initial design decisions and almost unmaintainable source code, and started a complete redesign and re-write in 1973.

Further quotes from CHESS 4.5 - The Northwestern University Chess Program [5] :

We quickly ruled out entering Chess 3.6. If there is anything more useless than yesterday's newspaper, it is last year's chess program. Our interest in the tournament lay in the chance to test something new and different, not to find out whether the other programs had improved enough to smash our old program. We knew, despite our unbeaten record and well-developed myth about the "solidity" of our program, that our luck must soon give out. The bubble would burst, and the gross weakness of Chess 3.6 would suddenly pour out in a series of ridiculous, humiliating blunders. For Chess 3.6 was the latest in a series of evolutionary changes to our original chess program, written in 1968-1969, and it faithfully carried most of the original design deficiencies. Chess 3.6 was, like the dinosaur, a species about to become extinct. Basically a Shannon type B program, it had a depth-first, alpha-beta, more-or-less fixed depth tree search. A primitive position evaluation function scored the endpoints and also doubled as a plausible move generator earlier in the tree by selecting "best-n" moves for further exploration. Rudimentary as they were, Chess 3.6's evaluation and tree search were just adequate to make "reasonable-looking" moves most of the time and not hang pieces to one- or two move threats. Apparently this was enough to play low class C chess and, for a while, to beat other programs.
In terms of organization, Chess 3.6 was a mess. Not only was it difficult to modify the evaluation function - it was difficult even to find it in the listing of the program.

Chess 4.0 - 4.9

Chess 4.0 and it's successors were more simple and modular written Tech style Shannon Type A programs.

Chess 3.6 was a mixture of Fortran and Assembly language (for CDC 6000/Cyber). Although we would have liked to use a high-level language, we felt that neither Fortran nor other languages available at the time offered the right combination of efficiency and power of expression. In writing Chess 4.0, we used assembly language so we could have complete control over the instructions that were generated. For Evalu8, which contains all of the "chess decisions", we used high-level assembly language macros, which give the "illusion" of a higher level language.
Although our plausible-move generator sounded plausible enough, and differed not very much from methods employed in several other chess programs, we had built up profound dissatisfactions with it over the years. A suggestion by Peter W. Frey triggered some thoughts on the matter, and as a result we dumped selective searching in favor of full-width searching, ostensibly a more primitive algorithm. 

Several search and evaluation routines were separated in modules (Evalu8, BASE, FULL, MINI), basic data structures were Bitboards and incremental updated square centric attack tables for evaluation and move generation purpose. Chess 4.x used iterative deepening, a sophisticated Transposition Table, and the Killer Heuristic (since 4.5). The basic design and detailed description of Chess 4.5 influenced and motivated a lot of other computer chess programmers and made Chess 4.5 an archetype of generations of computer chess programs. David Slate made the source code of Chess 4.6 available from The Computer History Museum [6].

Achievements

Chess 3.x won the first three ACM North American Computer Chess Championships, ACM 1970, ACM 1971 and ACM 1972. Already by August 1973, only a few month after the re-write, and without much testing and tuning, Chess 4.0 won it's first tournament, the ACM 1973, but had less luck during the first World Computer Chess Championship 1974, where it lost against CHAOS in round two.

Despite not winning the title in 1974, Chess 4.x continued domination of CC events. Chess' hardware were the Control Data Corporation (CDC) computers CDC 6600 and CDC Cyber series, and CDC Cyber hardware consultant David Cahlander joined the team. Chess 4.4 won the ACM 1975, Chess 4.5 ACM 1976 and Chess 4.6 ACM 1977 as well the second World Computer Chess Championship 1977 in Toronto. Chess 4.9 won the 10th ACM 1979 with a record of now eight (out of ten) North American Championship titles. Chess 4.9 finally participated at the WCCC 1980 in Linz, Austria, already competing with Slate's new program Nuchess.

Man-Machine

Chess 4.x delivered various man-machine matches, most notably the David Levy versus Chess 4.7 match in 1978, where Levy won his famous bet. In 1979, a Levy versus Chess 4.8 game was introduced to a greater audience in the German television ZDF, featured by Journalists Frederic Friedel and Volker Arzt [7].

Chesstor

In 1978, Chess 4.6 was invited to play the Minnesota's Twin Cities Open, won by Chess with a 5-0 score, further winning versus Walter Browne in a simultaneous exhibition. A new electronic chessboard was used for the first time. The micro-processor which controls the board senses the opponent's moves magnetically, transmits the move in algebraic via telephone to the Cyber 176, and then indicates Cyber 176's responses by illuminating small lights on the square of the piece to be moved and the one to which it is to go. Chesstor, as this device was called, also senses the hitting of the chess clock [8].

Namesakes

The 1978 program Chess 0.5 by Larry Atkin and Peter W. Frey, as published in Byte Magazine, was a separate program written in Pascal for didactic purposes. Chess 7.0 by Larry Atkin was a commercial program written in 6502 Assembly published in 1982/83 for various home computers. Another namesake was the strong Dutch program Chess 0.5X by Wim Elsenaar in the 80s, winner of DOCCC 1983 and 1984.

See also

Publications

Forum Posts

External Links

References

Up one level