Saturday, 1 May 2021

4K Tandy Micro Checkers: Another Bug Found


Well I think I uncovered another bug in Micro Checkers for the TRS-80 MC-10.  In my initial post about this program I noted that there was some spottiness regarding the implementation of forced jumping by the A.I.  What prompted this comment was my recollection of a moment when the computer moved a piece from its back row, despite the fact that lower down the board there was an opportunity for it to jump one of my pieces. This struck me as odd for two reasons. First, as noted, it is normal to expect mandatory jumping. Second, it is a normal strategy in checkers to protect your back row, in order to delay or prevent the opponent from kinging their pieces. So I resolved to examine the movement algorithm of the A.I to see if there was some obvious mistake. To help me do this I decided to do a line by line comparison  of the similar code from the GWCheckers program I found online on a French blog site.  I found some differences.  The key one I think is this line in Micro Checkers:

230 IFY=7THENN=N+2

(In my updated and renumbered version, as a memory saving measure, this line became: 23 IFY=7THENN=N+2). The corresponding line from the GWCheckers version was:

960 IF Y = 7 THEN Q = Q-2

Since in Micro Checkers the top line is line 7 (computer's side), I had the suspicion that the function of this line was to "demote" moves from the computer's back row in terms of priority.  The N variable in Micro Checkers and the Q variable in GWCheckers seem to be a count for prioritizing moves. The higher the value, the more attractive the move. In other words, the move option that gets the highest N/Q value is the one that gets selected. I think it is possible that the aberrant behaviour I witnessed might have been a result of this + sign instead of a - sign in line 230.  Why else would a back row move be prioritized over a possible jump?

However, I also found an additional check as part of the Micro Checkers code:


Whereas, the corresponding line from the GWCheckers version was:

230 FOR X = 0 TO 7: FOR Y = 0 TO 7: IF S (X, Y)> - 1 THEN 350

Also, you will note the Micro Checkers searches from the top row (7) down (0-- the player's side), whereas GWCheckers searches from the bottom row up.  I don't know what the significance of that change is.  I did try simply removing the red highlighted check for S(X,Y)=3, but the resulting game play was terrible, with the A.I moving into positions in which it could be jumped.  So I obviously didn't make that change permanent.  However, I wondered whether I should adopt the bottom up direction of  search.  I suspect that the algorithm simply selects any move with a higher N/Q value as it does its search.  So if it searches from bottom of the board (the human player's side) up, as in the GWCheckers, then a certain priority is given to offensive moves, since they could then be prioritized over any equal weighted top of board (computer side) moves.  I want the program to be more aggressive, especially early in the game, so I made the change to the GWCheckers search order.

Here is the line in Micro Checkers where the move is selected:

290 NEXTC:IFN>R(0)THENR(0)=N:R(1)=X:R(2)=Y:R(3)=J:R(4)=K


1080 NEXT C: IF Q> R (0) THEN R (0) = Q: R ( 1) = X: R (2) = Y: R (3) = U: R (4) = V

Because the check is for if a move (N/Q) is greater than any prior highest move, if a move further down the board (towards the human player) has the highest number, no equally high numbered move further back will be able to supplant it. Whereas in the original Micro Checkers, any back row move that gets established as highest (such as the aberrant back row move I noted above) can never be supplanted by any equally high move closer to the human side of the board (i.e more "offensive" plays). I'm not 100% sure the GW Strategy will result in better play and I am starting to lose my taste for playing these games of Checkers against a fairly simple A.I.  But I will continue testing and let you know if I think it needs to be changed back.

Another change that I made is that I noticed that the initial move was always the same from a fresh boot of the computer. The game had no way of randomly seeding the random number process.  However with a little change this could be easily accomplished via the initial INKEY$ input routine for asking whether one wanted to move first.  By relocating the RND assignment to variable T, within that key press routine, the operator's initial key press would randomly seed the random number sequence. So I changed:

60 A$=INKEY$:IFA$=""THEN60
70 IFA$="Y"THEN450
80 R(1)=(RND(4)*2)-1:R(2)=5:T=RND(2):T=T-1:IFT=0THENT=T-1


7 R(1)=RND(4)*2-1:R(2)=5:T=T-1:T=T+(T=0):R(3)=R(1)+T:R(4)=4:ON-(R(3)>7)GOTO7:GOTO32

I also found some more memory savings by consolidating a lot of additions and subtractions to N by way of simply adding and subtracting appropriately multiplied results from logical comparisons, rather than having separate lines using IF statements.  This allowed me to fix up the prompt clearing function.  Now when you change your mind about a move, and hit <ENTER> on an inappropriate square, the cancellation and return to the FROM prompt is signaled by the CLEARING of the TO prompt.

The Game MCCHKRS can  be played >>>here<<<. Select the "Play Game" button, then select the "Play Our Other 8-Bit Basic Game Ports" link, and then choose the filename from the Cassette list and type RUN.

Below is an image of me being trounced by the latest version of the game.  If you make a critical error in the early game, the computer can get and stay ahead of you.

Me getting trounced by the latest A.I.

Addendum: I put 100 FORX=7TO0STEP-1:FORY=7TO0STEP-1 back in place. It seemed that there was some suicidal behaviour of kinged pieces that might resulted from the change to a search order as in:
230 FOR X = 0 TO 7: FOR Y = 0 TO 7

I find this game interesting because clearly Tandy used an existing version of the program to create its 4K Checkers for the MC-10.  Either that, or someone took their version and debugged it and added graphics to create the PC version. It would be interesting to track down and verify the original author of the program. It doesn't appear that Tandy acknowledged the author of the program their documentation in any way:
So despite all the "copyright stuff" in their manual, it is not entirely clear to me that they respected copyright in the creation of the program.  They might have simply paid someone to condense some original BASIC program, without proper consent.

No comments:

Post a Comment