COMPUTE II ISSUE 1 / APRIL/MAY 1980 / PAGE 19

An Upgrade for KIM MICROCHESS 1.0

Garold R. Stone
P.O. Box 153
Annapolis Junction, MD. 20701

If you have Peter Jennings' MICROCHESS program for the KIM-1 microcomputer you can teach it to play a significantly better game of chess without adding a single byte of expansion memory. This article describes a “patch” I have written for MICROCHESS which gives the computer a more flexible opening game and two new strategies for the middle and end game. Just load your copy of MICROCHESS, enter my code from the accompanying program listing along with the chess opening sample from table one, and play chess. There are no changes in the way you run the program. (For a description of the MICROCHESS program see KB, August 1978, page 74). For clarity I will use the term MICROCHESS only to refer to the original program as written by Peter Jennings. I will say ”patch” to refer to the changes I am describing here.

Off the Shelf

The MICROCHESS I bought from Micro-ware Ltd. opens the game by playing from a pre-selected list of moves for a user chosen chess opening (Roy Lopez, French Defence, etc.). That opening list also contains one anticipated opponent move for each computer move. Things go well as long as the opponent makes the anticipated replies. But a human opponent seldom does that – at least I don't. As soon as I make a novel move MICROCHESS permanently abandons the opening list. Whenever MICROCHESS is forced to quit the opening list too early, coherent development of pieces stops, the queen usually comes out too early, an ill-prepared attack is launched, and the computer loses its ability to castle (because castling is only possible from the opening list).

Compromises in 1.1K

Mr. Jennings points to these problems in his excellent documentation manual:

“A major problem in the analysis is that there is only one strategy which is used for the opening, the middle game and the end game. This involves a considerable compromise of three different types of play.”

The single strategy used by MICROCHESS is best suited for the middle game, where the capture of pieces dominates. In order to add a dynamic opening strategy which would emphasize the development and positioning of pieces, I had to settle for my own set of compromises, as you'll see. I should point out that Mr. Jennings seems to have surmounted this problem in the other versions of MICROCHESS he has written for microcomputers with more memory, such as the PET, TRS-80, and the APPLE.

The Opening

Table 1 shows my data format for eight opening development moves. Unlike in MICROCHESS, anticipated opponent replies are not listed. On each turn the patched program evaluates all of the computer's available moves. The available move which comes out with the highest evaluation is compared with the evaluation for the next legal move in my opening list and the higher of the two is selected as the computer's move for that turn. The development move is usually selected because its evaluation is always boosted by a threshold factor. I set the threshold factor high enough so that only moves with a significantly higher evaluation can override the development move. The higher the threshold, the more likely it is that the development move will be selected for that turn. Thus, the computer follows an opening game plan, responds to significant attack threats or capture opportunities, and then continues to carry out the opening game plan on the next turn by consulting the opening list again.

Books on chess openings and opening game strategy can serve as guides in writing new lists of development moves. Choose openings which are general in nature and do not depend on specific moves by the opponent. Specify each development move by giving the piece (variable DEVP), the square of origin (FROM), and the destination (TO), using the same notation as in MICROCHESS (see tables 2 and 3). Openings for white and black will require separate notation. Fill all unused locations in the opening list with the magic number 1F (hexadecimal), which causes those locations to be skipped because they are off the board.

Castling

As in MICROCHESS the computer's castling move must be completed for it by moving its rook after the computer signals castling by moving its King the necessary two squares. My added programming will prevent castling if the computer's King is off its starting square or if it would end up in check. The other rules for castling are not checked, however. If the computer castles illegally, then the move must be refereed. The simplest way is to use the “touch-move” rule – once a player touches a piece it must be moved. Thus, the computer would have to move its King somewhere else, and you would enter that move for it. If there are no legal moves left for the King, then the computer must resign. This situation seldom comes up because I write openings which castle early enough to avoid the risk and annoyance of an illegal attempt.

See Tables 2 and 3 for coding of Pieces and Squares

Program Flow

What follows is a description of how the patched program works. MICROCHESS subroutines which are not defined in my accompanying program listing are in bold letters.

