Difference between revisions of "Chess (Program)"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
Line 92: | Line 92: | ||
[[Category:Mainframe]] | [[Category:Mainframe]] | ||
[[Category:Thesis]] | [[Category:Thesis]] | ||
+ | [[Category:Quotes]] |
Revision as of 12:34, 7 December 2019
Home * Engines * Chess - The Northwestern University Chess Program
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.
Contents
Photos
Ruben and Slate, WCCC 1974 [2]
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].
- Chess 4.0 from Evaluation Overlap by Mark Watkins
- Material in Chess 4.5 at Material Hash Table
- Mobility in Chess 4.6 at CDC Cyber
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
- Bitboard History
- History of Computer Chess
- The Mind Machines - WCCC 1977 Video
- WCCC 1986 Video at 3:52
Publications
- David Slate, Larry Atkin, Keith Gorlen (1971). CHESS 3.5 User Guide. Northwestern University
- Paul Rushton, Tony Marsland (1973). Current Chess Programs: A Summary of their Potential and Limitations. INFOR Journal of the Canadian Information Processing Society Vol. 11, No. 1, pdf
- Larry Atkin (1975). Chess 3.6: A Chess Playing Computer Program. Masters Thesis, Northwestern University, June 1975
- David Slate, Larry Atkin (1977). Chess 4.5 - The Northwestern University Chess Program. Chess Skill in Man and Machine, reprinted (1988) in Computer Chess Compendium
- David Slate, Ben Mittman (1978). Chess 4.6 - Where Do We Go From Here? Jerusalem Conference on Information Technology 1978 193-198
- Editor (1978). Computer beats U.S. chess champ. Personal Computing, Vol. 2, No. 10, pp. 84 » Chesstor
- David Cahlander (1979). Strength of a Chess Playing Computer. ICCA Newsletter, Vol. 2, No. 1
Forum Posts
- Chess 4.5 from 1976 by Robert Harrington, rgcc, April 20, 1996
- Re: CHESS 4.5 (1973) by Robert Hyatt, rgcc, April 07, 1997 » Bitboards, C++, Evaluation
- Chess 4.0 vs Belle 1973 by Joshua Lee, CCC, May 31, 2000 » Belle
External Links
- Chess (Northwestern University) from Wikipedia
- Chess' ICGA Tournaments
- Classic Computer Chess - ... The programs of yesteryear by Carey, hosted by the Internet Archive [9]
- Description of the computer programme CHESS 4.0, August 10, 1974, IFIP 74 Congress, Andrey Ershov Archive
- SCHACH: Computer bald Weltmeister? Der Spiegel 13/1979, March 26, 1979 (German) » Frieder Schwenkel
- The Slate/Atkin program and CHESS x.x by Bill Wall, Chess.com, September 23, 2011
- Ars Electronica - Die Teilnehmer an der 3. Computerschach-Weltmeisterschaft - CHESS 4.9 (German)
References
- ↑ Chess 4.6 electronic board at ACM 1978, Courtesy of Monroe Newborn, The Computer History Museum
- ↑ Ruben and Slate at 1st World Computer Chess Championship in Stockholm, WCCC 1974, by Monroe Newborn from The Computer History Museum
- ↑ Slate and Atkin at the 6th ACM North American Computer Chess Tournament in Minneapolis, Minnesota, ACM 1975, by Monroe Newborn from The Computer History Museum
- ↑ Larry Atkin (1975). Chess 3.6: A Chess Playing Computer Program. Masters Thesis, Northwestern University, June 1975
- ↑ David Slate and Larry Atkin (1977). CHESS 4.5 - The Northwestern University Chess Program. Chess Skill in Man and Machine, reprinted (1988) in Computer Chess Compendium
- ↑ Chess 4.6 source code, gift of David Slate, from The Computer History Museum, pdf
- ↑ ZDF: IM David Levy 1979 gegen Chess 4.8 from schach-computer wiki
- ↑ Editor (1978). Computer beats U.S. chess champ. Personal Computing, Vol. 2, No. 10, pp. 84
- ↑ Re: Old programs CHAOS and USC by Dann Corbit, CCC, July 11, 2015