Previous | Contents | Next

Draughts Part Two

DRAUGHTS

This is the section which decides upon which is the "best" move the computer can make, after the human's move.

You may have to follow this thinking we are about to embark upon very carefully. Here in brief is a systematic breakdown of the way in which the move is chosen.

We can scan the board, one (black) square at a time, and whenever we find a computer's piece we sit and think about it for a bit. To each move we find possible we assign a numerical value, such that the bigger the number, the better we think the move is. It then follows that to select a move we merely have to choose the one with the highest possible value.

Of course this idea won't let the computer plan ahead - it can only think one move at a time. In order to construct this list of moves, and accompanying numerical values we don't actually have to store every single move we find. Having located a possible move, and worked out its score, what happens is this:

If the score is LOWER than those on the list, the move is ignored.

If the score is EQUAL to those on the list, it is added to the end.

If the score is HIGHER than those on the list, then the list is abolished and a new one started.

In this way the list is always as short as it can possibly be. When the final decision time actually arrives the computer now merely has to select one of these moves at random. Next question - where will the list be stored? Answer The Stack. This simplifies things, but it does mean that we must keep a record of where the start of the list is. We shall store this at address 407B (OLD ROM 4022) and call this quantity LBASE. You will notice that in an earlier part of the program we used 407B/4022 to store a quantity called POINTER. Don't worry - this is quite alright. POINTER is not used in the previous section, and its value does not need to be preserved. LBASE was not used in the last section, and again its value does not need to be preserved. Using the same space twice for two different things is a space-saving trick you should get to know.

The decision making of the computer begins at address 4D8A. The first instruction is LD (LBASE),SP. The start of the list is now preserved. We can play around with the stack now as much as we like, as long as we remember to restore its value before we return to BASIC. The second and third instructions are LD BC,0000 and PUSH BC, which will indicate that there is nothing at all in the current list.

The checking loop thus looks like this. Notice that a new variable SQCHK is used. It is listed as residing at 4077, but OLD ROM owners should replace this address by 401C:

4D8A: ED737B40  BOARDSCAN LD (LBASE),SP    Initialise the list.
      010000              LD BC,0000
      C5                  PUSH BC
      213C40              LD HL,WKBOARD    Scan the board, one square
      7E        NXTCHK    LD A,(HL)        at a time.
      F680                OR 80
      FEBC                CP BC            Have we found a computer's
                                           piece?
      227740              LD (SQCHK),HL
      CA434E              JP Z,EVALUATE
      2A7740    KPCHKNG   LD HL,(SQCHK)
      2C                  INC L            Have we reached the end
      7D                  LD A,L           of the board yet?
      FE66                CP 66
      20EC                JR NZ,NXTCHK     Loop back if not.

As you can see, this particular bit is quite straightforward. You only need to (temporarily) add a few extra instructions to avoid crashing. These are:

4E43: C3D54D    EVALUATE  JP 4DD5          These additional lines
4DA9: C3D54D    CHOOSE    JP 4DD5          are temporary only. They
4DD5: ED7B7B40            LD SP,(LBASE)    will stop the program
4DD9: 0EA7                LD C,A7          crashing, but will not
4DDB: CDBC4C              CALL GAMEOVER    run it.

Can you see that loading SP with (LBASE) eliminates the need to POP everything from the stack before returning. LDing SP will fool the machine into thinking that the stack hasn't changed since we went into the loop.

Now we need to think about what form we want the list to take. Let's examine the problem in reverse. What form would we like the list to take, in order to make removing items from the stack easier.

The first item on the stack should be the number of steps involved in the move - that is one for a single move/jump, two for a double jump, three for a triple jump, and so on. The second item should be the numerical value which the items in the list have been assigned - the priority as we shall call it. Following these items of information we should have the list itself, starting with the square to be moved from, followed by a sequence of one or more directions in which to be moved. Immediately after this the second item in the list in the same form, then the third, and so on...

You'll notice that each thing we need on the stack will only need to be one byte in length. The number of steps cannot possibly be more than 255. The priority can be chosen however we like - we can always make it one byte if we wish. The initial square can be stored by only stacking the low part of its address in WKBOARD. The directions to be moved can be stored in the same manner as before - 05, 06, FA, or FB for plus or minus five or six. In order to make this program as space efficient as we can it makes sense to do just that.

To make a random decision let's assume there are B possible choices. We want therefore to choose a random number between 1 and B - or as we shall do between 0 and B-1. We shall do this by the following means:

4DA9: 3A3440    CHOOSE    LD A,(FRAMES)low    Select a random number
      90        REPEAT    SUB B               between 0 and B-1. This
      30FD                JR NC,REPEAT        number to be stored in
      80                  ADD A,B             the A register.
      C3D54D              JP 4DD5

OLD ROM users should replace the address 4034 by 401E. The final JP 4DD5 is merely a means of exiting the program.

