This is the old game of “21 MATCHES.”

It’s a very simple game in which 21 matches are laid on the table in a row and each player can take 1, 2, or 3 matches. The player taking the last match loses.

It’s one of the games that can be adapted for the PIC LAB-1 to show the concept of strategy and “intelligence.”
It’s YOU against the COMPUTER.
The player goes first and takes 1, 2 or 3 matches by pressing the button 1, 2 or 3 times. On each press, the number on the screen decrements.
The screen shows: 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1.
You can use matches or pen-and-paper to follow the game and try to work out the strategy used in the program.
The routines are fully documented in the program below but the actual strategy is not revealed. It’s shown, but not explained.
We have especially done this to force you to sit down and follow the instructions.
Now it’s your turn to do some study.
Computers are one of the most amazing things in the field of ARTIFICIAL INTELLIGENCE.
By the mere fact that they are able to process information at an extremely rapid rate, the outcome can appear as INTELLIGENCE. This program is the simplest example of this concept. It will beat you on your first few games and hopefully you will “home-in” on the secret.
Apart from providing the concept of “intelligence,” the program shows how to create a number of sub-routines to perform specific operations. Some of the routines have already been covered in our experiments, while the strategy sub-routine is new. The program will work with any number of matches (at the beginning of a game) and this can be altered by changing the value loaded into 0Ch in Main.

MACHINE CODE

”21” highlights the advantage creating a project with a microcontroller. The game requires a number of sub-routines that perform operations similar to “thinking.”
Try to carry out thinking routines with individual chips; you will need quite a number.
We say the PIC16F84 is equivalent to about 8 discrete chips, but in our case it would exceed 20!
As you build up a program, many sub-routines will need to carry out operations already produced by sub-routines you have already created and it is simply a matter of adding a single line such as CALL Convert, or CALL Display to take advantage of them.
Providing you stick to our convention of using files 0C to 19h for general purpose use, files 1A, 1B, 1C, 1D, 1E for decrementing (for use in Delays) and file 1F for flags, you will be able to recognise the grouping for each file.
The only major problem with Machine Code is identifying a value (such as 06) being loaded into a file and differentiating this from the name of a file (such as file 06). After a few hours of programming you will be able to read the code without a mistake.
But the main advantage of Machine Code is clarity. You are able to read the program exactly as the micro will carry out the instructions and nothing is “hidden” behind an “interpreter” program.
The complexity of ”21” is about the highest you can get for microcontrollers in this range, and if you can follow the routines in ”21,” you are well on the way to advanced programming.
As you go to larger processors and controllers, remembering the names of the files and ports is quite difficult and some form of assistance is needed.
This is when you will be introduced to a system called ”equates” where files are allocated names and these names are used when programming. You will also need a higher-level language.
But that’s for the next microprocessor. We still haven’t used one-quarter the memory in our device and as you get larger and larger programs, many of the sub-routines will CALL previous sections and a program with twice the complexity of say “21” may only occupy 10% more memory.
1k of memory can hold a lot of sub-routines and a very impressive program can be produced. If you think 1k or 2k is a small memory, try to fill it!
It is interesting to note that a complete CHESS game has been produced in 1k of memory, with 4 levels of play and a challenge factor of 7. It had very simple graphics but was one of the first programs to be produced on a computer (the ZX80) - and this was nearly 30 years ago!

STRATEGY ALGORITHM

An algorithm is a program or routine that solves a problem in a finite number of steps. To be able to design a strategy routine or algorithm, you have to know all the combinations and permutation of a particular operation. These are then condensed into a set of rules and a sequence of instructions is produced to execute the requirements.
There are different levels of programming and an algorithm is the highest. It needs to take into account all the possible choices and come up with the best decision. Obviously we are not making the decisions equivalent to a game of chess but there is still a choice to be made and an algorithm shows how to go about creating a routine that covers “all bases.”

There are different ways to do this.

1. You can write a single routine to encompass all the possibilities of the game.
   This is an algorithm.
2. You can advance down the program and create a new set of decisions for the situation at-hand.
   This is called the linear method.
3. You can provide a table that produces an output for each possibility.
   This is the table method.

