COMMENT ? VALID 00009 PAGES RECORD PAGE DESCRIPTION 00001 00001 00002 00002 BEGIN "GAME" 00005 00003 C GENMOVES, PBOARD, LEGALMOVE 00009 00004 C STATIC EVALUATION 00013 00005 C MAKE, UNMAKE, SORT 00017 00006 C DYNEVAL 00020 00007 C INITIALIZATION PROCEDURE, CHECKTEST 00023 00008 C THE MAIN PROGRAM 00024 00009 C BASIC DISPATCH LOOP 00034 ENDMK ?; BEGIN "GAME" COMMENT DEFINE SOME HANDY MACROS; DEFINE C="COMMENT", CRLF="'15&'12", INTARY="SAFE INTEGER ARRAY", WIN="10000000000", FORL(I,N)="FOR I?1 STEP 1 UNTIL N DO"; PRELOAD_WITH -11,-9,-10,-1,0,1,10,9,11; INTARY MOVDIR[-4:4]; C THIS IS THE ADDITIVE OFFSET FOR VARIOUS MOVES; PRELOAD_WITH -12,-11,-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12; INTARY GPRE[-12:12]; C THIS IS TO INITIALIZE ARRAY FOR STATICEVAL; INTARY B[0:99]; C THIS IS THE BOARD WITH EDGES ADDED, THE INDEX IS ROW*10+COLUMN, WITH ROW1 AND COLUMN 1 AT THE TOP AND LEFT RESPECTIVELY. B[I]=0 MEANS LOCATION I IS EMPTY, B[I]=99 MEANS LOCATION I IS AN APPENDED EDGE, B[I]=J WHERE J?0 MEANS THAT SQUARE I IS OCCUPIED BY MAN J. O PLAYS MEN 1 TO 12 AND X PLAYS -1 TO -12; INTARY L[-12:12];C THIS ARRAY,INDEXED BY MAN NUMBER, GIVES THE LOCATION OF EACH MAN ON THE BOARD. IF HE HAS BEEN CAPTURED THEN HIS LOCATION IS ZERO.; INTARY S[0:46];C THIS ARRAY IS USED TO KEEP THE CURRENT COUNTS OF THE NUMBER OF MEN IN EACH ROW, COLUMN, AND DIAGONAL.; INTARY SX[0:99,1:4];C THIS ARRAY IS INDEXED BY BOARD POSITION AND DIRECTION TO GIVE AN INDEX INTO ARRAY S WHERE THE COUNT FOR THAT DIRECTION AND LOCATION IS KEPT. THE DIRECTION INDEX IS 1 FOR HORIZONTAL, 2 FOR VERTICAL, 3 FOR LOWER LEFT TO UPPER RIGHT, AND 4 FOR UPPER LEFT TO LOWER RIGHT.; INTEGER TURN;C -1 FOR X TO PLAY,1 FOR O TO PLAY; INTEGER NUMMOVE,OLDNUM; C MOVE NUMBER; INTEGER CUTOFF;C THIS CONTROLS THE DEPTH OF THE LOOK-AHEAD PROCESS; INTEGER BREADTH;C THE BREADTH OF SEARCH; INTEGER BOARDS;C COUNT OF NUMBER OF BOARDS EXAMINED; INTEGER CPUTIME,OLDCPU;C COMPUTING TIME; INTARY DIV10,MOD10[0:99];C FASTER THAN DIVIDING; EXTERNAL PROCEDURE K.OUT; C GENMOVES, PBOARD, LEGALMOVE; C PROCEDURE TO GENERATE LEGAL MOVES AND PLACE THEM INTO THE OUTPUT ARRAYS MF AND MT, AND RETURN A COUNT OF THE NUMBER OF LEGAL MOVES GENERATED.; INTEGER PROCEDURE GENMOVES(INTARY MF,MT);BEGIN INTEGER COUNT,DIR,SIGN,Q,P,I,NTIM,Q1,TURN12; COUNT?0; TURN12?TURN*12; FOR P?TURN STEP TURN UNTIL TURN12 DO IF L[P] THEN C LOOP ON ALL MEN; FORL(DIR,4) C CONSIDER ALL DIRECTIONS IT CAN MOVE IN; FOR SIGN?-1,1 DO BEGIN C BOTH WAYS; LABEL NSIGN; Q?L[P]; NTIM?S[SX[Q,DIR]]-1; Q1?MOVDIR[DIR*SIGN]; FOR I?1 STEP 1 UNTIL NTIM DO BEGIN Q?Q+Q1; IF TURN*B[Q]<0 OR B[Q]=99 THEN GO TO NSIGN; END; Q?Q+Q1; IF B[Q]=99 OR TURN*B[Q]>0 THEN GO TO NSIGN; COUNT?COUNT+1; MF[COUNT]?L[P];MT[COUNT]?Q; NSIGN:END; RETURN(COUNT) END; C ***********************************************************; C PROCEDURE TO PRINTOUT THE BOARD AS IT STANDS; PROCEDURE PBOARD;BEGIN INTEGER I,J; OUTSTR( CRLF&" 1 2 3 4 5 6 7 8 "& CRLF&" ___________________________"); FOR I?10 STEP 10 UNTIL 80 DO BEGIN OUTSTR(CRLF&" | |"); OUTSTR(CRLF&" "&CVS(DIV10[I])&" | "); FOR J?1 STEP 1 UNTIL 8 DO BEGIN OUTSTR((IF B[I+J]=0 THEN " . " ELSE IF B[I+J]<0 THEN " X " ELSE " O ")) END; OUTSTR("|") END; OUTSTR(CRLF&" |_________________________|"&CRLF); END; C ***********************************************************; INTEGER PROCEDURE LEGALMOVE(INTEGER F,T); BEGIN INTEGER I,DIR,SIGN,DIF,INCR; DEFINE ELSECOND(A,B)="ELSE IF DIF MOD A = 0 THEN BEGIN INCR?A; DIR?B END"; IF TURN*B[F]?0 THEN RETURN(0); DIF? ABS(T-F); SIGN? IF T0 THEN BJ>0 ELSE BJ<0) THEN FOR K?P STEP P UNTIL P12 DO IF G[K]=GM THEN G[K]?V; END; IF P=-1 THEN FOR M?-12 STEP 1 UNTIL -1 DO G[M]?-G[M]; C FIND MIN DISTANCES BETWEEN GROUPS; MIN[1,1]?10; ARRBLT(MIN[1,2],MIN[1,1],143); FOR M?P STEP P UNTIL P11 DO C ONCE FOR EACH OF HIS MEN; IF (LM?L[M]) THEN C ONLY IF HE IS ON THE BOARD; BEGIN GM?G[M]; FOR N?M+P STEP P UNTIL P12 DO C HIT THE REST OF HIS MEN; IF GM?(GN?G[N]) AND (LN?L[N])THEN BEGIN V?(ABS(DIV10[LM]-DIV10[LN]) MAX ABS(MOD10[LM]-MOD10[LN]))-1; IF VCOUNT OR VALU[TWOM]>VALU[TWOM+1] THEN TWOM ELSE TWOM+1; WHILE K?TOP AND VVALU[K] THEN K?K+1; END; MF[J]?MFM;MT[J]?MTM;VALU[J]?V; END; FOR M?COUNT STEP -1 UNTIL 1 DO BEGIN TOP?M-1;V?VALU[M];MTM?MT[M];MFM?MF[M];J?M;K?1; WHILE K?TOP AND VVALU[K] THEN K?K+1; END; MF[J]?MFM;MT[J]?MTM;VALU[J]?V; END; END; C DYNEVAL; C **********************************************************; C PROCEDURE TO DO THE BASIC LOOK-AHEAD OPERATION WITH ALPHA-BETA PRUNING. THE GLOBAL ARRAYS ALPHA, MFBEST, AND MTBEST STORE THE BEST ALPHA AND THE BEST ASSOCIATED MOVE. THEY ARE ALL INDEXED BY THE DEPTH OF RECURSION.; C **********************************************************; INTARY ALPHA,MFBEST,MTBEST[-2:50]; RECURSIVE INTEGER PROCEDURE DYNEVAL(INTEGER DEPTH);BEGIN INTARY MF,MT[1:100]; C WHERE GENMOVE DOES IT'S STUFF; INTARY VALU[1:100];C FOR INITIAL STATIC EVALUATION; INTEGER COUNT,M,VAL,MAN,S1,S2; DEFINE SETBEST(M)="MFBEST[DEPTH]?MF[M];MTBEST[DEPTH]?MT[M]"; COUNT?GENMOVES(MF,MT); IF DEPTH?CUTOFF THEN BEGIN FORL(M,COUNT) BEGIN MAN?MAKEMOVE(MF[M],MT[M]); VALU[M]?STATICEVAL; UNMAKEMOVE(MF[M],MT[M],MAN) ; IF VALU[M]=-WIN THEN BEGIN SETBEST(M);RETURN(WIN) END; END; SORT(MF,MT,VALU,COUNT) END; ALPHA[DEPTH]?ALPHA[DEPTH-2];SETBEST(1); FORL(M,COUNT) IF ALPHA[DEPTH]=ALPHA[DEPTH-2] OR MALPHA[DEPTH] THEN BEGIN ALPHA[DEPTH]?-VAL;SETBEST(M) END; IF VAL?ALPHA[DEPTH-1] THEN RETURN(WIN);C STOP IF BETTER BRANCH KNOWN; END; RETURN(ALPHA[DEPTH]) END; C INITIALIZATION PROCEDURE, CHECKTEST; C ***********************************************************; C SET UP FOR START OF A GAME; C ***********************************************************; PROCEDURE INIT; BEGIN INTEGER I,DIR; C FIRST SET UP THE BOARD; FOR I?0 STEP 1 UNTIL 99 DO B[I]?0; FORL(I,6) BEGIN C INITIAL POSITIONS; B[I+11]?I;B[I+81]?I+6;C O'S MEN; B[I*10+11]?-I;B[I*10+18]?-I-6;C X'S MEN; END; C SETUP LOCATION ARRAY L; FOR I?0 STEP 1 UNTIL 99 DO IF B[I] THEN L[B[I]]?I; C FINISH BOARD BY MARKING EDGES WITH 99; FORL(I,10) B[I-1]?B[I+89]?B[I*10-1]?B[I*10-10]?99; C NOW INITIALIZE THE ARRAY SX; FORL(I,99) IF B[I]?99 THEN BEGIN SX[I,1]?DIV10[I];C ROWS GO IN S[1]...S[8]; SX[I,2]?MOD10[I]+8;C COLS GO IN S[9]...S[16]; SX[I,3]?MOD10[I] + DIV10[I]+15;C / IN S[17]...S[31]; SX[I,4]?MOD10[I] - DIV10[I]+39;C OTHER IN S[32]-S[46]; END; C NOW INITIALIZE THE ARRAY S WITH COUNTS; FORL(I,46) S[I]?2; S[1]?S[8]?S[9]?S[16]?6; S[17]?S[24]?S[31]?S[32]?S[39]?S[46]?0; TURN?-1; NUMMOVE?1; SCP1?SCM1?216; END; C TEST WHETHER PLAYER TO MOVE IS IN CHECK; BOOLEAN PROCEDURE CHECKTEST; BEGIN INTEGER COUNT, M, NOCHECK, FPOS, TPOS, MANCAP; INTARY MF,MT[1:100]; TURN?-TURN; COUNT?GENMOVES(MF,MT); TURN?-TURN; NOCHECK?TRUE; FORL(M,COUNT) IF NOCHECK THEN BEGIN FPOS?MF[M];TPOS?MT[M];L[MANCAP?B[TPOS]]?0; L[B[TPOS]?B[FPOS]]?TPOS;B[FPOS]?0; IF SCORE(-TURN)=0 THEN NOCHECK?FALSE; L[B[FPOS]?B[TPOS]]?FPOS;B[TPOS]?0; IF MANCAP THEN B[L[MANCAP]?TPOS]?MANCAP END; RETURN(¬NOCHECK) END; C THE MAIN PROGRAM; STRING PROCEDURE STRIN;BEGIN OUTSTR(CRLF&"==>");RETURN(INCHWL) END; STRING SS,TS1,FILE; INTARY GAME,ISCHECK[1:200];C GAME HISTORY; INTEGER I,M,BRK,WALLP,VALSOUT,AUTOSAVE,COUNT,BRCHAR,EOF,FLAG,KEY; SETBREAK(1,"0123456789",NULL,"IR"); SETBREAK(2,"0123456789",NULL,"XS"); OLDCPU?CALL(0,"RUNTIM"); SETFORMAT(0,2); C SETUP DIV10 AND MOD10; FOR I?0 STEP 1 UNTIL 99 DO BEGIN DIV10[I]?I DIV 10;MOD10[I]?I MOD 10 END; WALLP?VALSOUT?1; ALPHA[-2]?ALPHA[-1]?-WIN;BREADTH?15;CUTOFF?2; AUTOSAVE?TRUE; FILE?"LOA.TMP"; INIT;PBOARD; OUTSTR(CRLF&"TO SEE A LIST OF AVAILABLE COMMANDS, TYPE H "&CRLF); C BASIC DISPATCH LOOP; WHILE (SS?STRIN)?"Q" DO BEGIN LABEL OK; KEY?0; FOR TS1?"H","P","S","M","L","U","Z","O","I","W","V","C","B","A","E","K" DO BEGIN IF TS1=SS THEN DONE; KEY?KEY+1 END; CASE KEY OF BEGIN "H" OUTSTR(CRLF& "THE FOLLOWING COMMANDS ARE AVAILABLE: M1234 MOVE PIECE FROM 12 TO 34, THEN MACHINE REPLIES Z1234 MOVE PIECE FROM 12 TO 34, NO REPLY (CAN GIVE LIST OF MOVES) P PRINT BOARD L PRINT LISTING OF GAME U UNMAKE LAST TWO HALF-MOVES S RESTART Q QUIT E TYPE OUT BOARD EVALUATION (O VALUE, X VALUE, DIFFERENCE) WY PRINT BOARD AFTER EACH HALF-MOVE (Y OR N, INITIALLY Y) VY PRINT VALUES AFTER EACH MACHINE MOVE (Y OR N, INITIALLY Y) (O VALUE, X VALUE, DIFFERENCE, LOOK-AHEAD VALUE, POSITIONS EVALUATED, TIME IN SECONDS) C2 SET SEARCH DEPTH CUTOFF TO 2 (LOOK 3 HALF-MOVES AHEAD) B15 SET SEARCH BREADTH CUTOFF TO 15 (LOOK AT 15 BEST AT EACH LEVEL) A PRINT PRESENT VALUES OF BREADTH AND DEPTH CUTOFFS O WRITE OUT A DISK FILE FOR RECONSTRUCTING THIS GAME (INITIALIZED TO LOA.TMP. WHEN THE EXTENSION IS "".TMP"" THIS FILE IS WRITTEN OUT AUTOMATICALLY FOLLOWING EACH M OR Z MOVE, AND DELETED BY THE Q COMMAND. A NULL FILE SPECIFICATION CANCELS THE AUTOMATIC SAVING.) I RECONSTRUCT A GAME FROM A PREVIOUSLY SAVED FILE H TYPE OUT THIS INFORMATION X MOVES FIRST, THEN MOVES ALTERNATE. TO MOVE FIRST, SIMPLY TYPE M.... TO HAVE MACHINE MOVE FIRST, TYPE Z2143 (IT MOVES 21-43), THEN M...." &CRLF&CRLF); "P" PBOARD; BEGIN "S" INIT; IF WALLP THEN PBOARD END; BEGIN "M" M?CVD(SS[2 TO INF]); IF LEGALMOVE(M DIV 100, M MOD 100) THEN BEGIN GAME[NUMMOVE]?M;NUMMOVE?NUMMOVE+1; MAKEMOVE(M DIV 100,M MOD 100); IF WALLP THEN PBOARD; ISCHECK[NUMMOVE-1]?IF CHECKTEST THEN 1 ELSE 0; IF SCP1=0 OR SCM1=0 THEN BEGIN ISCHECK[NUMMOVE-1]?IF SCP1=0 AND SCM1=0 THEN 4 ELSE IF STATICEVAL=WIN THEN 3 ELSE 2; OUTSTR(CRLF&(CASE ISCHECK[NUMMOVE-1] OF (" "," ","YOU WIN--CONGRATULAIONS!","HA --YOU GAVE ME A WIN!","OOPS--A DRAW!"))); GO TO OK END; BOARDS?0; DYNEVAL(0); CPUTIME?CALL(0,"RUNTIM"); MAKEMOVE(MFBEST[0],MTBEST[0]); OUTSTR(CRLF&"MACHINE MOVES "&CVS(MFBEST[0])&" TO "&CVS(MTBEST[0])& (IF STATICEVAL?-WIN AND CHECKTEST THEN ", CHECK" ELSE " ")); TS1?CVF((CPUTIME-OLDCPU)/1000); OLDCPU?CPUTIME; IF VALSOUT THEN OUTSTR(CRLF&CVS(SCP1)&" "&CVS(SCM1)&" " &CVS(STATICEVAL)&" "&CVS(ALPHA[0])&" "&CVS(BOARDS)&" "&TS1); GAME[NUMMOVE]?MFBEST[0]*100+MTBEST[0]; ISCHECK[NUMMOVE]?IF CHECKTEST THEN 1 ELSE 0; NUMMOVE?NUMMOVE+1; IF STATICEVAL=-WIN THEN BEGIN OUTSTR(CRLF&(IF SCP1=0 AND SCM1=0 THEN "OOPS--I GAVE YOU A DRAW" ELSE "MACHINE WINS ... TOO BAD!")); ISCHECK[NUMMOVE-1]?IF SCP1=0 AND SCM1=0 THEN 4 ELSE 2 END; IF WALLP THEN PBOARD; IF AUTOSAVE THEN BEGIN OPEN(1,"DSK",8,0,2,COUNT,BRCHAR,EOF); ENTER(1,FILE,FLAG); WORDOUT(1,NUMMOVE-1); ARRYOUT(1,GAME[1],NUMMOVE-1); ARRYOUT(1,ISCHECK[1],NUMMOVE-1); CLOSE(1); END; GO TO OK END; OUTSTR(CRLF&"ILLEGAL MOVE...TRY AGAIN"); END; "L" FOR I?1 STEP 2 UNTIL NUMMOVE-1 DO OUTSTR(CRLF&CVS((I+1) DIV 2)&". "&CVS(GAME[I] DIV 100)&"-"&CVS(GAME[I] MOD 100) &(CASE ISCHECK[I] OF (" ","+ ","++","--"," DRAWN ")) &(IF I=NUMMOVE-1 THEN " " ELSE " "&CVS(GAME[I+1] DIV 100)&"-"&CVS(GAME[I+1] MOD 100) &(CASE ISCHECK[I+1] OF (" ","+ ","++","- "," DRAWN ")) ) ); BEGIN "U" OLDNUM?NUMMOVE-3;INIT; FORL(I,OLDNUM) MAKEMOVE(GAME[I]DIV 100,GAME[I]MOD 100); IF WALLP THEN PBOARD; NUMMOVE?OLDNUM+1 END; BEGIN "ZLOOP" TS1?SCAN(SS,1,BRK); TS1?SCAN(SS,2,BRK); WHILE LENGTH(TS1)>0 DO BEGIN M?CVD(TS1); IF ¬LEGALMOVE(M DIV 100,M MOD 100) THEN BEGIN OUTSTR("MOVE "&TS1&" ILLEGAL"); DONE END; GAME[NUMMOVE]?M; NUMMOVE?NUMMOVE+1; MAKEMOVE(M DIV 100,M MOD 100); ISCHECK[NUMMOVE-1]?IF CHECKTEST THEN 1 ELSE 0; IF SCP1=0 OR SCM1=0 THEN ISCHECK[NUMMOVE-1]?IF SCP1=0 AND SCM1=0 THEN 4 ELSE IF STATICEVAL=WIN THEN 3 ELSE 2; TS1?SCAN(SS,1,BRK); TS1?SCAN(SS,2,BRK); END; IF WALLP THEN PBOARD; IF AUTOSAVE THEN BEGIN OPEN(1,"DSK",8,0,2,COUNT,BRCHAR,EOF); ENTER(1,FILE,FLAG); WORDOUT(1,NUMMOVE-1); ARRYOUT(1,GAME[1],NUMMOVE-1); ARRYOUT(1,ISCHECK[1],NUMMOVE-1); CLOSE(1); END END; BEGIN "O" SS?SS[2:?]; WHILE SS=" " DO SS?SS[2:?]; IF ¬SS THEN BEGIN AUTOSAVE?FALSE; GO OK END; OPEN(1,"DSK",'10010,0,2,COUNT,BRCHAR,EOF); ENTER(1,SS,FLAG); IF FLAG THEN BEGIN OUTSTR("BAD FILE SPECIFICATION !!!!"); GO OK END; WORDOUT(1,NUMMOVE-1); ARRYOUT(1,GAME[1],NUMMOVE-1); ARRYOUT(1,ISCHECK[1],NUMMOVE-1); CLOSE(1); FILE?SS; AUTOSAVE?FILE[?-3:?]=".TMP"; END; BEGIN "I" SS?SS[2:?]; WHILE SS=" " DO SS?SS[2:?]; OPEN(2,"DSK",'10010,2,0,COUNT,BRCHAR,EOF); LOOKUP(2,SS,FLAG); IF FLAG THEN BEGIN IF FLAG LAND '777777=8 THEN OUTSTR("BAD FILE SPECIFICATION !!!!") ELSE OUTSTR("NONEXISTENT FILE !!!!"); GO OK END; INIT; OLDNUM?WORDIN(2); ARRYIN(2,GAME[1],OLDNUM); ARRYIN(2,ISCHECK[1],OLDNUM); FORL(I,OLDNUM) MAKEMOVE(GAME[I]DIV 100,GAME[I]MOD 100); IF WALLP THEN PBOARD; NUMMOVE?OLDNUM+1; END; "W" WALLP?(SS[2 FOR 1]="Y"); "V" VALSOUT?(SS[2 FOR 1]="Y"); "C" CUTOFF?CVD(SS[2 TO INF]); "B" BREADTH?CVD(SS[2 TO INF]); "A" OUTSTR(CRLF&"B: "&CVS(BREADTH)&" C: "&CVS(CUTOFF)); "E" OUTSTR(CRLF&CVS(SCP1)&" "&CVS(SCM1)&" "&CVS(STATICEVAL)); "K" K.OUT; "NOT RECOGNIZED" OUTSTR(SS&"???") END; OK:END; IF AUTOSAVE THEN BEGIN OPEN(1,"DSK",8,0,2,COUNT,BRCHAR,EOF); ENTER(1,FILE,FLAG); IF ¬FLAG THEN RENAME(1,"",0,FLAG); CLOSE(1) END; END;