4K Basic Checkers Game Program Fixed After 30 Years

I was bored, so I added cursor control input (AWSD) to  "Micro Checkers" from Tandy.  This was one of only a half dozen, or so,  programs released by Tandy before they discontinued the TRS-80 MC-10 after only a year of production.  Like all but the machine language hires pinball game provided by Tandy, it works in the limited 4K memory space of the unexpanded computer.  My updated version of the program still runs in 4K.  I had to use the RENUM command from MCX Basic, and some other code condensing tricks to get cursor input added while still keeping the revised program small enough to fit in 4K.

The original game did not play a very good game of checkers.  You can see in this video that there are opportunities for multiple jumps that are missed.  This got me to wondering whether there was a bug in the program, because it seemed a pretty serious deficiency for the A.I not to exploit opportunities for multiple jumps:

It's a funny little game. Some compromises obviously had to be made to get it to fit in 4K. For example, it doesn't prevent you jumping your own pieces or making 2 space "jump like" moves, even if there is no intervening opposing piece (perhaps someday when I'm bored again I'll try to add this).  And you have to determine/declare your own game loss or end and hit break to re-run the program. Occasionally it completely misses an available jump and simply moves a piece, so enforced jumping is a bit spotty. As I noted, there also seemed to be a buggy routine that prevented the A.I. from doing multiple jumps. But I can't be sure if I somehow simply ended with a compromised version. I got my copy from the Internet of course, since my own original tape has gone to the great bit-rot bucket in the sky. Specifically from chazbeenhad's longstanding MC-10 site:

https://chazbeenhad.tripod.com/

But it also seems the problem is in the version on the Color Computer Archive:

https://colorcomputerarchive.com/repo/MC-10/Software/Games/Micro%20Checkers.c10

Chazbeenhad also helpfully provided a scan of the instruction booklet:

Perhaps the original program worked. But if that is not the case, then shame on Tandy for distributing a buggy program.

As I investigated the code of the program I was able to identify the routine that was supposed to process the possibilities for further jumps after an initial jump made by the computer:

360 X=R(3):Y=R(4):IFS(X,Y)=-1THENB=-2:FORA=-2TOASTEP4:GOSUB400
370 IFS(X,Y)=-2THENFORA=-2TO2STEP4:FORB=-2TO2STEP4:GOSUB400:NEXTB
380 NEXTA:IFR(0)<>-99THEN320
390 GOTO450
400 J=X+A:K=Y+B:IFJ<0ORJ>7ORK<0ORK>7THEN420
410 IFS(J,K)=0ANDS(X+A/2,Y+B/2)>0THENGOSUB210
420 RETURN

I was able to determine that the FOR/NEXT loops in 360 and 370 were meant to be searches for an uncrowned jumping piece designated by S(X,Y)=-1 in line 360, or a crowned piece, designated by S(X,Y)=-2 in line 370.  By inserting the STOP command and running the program I was able to determine that the 360 routine was not successfully searching and finding and acting on possible jumps.  Each search called the subroutine at 400 and that routine made use of a routine at 210 to actuate the jumps.  It used a similar check in line 400 as the main routine up in the 200s, so the problem had to be in the search in line 360.  Initially I was able cut out the special 400 routine and just use the main jump search routine up in 200, to get multiple jumps to occur.  You can see me demonstrating that here:

The only problem was that I had to add a bunch of fudges to the regular move and jump routine (at the 200s) to prevent certain kinds of behaviour. The general jump routine, would of course, process whether ordinary moves could be made in nearby squares, whereas I just wanted it to process further jump possibilities.  I was able to add kludges to that prevented unwanted movements when that routine was called from 360 and 370, but this was not ideal as it added new variables, and I was already redlined for memory space.  But while I was fiddling with the program I had also been investigating other BASIC checkers programs on the Net.  I came across a piece of code for a GWBasic version of checkers that looked surprisingly similar to the code for the MC-10.

