Design Project in C++

Mastermind– A Game for Two Players

The best way to completely internalize all the ideas in this text, and to learn to think in the object oriented paradigm, is to find a really fun project that you are motivated to complete, to design the classes and to write the program.

In this section, we include a project that is based on a game called Mastermind. It is fun to play and does not involve any data structures more advanced than structs and arrays. There is ample opportunity to consider the details and design of the appropriate classes. Most important, when you are finished, you will have a fun program that can play the game better than most human opponents.

The Game

Mastermind is a game for two players. Each one chooses a secret code of four colors. Each color can be chosen from a set of six colors: (Red, Green, Blue, Yellow, Black, White). One may choose duplicate colors. The goal of the game is for each player to guess the other players secret code.

In order to guess the other player’s secret code, a player presents a four color code to his opponent. The opponent must respond by telling the first player:

  1. The number ofexact matches between the guess and his secret code, and
  2. The number of inexact matchesbetween the guess and his secret code.

An exact match means the codes match color and position. An inexact match means that thecodes match color but they are not in the correct position. No match is counted twice and exact matches take precedence over inexact matches, (hence the total exact and inexact matches on any guess is between zero and four.

For example: Say the secret code is (Red, Red, Green, White), then the match responses for the following guesses are shown below:

(Red, Blue, Black, Green)1 Exact 1 Inexact

(Red, Red, Red, Black)2 Exact 0 Inexact

(Green, Red, Red, White)2 Exact 2 Inexact

(Black, Yellow, Red, Green)0 Exact 2 Inexact

The players alternate making guesses and giving responses until one ofthem guesses the other’s secret code.

The Project

The project is to design a program in C++ to allow the computer play this game against the user. There are many design issues to consider. We will make a few suggestions on the more difficult problems, but otherwise we leave the design to the reader.

1. What classes should be defined?

A natural class to define is one called CODE, which stores a particular four color code in a particular order, and allows us at least to:

  1. Print out the code,
  2. Create a code from four colors,
  3. Compare the code to anothercode and return the exact and inexact matches, and
  4. Create a code based on an integer from 0 to 1295. (The need for this will not be obvious at first. For now, accept that it will be used in the computer’s strategy.) Note that there are 64 = 1296 four-color codes and each one can be identified with an integer from 0 to 1295. If we assign the colors Red, Green, Blue, Yellow, Black and Whiteto the numbers 0 through 5, then the integer x can be converted to a four-color code by first converting it to base 6. For example, the integer 123 is 0323 in base 6, which corresponds to the code (Red, Yellow, Blue, Yellow). The rightmost color is the one assigned to x%6, the color to the left of this is the one assigned to ((x-x%6)/6)%6, and so on.
  1. What strategy should the computer use?

Most people use an ill-defined intuitive approach to deciding on the next guess. Many try to identify the code piece by piece, sometimes guessing codes they know cannot be correct, only to obtain moreinformation about what might be correct. This approach can be effective and is by no means a bad strategy. However by the very nature of the approach, it is impossible to simulate on a computer! A strategy that is well suited to a computer, but not so well suited to a human being is described below. It gets the correct answeralmost all the time in 6 guesses or less, and often in 5 guesses or less. This beats all but the best and luckiest players.

The first guess of the computer will be chosen randomly, (a number from 0 to 1295 can be chosen, and converted to a code). After this guess, all subsequent guesses will be carefully planned. The principle of the computer’s strategy is to keep track of precisely which codes remain consistent with all the information it has received so far. That is, it will never choose a guess unless that guess has a chance of beingthecorrect one. (The machine’s first guess clearly sticks to this principle!) How does the machine continue?

Let’s say thatafter the machine’s first guess, it received a response of 1 Exact match and 1 Inexact match. Then the only codes that still have a chance to be the secret code, are those which match up 1 Exact and 1 Inexact, with the first guess. All other codes should be eliminated forever. The computer will generate all the codes and test each against its first guess. If a code matches 1-1 with the first guess, then it will remember (in a Boolean array of size 1296) that the code is still a possible candidate for the secret code. If the code does not match 1-1 with the first guess, then that code should be ruled out. The array of codes should be initializedto 0 (possible candidate), and each code’s slot is set to 1 when that code is ruled out. After this is complete, the computer randomly chooses any of the codes still marked 0 for its second guess.

When the response to the second guess comes back (say it is 2-1), the computer checks all remaining possible candidate codes to see if they match up 2-1 with the second guess. If not, then those codes are subsequently ruled out as possible candidates.

Each new guess, therefore, is consistent with all the information obtained up until that point in the game. It is hard for humans to play this way, but let’s try for the sake of experiment and an example. (Remember justto use the computer’s algorithm, and NOT to reason intuitively).

Guess ExactInexact

(Red, Red, Green, White)20

The next guess must match 2-0 with the first guess.

(Red, Red, Black, Yellow)11

The next guess must match 2-0 with the first guess and 1-1 with the second guess.

(Red, Yellow, Green, Blue)03

The next guess must match 2-0 with the first guess, 1-1 with the second guess and 0-3 with the third guess.

(Blue, Red, Yellow, White)22

Now it tends to get hard, because there are often no more than a couple of candidate codes left. We leave the last guess to the reader. Do you think your guess is the only one possible? Your program KNOWS the answer to this question.