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!

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

To Top   



12-3-04