Whenever it is the computer's turn to move, MICROCHESS command loop CHESS calls my version of subroutine GO (see 03A2 in the program listing). MICROCHESS uses the value of a variable called STATE to keep track of what it's doing. State 4 guides the generation and evaluation of the computer's available moves. There are other states for generating potential opponent replies, etc. MICROCHESS subroutine GNMX (see 03AA) initializes some variables called “counts” for evaluating moves and then generates all moves available to the computer on that turn. GNMX calls MICROCHESS subroutine JANUS to calculate and evaluate the counts for each trial move. Based on the value in STATE, JANUS decides what to do next – generate potential opponent replies for evaluation, calculate exchanges of pieces, etc. JANUS changes the value in STATE as it goes.

OPPONENT

Note: Whether playing White or Black, the Computer's starting squares are always 00 through 17. Be sure to orient the playing board so that the lower left corner is black. The White Queen should be on a white square and the Black Queen should be on a black square.

JANUS and portions of GNMX call each other recursively, again and again, until all of the computer's available moves have been evaluated in the light of all possible opponent replies. By the time program control returns from that very first call to subroutine GNMX, one move has emerged with an evaluation higher than all the others.

Then my patch searches the opening move list from the beginning to find the first piece (variable DEVP) which is still where it is supposed to be (FROM) (see 03B1). The move by this piece to its destination (TO) is checked for legality by a call into the middle of MICROCHESS subroutine CMOVE.

If the list move is legal, then the threshold factor (FACTOR) is stored in the variable BIAS for later use (see 03D8). MICROCHESS subroutine JANUS is called to do the counts for this list move and for the opponent's potential replies.

To evaluate these counts JANUS calls up my version of subroutine STRATEGY (see 1780-17C1). This is where the evaluation of the list move is boosted by adding the threshold factor which was stored earlier in the variable BIAS. Actually, this same subroutine STRATEGY is used by JANUS to evaluate any trial move but BIAS is always zero except for legal list moves. If the selected list move is not legal, then JANUS is not called to evaluate it, and no more list moves will be tried for that turn. This ensures that moves from the opening list are made in the order you wrote them. After the last list move has actually been moved, the variable OMOVE is set to zero and the opening list is ignored for the rest of the game (see 03AF).

As you exit subroutine STRATEGY you enter that portion of MICROCHESS which compares the evaluation of the current trial move with that of the best move so far, saving the better of the two as the new best move so far. This is also where MICROCHESS tests for check or checkmate before returning to JANUS. Control then passes to the MICROCHESS subroutine which takes the best trial move and actually moves it (see 03E3). The computer's move is flashed on the KIM display and the program returns to the MICROCHESS command loop, ready for the opponent to enter his move.

Middle and End Game

MICROCHESS sees only one and a half moves ahead. With this limited horizon it has trouble finding and closing in on the opposing King. To compensate for this I give a bonus of two points for moves inside a zone which surrounds the opposing King and moves along with it. The computer's Pawns and King do not get the bonus (see 179D).

Another strategy encourages moves which hem in the opposing King, in preparation for checkmate. The value of any trial move is decreased by the number of safe moves it leaves for the opposing King. This is the same as adding a point for each square denied to the opposing King. Since MICROCHESS calls subroutine JANUS to evaluate only legal moves, it was easy enough to put a subroutine call inside JANUS which would increment a mobility count (BKMOB) for each legal move found for the opponent King when the computer is checking for opponent reply moves during state zero (see 0112, 17D9, 179A).

Both strategies come into play only after the opening list has been emptied, so as not to interfere with the development of pieces during the opening game (see 1796).

Evaluation

I approached move evaluation in much the same way as in MICROCHESS – adding and subtracting weighted counts representing captures, position, and mobility for both sides. I did not use some of the counts generated by MICROCHESS and I created the new ones I described above. Given the severe memory restrictions, my goal was an evaluation formula which emphasizes immediate and tangible factors, such as position and the values of pieces captureable during the current turn. Less immediate factors, such as overall attack strengths, are given fractional weighting. These become influential only after more significant factors have cancelled each other out.

For now I've had to be satisfied with just breaking MICROCHESS of its habit of throwing away its pieces by occasionally making bad decisions about captures where pieces are exchanged. In my patch any piece the computer wants to capture must be greater than or equal to the most valuable piece the computer would lose by making that move (variable BMAXC). Only trial moves which pass this admittedly simplistic test are given an extra 20 hex points (see 17B1). There is more that could be done, like making better use of the MICROCHESS counts for exchanges involving up to three captures per side.