You can see that code listed here from a French language blog site:

https://gw--basic.blogspot.com/2014/04/this-is-game-of-checkers-jeu-de-dames.html

It can also be found in this directory on Github:

https://github.com/robhagemans/hoard-of-gwbasic/blob/master/KindlyRat/CHECKERS.BAS

Although obviously a more complex program with graphics for the pieces and board, and different variable names, you can see the basic structure of both programs are similar.  I was able to locate the same multiple jump search routine:

1340 X=R(3):Y=R(4):IF S(X,Y)=-1 THEN B=-2:FOR A=-2 TO 2 STEP 4:GOSUB 1370:NEXT A
1350 IF S(X,Y)=-2 THEN FOR A=-2 TO 2 STEP 4:FOR B=-2 TO 2 STEP 4:GOSUB 1360:NEXT B,A
1360 IF R(0)<>-99 THEN LOCATE ,30:PRINT" TO "CHR$(65+R(3))","CHR$(49+R(4)):R(0)=-99:GOTO 1240
1365 GOSUB 3000:GOTO 1590
1370 U=X+A:V=Y+B:IF U<0 OR U>7 OR V<0 OR V>7 THEN 1400
1380 IF S(U,V)=0 AND S(X+A/2,Y+B/2)>0 THEN GOSUB 910
1400 RETURN

The most serious difference between the two code snippets is highlighted in red. The MC-10 version has FORA=-2TOASTEP4 instead of FOR A=-2 TO 2 STEP 4.

It was using the variable A in the FOR/NEXT loop and also using that variable, instead of 2 to define the scope of the search.  It was also missing the NEXT A at the end of the line. Similarly in line 370 a NEXT for A was also missing.  Instead, the programmer put a NEXT at line 380.  This was probably an attempt to shave off some memory use by using a single NEXT for either of the IF routines used to select between un-kinged and kinged pieces.  The problem is I think that the A was used instead of a 2 to define the search loop for un-kinged pieces.  By changing that and adding the NEXTs at the end of the lines (and removing it from 380), I was able to get the program to make multiple jumps, probably in the way the original programmer intended.

I also added a check to the program to prevent it from allowing you to jump in a backward direction with an un-kinged piece after your first jump.  So now with the added cursor key feature to select moves, hopefully the program is much more easy to play and perhaps a little more accessible for those interested in exploring early A.I. Basic game programming efforts. It's a petty amazing feat to fit a BASIC checkers game into 4K.  Such early A.I. coding efforts deserve to be remembered.

Final note: Instead of entering -1,-1 to signal that you have ended a multiple jump sequence of you own, simply move the cursor onto a white square and hit <ENTER>.  Cursor movement is by WASD.  Use <ENTER> to select piece to move, then select place to move and hit <ENTER> again.  If you make a mistake, just hit <ENTER> on a non-movement space and then restart the piece selection process.

Addendum

I think I might have found the original source of the code for both the GWBASIC and the Tandy Micro Checkers versions of Checkers.  They both might be variations of a demonstration program from John Krutch's Artificial Intelligence for Small Computers, 1981.  A link to this book can be found on the Internet Archive here:

https://archive.org/details/krutch-experiments_in_artificial_intelligence_for_small_computers-1981/mode/2up 

I haven't done a complete line by line comparison of the 3 programs, but from Krutch's description of the algorithm, it seems to go about choosing moves in much the same way as I have observed from the play of Micro Checkers. The result is a very defensive approach. In short, it looks for jumps, then it looks for endangered pieces and then it looks for any move.  Krutch mentions that his program doesn't allow multiple jumps, leaving that privilege to the human player.  So I think that Micro Checkers might be a slightly improved version of the program that continues to process for jumps until there are none, after the initial jump. But all this is just speculation at this point.  I'll have to follow up on this at some point in the future to confirm.  Or someone else interested in the history of the development of such programs will have to.