How To Build a Calculator for Master Minds

Description

This piece of equipment (a kind of toy, a gadget, so to speak) is the result of a weekend/late night project I recently carried out at home, in order to tinker with PICs and learn how to program these little gems. The calculator sized device shown above plays a variant of the game called Bulls and Cows (or, in a variant, Jotto), a guessing game popularized by Invicta Plastics under the name Master Mind. Being based on a computer, my variant doesn't use colors and pegs, or cards, but numbers, naturally.

So what does it do? Well, the user thinks up a hidden code (an arbitrary 4 digit number composed of digits from 1 to 7), then the computer tries to guess it, by offering a combination. This combination is displayed on the 4 digit LED display. For example, in the picture above, it shows the combination 1425.  

These guesses are in turn rated by the user by using two buttons, telling the computer how many places are having the correct digit displayed, and how many of the rest are correct, but misplaced. The computer uses this to select then next try, and so on, until either the hidden code is known to the computer - or the user is known to have made a mistake :-). In the former case the computer displays the correct combination and flashes the decimal points in form of a running light. I the latter case, it displays four zeros 0000, indicating an error.

Sources and Binaries (download)

The program is written in a a PicBasic / Assembler mixture.

If anybody would like to build this gadget, and perhaps tinker a bit with the code, without having access to a Picbasic compiler, please have a look at the very same program, but translated into Standard Microchip Assembler language. It contains no Picbasic statements, no macros anymore, but pure plain Microchip Assembler code only. This source differs from a straight disassembly by the fact that all program labels are still there.

For just building the toy, and using my program as a black box, here is the binary, in Intel hex format as produced by the assembler, and as it is used by most of the PIC programmers. Use a programmer to put the binary into a PIC16F84 (WDT off!), and wire it as described below.

User interface and instructions for using the calculator

The calculator has two buttons and a four digit display. The left button cycles through the numbers 0..4, the right key has the role of an enter key.

Initially, the calculator is switched off.  Think up a combination (say: 1234).   Remember: use digits between 1 and 7. Neither 0 nor 8 or 9 are allowed.

Now press the left key once.

When the left key is pressed, the processor wakes up and displays the first question, immediately. For example, it displays the combination 1467.

Here, in this example, it got one position right (the first one), and one additional digit (4, which is in the wrong position) right. So we have to enter "11", the first one for a correct position, the second one for a correct number.

We do that by pressing the left button once. Now it displays a "0" in the position next to the rightmost position, i.e. "__0_". We press the left key again "__1_" and enter it by pressing the right key once. Now we see "__10" in the display. Pressing the left key this time increments the rightmost digit ("__11"). Fine, we press the right button (the "enter" key) again, and after less than half a second, the calculator displays its next guess, 1236 in this example. Now this is almost right, so we enter "__30" by pressing <left> <left> <left><left> <right> <right>. The next guess is "1136", we enter "__20", then 1256 ("__20"). Bingo: the display shows 1234, and blinks the decimal points as a running light in order to indicated success.  We enjoy it, press one of the buttons for one last time, which puts the device to sleep, where it consumes less than 2 µA.

In summary:

We choose the hidden Code 1234

History and theory of operation

This is about the fifth or sixth implementation of that problem I did over the years. The first implementation was done on a 4 MHz single board computer called Nascom II, written in Z80 assembler language, a few years after the game was popularized as Mastermind. The second one was an port of the same algorithm to the same machine, but with the machine converted into a CP/M computer in the meantime. Then I wrote a version in G-Level PLI, still on my home-brew CP/M machine. That PLI version got ported to a large IBM mainframe, later. Etc.

The code breaking strategy is a nice little algorithmic problem to explore new languages or new architectures with, not as trite as the ubiquitous prime number generator, but not too complicated either.  The computerized game itself isn't very interesting anymore - Knuth [1] found the optimal strategy for a specific game (i.e. 4x6) by doing an exhaustive search, one year after the game was brought to marked by Invicta Plastics, and published it in an article - , but the various algorithms for different space and time constraints are still interesting, IMHO.

In the case of the PIC, which has barely enough memory for storing the answers, implementing the generic variant of my algorithm (which finds a good question for an arbitrary n x m game, by using a variant of the classical Branch-and-Bound strategy), is completely out of question. So is storing Knuths decision tables. (Well, perhaps ... hmmm). Anyway, on a mid-range PIC even the solution to the problem of selecting one element from a set of currently unknown size with equal probability is not completely obvious.

