Bulls & Cows Game
9th March 2015
Bulls & Cows is an excellent traditional pencil and paper game of logical deduction [1]. It became popular in the form of a colour peg version called Mastermind, originally marketed by Invicta Plastics, and subsequently by Hasbro. This article describes a pocket Bulls & Cows game, based on an Arduino Uno or ATmega328, which plays Bulls & Cows with you:
Bulls & Cows game guessing my code.
Playing Bulls & Cows
In the pencil and paper version of the game two players begin by each thinking of a code, consisting of four digits. The players then take turns in making inspired guesses at the others player's code. The guesser is given the following information about the guess:
- The number of Bulls; digits correct and in the correct position (bull's-eyes).
- The number of Cows; digits correct but not in the right position.
The first player to guess the other player's code is the winner.
As an example, here's a sample game (the player's code was 2745):
Guess: 1389 - Reply: 0 Bulls, 0 Cows.
Guess: 1234 - Reply: 0 Bulls, 2 Cows.
Guess: 1759 - Reply: 1 Bull, 1 Cow.
Guess: 1785 - Reply: 2 Bulls, 0 Cows.
Guess: 2745 - Reply: 4 Bulls!
Over the years I've written programs to play Bulls & Cows on a variety of different computers, and I thought it would be fun to do one for the Arduino. I implemented it on an ATmega328 on a prototyping board, but it could equally well be run on an Arduino Uno board.
Using the Bulls & Cows program
The Bulls & Cows program not only thinks of a code which you are to guess, but tries simultaneously to guess a code you have thought of.
When the program first runs, press "*" to continue from the "Hello" message.
The program then shows the number of the round, and prompts for you to enter a guess at the computer's code:
----.r1
Enter a four-digit guess, and press "*" to continue. Alternatively if you make a mistake you can press "#" to clear the display and enter the guess again.
The program then reveals the number of Bulls and Cows for your guess, Bulls followed by Cows; for example:
0123.02
Pressing "*" then displays the program's next guess at your number, after a short delay; for example:
2102.--
Enter the reply in the same format, Bulls followed by Cows; for example:
2102.00
Then press "*" to continue to round 2:
----.r2
The game continues until either you guess the computer's code, in which it displays "I LOSE", or it guesses your code, when it displays "Ho-Ho", but allows you to continue trying to guess its code.
Calculating the number of Bulls and Cows
One obvious way of finding the number of Bulls and Cows between two numbers is to make four comparisons between digits in corresponding positions to get the number of Bulls, and then make the remaining 12 comparisons between digits in different positions to get the number of Cows. Digits contributing to Bulls or Cows at any stage must be deleted so they cannot be counted again. The execution time with this method is proportional to the square of the number of digits.
A better method, used in the following program, has an execution time that is only proportional to the number of digits. The method is to keep counters for each of the ten possible digits in an array Spectrum[]. Initially the counters are set to zero. Digits in the two codes are then compared a pair at a time. If the pair matches it is counted as a Bull. If they do not match, the counter for the digit in one code is incremented, and the counter for the digit in the other code is decremented. If incrementing a digit counter gives a negative or zero result, a Cow is recorded because the counter must at some earlier stage have been decremented due to an occurrence of the same digit in the other code. Likewise, if decrementing a digit counter gives a positive or zero result, a Cow is recorded for the same reason.
After the four corresponding pairs of digits have been compared in this way the routine returns with the number of Bulls and Cows:
int BullCow (int a, int b) {
int Spectrum[10];
int cows = 0, bulls = 0;
for (int x=0; x<10; x++) Spectrum[x] = 0;
for (int digit=0; digit<4; digit++) {
int digita = a % 10, digitb = b % 10;
if (digita == digitb) bulls++;
else {
Spectrum[digita]++;
if (Spectrum[digita] <= 0) cows++;
Spectrum[digitb]--;
if (Spectrum[digitb] >= 0) cows++;
}
a = a / 10; b = b / 10;
}
return bulls*10 + cows;
}
Guessing the player's code
The algorithm used by the program to guess the player's code is very simple. The program keeps a list of its previous guesses at the player's code, and the player's replies, in the arrays Guesses[] and Replies[]. At every stage in the game it chooses a new guess which is compatible with all the previous guesses and replies. This new guess is therefore a candidate for the correct answer:
Try = Start;
do {
Try = (Try + 1) % 10000;
Guesses[turn] = Try;
Replies[turn] = 44;
n=-1;
do {
n++;
} while (BullCow(Try, Guesses[n]) == Replies[n]);
} while ((n < turn) && (Try != Start));
Since every guess reduces the number of possibilities, eventually the algorithm arrives at the correct code.
For efficiency it puts the next try at the end of the list of guesses, with the impossible reply "44". If this is the first guess that isn't compatible with the replies we know that all the previous guesses were compatible, and so this is a valid candidate.
If the player has given inconsistent answers to the program's guesses it will, at some stage, be unable to find any guess which is suitable. In that event it displays "Error" and claims a victory.
Here's the whole of the main program that plays Bulls and Cows:
void loop() {
int Guesses[20];
int Replies[20];
int turn, Try, n, YourReply, Result;
randomSeed(millis());
// Start new game - choose a code
int MyCode = random(10000);
int Start = random(10000);
turn = 0;
Try = Start;
YourReply = 0;
Result = 0;
do {
// Start new turn
// Prompt for your guess
if (Result != 40) {
Prompt(turn);
int YourGuess = Read(4);
Result = BullCow(YourGuess, MyCode);
ShowScore(Result);
WaitForGo();
if (Result == 40) ShowMessage(ILose);
}
// Prompt for my guess
if (YourReply != 40) {
// Find guess compatible with all your previous replies
ClearDisplay();
do {
Try = (Try + 1) % 10000;
Guesses[turn] = Try;
Replies[turn] = 44;
n=-1;
do {
n++;
} while (BullCow(Try, Guesses[n]) == Replies[n]);
} while ((n < turn) && (Try != Start));
if (Try == Start) {
ShowMessage(Error);
YourReply = 40;
} else {
Display(Guesses[turn]);
YourReply = Read(2);
Replies[turn] = YourReply;
if (YourReply == 40) ShowMessage(HoHo);
}
}
turn++;
} while (!((Result == 40) && (YourReply == 40)));
}
The program first seeds the random() function from millis(), to ensure a different sequence of numbers each time the program runs. It then proceeds through the turns, first showing the score for the player's guess, and then guessing the player's code.
Multiplexing the display
As in a few of my previous projects, the display is generated under interrupt, using the contents of the array Buffer[]. For example, to display "123456" execute:
Buffer[0]=1; Buffer[1]=2; Buffer[2]=3; Buffer[3]=4; Buffer[4]=5; Buffer[5]=6;
The program uses Timer/Counter1 to generate an interrupt at 250Hz, which is used to multiplex the display. To make it easier to wire up the circuit on the breadboard I connected the segments to arbitrary pins on Port D. The array Segments[] specifies how they are wired, and the routine ReorderBits() then reorders the bits in the segment definitions to account for this:
void ReorderBits() {
char segs, newsegs;
for (int i=0; i<charArrayLen; i++) {
segs = charArray[i];
newsegs = 0;
for (int i=0; i<8; i++) {
newsegs = newsegs | ((segs & 1)<<Segments[i]);
segs = segs >> 1;
}
charArray[i]=newsegs;
}
}
Timer/Counter1 is then configured in setup():
TCCR1A = 0<<WGM10; TCCR1B = 1<<WGM12 | 2<<CS10; // Divide by 8 OCR1A = 499; // Compare match at 250Hz TIMSK1 |= 1<<OCIE1A; // Compare match interrupt enable
The compare match interrupt service routine then simply calls DisplayNextDigit():
ISR (TIMER1_COMPA_vect) {
DisplayNextDigit();
}
This reads the data in the appropriate element of Buffer[] and lights the segments in the corresponding display digit:
void DisplayNextDigit() {
char segs, row;
pinMode(Digits[digit], INPUT);
digitalWrite(Digits[digit], LOW);
digit = (digit+1) % Ndigits;
segs = charArray[Buffer[digit]];
// Decimal points
if ((dp & 1<<digit) != 0) segs = segs | (1<<Segments[7]);
DDRD = 0; // All inputs
PORTD = ~segs; // 1 = low
DDRD = segs; // 1 = output
pinMode(Digits[digit], OUTPUT);
digitalWrite(Digits[digit], HIGH);
// Check keyboard
row = Matrix[PINC & 0x0F];
if (row == 0) Keys[digit] = 0; else Keys[digit] = row + digit;
}
Finally, here's a routine to display a four-digit number on the first four displays:
void Display (int i) {
for (int d=3; d>=0 ; d--) {
Buffer[d]=i % 10;
i = i / 10;
}
dp = 3;
}
Additional routines ShowMessage() and ShowScore() display a message and the Bulls and Cows score respectively.
Reading the keyboard
The 12 keys on the keypad I used are arranged in a 3 x 4 matrix. The columns are connected to the same I/O lines that drive display digits 0 to 2, and the rows are connected to bits 0 to 3 of PORT C. The state of each column is read during the display multiplexing by the DisplayNextDigit() routine, and put into the corresponding element of the array Keys[].
The routine Read(4) reads a four-digit code, or Read(2) reads a two-digit reply from the keyboard, and in each case displays it on the appropriate display digits:
int Read (int length) {
int key, first;
if (length == 4) first = 0; else first = 4;
int last = first + length;
do {
int d = first, result = 0;
for (int d=first; d<last ; d++) Buffer[d]= Dash;
// Read next key
do {
do ; while (Key() == 0);
key = Key();
do ; while (Key() != 0);
// Return on *
if (key == 10) { if (d == last) return result; }
// Enter digit
else if ((key <= 11) & (d < last)) {
if (key == 11) key = 0;
Buffer[d] = key;
result = result*10 + key;
d++;
}
// # clears display
} while (key != 12);
} while (1);
}
The Read() routine also handles the "*" and "#" keys.
The circuit
To keep the project as cheap as possible I used a standard 12-key keypad, available from SparkFun [2] or HobbyTronics in the UK [3], and two 0.28" 3-digit 7-segment LED displays, bought on eBay from a supplier in Shenzhen for £1.30 for five!
Here's the whole circuit, roughly reflecting the way it was laid out on the breadboards:
Circuit of the Bulls & Cows game based on an ATmega328.
Hardware
The Bulls & Cows Game was built on three mini breadboards clipped together; these are available from SparkFun [4] or HobbyTronics in the UK [5]. Here's a photograph with the keypad removed to show the wiring to the processor:
Layout of the Bulls & Cows Game on three mini breadboards.
I used an ATmega328 chip with the default fuse settings, which gives an internal 1MHz clock and avoids the need for a crystal. I uploaded the program to the ATmega328 using Sparkfun's Tiny AVR Programmer [6] (available in the UK from Proto-PIC [7]), using the ATmega328p (internal 1MHz clock) option on the Boards menu. The circuit was powered from a 50mAH rechargeable lithium battery; I use the HobbyTronics LiPo charger [8] to charge it.
Here's the whole program for the Bulls & Cows Game: Bulls & Cows Program.
Addenda
12th March 2015: I've added some minor improvements.
31st March 2015: For an improved version see Bulls & Cows Game 2.
- ^ Number Bulls & Cows on Pencil and Paper Games.
- ^ Keypad - 12 Button on SparkFun.
- ^ Matrixed Data Keypad 3 x 4 on HobbyTronics.
- ^ Breadboard - Mini Modular on SparkFun.
- ^ Mini Breadboard on HobbyTronics.
- ^ Tiny AVR Programmer on Sparkfun.
- ^ Tiny AVR Programmer on Proto-PIC.
- ^ USB LiPo Battery Charger from HobbyTronics
blog comments powered by Disqus