Imagine the list is complete and we are about to remove one item from it. The stack now looks like this:

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

If we now use the instruction POP BC, B will contain the priority, and C the no. of steps. The priority is now a redundant piece of information, since it was only needed to construct the list in the first place. C however is very important. In the diagram above C would be one, but it doesn't have to be.

The stack now looks like this - but let's generalise a bit more by assuming there are two steps per move, not one:

+----------------------------+----------------------------> - <----------+
|initial direction direction |initial direction direction >   < direction|
|square  one       two       |square  one       two       >   < two      |
+----------------------------+----------------------------> - <----------+
|                                                                        |
sp                                                                   lbase

If A is an indication of which of these moves we are to choose then it seems logical that we must remove A of them from the stack. Then the required move would be at the top of the stack. Thus if A is zero we do nothing, otherwise we must use some kind of loop. Can you see that POP HL followed by DEC SP will remove one byte from the stack rather than two, and that INC SP can be used to skip over one of the bytes.

The required loop is this:

4DB0: C1                  POP BC           Find the number of steps
      41                  LD B,C           per move.
      2808                JR Z,FIRSTOFF    Do nothing if A is zero.
      33        NSQOFF    INC SP           Remove a total of A
      33        NEXTOFF   INC SP           complete moves from the
      10FD                DJNZ NEXTOFF     stack.
      41                  LD B,C
      3D                  DEC A
      20F8                JR NZ,NSQOFF

The selected move is now at the top of the stack. To carry it out let's first take a look at what the stack is now like:

+------------------------------> - -
|initial  direction  direction >
|square   one        two       >
+------------------------------> - -
|
sp

To find the initial square the sequence is POP HL followed by LD H,WKBOARD-high. You see "initial square" is the low part of the address. By assigning H with the high part we ensure that the register pair HL contains the absolute address of the square from which we must move. H must be assigned after the POP HL instruction though, since there is no real way we can manage to remove L on its own. Finally the instruction LD B,C once more will assign B with the number of steps we have to make. The procedure for carrying out these steps is much simpler than before since we don't have to check for cheating - we shall write the program such that the computer cannot cheat.

4DBA: E1        FIRSTOFF  POP HL               Find the absolute address
4DBC: E1        FIRSTOFF  POP HL               Find the absolute address
      2640                LD H,WKBOARD-high    from which we must move.

To remove one direction at a time from the stack we shall use the sequence DEC SP/POP DE. In this way E will be assigned with the required direction. D will contain useless information.

4DBF: 41                  LD B,C
      3B        NEXTSTEP  DEC SP           Find which direction the
      D1                  POP DE           computer is to move.
      4E                  LD C,(HL)        Get computer's piece.
      3680                LD (HL),80       Overwrite with black sq.
      7D                  LD A,L           Find destination square.
      83                  ADD A,E
      6F                  LD L,A
      7E                  LD A,(HL)        Is this square empty?
      FE80                CP 80
      2805                JR Z,SQUARE      If so, move.
      3680                LD (HL),80       If not, jump.
      7D                  LD A,L
      83                  ADD A,E
      6F                  LD L,A
      71        SQUARE    LD (HL),C        Put piece in position.
      10EB                DJNZ NEXTSTEP    Same for next direction.

You should now be at address 4DD5, at which is stored the sequence

4DD5: ED7B7B40            LD SP,(LBASE)
      0EA7                LD C,A7
      CDBC4C              CALL GAMEOVER
4DDE: 2A0C40    BDPRINT   LD HL,(D_FILE)
                ...
                and so on down to
4DF0: C9                  RET

[Download available for 16K ZX81 -> chapter13-draughts2.p.]

This means that provided the stack is correctly set up we can actually see this whole mechanism working. What I want you to do now is to write a short routine to set up the stack so that all of the possible opening moves are stored. You should be able to do this all by yourself. I will tell you though that the routine should be placed at address 4E43 (what will eventually be the EVALUATE routine) and should be terminated by the instruction JP CHOOSE (C3A94D). One way of doing this bit would be LD HL,something/PUSH HL/LD HL,something/PUSH HL/and so on, but if you can think of a better way by all means use it.

You may now RUN the draughts program by typing RUN 4. You will be asked for an input - make your move as you have been doing in the past. Now watch what happens to the computer's side - one of the pieces should move! Break out of the program, since as yet it can only decide upon the first move of the game.

Now RUN it again - again by typing RUN 4. Does the computer make the same move? If it does it's purely coincidence, since choosing from the list is done at random. Try again, and again, remembering to break out of the prorgam each time and re-run. You should get a different result each time.

We'll leave the program at this stage and continue later on with the mechanism of setting up the stack correctly in the first place, and actually deciding which moves are better than others.

In the next chapter we'll look at some complete (and short) games designed to demonstrate what machine code can achieve in terms of speed, and in very few bytes compared with BASIC.

Previous | Contents | Next