Previous | Contents | Next

Draughts Part Three

DRAUGHTS

The story so far... Once upon a time a human being input a move to a ZX computer. The computer checked this move to make sure that no cheating was going on, and cast a wicked spell on the poor human if it was, which meant that the whole move had to be typed in all over again. The move was made. The computer started to search through the board for pieces that it could move. Having found a piece, but not knowing whether or not it could move, it then miraculously found itself at an address called EVALUATE. Where do we go from here?

Let's start off by saying that a neutral move - that is a move which achieves nothing, but also loses nothing - has a "priority" of 80 (hex).

The first point worth noting is that if a piece is in imminent danger of being captured then it stands to reason that we ought to move it out of the way - unless something more important crops up. Secondly, if a piece if preventing another piece from being captured, then we should be less likely to move it. Both of these conditions apply regardless of which direction we consider moving the piece. It stands to reason then that we should work out this part of the priority first, before we start analysing each of the different directions. We must therefore work out a numerical value that corresponds to the square that we are looking at. This value will then be added to 80, after which each direction in turn will be analysed.

EVALUATE will therefore start off

4E43: CDF14D    EVALUATE  CALL SQUAREVAL
      C680                ADD A,80
      322140              LD (INITIAL),A

The last instruction stores the value we've found for use later on in the game. On the OLD ROM the address of INITIAL should be changed to 4019. Now let's take a closer look at the subroutine SQUAREVAL. It will assign a value as follows - starting with zero, if a piece is in danger it will add five, or seven for a king. If it is protecting a piece it will subtract five, or seven for a king. Further, the subroutine, as with all subroutines from now on, must not be allowed to alter the values of any register except A. One way of doing this is to begin the subroutine

4DF1: C5        SQUAREVAL PUSH BC
      D5                  PUSH DE
      E5                  PUSH HL

Here is the complete subroutine. Follow it through carefully. It should be sufficiently annotated for you to make sense of exactly what's going on.

[Write to 4DF1h.]

C5        SQUAREVAL PUSH BC        Store the current value of the regi-
D5                  PUSH DE        sters on the stack, to be retrieved
E5                  PUSH HL        at the end of the subroutine.
0600                LD B,00        B is being used as a flag here. The
                                   first time round the loop it will be
      zero, the second time round it will be one. Watch the checks on B
      carefully. The loop will check for protection the first time
      round, but for danger the second time round.

11974C    STARTOFF  LD DE,TABLE    DE is a pointer, which points to the
                                   table of directions of movement.
1A        NOWT      LD A,(DE)
4F                  LD C,A         C now contains such a direction.
D62E                SUB 2E
282A                JR Z,EXIT      If this "direction" is 2E we have
                                   passed the end of the table. We
                                   should exit with value zero.
1C                  INC E          Move pointer to next direction in
                                   table.
E1                  POP HL
E5                  PUSH HL        L contains the low part of the
2640                LD H,40        current square. We retrieve it
                                   without altering the stack, and
                                   reassign H to the high part of
                                   this address.
7D                  LD A,L         
81                  ADD A,C        Find square to be looked at in this
CB40                BIT 0,B        direction. Watch how B affects what
2001                JR NZ,LA       happens.
81                  ADD A,C
6F        LA        LD L,A
3E7F                LD A,7F        Watch how A is constructed here. If
B1                  OR C           a human's piece is present A will
A6                  AND (HL)       end up as 27 UNLESS that piece is a
FE27                CP 27          non-king which can't move towards
20E5                JR NZ,NOWT     us. Then it will produce A7. No
                                   other piece can generate the result
                                   27.
7D                  LD A,L
91                  SUB C          Look at next square towards us. If B
6F                  LD L,A         is zero we are looking at a possible
                                   piece being protected. If B is one
                                   we are looking at ourselves.
7E                  LD A,(HL)
37                  SCF            This is another way of checking for
17                  RLA            a computer's piece regardless of
CB40                BIT 0,B        whether or not it is a king, but
2006                JR NZ,LB       watch the carry flag.
FE79                CP 79
20D7                JR NZ,NOWT
7E                  LD A,(HL)
17                  RLA
3F        LB        CCF            Now notice the clever way we decide
3E81                LD A,81        on 5 for a piece, or 7 for a king.
17                  RLA
17                  RLA            A now contains 5 or 7 as needed.
CB40      EXIT      BIT 0,B        The loop is now ended.
2006                JR NZ,LC
04                  INC B          This is what happens if B was zero.
67                  LD H,A         The value 5, 7 or 0 is stored on the
E3                  EX (SP),HL     stack behind HL.
E5                  PUSH HL
18C3                JR STARTOFF
57        LC        LD D,A         This is what happens if B was one.
                                   D now contains the current value
                                   0, 5, or 7.