I hope I've made my point. All you need is a shoe horn and you can slip just about any changes you want into the 1.1K KIM MICROCHESS. You may pinch a few toes in the process, but the result is a KIM that plays better chess. By trying to “upgrade” MICROCHESS I really learned to appreciate what an excellent piece of work it is.

MICROCHESS is available on KIM cassette with documentation manual from Micro-Ware Ltd., 496 Albert St., Suite 7, Waterloo, Ontario, Canada, N2L 3V4

Abbreviated Instructions for Loading and Running MICROCHESS 1.0 UPGRADE

Load:

Enter (RS) to reset KIM

Enter (AD) 00F1 (DA) 00 to reset decimal flag

Enter (AD) 17F9 (DA) C1 to enter tape ID for program segment

Enter (AD) 1873 (GO) to start read routine of KIM

Press “Play” on cassette player

STOP recorder when display shows: 0000

Enter (RS) (AD) 1873 (GO) to read second program segment (same label “C1”)

STOP recorder when display shows: 0000

Enter (RS) (GO) to start program execution

Playing:

Enter (C) on KIM hexpad keyboard to reset program for new game

Enter (PC) (for “play chess”) because KIM plays first

After KIM gives its move, enter your move as FROM-TO according to the board notations in table 3 of the article. Keep typing until your move shows correctly, then enter (F) (PC).

 	 	 	 	0110 	 	.BA 	$3A2 	
03A2- 	A2 	04 	 	0120 	GO 	LDX 	#$04	; RESET BEST EVALUATION
03A4- 	86 	FA 	 	0130 	 	STX 	*BESTV 	; SO FAR
03A6- 	86 	B5 	 	0140 	 	STX 	*STATE 	; STATE = 4; TRAIL MOVES
03A8- 	A2 	12 	 	0150 	 	LDX 	#$12	; ZERO COUNTERS & BIAS
03AA- 	20 	02 	02 	0160 	 	JSR 	GNMX	; GENERATE TRAIL MOVES
03AD- 	A4 	DC 	 	0170 	 	LDY 	*OMOVE 	; OPENING LIST DONE?
03AF- 	10 	32 	 	0180 	 	BPL 	NODEVP 	; - YES, MID-GAME
03B1- 	A0 	E6 	 	0190 	 	LDY 	#$E6	; - NO, NEXT DEVP
03B3- 	C8 	 	 	0200 	NEXT 	INY 	 	
03B4- 	C8 	 	 	0210 	 	INY 	;	INDEX OF DEVP
03B5- 	84 	DC 	 	0220 	 	STY 	*OMOVE 	; OPENING LIST EMPTY?
03B7- 	10 	2A 	 	0230 	 	BPL 	NODEVP 	; - YES, MID-GAME
03B9- 	B6 	DC 	 	0240 	 	LDX 	*DEVP,Y ; -NO, NEXT DEVP
03BB- 	86 	B0 	 	0250 	 	STX 	*PIECE 	
03BD- 	B5 	50 	 	0260 	 	LDA 	*BOARD,X; DEVP LOCATION
03BF- 	C8 	 	 	0270 	 	INY 	;	INDEX OF FROM
03C0- 	48 	 	 	0280 	 	PHA 	;	(SAVE DEVP LOCATION)
03C1- 	98 	 	 	0290 	 	TYA 	;	TRANSFER INDEX OF
03C2- 	AA 	 	 	0300 	 	TAX 	;	FROM INTO X
03C3- 	68 	 	 	0310 	 	PLA 	;	DEVP LOCATION IN ACCUM
03C4- 	D5 	DC 	 	0320 	 	CMP 	*FROM,X ; DEVP AT ORIGIN?
03C6- 	D0 	EB 	 	0330 	 	BNE 	NEXT	; - NO, GET NEW DEVP
03C8- 	E8 	 	 	0340 	 	INX 	;	INDEX OF TO
03C9- 	B5 	DC 	 	0350 	 	LDA 	*TO,X	; CHECK LEGALLITY OF DEVP
03CB- 	20 	D1 	02 	0360 	 	JSR 	CMOVE	; FROM .FROM TO .TO
03CE- 	30 	13 	 	0370 	 	BMI 	NODEVP 	; NEQ = ILLEGAL MOVE
03D0- 	A6 	B0 	 	0380 	 	LDX 	*PIECE 	; - LEGAL MOVE
03D2- 	E0 	08 	 	0390 	 	CPX 	#$08	; IS PIECE A PAWN
03D4- 	30 	02 	 	0400 	 	BMI 	LEGAL	; NEG = NOT PAWN
03D6- 	70 	0B 	 	0410 	 	BVS 	NODEVP 	; SET = ILLEGAL PAWN CAPTURE
03D8- 	A6 	C3 	 	0420 	LEGAL 	LDX 	*FACTOR	; LEGAL OPENING MOVE!!
03DA- 	86 	F0 	 	0430 	 	STX 	*BIAS	; SET BIAS TO FACTOR
03DC- 	A2 	04 	 	0440 	 	LDX 	#$04	; EVALUATE OPENING MOVE
03DE- 	86 	B5 	 	0450 	 	STX 	*STATE 	; AND PUT IT IN BESTV
03E0- 	20 	00 	01 	0460 	 	JSR 	JANUS	; IF ITS THE BEST MOVE
03E3- 	A6 	FA 	 	0470 	NODEVP	LDX	*BESTV 	; SO FAR
03E5- 	E0 	0F 	 	0480 	 	CPX 	#$0F	; RESIGN OR STALEMATE IF
03E7- 	4C 	C2 	17 	0490 	 	JMP 	CONT	; BESTV TOO LOW
 	 	 	 	0500 	; 	 	 	
 	 	 	 	0510 	 	.BA 	$17C2 	 	
