Mastermind

Mastermind is a code-breaking game where one player (or the computer) sets a secret code — a sequence of colored pegs — and the other player tries to guess it within a limited number of attempts. After each guess, the codemaker provides feedback indicating how many pegs are the correct color in the correct position (black pegs) and how many are the correct color but in the wrong position (white pegs). The classic version uses 4 positions and 6 colors, allowing 10-12 guesses.

Rules

1. The codemaker creates a secret code of 4 colored pegs, chosen from 6 possible colors. Duplicate colors are allowed.
2. The codebreaker makes a guess by placing 4 colored pegs in a row.
3. The codemaker responds with feedback pegs:

• Black peg: One peg is the correct color in the correct position.
• White peg: One peg is the correct color but in the wrong position.

1. Each color in the guess is matched at most once: exact matches (black) take priority over color matches (white).
2. The codebreaker uses the feedback to refine subsequent guesses.
3. The game ends when the code is guessed correctly or the maximum number of guesses is exhausted.

Strategies

• Knuth's Algorithm: In 1977, Donald Knuth proved that the classic 4-peg, 6-color Mastermind can always be solved in at most 5 guesses. His minimax algorithm starts with the guess (1, 1, 2, 3) and chooses each subsequent guess to minimize the worst-case number of remaining possibilities.
• First Guess Optimization: Start with a guess containing two pairs of colors (e.g., AABB). This provides maximum information about which colors are present.
• Track Eliminated Codes: After each feedback, mentally or physically eliminate all codes inconsistent with the feedback received so far. Your next guess should be consistent with all previous feedback.
• Information Maximization: Choose guesses that divide the remaining possibilities into groups as equal in size as possible. The guess that creates the most even split provides the most information regardless of the feedback.
• Color Counting: Use early guesses to determine which colors appear in the code and how many times. Once you know the color composition, focus on finding the correct arrangement.
• Process of Elimination: If a guess receives 0 black, 0 white feedback, none of those colors appear in the code. This can dramatically narrow the search space.

Mastermind was invented in 1970 by Mordecai Meirowitz, an Israeli postmaster and telecommunications expert. After being rejected by several toy companies, the game was eventually manufactured and distributed by Invicta Plastics, a small British company based in Leicester, England. The game was released in 1971 and became an international sensation, selling over 50 million copies in its first decade.

The game's design was influenced by an older pencil-and-paper game called "Bulls and Cows" (also known as "Moo"), which dates back at least to the early 20th century. In Bulls and Cows, players guess a secret number, receiving feedback about correct digits in correct positions ("bulls") and correct digits in wrong positions ("cows"). Meirowitz's innovation was to transform this abstract number game into a visually appealing board game with colored pegs, making it accessible to a broader audience.

Mastermind attracted significant attention from mathematicians and computer scientists. In 1977, Donald Knuth published a landmark paper demonstrating that the codebreaker can always determine the code in at most five guesses using a minimax strategy. This analysis connected the game to information theory, combinatorics, and algorithm design. The problem of optimal Mastermind strategy has since been studied extensively, with variants involving different numbers of pegs and colors analyzed for their computational complexity — in fact, Mastermind with an arbitrary number of pegs and colors was proven to be NP-complete in 2005.

The game has spawned numerous variants, including Super Mastermind (5 pegs, 8 colors), Grand Mastermind (5 pegs with pattern shapes), and electronic versions. It has also influenced game design more broadly, with the Mastermind mechanic appearing in video games such as "Fallout" (terminal hacking) and the mobile game "Wordle" (which applies a similar feedback mechanism to word guessing). Mastermind remains a staple of logic game collections and a popular introduction to combinatorial reasoning.