Mastermind

Most of you have played Mastermind, where a selection of 4 coloured pegs is hidden behind a shield, and the “mastermind” demonstrates his abilities by using logic and guesswork to match the sequence and colour of the pegs behind the shield.

Task 1

Write a computer program to allow a human to test his mastermind against the computer.

For a more advanced task, the algorithm below gives advice on how to get the computer to play the game.

To efficiently win at Mastermind consider the following facts.

• There are four peg positions and 6 colour choices for each position.  This gives 6 X 6 X 6 X 6 possible colour/position combinations, or 1276.
  
• The score for each guess can be written as two numbers between 0 and 4.  Let’s write a score of a guess, G, against a pattern, P, as S(G,P) = [R, W].  R is the number of pegs in G which match pattern P in colour and location (the red pegs).  W is the number of pegs in G that match P in colour, but are in the wrong position (the white pegs).
  
• There are 5 possible values for R (0 to 4) and for W.  This gives 5 X 5 or 25 possible score combinations. Of these, only 14 are valid.  The sum of R and W must be less than or equal to 4, since each peg represents at most one peg in the score, which eliminates 10 scores.  Also, score [3,1] is impossible.  Why?
  
• Thus, the set of 1276 possible peg arrangements id divided into 14 groups, based on their score compared to the given pattern.
  
• Scores are commutative.  i.e. S(G, P) = S(P, G) .  Therefore, the next guess must come from another pattern in the same score group.  This will be at least as good as the last guess, but also possibly a better guess.  In this way, you eliminate many combinations that cannot lead you to a solution.
  

  For example, Assume the secret pattern is BBBB (4 blues).  The previous guess was BGGB, or blue, green, green, blue.  This would score [2, 0].  Combinations in this group include YGGY, BGRR, GGGG, etc and also, BBBB.  Thus the next guess may be BGRR, and the score is [2,0].  But if we’d guessed BGBG…

The algorithm to win at Mastermind is:

1. Make a first guess with 2 pegs of one colour and 2 of another.  This seems to give the best head start.
   

While guess G does not match pattern P do

1. “Guess” a combination with at least the same score, and that is not the same as a previous guess.
   

Extension

There is one further enhancement that can be made.  Since each guess divides the possible solutions into groups, it is best to make these groups as similar in size as possible.  If we record the largest if the 14 subsets for each guess and then pick the guess that has the smallest “largest subset”, we can improve our results slightly on average over just choosing random

Credit Blundell@MonktonCoombe

IMAGE CREDIT: https://en.wikipedia.org/wiki/Mastermind_(board_game)