17C2- 	90 	12 	 	0520 	CONT 	BCC 	MATE	; (ORIGINAL MICROCHESS
17C4- 	A6 	FB 	 	0530 	MV2 	LDX 	*BESTP 	; CODING)
17C6- 	B5 	50 	 	0540 	 	LDA 	*BOARD,X	; MOVE AND DISPLAY THE
17C8- 	85 	FA 	 	0550 	 	STA 	*BESTV 	; BEST MOVE
17CA- 	86 	B0 	 	0560 	 	STX 	*PIECE 	
17CC- 	A5 	F9 	 	0570 	 	LDA 	*BESTM 	
17CE- 	85 	B1 	 	0580 	 	STA 	*SQUARE 	
17D0- 	20 	4B 	03 	0590 	 	JSR 	MOVE 	
17D3- 	4C 	00 	00 	0600 	 	JMP 	CHESS	; END COMPUTER'S TURN
17D6- 	A9 	FF 	 	0610 	MATE 	LDA 	#$FF	; RESIGN OR
17D8- 	60 	 	 	0620 	 	RTS 	 	
 	 	 	 	0630 	; 	 	 	
 	 	 	 	0640 	 	.BA 	$1780 	
1780- 	A9 	80 	 	0650	STRATEGY LDA	#$80 	; EVALUATION = 80 + OR - SCORE
1782- 	18 	 	 	0660 	 	CLC 	 	
1783- 	65 	EB 	 	0670 	 	ADC 	*WMOB	; COMPUTER'S MOBILITY
1785- 	4A 	 	 	0680 	 	LSR 	A 	
1786- 	18 	 	 	0690 	 	CLC 	 	
1787- 	69 	40 	 	0700 	 	ADC 	#$40	; RESET EVAL TO 80 +OR- SCORE
1789- 	65 	ED 	 	0710 	 	ADC 	*WCC	; COMPUTER'S ATTACK STRENGTH
178B- 	38 	 	 	0720 	 	SEC 	 	
178C- 	E5 	E5 	 	0730 	 	SBC 	*BCC	; OPPONENT'S ATTACK STRENGTH
178E- 	4A 	 	 	0740 	 	LSR 	A 	 	
178F- 	4A 	 	 	0750 	 	LSR 	A	; MOBILITY X 1/16
1790- 	4A 	 	 	0760 	 	LSR 	A	; ATTACK STRENGTH X 1/8
1791- 	18 	 	 	0770 	 	CLC 	 	
1792- 	69 	70 	 	0780 	 	ADC 	#$70	; RESET EVAL TO 80 +OR- SCORE
1794- 	65 	F0 	 	0790 	 	ADC 	*BIAS	; ZERO UNLESS DEVP MOVE
1796- 	A4 	DC 	 	0800 	 	LDY 	*OMOVE 	; NEGATIVE IF STILL DEVP
1798- 	30 	17 	 	0810 	 	BMI 	CAPTEST ; MID-GAME IF POSITIVE
179A- 	38 	 	 	0820 	 	SEC 	;	DEDUCT MOBILITY OF THE
179B- 	E5 	EF 	 	0830 	 	SBC 	*BKMOB	; OPPONENT'S KING
179D- 	A6 	B0 	 	0840 	 	LDX 	*PIECE 	; BONUS FOR MOVE INTO
179F- 	CA 	 	 	0850 	 	DEX 	;	OPPONENT'S KING ZONE
17A0- 	E0 	07 	 	0860 	 	CPX 	#$07	; NOT FOR COMPUTER'S KING
17A2- 	B0 	0D 	 	0870 	 	BCS 	CAPTEST ; OR PAWNS
17A4- 	48 	 	 	0880 	 	PHA 	;	(SAVE EVALUATION)
17A5- 	A5 	60 	 	0890 	 	LDA 	*BK	; LOCATION OF OPPONENT'S KING
17A7- 	38 	 	 	0900 	 	SEC 	 	
17A8- 	E9 	38 	 	0910 	 	SBC 	#$38	; CALCULATE KING ZONE
17AA- 	C5 	B1 	 	0920 	 	CMP 	*SQUARE ; MOVE INTO ZONE?
17AC- 	68 	 	 	0930 	 	PLA 	;	(RESTORE EVALUATION)
17AD- 	B0 	02 	 	0940 	 	BCS 	CAPTEST ; CARRY CLEAR IS IN ZONE
17AF- 	69 	02 	 	0950 	 	ADC 	#$02	; ADD BONUS, NEAR KING
17B1- 	A6 	DD		0960 CAPTEST	LDX	*WCAP0	; IF COMPUTER'S CAPTURE
17B3- 	E4 	E4 	 	0970 	 	CPX 	*BMAXC 	; IS NOT GREATER THAN
17B5- 	90 	03 	 	0980 	 	BCC 	QUIT	; OR EQUAL OPP, QUIT
17B7- 	18 	 	 	0990	MOVEOK	CLC 	;	PASSES CAPTURE TEST
17B8- 	69 	20 	 	1000 	 	ADC 	#$20	; POINTS FOR GOOD MOVE
17BA- 	65 	DD 	 	1010 	QUIT 	ADC 	*WCAP0 	; POINTS FOR CAPTURE
17BC- 	38 	 	 	1020 	 	SEC 	;	POINTS FOR OPPONENT'S
17BD- 	E5 	E4 	 	1030 	 	SBC 	*BMAXC 	; MAX CAPTURE IN REPLY
17BF- 	4C 	77 	03 	1040 	 	JMP 	CKMATE 	; TEST FOR CHECKMATE
 	 	 	 	1050 	; 	 	 	
 	 	 	 	1060 	 	.BA 	$17D9 	
