Chess 0.5
BYTE, Vol. 3, No. 10 [1] Chess 0.5,
a program by Larry Atkin and Peter W. Frey for didactic purposes, written in the ETH Zurich dialect of Pascal for the CDC 6600 series of mainframes, published 1978/1979 in Byte Magazine, and re-published on-line in 2005, available from Scott A. Moore’s [2] sites, unfortunately with some OCR-errors such as syntactical correct replacement of ‘*’ by ‘+’ with score factor by side (XTMV, ±1) in some places [3] . Chess 0.5 may be compiled with GNU Pascal for recent hardware. Due to non-local goto statements over procedure or function boundaries compiling with Free Pascal is not possible [4] .
Larry Atkin is co-author of the famous Northwestern University Chess line of programs. At the time of the article, Chess was at about version 4.6 [5] . Chess 0.5 is based on his intimate knowledge of that program, but is a seperate program designed for pedagogical purposes to play chess vaguely well [6] using Chess 4.x like structures of a Shannon Type A approach with alpha-beta and quiescence search, bitboards and incremental updated attack tables.
Blueprint
As encouraged by Frey and Atkin in their article “The reader with an interest in chess and programming should use this listing as starting point for developing a program” [7] , Chess 0.5 was origin of at least three other competing programs, the Austrian Merlin by Hermann Kaindl, Helmut Horacek, Marcus Wagner and Roland Schreier, further developed in Pascal except some time critical, often called routines, which were re-written in CDC assembly by Wagner [8] [9] , the Dutch Chess 0.5X by Wim Elsenaar, a PDP-11 assembly port, and according to postings in rgcc [10] , the Finnish Shy by Juha Kasanen, Mika Korhonen and Timo Saari, written in Algol.
Description
Board Representation
Chess 0.5 keeps an 8x8 board either indexed by square or rank and file, …
… and further relies on bitboards, defined as union of arrays of sets and integers:
Beside the mailbox arrays (BOARD, MBORD) and bitboard board definition (TPLOC, TMLOC), Chess 0.5 maintains incremental updated attack tables, two 8x8 arrays ATKTO and ATKFR, the first for every square a attack bitboard to other squares of the piece (if any) residing on that square, the second for each square a bitboard of all white and black man attacking this square.
Bitboard Infrastructure
Setwise Operations
Bitboard intersection, union and relative complement are implemented with set-wise operations “*, +, -”, complement (not) by relative complement from the universe ([AX..ZX]):
BitScan
BitScan reverse with reset is implemented with machine dependent CDC 6600 float conversion (omitted here) - the machine independent code inefficiently loops over up to 2*32 bits of the set and cries for improvement:
Popcount
The machine independent population count relies on the above bitscan with reset!
Evaluation
Chess 0.5’s evaluation routine EVALU8 implements a lazy evaluation only for too worse scores. If the incremental updated material balance plus the maximum positional score is still less or equal than alpha (best value two plies up BSTVL[JNTK-2]), only the material balance is assigned without further positional analysis. Otherwise EVALU8 consides piece mobility (counting attacks), pawn structure, king safety and some rook terms such as doubled rooks and rook on 7th rank. Differences of light minus dark positional terms are adjusted by appropriate feature weights. To make white point of view scores relative to the side to move, they are multiplied by a score factor (+1, -1) indexed by side.
Search
The search is implemented spaghetti like non-recursively as finite-state machine with goto labels using explicit stacks aka ply indexed arrays, and features iterative deepening with aspiration and alpha-beta pruning. The value array of best moves indexed by current ply is the current alpha of a newly entered node, initialized by grand parent’s best value (ply-2) - best value of the parent node (ply-1) is minus beta in the negamax sense. The nested function SELECT implements a staged move generation, considering root search (ply 0), full-width and quiescence, generating captures in MVV/LVA order, killers, and remaining moves. While the ply indices range from 0 to 16, the best value array needs three additional sentinels due to ply-2, ply-1, and ply+1 accesses. The outline of the search routine with jump labels (:) is given below, most lines omitted:
See also
Publications
- Peter W. Frey, Larry Atkin (1978). Creating a Chess Player. An Essay on Human and Computer Chess Skill, BYTE, Vol. 3, No. 10, pp. 182-191. pdf from The Computer History Museum
- Peter W. Frey, Larry Atkin (1978). Creating a Chess Player, Part 2: Chess 0.5. BYTE, Vol. 3, No. 11
- Peter W. Frey, Larry Atkin (1978). Creating a Chess Player, Part 3: Chess 0.5 (continued). BYTE, Vol. 3, No. 12
- Peter W. Frey, Larry Atkin (1979). Creating a Chess-Player, Part 4: Thoughts on Strategy. In Blaise W. Liffick (ed.), The Byte Book of Pascal, pp. 143-155. Byte Publications, also BYTE, Vol. 4, No. 1
Forum Posts
- Byte Chess 0.5 finally available. From Byte Magazine 1978 by I Forget, rgcc, June 01, 2005
- Update for Byte Chess 0.5 by I Forget, comp.lang.pascal.misc, June 12, 2005
- Missing from Computer-Chess Wiki by Sylwy, CCC, July 05, 2011
- Need a little help from a Pascal guru (Chess05 Frey/Atkin) by Jim Ablett, CCC, January 09, 2012
External Links
Byte Chess 0.5 source code hosted by Scott A. Moore
- Classic Computer Chess - … The programs of yesteryear by Carey, hosted by the Internet Archive
- Computer-Schach by Andre Adrian (German)
Chess05GNU.pas References
- ↑ Byte Vol. 3, No. 10, October 1978 from the Internet Archive
- ↑ Scott A. Moore’s site
- ↑ Byte Chess 0.5 source code (OCR-Errors!)
- ↑ Re: Need a little help from a Pascal guru (Chess05 Frey/Atkin) by Steven Edwards, CCC, January 09, 2012
- ↑ Chess 4.6 source code, gift of David Slate, from The Computer History Museum, pdf
- ↑ Chess 0.5, Release 1 - 2005-05-30
- ↑ Peter W. Frey, Larry Atkin (1978). Creating a Chess Player, Part 3: Chess 0.5 (continued). BYTE, Vol. 3, No. 12
- ↑ Werner DePauli-Schimanovich (2006). Europolis 6. Informatik für Spiele und Verkehr. Extension der Mengenlehre, Herausgeber: Franz Pichler, Universitätsverlag Rudolf Trauner, ISBN 978-3-85487-946-6, (SG7) Merlin (ein ComputerChess-Programm) s. 171 (German), Google Books
- ↑ Helmut Horacek, Marcus Wagner (1981). Das Schachprogramm Merlin, Verbesserung von Laufzeit-Effizient, Eröffnungsbibliothek und Bewertungsfunktion. 4. Tagung “Berichte aus Informatik-Instituten” (German)
- ↑ Re: Byte Chess 0.5 finally available. From Byte Magazine 1978 by I Forget, rgcc, June 02, 2005