The table method is the simplest and the linear method is the next simplest.
But our approach is to use an algorithm to cover all possibilities. This is the hardest and involves the most complex programming.
No matter which arrangement is decided on, producing this section of a program is the most rewarding of all. It gives a feeling of feedback and activity.
The three methods show that even the most complex part of a program can be carried out with very simple programming steps or very advanced programming.
Simple steps may take a few extra lines of code but when you have plenty of program-space, don’t worry about the “waste.”
Many of the experiments we have produced in this course carry out operations in a very simplistic way and are not representative of advance-programming. But if the end result is the same, don’t create complexities.
In advanced-programming, there are a number of LOGIC commands that can be used to perform very impressive operations in a very small number of steps. There are operations such as: SUBWF, ADDWF, XORLW, XORWF etc and sometimes you have to carry out a bit-for-bit comparison to see exactly what has been performed with each instruction.

Download the program below into the PIC LAB-1 and play the game a number of times to get a feeling of the sequence.
The flow of the strategy algorithm is explained later. For now, try to work out as much of the program as you can.
The files for “21Match” can be found HERE. Click and a window will open with the files. Locate Notepad.exe in the window and click on it. Notepad will open. Click on the file you want to open and slide it across to the Notepad window. The file will appear!

     ;21Match.asm
     ;Project: "21-MATCHES" Game
List P = 16F84
#include <p16F84.inc>
__CONFIG 1Bh ;_CP_OFF & _PWRTE_ON & _WDT_OFF & _RC_OSC

         ORG 0          ;Start of memory for the program.
SetUp    BSF 03,5       ;Go to Bank 1
         MOVLW 03       ;Load W with 0000 0011
         MOVWF 05       ;Make RA0, RA1 input
         CLRF 06        ;Make all port B output
         BCF 03,5       ;Go to Bank 0 - the program memory area.
         CLRF 11h       ;Clear the random number file
         CLRF 14h       ;Clear the "3-times button pressed" file
         CLRF 1F        ;Clear the button-press file
         GOTO Main

Table    ADDWF 02h,1    ;Add W to the Program Counter to create a jump.
         RETLW 3Fh      ;0    format= gfedcba
         RETLW 30h      ;1
         RETLW 5Bh      ;2
         RETLW 4Fh      ;3
         RETLW 66h      ;4
         RETLW 6Dh      ;5
         RETLW 7Dh      ;6
         RETLW 07h      ;7
         RETLW 7Fh      ;8
         RETLW 6Fh      ;9
         RETLW 6Eh      ;y
         RETLW 3Fh      ;O
         RETLW 3Eh      ;U
         RETLW 00h      ;
         RETLW 38h      ;L
         RETLW 3Fh      ;O
         RETLW 6Dh      ;S
         RETLW 79h      ;E
         RETLW 00h      ;
         RETLW 0FFh     ;End of message

                        ;This sub-routine works out the "Computer No of
                        ;matches." The number of matches (file 0C) is loaded
                        ;into file 0F. The ;number of matches to be removed is
                        ;worked-out and put into file 10h.


Comp     MOVF 0C,0      ;Move file 0C to W
         MOVWF 0F       ;Move W to file 0F for this operation
CompA    MOVLW 02
         XORWF 0F,0
         BTFSS 03,2
         GOTO Comp1
         MOVLW 01
         MOVWF 10h      ;"Computer takes 1"
         RETURN
Comp1    MOVLW 03
         XORWF 0F,0
         BTFSS 03,2
         GOTO Comp2
         MOVLW 02
         MOVWF 10h      ;"Computer takes 2"
         RETURN
Comp2    MOVLW 04
         XORWF 0F,0
         BTFSS 03,2
         GOTO Comp3
         MOVLW 03
         MOVWF 10h      ;"Computer takes 3"
         RETURN
Comp3    MOVLW 05
         XORWF 0F,0
         BTFSS 03,2
         GOTO Comp4
         MOVF 11h,0     ;Put random number into W
         MOVWF 10h      ;"Computer takes Random number">
         RETURN
Comp4    DECF 0Fh,1     ;File 0F is greater than 5 so reduce it by 4
         DECF 0Fh,1
         DECF 0Fh,1
         DECF 0Fh,1
         GOTO CompA

                        ;This sub-routine converts the hex value in file 0C to
                        ;decimal values in files 0D and 0E.
                        ;File 0D is the "units" and file 0E is the "tens"