7D                  LD A,L         The square behind us is located.
91                  SUB C
6F                  LD L,A
7E                  LD A,(HL)      The contents of this square are
                                   examined.
FE80                CP 80          If it is not a blank square we are
28BD                JR NZ,NOWT     not in danger.
28BD                JR Z,NOWT      not in danger.
7A                  LA A,D         The current value is retrieved.
E1                  POP HL
D1                  POP DE         D now contains the previous value
                                   0, 5, or 7.
92                  SUB D          The final square-value is calculated.
D1                  POP DE         The remaining registers are removed
C1                  POP BC         from the stack.
C9                  RET            End of subroutine.

This works because if you take a look at the diagram below you'll see very clearly the conditions under which we define a piece as being "in danger" or protecting. Compare carefully what the subroutine does both times round, with each of the diagrams.

                          +------------+
                          |            |
                          |  human's   |
                          |   piece    |
     PROTECTING           |            |
                          |            |
             +------------+------------+            +------------+
             |            |                         |            |
             | computer's |                         |  human's   |
             |   piece    |                         |   piece    |
             |            |                         |            |
             |            |                         |            |
+------------+------------+            +------------+------------+
|   square   |                         |   square   |
|   being    |                         |   being    |
|   valued   |                         |   valued   |
|     --     |                         |     --     |
|     us     |                         |     us     |
+------------+            +------------+------------+
                          |            |
                          |            |
                          |   blank    |        IN DANGER
                          |   square   |
                          |            |
                          +------------+

Now for the rest of that decision making routine EVALUATE. It contains a deliberate mistake - see if you can find it (the program will still run perfectly smoothly even with the mistake still in)! If you can't sus it out on your own I'll tell you later on.

This routine is designed to compute a numerical value - a "priority" - for any individual move. Having done so it will compare this priority with those moves stored on the stack. If the new priority is less, it will forget this move and go on to explore a new one. If the new move is equal in priority it will be stored on the stack. If the new priority is more than those on the stack then the list will be abolished, and a new list started.

The registers in the routine have the following jobs:

  • A - a general purpose working register.
  • B - counts the number of items in the list. You may remember the CHOOSE routine earlier on relied on B containing this number of items.
  • C - a general purpose working register.
  • DE - a pointer which looks at the table of allowable directions of movement.
  • H - the direction being moved.
  • L - the low part of the address of the current square.

The routine begins at address 4E43:

[Write to 4E43h.]

CDF14D    EVALUATE  CALL SQUAREVAL     Check for danger and/or
C680                ADD 80             protection at current square.
322140              LD (INITIAL),A

11974C              LD DE,TABLE        Set pointer to start of table.
4D                  LD C,L             Remember low part of the address
                                       of current square for later use.
69        NXTMRND   LD L,C             Retrieve the value.
2640                LD H,40            Assign high part of this address.
1A        NXTDIR    LD A,(DE)          Select direction of movement.
1C                  INC E              Move table pointer.
CB7E                BIT 7,(HL)         Check whether or not we are
                                       looking at a king.
2804                JR Z,ANYDIR        If so we can move in any direct.
CB7F                BIT 7,A            Check whether current direction
                                       is forward or backward.
20F6                JR NZ,NXTDIR       If backward pick a new direction.
FE2E      ANYDIR    CP 2E              If this direction is 2E then we
CAA04D              JP Z,KPCHKNG       have covered all four directions.
C5                  PUSH BC            Temporarily stack B - the number
                                       of items in the list of moves.
47                  LD B,A             Store current direction temp.
B1                  ADD A,C            Find the address of the dest-
6F                  LD L,A             ination square in this direction.
7E                  LD A,(HL)          Find the contents of this square.
60                  LD H,B             The direction being moved is now
                                       stored in H, as required.
C1                  POP BC             The number of choices of moves on
                                       the stack - B - is recovered.
FE80                CP 80              Is this destination square empty?
20E3      TEST      JR NZ,NXTMRND      If not pick a new direction to
                                       examine.
ED537940            LD (SCANSQR),DE    Temporarily store the value of DE

Note that while we need to temporarily store DE somewhere, we must not stack it, since we are shortly about to use the stack to examine our list. OLD ROM owners should interpret the address (SCANSQR) as 4020.

[Write to 4E70h.]

CDF14D              CALL SQUAREVAL    Check for danger and/or protection
                                      at destination square.