17D9- 	D0 	06 	 	1070	BKMOVE	BNE 	OUTBK	; RTS IF STATE NOT ZERO
17DB- 	C9 	00 	 	1080 	 	CMP 	#$00	; RTS IF NOT OPP KING'S
17DD- 	D0 	02 	 	1090 	 	BNE 	OUTBK	; MOVE
17DF- 	E6 	EF 	 	1100 	 	INC 	*BKMOB 	; COUNT LEGAL OPP KING
17E1- 	60 	 	 	1110 	OUTBK 	RTS 	;	MOVES
 	 	 	 	1120 	; 	 	 	
 	 	 	 	1130 	 	.BA 	$0112 	
0112- 	E0 	00 	 	1140 	 	CPX 	#$00	; COUNT LEGAL REPLY MOVES
0114- 	20 	D9 	17 	1150 	 	JSR 	BKMOVE 	; FOR OPPONENT'S KING
0117- 	EA 	 	 	1160 	 	NOP 	 	
 	 	 	 	1170 	; 	 	 	
 	 	 	 	1180 	 	.BA 	$200 	
0200- 	A2 	11 	 	1190 	 	LDX 	#$11	; CLEAR COUNTERS, NOT BIAS
 	 	 	 	1200 	 	.EN 	 	

• Back to previous page
• View this issue's table of contents