Convert  CLRF 0D
         CLRF 0E
         MOVF 0C,0      ;Move file 0C to W
         MOVWF 0F       ;Move W to file 0F for decrementing
         INCF 0F,1      ;To account for the next two lines
Conv1    DECFSZ 0F,1    ;Decrement file 0F
         GOTO Conv2
         RETURN
Conv2    INCF 0D,1
         MOVLW 0A
         XORWF 0D,0
         BTFSS 03,2     ;Test the zero flag for "ten"
         GOTO Conv1
         INCF 0E,1      ;Increment the "tens"
         CLRF 0D        ;Zero the "units"
         GOTO Conv1     ;Do another conversion

Delay    MOVLW 60h
         MOVWF 1B
         DelA NOP
         NOP
         DECFSZ 1A,1
         GOTO DelA
         BTFSC 05,0     ;Look at push button
         GOTO DelC
         BCF 1F,0
DelB     DECFSZ 1B,1
         GOTO DelA
         RETURN
DelC     BTFSC 1F,0     ;Test the button-press flag
         GOTO DelB
         INCF 14h       ;Increment "3-times pressed" file
         BTFSS 14h,2    ;Button pressed too many times
         DECF 0C,1      ;Decrement the count file
         MOVLW 04
         MOVWF 13h      ;Number of loops of display before computer turn
         BSF 1F,1       ;Set the flag for above loop
         BSF 1F,0       ;Set the button-press flag
         GOTO DelB


Display  MOVLW 00       ;Blank the leading "0"
         XORWF 0Eh,0    ;  "   "   "
         BTFSC 03,2     ;  "   "   "
         GOTO Disp1     ;  "   "   "
         MOVF 0Eh,0     ;Move file 0E to W. Show "tens"
         CALL Table
         MOVWF 06       ;Show value on 7-segment display
         CALL Delay
         CLRF 06        ;Blank the display
         CALL Delay
         MOVF 0Dh,0     ;Move file 0D to W. Show "units"
         CALL Table
         MOVWF 06       ;Show value on 7-segment display
         CALL Delay
         CLRF 06        ;Blank the display
Disp     CALL Delay
         CALL Delay
         CALL Delay
         RETURN
Disp1    MOVF 0Dh,0     ;Move file 0D to W. Show "units"
         CALL Table
         MOVWF 06       ;Show value on 7-segment display
         GOTO Disp

                        ;"Mess1" shows on 7-segment display: "I Lose"

Mess1    MOVLW 40h      ;Show "-"
         MOVWF 06
         CALL Show
         CALL Show
         MOVLW 06       ;Show the letter"I"
         MOVWF 06
         CALL Show
         CALL Show
         CALL Show
         CALL Show
         MOVLW 0Dh
         MOVWF 12h      ;Jumper for table
Mess1A   CLRF 06
         CALL Show
         MOVF 12h,0
         CALL Table
         MOVWF 06       ;Output to display
         MOVLW 0FFh     ;Detect end of Table
         XORWF 06,0
         BTFSC 03,2
         GOTO Main      ;End of Table detected
         INCF 12h,1     ;Jump to next letter
         CALL Show
         CALL Show
         GOTO Mess1A

                        ;"Mess2" shows on 7-segment display: "You Lose"

Mess2    MOVLW 0Ah
         MOVWF 12h      ;Jumper for table
         GOTO Mess1A

Show     NOP            ;Create 250mS delay
         DECFSZ 1A,1
         GOTO Show
         DECFSZ 1B,1
         GOTO Show
         RETURN

                        ;"Value" displays the number of matches the computer
                        ;will remove. It is displayed on the 8 LEDs as one LED,
                        ;two LEDs or three LEDs. File 10h is computer number.

Value    MOVLW 01
         XORWF 10h,0
         BTFSS 03,2
         GOTO Val1
         MOVLW 80h
         MOVWF 06
         GOTO Val3
Val1     MOVLW 02
         XORWF 10h,0
         BTFSS 03,2
         GOTO Val2
         MOVLW 0C0h
         MOVWF 06
         GOTO Val3
Val2     MOVLW 0E0h
         MOVWF 06
Val3     MOVLW 0Ah      ;Create 2 sec delay to show
         MOVWF 1C       ;   computer value on 8 LEDs
Val4     NOP
         DECFSZ 1A,1
         GOTO Val4
         DECFSZ 1B,1
         GOTO Val4
         DECFSZ 1C,1
         GOTO Val4
         RETURN