So for this variant, I had to use the simple minded random strategy, which is practically almost as good as the optimal strategy (according to Mike Wiener, see [3]).  It should find the hidden code in about five tries, too. I allocated 18 bytes of the 68 Bytes available on the 16F84, giving room for six answers at most. This leaves a little bit of room for trying different strategies without having to change the memory layout. Another 16 bytes are necessary for storying four combinations, while doing the search, uncompressed, for simplicity and speed.

One comparison needs about 150 instructions, or 150µs, on a nominal 4 MHz clock. That amounts to 150µs*2401 = 1/3 seconds looking at every possible combination after the first question. When using a 8 MHz resonator, as I did (a 16F84-04 runs quite well even with a 10 MHz quartz or resonator, if one doesn't need the full temperature/Vdd range, no need to buy the expensive -10 version), the questions usually get computed in less than half a second. That's fast enough.

A few remarks about the Algorithms used will be added on a separate page.

References

[1] Donald E. Knuth, The Computer as Master Mind. J. Recreational Mathematics, Vol. 9(1) (1976-77), 1-6.

[2] Kenji Koyama, Tony W. Lai. An Optimal Mastermind Strategy, J. Recreational Mathematics, VOl. 25(4), 251-256,1993 (my copy says 1993, not 1994)

[3] http://www.math.niu.edu/~rusin/uses-math/games/mastermind/mastermind

Construction and instructions for building the calculator.

The whole thing needs only a few parts, as shown in the part list above. It doesn't even have a power switch. Everything, including the 7-segment encoding and multiplexing, and switching off power (utilizing the processors sleep mode and wake up on port change) is done by the processor and in software. So building the circuit boils down to solder in four seven-segments-displays (a 40 pin socket will do, too), a socket for the processor, and to wire all the many pins of the HDSPs correctly to the processors socket.

Circuit diagram

This diagram has been drawn after building the device (using random wiring on a spare pcb), in order to document it.

All anodes of all digits are driven by port B (seven segments plus a single decimal point), by connecting identical pins (i.e. pin 1 of the first display with pin 1 of the second, third and forth, and so on. Segment a to g correspond to PB0 to PB6, DP, the decimal point, is connected to PB7.

Four lines of port A are used for multiplexing the four digits, PA0 is connected to the common kathode of the first (leftmost) digit, and so on.

One port A pin (PA4) is still free and unused. It has to be connected to ground, in order to reduce power consumption in power-down mode. In addition, two of the port B pins are connected to a switch (push button), which is connected to ground. There are no pull-up resistors necessary, because some of the port B pins have weak internal pull-up resistors, optionally. Multiplexing and sharing a single pin between driving various leds and sensing the button is done by carefully switching the port B pins between input and output. For example, during the multiplexing, those two port B pins which are connected to the switches too, are made input frequently, in order to enable the pull-ups and to check the switch state. As soon and as long as a closed switch is detected, all pins are held in input state, in order to avoid short-circuiting a driving pin for more than a few ms. This method worked remarkably well. There is one drawback - the display is dark as long as a button is pressed.

HDSP 5503	Bits on Port B	1,65 V, 30 mA (L x B x H): 17,2 x 12,6 x 8 mm 14,2mm
	' Anodes ' ' +--0--+ ' | | ' 5 1 ' | | ' +--6--+ ' | | ' 4 2 ' | | ' +--3--+ (7)

Remarks

Using about 5 V from a 4 cell, 110Ah Nicad battery pack (from a surplus sale), I measure between 25 and 30 mA during operation, and about 2 µA in sleep mode. It was necessary to ground PA4, in order to archive this. (A floating PA4 drives Ipd up to 100 µA and more).  That power consumption amounts to about three hours of continous operation on that battery, or many years of power down mode (theoretically, because it gets empty because self-discharge, much earlier).

For that reason, I didn't consider a power switch necessary. The device goes into power saving mode immediately after the display is darkened. When the left button is pressed, it wakes up again.

Getting the display right required quite a bit of tinkering with the times and the method. Finally, I used a two-level multiplex, where  no more than two segments are lit at the same time.

Cost

Future enhancements

• Automatic power-off after idling for a few minutes.
• Competition mode, where computer and user can change role. Results could be easily stored in the non-volatile EEPROM of the 16F84, which is currently unused. Unfortunately, the 1 K program space is already almost filled up, so the program would have to be reorganized.

Copyright © 1998 by Wolfgang Strobl, all rights reserved.
Personal and educational use granted. Use at your own risk.

98-11-22 Wolfgang Strobl, GMD NET.iT