This is necessary because a move into danger is bad, and moving to protect another piece is good. Notice that by design the subroutine SQUAREVAL will not change the value of any register except A. One unfortunate flaw in the subroutine means that moving a king into danger will only generate the value five, rather than seven. Can you see why? Follow the subroutine through if you can't. Finally you should note that SQUAREVAL only requires L to be assigned initially, not HL. This is deliberate.

[Write to 4E73h.]

57        NEWPRI    LD D,A            Negate this quantity, since we do
3A2140              LD A,(INITIAL)    not want to move into danger, and
92                  SUB D             we do want to move to protect
57                  LD D,A            another piece. Add in the original
                                      square value and store the result
                                      in D.
1E01                LD E,01           The number one is the number of
69                  LD L,C            steps involved in this move.

We now have D containing the computed priority of this move, and E containing the number of steps in this move.

[Write to 4E7Ch.]

E3                  EX (SP),HL        We now have H containing the
                                      priority of the list, and L con-
                                      taining the no. of steps for each
                                      move on the list.
A7                  AND A
ED52                SBC HL,DE         Compare these two sets of
280D                JR Z,EQUAL        quantities.
19                  ADD HL,DE         Restore HL and the stack-top.
E3                  EX (SP),HL
3013                JR NC,FORGETIT    If computed priority is less, then
                                      do nothing.
ED7B7B40            LD SP,(LBASE)     Otherwise begin new list.
0600                LD B,00           Zero items on list so far.
D5                  PUSH DE           Stack the priority and no. of
1802                JR NEWITEM        steps.
19        EQUAL     ADD HL,DE         Restore HL and the stack-top.
E3                  EX (SP),HL
04        NEWITEM   INC B             Increase no. of items in list.
E5                  PUSH HL

Now H contains the direction moved, and L the low part of the initial square. The top of the stack therefore now looks like this:

+-------------------+-------+--------->
|initial  direction |no. of |priority >
|square   one       |steps  |         >
+-------------------+-------+--------->
|
sp

This is not quite what we want - we want it to look like this:

+-------+---------+------------------->
|no. of |priority |initial  direction >
|steps  |         |square   one       >
+-------+---------+------------------->
|
sp

So we now want to swap the first and second bytes at the top of the stack with the third and fourth bytes. We want to do this without altering the position of the stack pointer, and without altering any of the registers. The following will achieve this - follow it through carefully -

[Write to 4E93h.]

33                  INC SP        Move the stack pointer to the initial
33                  INC SP        square (final position).
E3                  EX (SP),HL    Store initial square and direction 1.
3B                  DEC SP        Move the stack pointer back where it
3B                  DEC SP        came from.
E3                  EX (SP),HL    Store the number of steps and priority

Note that even HL remains unchanged by this method. EVALUATE needs only two more instructions to complete it. These are

[Write to 4E99h.]

ED5B7940  FORGETIT  LD DE,(SCANSQR)    Restore the previous values of D
18B0                JR NXTMRND         and E, and do the same for next
                                       direction.

As it stands the program will not test whether or not a computer's piece has reached the back row (and thus become a king). This is not a programming error, this is quite deliberate. The reason is that this is something I'd like you to do for yourself. Study the way in which the check on a human's piece is made - the low part of the destination address is compared with the low part of the address of the boundary between the back row and the second row - and make a similar test. You should find this a very simple addition to the program.

The EVALUATE routine is now complete. The whole program is now a closed structure - there are no holes in it now, no RET statements temporarily taking the place of subroutines that aren't there. If you now RUN the program (by typing RUN 4) it will actually make moves! Of course it won't do much else, but you should now be able to see how far we've progressed.

Oh - there is of course that deliberate mistake to think about. If you didn't notice it in the listing you probably noticed it by playing it. The problem is that the computer won't jump. As you can imagine this leads to a very poor game on its part.