Main     MOVLW 16h      ;15h = 21 16h = 21
         MOVWF 0Ch
Main1    INCF 11h,1     ;Increment the random number
         MOVLW 04
         XORWF 11h,0
         BTFSC 03,2     ;Test zero bit for match
         GOTO Main4
Main2    CALL Convert
         CALL Display
         BTFSS 1F,1     ;Has button been pressed?
         GOTO Main1
         DECFSZ 13h,1   ;Decrement the 4-loop file before computer turn
         GOTO Main1
         CLRF 14h       ;Clear the "3-times button pressed" file
         MOVLW 00
         XORWF 0Ch,0
         BTFSC 03,2     ;Test zero flag for match
         GOTO Mess2     ; "You lose"
         MOVLW 01
         XORWF 0Ch,0
         BTFSC 03,2     ;Test the zero flag
         GOTO Mess1     ; "I Lose"
         CALL Comp      ;Go to "Computer Turn" for No of matches to remove
         CALL Value     ;Display computer value for 2 secs
Main3    CALL Convert
         CALL Display
         DECF 0Ch,1
         DECFSZ 10h,1   ;Decrement the "computer matches" value.
         GOTO Main3
         BCF 1F,1       ;Clear the loop flag
         GOTO Main1
         CLRF 11h
Main4    INCF 11h
         GOTO Main2

         END            ;Tells assembler end of program

THE PROGRAM

The program is designed to work with any number of matches. If it starts with 21, the random number section will not be needed. If it starts with 22, you will be able to see the random number feature come into operation.
Let’s go though the program, one section at a time.
The first section is the first 11 instructions in Main (actually instructions 3 -11). It does three things:

1. The Random Number file is incremented (it must be 1, 2 or 3).
2. The Convert sub-routine is executed to convert the number of matches (in hex) is converted to a decimal number.
3. The Display sub-routine is executed to show the number of matches on the 7-segment display.
   The flow chart for this is:

In the flow chart above, the program is looping, waiting for the switch to be pressed. The random number file is here as human involvement will create an unknown value in the file. It is cleared in SetUp. When it reaches 4, it is cleared and loaded with 1. In this way it will only contain 1, 2 or 3.
The Convert routine takes the number of matches (in hex) and converts it to a decimal number.
The decimal number will be placed in files 0D and 0E. These two files are cleared at the beginning of the sub-routine and the hex value in file 0C is placed in file 0F as a temporary file so that file 0C will not be altered. The hex value is transferred to the two decimal files by a process called decrementing. The units file is incremented in a loop and at the same time, file 0F is decremented.
On each loop, the units file is tested to see if it has reached “10” (0A). If it has, it is zeroed and the tens file is incremented. When file 0F is zero, the transfer is complete.
The micro then returns to Main and goes to Display.
The Display sub-routine shows the “tens” and “units” on a 7-segment display.
The routine firstly checks the value of the file by comparing it to 00. If it is zero, the routine displays only the “units.” To display a value, the decimal value is used as a jump value for a Table and the program returns with the display-value. This value is outputted to port 06.
A Delay is then called to allow the value to appear on the display.
The display is then blanked and Delay is called to create separation between digits in case the same numeral needs to be displayed as the “units.”

Since the micro will be spending most time in the Delay routine, this is where the switch commands are placed and it requires some detailed analysis:

The instruction to “look at push button” is in the inner loop and it is accessed every millisecond.
If the button is pressed, a bit in the flag file is SET. (1F,0) and the micro decrements the number of matches, loads a counter with 4 for the number of loops of the display before the computer has its turn and sets the button-press flag.
If the button is pressed more than 3 times, the routine jumps over the instruction to decrement the number matches.
It then completes the delay routine and returns to Main.
The button-press routine must be placed where it will receive immediate attention and that’s why the Delay routine is ideal.
In computer-terms, the button will be pressed for a long time and the delay routine will loop many times while the button is pressed.
As soon as the button is recognised, the match-number is decremented and flag 1F,0 is set, so that the match-count is not decremented again, until the button is released.
The Delay takes approximately 250mS to execute and if the button is pressed a number of times during this execution, the match-count will be decremented accordingly. It is an important feature to fetch the button-presses.
The 1mS delay between each look at the button is called “switch debounce” and is extremely important. This 1mS is the time taken to decrement file 1A.
The Delay routine also re-sets the 4-loop counter for the display so that the player can view the screen after each press of the button.
The placement of an instruction in a routine is very important. For instance, the 4-loop counter must be placed so that is gets re-set each time the button is pressed.

