"21"
P5a
 

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

SetUp









Table



























Comp

CompA






Comp1






Comp2






Comp3






Comp4









Convert




Conv1


Conv2








Delay








DelB


DelC











Display














Disp



Disp1






Mess1











Mess1A















Mess2



Show










Value






Val1






Val2

Val3

Val4









Main

Main1




Main2
















Main3







Main4


ORG 0
BSF 03,5
MOVLW 03
MOVWF 05
CLRF 06
BCF 03,5
CLRF 11h
CLRF 14h
CLRF 1F
GOTO Main

ADDWF 02h,1
RETLW 3Fh
RETLW 30h
RETLW 5Bh
RETLW 4Fh
RETLW 66h
RETLW 6Dh
RETLW 7Dh
RETLW 07h
RETLW 7Fh
RETLW 6Fh
RETLW 6Eh
RETLW 3Fh
RETLW 3Eh
RETLW 00h
RETLW 38h
RETLW 3Fh
RETLW 6Dh
RETLW 79h
RETLW 00h
RETLW 0FFh







MOVF 0C,0
MOVWF 0F
MOVLW 02
XORWF 0F,0
BTFSS 03,2
GOTO Comp1
MOVLW 01
MOVWF 10h
RETURN
MOVLW 03
XORWF 0F,0
BTFSS 03,2
GOTO Comp2
MOVLW 02
MOVWF 10h
RETURN
MOVLW 04
XORWF 0F,0
BTFSS 03,2
GOTO Comp3
MOVLW 03
MOVWF 10h
RETURN
MOVLW 05
XORWF 0F,0
BTFSS 03,2
GOTO Comp4
MOVF 11h,0
MOVWF 10h
RETURN
DECF 0Fh,1
DECF 0Fh,1
DECF 0Fh,1
DECF 0Fh,1
GOTO CompA





CLRF 0D
CLRF 0E
MOVF 0C,0
MOVWF 0F
INCF 0F,1
DECFSZ 0F,1
GOTO Conv2
RETURN
INCF 0D,1
MOVLW 0A
XORWF 0D,0
BTFSS 03,2
GOTO Conv1
INCF 0E,1
CLRF 0D
GOTO Conv1

MOVLW 60h
MOVWF 1B
DelA NOP
NOP
DECFSZ 1A,1
GOTO DelA
BTFSC 05,0
GOTO DelC
BCF 1F,0
DECFSZ 1B,1
GOTO DelA
RETURN
BTFSC 1F,0
GOTO DelB
INCF 14h
BTFSS 14h,2
DECF 0C,1
MOVLW 04
MOVWF 13h
BSF 1F,1
BSF 1F,0
GOTO DelB


MOVLW 00
XORWF 0Eh,0
BTFSC 03,2
GOTO Disp1
MOVF 0Eh,0
CALL Table
MOVWF 06
CALL Delay
CLRF 06
CALL Delay
MOVF 0Dh,0
CALL Table
MOVWF 06
CALL Delay
CLRF 06
CALL Delay
CALL Delay
CALL Delay
RETURN
MOVF 0Dh,0
CALL Table
MOVWF 06
GOTO Disp



MOVLW 40h
MOVWF 06
CALL Show
CALL Show
MOVLW 06
MOVWF 06
CALL Show
CALL Show
CALL Show
CALL Show
MOVLW 0Dh
MOVWF 12h
CLRF 06
CALL Show
MOVF 12h,0
CALL Table
MOVWF 06
MOVLW 0FFh
XORWF 06,0
BTFSC 03,2
GOTO Main
INCF 12h,1
CALL Show
CALL Show
GOTO Mess1A



MOVLW 0Ah
MOVWF 12h
GOTO Mess1A

NOP
DECFSZ 1A,1
GOTO Show
DECFSZ 1B,1
GOTO Show
RETURN





MOVLW 01
XORWF 10h,0
BTFSS 03,2
GOTO Val1
MOVLW 80h
MOVWF 06
GOTO Val3
MOVLW 02
XORWF 10h,0
BTFSS 03,2
GOTO Val2
MOVLW 0C0h
MOVWF 06
GOTO Val3
MOVLW 0E0h
MOVWF 06
MOVLW 0Ah
MOVWF 1C
NOP
DECFSZ 1A,1
GOTO Val4
DECFSZ 1B,1
GOTO Val4
DECFSZ 1C,1
GOTO Val4
RETURN


MOVLW 16h 
MOVWF 0Ch
INCF 11h,1
MOVLW 04
XORWF 11h,0
BTFSC 03,2
GOTO Main4
CALL Convert
CALL Display
BTFSS 1F,1
GOTO Main1
DECFSZ 13h,1
GOTO Main1
CLRF 14h
MOVLW 00
XORWF 0Ch,0
BTFSC 03,2
GOTO Mess2
MOVLW 01
XORWF 0Ch,0
BTFSC 03,2
GOTO Mess1
CALL Comp
CALL Value
CALL Convert
CALL Display
DECF 0Ch,1
DECFSZ 10h,1
GOTO Main3
BCF 1F,1
GOTO Main1
CLRF 11h
INCF 11h
GOTO Main2

END 
;Start of memory for the program.
;Go to Bank 1
;Load W with 0000 0011
;Make RA0, RA1 input
;Make all port B output
;Go to Bank 0 - the program memory area.
;Clear the random number file
;Clear the "3-times button pressed" file
;Clear the button-press file


;Add W to the Program Counter to create a jump.
;0    format= gfedcba
;1
;2
;3
;4
;5
;6
;7
;8
;9
;y
;O
;U
;
;L
;O
;S
;E
;
;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.


;Move file 0C to W
;Move W to file 0F for this operation 





;"Computer takes 1"






;"Computer takes 2"






;"Computer takes 3"





;Put random number into W
;"Computer takes Random number">

;File 0F is greater than 5 so reduce it by 4





;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"



;Move file 0C to W
;Move W to file 0F for decrementing
;To account for the next two lines
;Decrement file 0F





;Test the zero flag for "ten"

;Increment the "tens"
;Zero the "units"
;Do another conversion







;Look at push button





;Test the button-press flag

;Increment "3-times pressed" file
;Button pressed too many times
;Decrement the count file

;Number of loops of display before computer turn
;Set the flag for above loop
;Set the button-press flag



;Blank the leading "0"
;    "       "        "
;    "       "        "
;    "       "        "
;Move file 0E to W. Show "tens"

;Show value on 7-segment display

;Blank the display

;Move file 0D to W. Show "units"

;Show value on 7-segment display

;Blank the display 




;Move file 0D to W. Show "units"

;Show value on 7-segment display


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

;Show "-"



;Show the letter"I"






;Jumper for table




;Output to display
;Detect end of Table


;End of Table detected
;Jump to next letter




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


;Jumper for table


;Create 250mS delay






;"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.

















;Create 2 sec delay to show
;             computer value on 8 LEDs










;15h = 21 16h = 21

;Increment the random number


;Test zero bit for match 



;Has button been pressed?

;Decrement the 4-loop file before computer turn

;Clear the "3-times button pressed" file


;Test zero flag for match
; "You lose" 


;Test the zero flag
; "I Lose"
;Go to "Computer Turn" for No of matches to remove
;Display computer value for 2 secs



;Decrement the "computer matches" value.

;Clear the loop flag 





;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. 
 

To Top   



12-3-04