25,161
edits
Changes
Created page with "'''Home * Engines * Chess 0.5''' FILE:223-front.gif|border|right|thumb|link=https://archive.org/details/byte-magazine-1978-10| [[Byte Magazine#BYTE310|BYT..."
'''[[Main Page|Home]] * [[Engines]] * Chess 0.5'''
[[FILE:223-front.gif|border|right|thumb|link=https://archive.org/details/byte-magazine-1978-10| [[Byte Magazine#BYTE310|BYTE, Vol. 3, No. 10]] <ref>[https://archive.org/details/byte-magazine-1978-10 Byte Vol. 3, No. 10, October 1978] from the [https://en.wikipedia.org/wiki/Internet_Archive Internet Archive]</ref> ]]
'''Chess 0.5''',<br/>
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 <ref>[http://www.moorecad.com/standardpascal/scottmoore.html Scott A. Moore's site]</ref> sites, unfortunately with some [https://en.wikipedia.org/wiki/Optical_character_recognition OCR]-errors such as syntactical correct replacement of '*' by '+' with score factor by side (XTMV, ±1) in some places <ref>[http://www.moorecad.com/standardpascal/Chess05.pas Byte Chess 0.5 source code] (OCR-Errors!)</ref> . Chess 0.5 may be compiled with [[Pascal#GNUPascal|GNU Pascal]] for recent hardware. Due to non-local [https://en.wikipedia.org/wiki/Goto goto] statements over procedure or function boundaries compiling with [[Pascal#FreePascal|Free Pascal]] is not possible <ref>[http://www.talkchess.com/forum/viewtopic.php?t=41896&start=1 Re: Need a little help from a Pascal guru (Chess05 Frey/Atkin)] by [[Steven Edwards]], [[CCC]], January 09, 2012</ref> .
Larry Atkin is co-author of the famous [[Northwestern University]] [[Chess (Program)|Chess]] line of programs. At the time of the article, Chess was at about version 4.6 <ref>[http://www.computerhistory.org/chess/full_record.php?iid=sft-431614f455002 Chess 4.6 source code], gift of [[David Slate]], from [[The Computer History Museum]], [http://archive.computerhistory.org/projects/chess/related_materials/software/3-3.Chess_4.6_Sourcecode.102645430/chess_4-6.sourcecode.102645430.pdf pdf]</ref> . 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 <ref>[http://www.moorecad.com/standardpascal/ByteChess.txt Chess 0.5, Release 1 - 2005-05-30]</ref> using Chess 4.x like structures of a [[Type A Strategy|Shannon Type A]] approach with [[Alpha-Beta|alpha-beta]] and [[Quiescence Search|quiescence search]], [[Bitboards|bitboards]] and [[Incremental Updates|incremental updated]] [[Attack and Defend Maps|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" <ref>[[Peter W. Frey]], [[Larry Atkin]] ('''1978'''). ''[https://archive.org/stream/byte-magazine-1978-12/1978_12_BYTE_03-12_Life#page/n141/mode/2up Creating a Chess Player, Part 3: Chess 0.5 (continued)]''. [[Byte Magazine#BYTE312|BYTE, Vol. 3, No. 12]]</ref> , 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 6600|CDC]] [[Assembly|assembly]] by Wagner <ref>[[Werner DePauli-Schimanovich-Göttig|Werner DePauli-Schimanovich]] ('''2006'''). ''[http://www.trauner.at/buchdetail.aspx?artnr=20199541 Europolis 6]''. Informatik für Spiele und Verkehr. Extension der Mengenlehre, Herausgeber: Franz Pichler, [http://www.trauner.at/Default.aspx Universitätsverlag Rudolf Trauner], ISBN 978-3-85487-946-6, (SG7) Merlin (ein ComputerChess-Programm) s. 171 (German), [http://books.google.com/books?id=Gf4WibmHVbcC&pg=PA175&lpg=PA175&source=bl&ots=YPtaHAp3Z4&sig=DNRPh11heo8Q1zS3UOBe0qoCF-8&hl=en&ei=0GmnTMX1GMfJswaL-NivDA&sa=X&oi=book_result&ct=result&resnum=1&ved=0CBgQ6AEwAA#v=onepage&q&f=false Google Books]</ref> <ref>[[Helmut Horacek]], [[Marcus Wagner]] ('''1981'''). ''Das Schachprogramm Merlin, Verbesserung von Laufzeit-Effizient, Eröffnungsbibliothek und Bewertungsfunktion.'' 4. Tagung "Berichte aus Informatik-Instituten" (German)</ref> , the Dutch [[Chess 0.5X]] by [[Wim Elsenaar]], a [[PDP-11]] assembly port, and according to postings in [[Computer Chess Forums|rgcc]] <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/3iSe8NsM024/DrW8Dzsr2tYJ Re: Byte Chess 0.5 finally available. From Byte Magazine 1978] by I Forget, [[Computer Chess Forums|rgcc]], June 02, 2005</ref> , the Finnish [[Shy]] by [[Juha Kasanen]], [[Mika Korhonen]] and [[Timo Saari]], written in [[Algol]].
=Description=
==Board Representation==
Chess 0.5 keeps an [[8x8 Board|8x8 board]] either indexed by [[Squares|square]] or [[Ranks|rank]] and [[Files|file]], ...
<pre>
CONST
AX = 0; ZX = 31; (* SUBSETS OF SQUARES *)
AS = 0; ZS = 63; (* BOARD VECTOR LIMITS *)
TYPE
TF = (F1,F2,F3,F4,F5,F6,F7,F8); (* FILES *)
TR = (R1,R2,R3,R4,R5,R6,R7,R8); (* RANKS *)
TI = INTEGER; (* NUMBERS *)
TS = AS..ZS; (* SQUARES *)
TX = AX..ZX; (* SOME SQUARES *)
TY = AY..ZY; (* NUMBER OF TX'S IN A BOARD *)
TM = (LITE,DARK,NONE); (* SIDES *)
TP = (LP,LR,LN,LB,LQ,LK,DP,DR,DN,DB,DQ,DK,MT); (* PIECES: LIGHT PAWN,... , DARK KING, EMPTY SQUARE *)
SX = SET OF TX; (* SET OF SOME SQUARES *)
RB = RECORD (* BOARDS *)
RBTM : TM; (* SIDE TO MOVE *)
RBTS : TT; (* ENPASSANT SQUARE *)
RBTI : TI; (* MOVE NUMBER *)
RBSQ : SQ; (* CASTLE FLAGS *)
CASE INTEGER OF
0: ( RBIS : ARRAY [TS] OF TP); (* INDEXED BY SQUARE *)
1: ( RBIRF : ARRAY [TR,TF] OF TP);(* INDEXED BY RANK AND FILE *)
END;
</pre>
<span id="Bitboard"></span>... and further relies on [[Bitboards|bitboards]], defined as union of arrays of sets and integers:
<pre>
RS = RECORD (* BIT BOARDS *)
CASE INTEGER OF
0: (RSSS: ARRAY [TY] OF SX); (* ARRAY OF SETS *)
1: (RSTI: ARRAY [TY] OF TI); (* ARRAY OF INTEGERS *)
END;
</pre>
Beside the [[Mailbox|mailbox]] arrays (BOARD, MBORD) and [[Bitboard Board-Definition|bitboard board definition]] (TPLOC, TMLOC), Chess 0.5 maintains [[Incremental Updates|incremental updated]] [[Attack and Defend Maps|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 [[Square Attacked By|attacking this square]].
<pre>
BOARD : RB; (* THE BOARD *)
MBORD : ARRAY [TS] OF TP; (* LOOK-AHEAD BOARD *)
ATKFR : ARRAY [TS] OF RS; (* ATTACKS FROM A SQUARE *)
ATKTO : ARRAY [TS] OF RS; (* ATTACKS TO A SQUARE *)
ALATK : ARRAY [TM] OF RS; (* ATTACKS BY EACH COLOR *)
TPLOC : ARRAY [TP] OF RS; (* LOCATIONS OF PIECE BY TYPE *)
TMLOC : ARRAY [TM] OF RS; (* LOCATIONS OF PIECE BY COLOR *)
</pre>
==Bitboard Infrastructure==
===Setwise Operations===
[[General Setwise Operations#Intersection|Bitboard intersection]], [[General Setwise Operations#Union|union]] and [[General Setwise Operations#RelativeComplement|relative complement]] are implemented with [http://www.freepascal.org/docs-html/ref/refsu50.html set-wise operations] "*, +, -", [[General Setwise Operations#ComplementSet|complement]] (not) by relative complement from the [[General Setwise Operations#EmptyAndUniverse|universe]] ([AX..ZX]):
<pre>
PROCEDURE ANDRS (* INTERSECTION OF TWO BITBOARDS *)
(VAR C:RS; (* RESULT *)
A, B:RS); (* OPERANDS *)
VAR
INTY : TY; (* BIT BOARD WORD INDEX *)
BEGIN
FOR INTY := AY TO ZY DO
C.RSSS[INTY] := A.RSSS[INTY] * B.RSSS[INTY];
END; (* ANDRS *)
PROCEDURE IORRS (* UNION OF TWO BIT BOARDS *)
(VAR C:RS; (* RESULT *)
A, B:RS); (* OPERANDS *)
VAR
INTY : TY; (* BIT BOARD WORD INDEX *)
BEGIN
FOR INTY := AY TO ZY DO
C.RSSS[INTY] := A.RSSS[INTY] + B.RSSS[INTY];
END; (* IORRS *)
PROCEDURE NOTRS (* COMPLEMENT OF A BIT BOARD *)
(VAR C:RS; (* RESULT *)
A:RS); (* OPERAND *)
VAR
INTY : TY; (* BIT BOARD WORD INDEX *)
BEGIN
FOR INTY := AY TO ZY DO
C.RSSS[INTY] := [AX..ZX] - A.RSSS[INTY];
END; (* NOTRS *)
</pre>
===BitScan===
<span id="BitScan"></span>[[BitScan#BitscanwithReset|BitScan reverse with reset]] is implemented with machine dependent [[CDC 6600]] [[Float#BitScan|float conversion]] (omitted here) - the machine independent code inefficiently loops over up to 2*32 bits of the set and cries for improvement:
<pre>
FUNCTION NXTTS (* NEXT ELEMENT IN BIT BOARD *)
(VAR A:RS; (* BIT BOARD TO LOCATE FIRST SQUARE, AND THEN REMOVE *)
VAR B:TS (* SQUARE NUMBER OF FIRST SQUARE IN BIT BOARD *)
): TB; (* TRUE IFF ANY SQUARES WERE SET INITIALLY *)
LABEL
11; (* RETURN *)
VAR
INTX : TX; (* BIT BOARD BIT INDEX *)
INTY : TY; (* BIT BOARD WORD INDEX *)
X : RK; (* KLUDGE WORD *)
BEGIN
FOR INTY := ZY DOWNTO AY DO (* LOOP THRU BIT BOARD WORDS *)
IF A.RSTI[INTY] <> 0 THEN
BEGIN
FOR INTX := ZX DOWNTO AX DO (* LOOP THROUGH BITS IN WORD OF SET *)
IF INTX IN A.RSSS[INTY] THEN
BEGIN
B := INTX+INTY*(ZX+1); (* RETURN SQUARE NUMBER *)
A.RSSS[INTY] := A.RSSS[INTY] - [INTX]; (* REMOVE BIT FROM WORD *)
NXTTS := TRUE; (* RETURN A BIT SET *)
GOTO 11; (* RETURN *)
END;
END;
NXTTS := FALSE; (* ELSE RETURN NC BITS SET *)
11: (* RETURN *)
END; (* NXTTS *)
</pre>
===Popcount===
<span id="Popcount"></span>The machine independent [[Population Count|population count]] relies on the above [[Chess 0.5#BitScan|bitscan with reset]]!
<pre>
FUNCTION CNTRS (* COUNT NENBERS OF A BIT BOARD *)
(A:RS): TS; (* BIT BOARD TO COUNT *)
VAR
INTS : TS; (* TEMPORARY *)
INRS : RS; (* SCRATCH *)
IMTS : TS; (* SCRATCH *)
BEGIN
INTS := 0;
CPYRS(INRS,A);
WHILE NXTTS(INRS,IMTS) DO
INTS := INTS+1; (* COUNT SQUARES *)
CNTRS := INTS; (* RETURN SUM *)
END; (* CNTRS *)
</pre>
<span id="EVALU8"></span>
==Evaluation==
Chess 0.5's [[Evaluation|evaluation]] routine '''EVALU8''' implements a [[Lazy Evaluation|lazy evaluation]] only for too worse [[Score|scores]]. If the [[Incremental Updates|incremental updated]] [[Material|material balance]] plus the maximum positional score is still less or equal than [[Alpha|alpha]] (best value two plies up BSTVL[JNTK-2]), only the material balance is assigned without further positional analysis. Otherwise '''EVALU8''' consides [[Mobility|piece mobility]] (counting attacks), [[Pawn Structure|pawn structure]], [[King Safety|king safety]] and some rook terms such as doubled rooks and [[Rook On Seventh|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|side to move]], they are multiplied by a score factor (+1, -1) indexed by side.
<pre>
PROCEDURE EVALU8; (* EVALUATE CURRENT POSITION *)
FUNCTION EVKING (* EVALUATE KING *)
FUNCTION EVMOBL (* EVALUATE MOBILITY *)
FUNCTION EVPAWN (* EVALUATE PAWNS *)
FUNCTION EVROOK (* EVALUATE ROOKS *)
BEGIN
IF XTMV[JNTM]*MBVAL[JNTK] + MAXPS <= BSTVL[JNTK-2] THEN (* !!! OCR *)
(* MOVE WILL PRUNE ANYWAY *)
INTV := XTMV[JNTM] * MBVAL[JNTK]
ELSE
BEGIN
INTV := ( FWPAWN*(EVPAWN(TPLOC[LP],S2,R2)-EVPAWN(TPLOC[DP],S4,R7))
+ FWMINM*(EVMOBL(LB,LN) -EVMOBL(DB,DN) )
+ FWMAJM*(EVMOBL(LR,LQ) -EVMOBL(DR,DQ) )
+ FWROOK*(EVROOK(TPLOC[LR],XRRS[R7])
-EVROOK(TPLOC[DR],XRRS[R2]) )
+ FWKING*(EVKING(TPLOC[LK],TPLOC[LP])
-EVKING(TPLOC[DK],TPLOC[DP]) )
) DIV 64;
MAXPS := MAX(MAXPS,ABS(INTV));
INTV := XTMV[JNTM] * (MBVAL[JNTK] + INTV);
END;
IF SWTR THEN
BEGIN
WRITE(" EVALU8",JNTK,JNTW,INDEX[JNTK],INTV);
PRIMOV(MOVES[INDEX[JNTK]]);
END;
VALUE[INDEX[JNTK]] := INTV; (* RETURN SCORE *)
END; (* EVALU8 *)
</pre>
<span id="Search"></span>
==Search==
The [[Search|search]] is implemented spaghetti like [[Iterative Search|non-recursively]] as [https://en.wikipedia.org/wiki/Finite-state_machine finite-state machine] with [https://en.wikipedia.org/wiki/Goto goto] labels using explicit [[Stack|stacks]] aka [[Ply|ply]] indexed [[Array|arrays]], and features [[Iterative Deepening|iterative deepening]] with [[Aspiration Windows|aspiration]] and [[Alpha-Beta|alpha-beta pruning]]. The value array of [[Best Move|best moves]] indexed by current ply is the current [[Alpha|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|beta]] in the [[Negamax|negamax]] sense. The nested function SELECT implements a [[Move Generation#Staged|staged move generation]], considering [[Root|root search]] (ply 0), full-width and [[Quiescence Search|quiescence]], generating [[Captures|captures]] in [[MVV-LVA|MVV/LVA]] order, [[Killer Move|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:
<pre>
BSTVL : ARRAY [AKM2..ZKP1] OF TV; (* VALUE OF BEST MOVE [-2..17] *)
FUNCTION SEARCH (* SEARCH LOOK-AHEAD TREE *)
: TW; (* RETURNS THE BEST MOVE *)
PROCEDURE NEWBST (* SAVE BEST MOVE INFORMATION *)
(A:TK); (* PLY OF BEST MOVE *)
FUNCTION MINMAX (* PERFORM MINIMAX OPERATION *)
(A:TK) (* PLY TO MINIMAX AT *)
: TB; (* TRUE IF REFUTATION *)
MINMAX := FALSE; (* DEFAULT IS NO PRUNING *)
IF -BSTVL[A+1] > BSTVL[A] THEN (* Score > Alpha ? *)
BEGIN
BSTVL[A] := -BSTVL[A+1]; (* Alpha = Score *)
NEWBST(A); (* SAVE BEST MOVE *)
MINMAX := BSTVL[A+1] <= BSTVL[A-1]; (* -Score < -Beta => Score > Beta *)
END;
END; (* MINMAX *)
FUNCTION SELECT (* SELECT NEXT MOVE TO SEARCH *)
: TB; (* TRUE IF MOVE RETURNED *)
BEGIN
21: (* NEW SEARCH MOOE *)
CASE SRCHM[JNTK] OF
H0: (* INITIALIZE FOR NEW MOVE *)
H1: (* INITIALIZE AT NEW DEPTH *)
H2: (* CAPTURE SEARCH *)
H3: (* FULL WIDTH SEARCH - CAPTURES *)
H4: (* INITIALIZE SCAN OF CASTLE MOVES AND OTHER MOVES BY KILLER PIECE *)
H5: (* FULL WIDTH SEARCH - CASTLES AND OTHER MOVES BY KILLER PIECE *)
H6: (* FULL WIDTH SEARCH - REMAINING MOVES *)
H7: (* RESEARCH FIRST PLY *)
22: (* SELECT EXIT *)
SELECT := INTB; (* RETURN VALUE *)
END; (* SELECT *)
BEGIN (* SEARCH *)
EVALU8; (* INITIAL GUESS AT SCORE *)
BSTVL[AK-2] := VALUE[AW] - WINDOW; (* INITIALIZE ALPHA-BETA WINDON *)
BSTVL[AK-1] := -(VALUE[AW] + WINDOW);
JMTK := AK+1;
WHILE (NODES < FNODEL) AND (JNTK < MAX(ZK DIV 2, ZK-8)) DO
BEGIN
11: (* START NEW PLY *)
12: (* DIFFERENT FIRST MOVE *)
13: (* FLOAT VALUE BACK *)
IF MINMAX(JNTK) THEN
GOTO 15; (* PRUNE *)
14: (* FIND ANOTHER MOVE AT THIS PLY *)
15: (* BACK UP A PLY *)
16: (* EXIT SEARCH *)
SEARCH := BSTMV[AK]; (* RETURN BEST MOVE *)
END; (* SEARCH *)
</pre>
=See also=
* [[Chess (Program)|Chess]]
* [[Chess 0.5X]]
* [[Chess 7.0]]
* [[CookieCat]]
* [[Merlin]]
* [[Shy]]
=Publications=
* [[Peter W. Frey]], [[Larry Atkin]] ('''1978'''). ''[https://archive.org/stream/byte-magazine-1978-10/1978_10_BYTE_03-10_Chess_for_the_Microcomputer#page/n181/mode/2up Creating a Chess Player].'' An Essay on Human and Computer Chess Skill, [[Byte Magazine#BYTE310|BYTE, Vol. 3, No. 10]], pp. 182-191. [http://archive.computerhistory.org/projects/chess/related_materials/text/3-3.Creating_A_Chess_Player/Creating_A_Chess_Player.Frey_Atkin.Byte_Magazine.Oct-1978.062303029.pdf pdf] from [[The Computer History Museum]]
* [[Peter W. Frey]], [[Larry Atkin]] ('''1978'''). ''[https://archive.org/stream/byte-magazine-1978-11/1978_11_BYTE_03-11_The_Sky_is_the_Limit#page/n163/mode/2up Creating a Chess Player, Part 2: Chess 0.5]''. [[Byte Magazine#BYTE311|BYTE, Vol. 3, No. 11]]
* [[Peter W. Frey]], [[Larry Atkin]] ('''1978'''). ''[https://archive.org/stream/byte-magazine-1978-12/1978_12_BYTE_03-12_Life#page/n141/mode/2up Creating a Chess Player, Part 3: Chess 0.5 (continued)]''. [[Byte Magazine#BYTE312|BYTE, Vol. 3, No. 12]]
* [[Peter W. Frey]], [[Larry Atkin]] ('''1979'''). ''[https://archive.org/stream/byte-magazine-1979-01/1979_01_BYTE_04-01_Life_Algorithms#page/n127/mode/2up Creating a Chess-Player, Part 4: Thoughts on Strategy]''. In [http://cs.millersville.edu/~liffick/ Blaise W. Liffick] (ed.), [http://books.google.com/books/about/The_BYTE_book_of_Pascal.html?id=ofpfQgAACAAJ The Byte Book of Pascal], pp. 143-155. Byte Publications, also [[Byte Magazine#BYTE401|BYTE, Vol. 4, No. 1]]
=Forum Posts=
* [https://groups.google.com/d/msg/rec.games.chess.computer/3iSe8NsM024/-SrmrNv4saMJ Byte Chess 0.5 finally available. From Byte Magazine 1978] by I Forget, [[Computer Chess Forums|rgcc]], June 01, 2005
* [https://groups.google.com/d/msg/comp.lang.pascal.misc/ATJoB3c4-jM/9nM_TWmqAwUJ Update for Byte Chess 0.5] by I Forget, [http://groups.google.com/group/comp.lang.pascal.misc/topics comp.lang.pascal.misc], June 12, 2005
* [http://www.talkchess.com/forum/viewtopic.php?t=41896 Need a little help from a Pascal guru (Chess05 Frey/Atkin)] by [[Jim Ablett]], [[CCC]], January 09, 2012
=External Links=
* [http://www.moorecad.com/standardpascal/ByteChess.txt Chess 0.5, Release 1 - 2005-05-30] by [http://www.moorecad.com/standardpascal/scottmoore.html Scott A. Moore]
: [http://www.moorecad.com/standardpascal/Chess05.pas Byte Chess 0.5 source code] hosted by [http://www.moorecad.com/standardpascal/scottmoore.html Scott A. Moore]
* [http://web.archive.org/web/20071221115817/http://classicchess.googlepages.com/Chess.htm Classic Computer Chess - ... The programs of yesteryear] by [[Carey Bloodworth|Carey]], hosted by the [https://en.wikipedia.org/wiki/Internet_Archive Internet Archive]
* [http://www.andreadrian.de/schach/ Computer-Schach] by [[Andre Adrian]] (German)
: [http://www.andreadrian.de/schach/Chess05GNU.pas Chess05GNU.pas]
=References=
<references />
'''[[Engines|Up one Level]]'''
[[FILE:223-front.gif|border|right|thumb|link=https://archive.org/details/byte-magazine-1978-10| [[Byte Magazine#BYTE310|BYTE, Vol. 3, No. 10]] <ref>[https://archive.org/details/byte-magazine-1978-10 Byte Vol. 3, No. 10, October 1978] from the [https://en.wikipedia.org/wiki/Internet_Archive Internet Archive]</ref> ]]
'''Chess 0.5''',<br/>
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 <ref>[http://www.moorecad.com/standardpascal/scottmoore.html Scott A. Moore's site]</ref> sites, unfortunately with some [https://en.wikipedia.org/wiki/Optical_character_recognition OCR]-errors such as syntactical correct replacement of '*' by '+' with score factor by side (XTMV, ±1) in some places <ref>[http://www.moorecad.com/standardpascal/Chess05.pas Byte Chess 0.5 source code] (OCR-Errors!)</ref> . Chess 0.5 may be compiled with [[Pascal#GNUPascal|GNU Pascal]] for recent hardware. Due to non-local [https://en.wikipedia.org/wiki/Goto goto] statements over procedure or function boundaries compiling with [[Pascal#FreePascal|Free Pascal]] is not possible <ref>[http://www.talkchess.com/forum/viewtopic.php?t=41896&start=1 Re: Need a little help from a Pascal guru (Chess05 Frey/Atkin)] by [[Steven Edwards]], [[CCC]], January 09, 2012</ref> .
Larry Atkin is co-author of the famous [[Northwestern University]] [[Chess (Program)|Chess]] line of programs. At the time of the article, Chess was at about version 4.6 <ref>[http://www.computerhistory.org/chess/full_record.php?iid=sft-431614f455002 Chess 4.6 source code], gift of [[David Slate]], from [[The Computer History Museum]], [http://archive.computerhistory.org/projects/chess/related_materials/software/3-3.Chess_4.6_Sourcecode.102645430/chess_4-6.sourcecode.102645430.pdf pdf]</ref> . 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 <ref>[http://www.moorecad.com/standardpascal/ByteChess.txt Chess 0.5, Release 1 - 2005-05-30]</ref> using Chess 4.x like structures of a [[Type A Strategy|Shannon Type A]] approach with [[Alpha-Beta|alpha-beta]] and [[Quiescence Search|quiescence search]], [[Bitboards|bitboards]] and [[Incremental Updates|incremental updated]] [[Attack and Defend Maps|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" <ref>[[Peter W. Frey]], [[Larry Atkin]] ('''1978'''). ''[https://archive.org/stream/byte-magazine-1978-12/1978_12_BYTE_03-12_Life#page/n141/mode/2up Creating a Chess Player, Part 3: Chess 0.5 (continued)]''. [[Byte Magazine#BYTE312|BYTE, Vol. 3, No. 12]]</ref> , 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 6600|CDC]] [[Assembly|assembly]] by Wagner <ref>[[Werner DePauli-Schimanovich-Göttig|Werner DePauli-Schimanovich]] ('''2006'''). ''[http://www.trauner.at/buchdetail.aspx?artnr=20199541 Europolis 6]''. Informatik für Spiele und Verkehr. Extension der Mengenlehre, Herausgeber: Franz Pichler, [http://www.trauner.at/Default.aspx Universitätsverlag Rudolf Trauner], ISBN 978-3-85487-946-6, (SG7) Merlin (ein ComputerChess-Programm) s. 171 (German), [http://books.google.com/books?id=Gf4WibmHVbcC&pg=PA175&lpg=PA175&source=bl&ots=YPtaHAp3Z4&sig=DNRPh11heo8Q1zS3UOBe0qoCF-8&hl=en&ei=0GmnTMX1GMfJswaL-NivDA&sa=X&oi=book_result&ct=result&resnum=1&ved=0CBgQ6AEwAA#v=onepage&q&f=false Google Books]</ref> <ref>[[Helmut Horacek]], [[Marcus Wagner]] ('''1981'''). ''Das Schachprogramm Merlin, Verbesserung von Laufzeit-Effizient, Eröffnungsbibliothek und Bewertungsfunktion.'' 4. Tagung "Berichte aus Informatik-Instituten" (German)</ref> , the Dutch [[Chess 0.5X]] by [[Wim Elsenaar]], a [[PDP-11]] assembly port, and according to postings in [[Computer Chess Forums|rgcc]] <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/3iSe8NsM024/DrW8Dzsr2tYJ Re: Byte Chess 0.5 finally available. From Byte Magazine 1978] by I Forget, [[Computer Chess Forums|rgcc]], June 02, 2005</ref> , the Finnish [[Shy]] by [[Juha Kasanen]], [[Mika Korhonen]] and [[Timo Saari]], written in [[Algol]].
=Description=
==Board Representation==
Chess 0.5 keeps an [[8x8 Board|8x8 board]] either indexed by [[Squares|square]] or [[Ranks|rank]] and [[Files|file]], ...
<pre>
CONST
AX = 0; ZX = 31; (* SUBSETS OF SQUARES *)
AS = 0; ZS = 63; (* BOARD VECTOR LIMITS *)
TYPE
TF = (F1,F2,F3,F4,F5,F6,F7,F8); (* FILES *)
TR = (R1,R2,R3,R4,R5,R6,R7,R8); (* RANKS *)
TI = INTEGER; (* NUMBERS *)
TS = AS..ZS; (* SQUARES *)
TX = AX..ZX; (* SOME SQUARES *)
TY = AY..ZY; (* NUMBER OF TX'S IN A BOARD *)
TM = (LITE,DARK,NONE); (* SIDES *)
TP = (LP,LR,LN,LB,LQ,LK,DP,DR,DN,DB,DQ,DK,MT); (* PIECES: LIGHT PAWN,... , DARK KING, EMPTY SQUARE *)
SX = SET OF TX; (* SET OF SOME SQUARES *)
RB = RECORD (* BOARDS *)
RBTM : TM; (* SIDE TO MOVE *)
RBTS : TT; (* ENPASSANT SQUARE *)
RBTI : TI; (* MOVE NUMBER *)
RBSQ : SQ; (* CASTLE FLAGS *)
CASE INTEGER OF
0: ( RBIS : ARRAY [TS] OF TP); (* INDEXED BY SQUARE *)
1: ( RBIRF : ARRAY [TR,TF] OF TP);(* INDEXED BY RANK AND FILE *)
END;
</pre>
<span id="Bitboard"></span>... and further relies on [[Bitboards|bitboards]], defined as union of arrays of sets and integers:
<pre>
RS = RECORD (* BIT BOARDS *)
CASE INTEGER OF
0: (RSSS: ARRAY [TY] OF SX); (* ARRAY OF SETS *)
1: (RSTI: ARRAY [TY] OF TI); (* ARRAY OF INTEGERS *)
END;
</pre>
Beside the [[Mailbox|mailbox]] arrays (BOARD, MBORD) and [[Bitboard Board-Definition|bitboard board definition]] (TPLOC, TMLOC), Chess 0.5 maintains [[Incremental Updates|incremental updated]] [[Attack and Defend Maps|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 [[Square Attacked By|attacking this square]].
<pre>
BOARD : RB; (* THE BOARD *)
MBORD : ARRAY [TS] OF TP; (* LOOK-AHEAD BOARD *)
ATKFR : ARRAY [TS] OF RS; (* ATTACKS FROM A SQUARE *)
ATKTO : ARRAY [TS] OF RS; (* ATTACKS TO A SQUARE *)
ALATK : ARRAY [TM] OF RS; (* ATTACKS BY EACH COLOR *)
TPLOC : ARRAY [TP] OF RS; (* LOCATIONS OF PIECE BY TYPE *)
TMLOC : ARRAY [TM] OF RS; (* LOCATIONS OF PIECE BY COLOR *)
</pre>
==Bitboard Infrastructure==
===Setwise Operations===
[[General Setwise Operations#Intersection|Bitboard intersection]], [[General Setwise Operations#Union|union]] and [[General Setwise Operations#RelativeComplement|relative complement]] are implemented with [http://www.freepascal.org/docs-html/ref/refsu50.html set-wise operations] "*, +, -", [[General Setwise Operations#ComplementSet|complement]] (not) by relative complement from the [[General Setwise Operations#EmptyAndUniverse|universe]] ([AX..ZX]):
<pre>
PROCEDURE ANDRS (* INTERSECTION OF TWO BITBOARDS *)
(VAR C:RS; (* RESULT *)
A, B:RS); (* OPERANDS *)
VAR
INTY : TY; (* BIT BOARD WORD INDEX *)
BEGIN
FOR INTY := AY TO ZY DO
C.RSSS[INTY] := A.RSSS[INTY] * B.RSSS[INTY];
END; (* ANDRS *)
PROCEDURE IORRS (* UNION OF TWO BIT BOARDS *)
(VAR C:RS; (* RESULT *)
A, B:RS); (* OPERANDS *)
VAR
INTY : TY; (* BIT BOARD WORD INDEX *)
BEGIN
FOR INTY := AY TO ZY DO
C.RSSS[INTY] := A.RSSS[INTY] + B.RSSS[INTY];
END; (* IORRS *)
PROCEDURE NOTRS (* COMPLEMENT OF A BIT BOARD *)
(VAR C:RS; (* RESULT *)
A:RS); (* OPERAND *)
VAR
INTY : TY; (* BIT BOARD WORD INDEX *)
BEGIN
FOR INTY := AY TO ZY DO
C.RSSS[INTY] := [AX..ZX] - A.RSSS[INTY];
END; (* NOTRS *)
</pre>
===BitScan===
<span id="BitScan"></span>[[BitScan#BitscanwithReset|BitScan reverse with reset]] is implemented with machine dependent [[CDC 6600]] [[Float#BitScan|float conversion]] (omitted here) - the machine independent code inefficiently loops over up to 2*32 bits of the set and cries for improvement:
<pre>
FUNCTION NXTTS (* NEXT ELEMENT IN BIT BOARD *)
(VAR A:RS; (* BIT BOARD TO LOCATE FIRST SQUARE, AND THEN REMOVE *)
VAR B:TS (* SQUARE NUMBER OF FIRST SQUARE IN BIT BOARD *)
): TB; (* TRUE IFF ANY SQUARES WERE SET INITIALLY *)
LABEL
11; (* RETURN *)
VAR
INTX : TX; (* BIT BOARD BIT INDEX *)
INTY : TY; (* BIT BOARD WORD INDEX *)
X : RK; (* KLUDGE WORD *)
BEGIN
FOR INTY := ZY DOWNTO AY DO (* LOOP THRU BIT BOARD WORDS *)
IF A.RSTI[INTY] <> 0 THEN
BEGIN
FOR INTX := ZX DOWNTO AX DO (* LOOP THROUGH BITS IN WORD OF SET *)
IF INTX IN A.RSSS[INTY] THEN
BEGIN
B := INTX+INTY*(ZX+1); (* RETURN SQUARE NUMBER *)
A.RSSS[INTY] := A.RSSS[INTY] - [INTX]; (* REMOVE BIT FROM WORD *)
NXTTS := TRUE; (* RETURN A BIT SET *)
GOTO 11; (* RETURN *)
END;
END;
NXTTS := FALSE; (* ELSE RETURN NC BITS SET *)
11: (* RETURN *)
END; (* NXTTS *)
</pre>
===Popcount===
<span id="Popcount"></span>The machine independent [[Population Count|population count]] relies on the above [[Chess 0.5#BitScan|bitscan with reset]]!
<pre>
FUNCTION CNTRS (* COUNT NENBERS OF A BIT BOARD *)
(A:RS): TS; (* BIT BOARD TO COUNT *)
VAR
INTS : TS; (* TEMPORARY *)
INRS : RS; (* SCRATCH *)
IMTS : TS; (* SCRATCH *)
BEGIN
INTS := 0;
CPYRS(INRS,A);
WHILE NXTTS(INRS,IMTS) DO
INTS := INTS+1; (* COUNT SQUARES *)
CNTRS := INTS; (* RETURN SUM *)
END; (* CNTRS *)
</pre>
<span id="EVALU8"></span>
==Evaluation==
Chess 0.5's [[Evaluation|evaluation]] routine '''EVALU8''' implements a [[Lazy Evaluation|lazy evaluation]] only for too worse [[Score|scores]]. If the [[Incremental Updates|incremental updated]] [[Material|material balance]] plus the maximum positional score is still less or equal than [[Alpha|alpha]] (best value two plies up BSTVL[JNTK-2]), only the material balance is assigned without further positional analysis. Otherwise '''EVALU8''' consides [[Mobility|piece mobility]] (counting attacks), [[Pawn Structure|pawn structure]], [[King Safety|king safety]] and some rook terms such as doubled rooks and [[Rook On Seventh|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|side to move]], they are multiplied by a score factor (+1, -1) indexed by side.
<pre>
PROCEDURE EVALU8; (* EVALUATE CURRENT POSITION *)
FUNCTION EVKING (* EVALUATE KING *)
FUNCTION EVMOBL (* EVALUATE MOBILITY *)
FUNCTION EVPAWN (* EVALUATE PAWNS *)
FUNCTION EVROOK (* EVALUATE ROOKS *)
BEGIN
IF XTMV[JNTM]*MBVAL[JNTK] + MAXPS <= BSTVL[JNTK-2] THEN (* !!! OCR *)
(* MOVE WILL PRUNE ANYWAY *)
INTV := XTMV[JNTM] * MBVAL[JNTK]
ELSE
BEGIN
INTV := ( FWPAWN*(EVPAWN(TPLOC[LP],S2,R2)-EVPAWN(TPLOC[DP],S4,R7))
+ FWMINM*(EVMOBL(LB,LN) -EVMOBL(DB,DN) )
+ FWMAJM*(EVMOBL(LR,LQ) -EVMOBL(DR,DQ) )
+ FWROOK*(EVROOK(TPLOC[LR],XRRS[R7])
-EVROOK(TPLOC[DR],XRRS[R2]) )
+ FWKING*(EVKING(TPLOC[LK],TPLOC[LP])
-EVKING(TPLOC[DK],TPLOC[DP]) )
) DIV 64;
MAXPS := MAX(MAXPS,ABS(INTV));
INTV := XTMV[JNTM] * (MBVAL[JNTK] + INTV);
END;
IF SWTR THEN
BEGIN
WRITE(" EVALU8",JNTK,JNTW,INDEX[JNTK],INTV);
PRIMOV(MOVES[INDEX[JNTK]]);
END;
VALUE[INDEX[JNTK]] := INTV; (* RETURN SCORE *)
END; (* EVALU8 *)
</pre>
<span id="Search"></span>
==Search==
The [[Search|search]] is implemented spaghetti like [[Iterative Search|non-recursively]] as [https://en.wikipedia.org/wiki/Finite-state_machine finite-state machine] with [https://en.wikipedia.org/wiki/Goto goto] labels using explicit [[Stack|stacks]] aka [[Ply|ply]] indexed [[Array|arrays]], and features [[Iterative Deepening|iterative deepening]] with [[Aspiration Windows|aspiration]] and [[Alpha-Beta|alpha-beta pruning]]. The value array of [[Best Move|best moves]] indexed by current ply is the current [[Alpha|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|beta]] in the [[Negamax|negamax]] sense. The nested function SELECT implements a [[Move Generation#Staged|staged move generation]], considering [[Root|root search]] (ply 0), full-width and [[Quiescence Search|quiescence]], generating [[Captures|captures]] in [[MVV-LVA|MVV/LVA]] order, [[Killer Move|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:
<pre>
BSTVL : ARRAY [AKM2..ZKP1] OF TV; (* VALUE OF BEST MOVE [-2..17] *)
FUNCTION SEARCH (* SEARCH LOOK-AHEAD TREE *)
: TW; (* RETURNS THE BEST MOVE *)
PROCEDURE NEWBST (* SAVE BEST MOVE INFORMATION *)
(A:TK); (* PLY OF BEST MOVE *)
FUNCTION MINMAX (* PERFORM MINIMAX OPERATION *)
(A:TK) (* PLY TO MINIMAX AT *)
: TB; (* TRUE IF REFUTATION *)
MINMAX := FALSE; (* DEFAULT IS NO PRUNING *)
IF -BSTVL[A+1] > BSTVL[A] THEN (* Score > Alpha ? *)
BEGIN
BSTVL[A] := -BSTVL[A+1]; (* Alpha = Score *)
NEWBST(A); (* SAVE BEST MOVE *)
MINMAX := BSTVL[A+1] <= BSTVL[A-1]; (* -Score < -Beta => Score > Beta *)
END;
END; (* MINMAX *)
FUNCTION SELECT (* SELECT NEXT MOVE TO SEARCH *)
: TB; (* TRUE IF MOVE RETURNED *)
BEGIN
21: (* NEW SEARCH MOOE *)
CASE SRCHM[JNTK] OF
H0: (* INITIALIZE FOR NEW MOVE *)
H1: (* INITIALIZE AT NEW DEPTH *)
H2: (* CAPTURE SEARCH *)
H3: (* FULL WIDTH SEARCH - CAPTURES *)
H4: (* INITIALIZE SCAN OF CASTLE MOVES AND OTHER MOVES BY KILLER PIECE *)
H5: (* FULL WIDTH SEARCH - CASTLES AND OTHER MOVES BY KILLER PIECE *)
H6: (* FULL WIDTH SEARCH - REMAINING MOVES *)
H7: (* RESEARCH FIRST PLY *)
22: (* SELECT EXIT *)
SELECT := INTB; (* RETURN VALUE *)
END; (* SELECT *)
BEGIN (* SEARCH *)
EVALU8; (* INITIAL GUESS AT SCORE *)
BSTVL[AK-2] := VALUE[AW] - WINDOW; (* INITIALIZE ALPHA-BETA WINDON *)
BSTVL[AK-1] := -(VALUE[AW] + WINDOW);
JMTK := AK+1;
WHILE (NODES < FNODEL) AND (JNTK < MAX(ZK DIV 2, ZK-8)) DO
BEGIN
11: (* START NEW PLY *)
12: (* DIFFERENT FIRST MOVE *)
13: (* FLOAT VALUE BACK *)
IF MINMAX(JNTK) THEN
GOTO 15; (* PRUNE *)
14: (* FIND ANOTHER MOVE AT THIS PLY *)
15: (* BACK UP A PLY *)
16: (* EXIT SEARCH *)
SEARCH := BSTMV[AK]; (* RETURN BEST MOVE *)
END; (* SEARCH *)
</pre>
=See also=
* [[Chess (Program)|Chess]]
* [[Chess 0.5X]]
* [[Chess 7.0]]
* [[CookieCat]]
* [[Merlin]]
* [[Shy]]
=Publications=
* [[Peter W. Frey]], [[Larry Atkin]] ('''1978'''). ''[https://archive.org/stream/byte-magazine-1978-10/1978_10_BYTE_03-10_Chess_for_the_Microcomputer#page/n181/mode/2up Creating a Chess Player].'' An Essay on Human and Computer Chess Skill, [[Byte Magazine#BYTE310|BYTE, Vol. 3, No. 10]], pp. 182-191. [http://archive.computerhistory.org/projects/chess/related_materials/text/3-3.Creating_A_Chess_Player/Creating_A_Chess_Player.Frey_Atkin.Byte_Magazine.Oct-1978.062303029.pdf pdf] from [[The Computer History Museum]]
* [[Peter W. Frey]], [[Larry Atkin]] ('''1978'''). ''[https://archive.org/stream/byte-magazine-1978-11/1978_11_BYTE_03-11_The_Sky_is_the_Limit#page/n163/mode/2up Creating a Chess Player, Part 2: Chess 0.5]''. [[Byte Magazine#BYTE311|BYTE, Vol. 3, No. 11]]
* [[Peter W. Frey]], [[Larry Atkin]] ('''1978'''). ''[https://archive.org/stream/byte-magazine-1978-12/1978_12_BYTE_03-12_Life#page/n141/mode/2up Creating a Chess Player, Part 3: Chess 0.5 (continued)]''. [[Byte Magazine#BYTE312|BYTE, Vol. 3, No. 12]]
* [[Peter W. Frey]], [[Larry Atkin]] ('''1979'''). ''[https://archive.org/stream/byte-magazine-1979-01/1979_01_BYTE_04-01_Life_Algorithms#page/n127/mode/2up Creating a Chess-Player, Part 4: Thoughts on Strategy]''. In [http://cs.millersville.edu/~liffick/ Blaise W. Liffick] (ed.), [http://books.google.com/books/about/The_BYTE_book_of_Pascal.html?id=ofpfQgAACAAJ The Byte Book of Pascal], pp. 143-155. Byte Publications, also [[Byte Magazine#BYTE401|BYTE, Vol. 4, No. 1]]
=Forum Posts=
* [https://groups.google.com/d/msg/rec.games.chess.computer/3iSe8NsM024/-SrmrNv4saMJ Byte Chess 0.5 finally available. From Byte Magazine 1978] by I Forget, [[Computer Chess Forums|rgcc]], June 01, 2005
* [https://groups.google.com/d/msg/comp.lang.pascal.misc/ATJoB3c4-jM/9nM_TWmqAwUJ Update for Byte Chess 0.5] by I Forget, [http://groups.google.com/group/comp.lang.pascal.misc/topics comp.lang.pascal.misc], June 12, 2005
* [http://www.talkchess.com/forum/viewtopic.php?t=41896 Need a little help from a Pascal guru (Chess05 Frey/Atkin)] by [[Jim Ablett]], [[CCC]], January 09, 2012
=External Links=
* [http://www.moorecad.com/standardpascal/ByteChess.txt Chess 0.5, Release 1 - 2005-05-30] by [http://www.moorecad.com/standardpascal/scottmoore.html Scott A. Moore]
: [http://www.moorecad.com/standardpascal/Chess05.pas Byte Chess 0.5 source code] hosted by [http://www.moorecad.com/standardpascal/scottmoore.html Scott A. Moore]
* [http://web.archive.org/web/20071221115817/http://classicchess.googlepages.com/Chess.htm Classic Computer Chess - ... The programs of yesteryear] by [[Carey Bloodworth|Carey]], hosted by the [https://en.wikipedia.org/wiki/Internet_Archive Internet Archive]
* [http://www.andreadrian.de/schach/ Computer-Schach] by [[Andre Adrian]] (German)
: [http://www.andreadrian.de/schach/Chess05GNU.pas Chess05GNU.pas]
=References=
<references />
'''[[Engines|Up one Level]]'''