The mistake is in the line labelled TEST. It currently says JR NZ,NXTMRND, which means that if a square in any particular direction is simply not empty then it will try a different direction. The line should read JR NZ,WHAT, where WHAT is a routine (which we haven't yet written) which is designed to decide whether the destination square contains a human's piece, whether a jump is possible - even whether or not a multiple jump is possible - and to evaluate the priority of whatever it finds.

[Thunor: To fix the deliberate mistake, change the byte at address 4E6Bh to 33h.]

Here is one such subroutine. It is not the only possible one, but a suggestion of one means of doing it. This particular version will cope only with single jumps, not with multiple jumps: The routine begins at 4E9B [4E9F]:

[Write to 4E9Fh.]

ED537940  WHAT      LD (SCANSQR),DE    Temporarily store value of DE.
57                  LD D,A             Store the contents of the square
                                       we are now looking at in D.
E67F                AND 7F             Is it a human's piece?
FE27                CP 27
2806                JR Z,FOUND
ED5B7940            LD DE,(SCANSQR)    If not, retrieve the original
1899                JR NXTMRND         value of DE and resume search.
189F                JR NXTMRND         value of DE and resume search.
3E81      FOUND     LD A,81            Assign A with either five or
CB12                RL D               seven depending on whether or not
3F                  CCF                we have found a king.
17                  RLA
17                  RLA
57                  LD D,A             Store this in D.
5C                  LD E,H             Store the current direction in E.
7D                  LD A,L             Find the next square in this
84                  ADD A,H            direction.
6F                  LD L,A
2640                LD H,WKBOARD-low
7E                  LD A,(HL)          Find the contents of this square.
63                  LD H,E             Restore H to its previous value.
FE80                CP 80              Is this square empty?
2807                JR Z,JUMP
ED537940            LD DE,(SCANSQR)    If not, restore the original
C34F4E              JP NXTMRND         value of DE and resume search.
CDF14D    JUMP      CALL SQUAREVAL     Check for danger and/or
                                       protection at destination square.
92                  SUB D              Take contents of square into
                                       account.
18A2                JR NEWPRI          Check this new priority to see if
                                       it's worth stacking.

[Download available for 16K ZX81 -> chapter15-draughts3.p. That's it for the author supplied code. The author states that to finish it requires that you write the remaining parts yourself! At the moment I don't intend to go any further with the program as I was expecting it to be a complete version. The version here that I am offering for download includes all of the author offered code and the modification to the deliberate mistake. Set RAMTOP to 4A00 (18944) with POKE 16389,74/NEW. Type RUN 4 to play the game. Unfortunately the game crashes when the computer makes a jump. When transcribing, I have a process of checking the code when writing it and then checking again when I've written a sizeable chunk. I've also gone through and checked the hex-code of the program against the listing in appendix six, and so I believe there is a logic error somewhere that I currently don't have the time to track down.]

[Thunor: For the NEW ROM only, there's a detailed program listing with instructions in appendix six.]

As you can see, the principle for finding a single jump is relatively straightforward. With this routine in place the computer will now play an adequate game of draughts, but although the human player is allowed to make multiple jumps, the computer will not. This addition I leave you to write yourself. I will, however give you a couple of hints.

First of all, the registers all have specific uses. All that is, except for A and C. These are as follows:

  • B - The number of choices of move available.
  • D - The priority of the current move.
  • E - The number of steps in the current move.
  • H - The direction being moved this step.
  • L - The low part of the address of the current square (within WKBOARD).

I suggest giving C a use too - it should be used to store which step of a multiple-step move we are currently examining. In other words, on the second step C will be two, on the third step C will be three, and so on. It is fairly easy to preserve the values of all of the registers by making proper use of the stack.

Nesting the subroutines and loops properly, so that the same routine is used to check for a third move as is used to check for a second move, is not as difficult as you might think - it merely requires a bit of positive thinking. It also has the advantage that, in theory, the computer can actually make twelve-fold jumps with no extra programming. The looping is not the biggest problem.

There are two problems which will face you. These are:

  • Having stored C-1 steps of the current move on the stack, how do we store step C (i.e. how do we insert it into the middle of the stack)?
  • Having established that the current move now stands at C steps, and can be increased no more, one of the following must happen: If C is less than E then the current move is abolished; if C is equal to E, the stack is left unchanged; if C is greater than E then the whole list of moves on the stack except the current move is abolished.

Let's take a look at the first problem first. Assuming C-1 steps are stacked, the situation we now have is this:

+---+---------+------------------> - <------+------------------> - <------+
| E |priority |initial dir. dir. >   < dir. |initial dir. dir. >   < dir. |
|   |         |square   1    2   >   < C-1  |square   1    2   >   <  E   |
+---+---------+------------------> - <------+------------------> - <------+
|
sp

We wish to insert "direction C" between "direction C-1" and the initial square of the second move. The following subroutine will do just that, but follow it through very carefully because its mechanism is quite intricate.

C5        ADDASTEP  PUSH BC       The number of bytes at the top of the
D5                  PUSH DE       stack which need to be shifted down
E5                  PUSH HL       is C plus two, but once BC, DE, and HL
3E08                LD A,08       have been pushed onto the stack the
81                  ADD A,C       actual number is C plus eight.
210000              LD HL,0000
44                  LD B,H
4F                  LD C,A        The number is stored in BC.
39                  ADD HL,SP     HL points to the top of the stack.
54                  LD D,H
5D                  LD E,L
1B                  DEC DE        DE points to one byte below this.
EDB0                LDIR          Part of the stack is moved down.
3B                  DEC SP        The stack pointer is moved also.
E1                  POP HL
7C                  LD A,H
12                  LD (DE),A     The current direction is put in place.
D1                  POP DE
C1                  POP BC        The registers are retrieved.
0C                  INC C         C is increased to indicate that we are
                                  now at the next step.

You'll notice that the sequence LD HL,0000/ADD HL,SP is necessary because there is no such instruction as LD HL,SP (even though LD SP,HL is allowed). LDIR is used to shift the required part of the stack down one byte. The exact number of bytes to be shifted must first be very carefully calculated, and stored in BC in order that LDIR will work properly. Coincidentally LDIR will leave DE finally pointing to just the right address for us to store the current direction. Since HL is at the top of the stack we may remove it, and load the current direction (H) into position, via A, before we remove DE and BC. Thus the stack pointer is still where we want it, and none of the values of any register (except A) have been changed.

The stack now looks like this:

+---+---------+------------------> - <-----------+-------------> - <------+
| E |priority |initial dir. dir. >   < dir. dir. |initial dir. >   < dir. |
|   |         |square   1    2   >   < C-1   C   |square   1   >   <  E   |
+---+---------+------------------> - <-----------+-------------> - <------+
|
sp

Finally, C is incremented because we are now ready to examine the next step.

The two procedures involved in the second problem may be solved by careful study of the above process. To abolish the current move is simple - DE is popped, the stack pointer is then incremented by the exact number of bytes, and DE is pushed back again. The second procedure, that of abolishing the whole list except for the current move may be achieved by loading HL with the position within the stack of "direction C", DE with the contents of the variable LBASE, and then using LDDR, however, you'll have to do some thinking in order to work out BC (the number of bytes to be moved) and the new position of the stack pointer. If you understand how ADDASTEP works it will not be all that difficult to do.

With this problem to solve, I will leave you. It's not impossible I assure you. Finally, consider the length of this program so far - our addresses still begin with 4E, and we are allowed to go as far as 4FFF (although we need some left over for the screen and the stack). 1K draughts is quite, quite possible. With thought you may even be able to shorten it further.

DOWNLOADING

Although the program is only 1K it is currently stored in the fourth K. To download it into the first K the procedure is this.

Change every address beginning with 4C to the corresponding address which begins 40. Do the same for 4D, changing it to 41, change 4E to 42, and 4F to 43.

Delete all lines of BASIC except the following:

OLD ROM                            NEW ROM
1 RANDOMISE USR(printboard)        1 INPUT A$
2 INPUT A$                         2 RAND USR game
3 RANDOMISE USR(game)
4 GO TO 2                (USE ANY FIVE DIGIT NUMBER FOR NOW)

Reserve enough space for the machine code using a series of REM statements from line 5 onwards. On the OLD ROM a REM statement with 46 characters after the word REM occupies exactly fifty bytes. On the NEW ROM a REM statement with 44 characters after the word REM occupies fifty bytes. The machine code will eventually overwrite not only the characters after the word REM, but the word REM itself and even the line numbers.

OLD ROM: type POKE 16463,-1
NEW ROM: type POKE 16535,-1

All of your REMs should disappear from the listing.

Now, using a machine code program, which you should store somewhere in the third K, copy all of the draughts program from address 4C97 onwards, down to 4097 onwards.

OLD ROM: copy the board printing routine to the print immediately after the draughts program proper finishes.

NEW ROM: DO NOT copy the board printing routine at all. Instead, leave it at 4C09, and replace the instruction RET by the following machine code program.

217D40              LD HL,FIRSTLINE    Fool the ROM into thinking that
222940              LD (NXTLIN),HL     the first line of the program is
C30703              JP SAVE            about to be executed, then jump
                                       to the SAVE routine.

Start your cassette recorder up, so that it is recording, not playing, and type as a direct command RAND USR 19487. This should be done in the FAST mode. The program will then do the following tasks:

  • Print the playing board.
  • Specify that line one is about to be executed.
  • SAVE the program, and the current display file (with the board pre-set-up) and the fact that line one is about to be executed.

When you re-load from tape you will be in mid-program, with the first move (yours) about to be made.

The label "printboard" for the OLD ROM refers to the address at which the board printing routine is to be placed. The label "game" refers to the address 16612.

For the OLD ROM, the address WKBOARD should be changed to that of the board printing routine throughout. In this way the same space is effectively used twice. For the NEW ROM, the address WKBOARD should be left unchanged at 403C.

Previous | Contents | Next