The micro returns to Main and the button-press flag 1F,1 tells the micro that the button has been pressed. The 4-loop counter (file 13h) is decremented and when it is zero, the micro clears the flag that prevent more than 3 button-presses and tests to see if the number of matches is zero.
This test is done before the computer has its turns and if no matches are left, it means the player has taken the last match and forfeited his ability to win the game.
If 1 match is left, the computer loses.
The program then calls ”Comp.”

The first thing Comp does is put the number of matches into file 0F to save file 0C. It then reduces the number of matches to 2, 3, 4, or 5. It does this by looking to see if the number is 2. If not, it looks to see if the number is 3, 4, or 5. If it is above 5, it removes 4 matches and starts the routine again.
If the number is 2, it will remove 1 match, and this number is placed in file 10h. It does a similar process for 3 and 4 matches.
If the number is 5, the computer is on a losing streak and it must take a random number. This is the “thinking” part of the program and the random number is obtained from file 11h.
The micro exits with a “computer number” in file 10h.

The next sub-routine is very simple. It displays the “computer number ” on the 8 LED display as one LED, two LEDs or three LEDs. A 2-second delay is then executed to show the value.

At Main 3, the number of matches in the game is shown again and the program loops this section and decrements the number of matches for the “computer turn.”
The micro is taken to main 1 and sits in a holding loop for the player to take another turn.

THE STRATEGY ALGORITHM

Do not read this until you have played the game and need to know the inner working of the “decision routine.”
The thing that makes computers impressive is a feeling of intelligence.
When feedback comes in the form of a response to a game, a challenge is apparent.
The routine creating the algorithm in the game above, is “Comp.”
“Thinking” routines can be based on one of three approaches:

1. They can be directly linked (on a one-to-one basis) to the input information via a table or sequence or mathematical equation.
2. They can be linked after assessing a number of input values - the algorithm approach,
3. They can be linked via a random number generator.

Every situation is different and the aim is to create a decision of “THE BEST RESULT.”
This obviously means avoiding a silly result but if the situation is ”hopeless,” a result must still be generated. This is where the “last resort” of a random number comes in.
This introduces variations to the game and provides the concept of ”thinking.”

The most important part of creating a Strategy Routine is to “cover all bases.” In other words, all possibilities must be covered. The only way to prove this is to “play the game.” We have produced a program for TIC TAC TOE (in another project) and the only way to produce the strategy section was to play the game many times and see if a “loop-hole” existed. It was then necessary to have other members of staff play the game to see if thinking by a different player was also accounted for.

Now we come to the strategy behind ”21.”
One interesting aspect of the program is its ability to cater for any number of matches. The point we didn’t mention is the outcome.
Different numbers of matches have a different outcome (when the player is aware of the strategy behind the game).
A program can also be designed to allow the computer to make the first move, but most players want to play the first hand - they think they have more control over the outcome. In some cases, they do. It depends on the number of matches in the game.

The basis behind ”21” is to divide the matches into groups of 4. If the player takes one match, the computer takes 3. If the player take 2 matches, the computer takes 2. If the player takes one match, the computer takes 3.
This means we can “chop-off” blocks of 4 matches since we know what to do with each block of 4, provided we get into the right position as soon as possible.
With 21 matches we knock off “blocks of 4” and get 5 remaining matches. If the player takes 1 match. The computer takes 3 matches and wins. If the player takes 2 matches in his first turn, the computer takes 2 matches, and wins.
If the player takes 3 matches, the computer takes 1 match and wins.
In other words, the player cannot win with a game of “21.”

“22”

If the game is extended to 22 matches, a different situation is produced.
If the player knows the strategy behind the game, he will be able to see the RANDOM NUMBER come into operation.
At the start of the game, if the player takes 1 match, the computer takes a random number. If the player knows the strategy, the computer cannot win, however if the player does not take the correct number of matches during each turn, “a winning sequence” may be presented to the computer and it will then fall into the sequence of removing matches according to the pattern outlined above.
The program has been supplied as “22” in the .zip files, to see the “thinking” come into operation.