Mastermind, invented by Mordecai Meirowitz and first published by Invicta Plastics in 1970, is a code-breaking game that sits at the intersection of combinatorics, information theory, and algorithmic strategy. The standard game involves a secret code of 4 positions chosen from 6 colors (with repetition allowed), giving 6^4 = 1,296 possible codes. The codebreaker receives feedback after each guess in the form of black pegs (correct color in correct position) and white pegs (correct color in wrong position), and must deduce the secret code in as few guesses as possible.

The most famous contribution to Mastermind strategy comes from Donald Knuth, one of the most influential computer scientists in history. In his 1977 paper "The Computer as Master Mind," Knuth proved that the secret code can always be determined in at most five guesses using a minimax strategy. His algorithm works by selecting the guess that minimizes the maximum number of remaining possibilities across all possible feedback responses. The first guess in Knuth's strategy is always 1122 (two pairs of colors), which is provably optimal for worst-case performance. After receiving feedback, the algorithm eliminates all codes inconsistent with that feedback, then selects the next guess that minimizes the worst-case remaining set.

From a combinatorial perspective, Mastermind is a constraint satisfaction problem. Each guess-feedback pair eliminates a portion of the 1,296 possible codes. A black peg tells you that a specific color is in a specific position; a white peg tells you a color is present but misplaced; and the absence of pegs tells you certain colors are not in the code at all. The feedback partitions the remaining possibilities into equivalence classes, and the optimal strategy is to choose guesses that create the most balanced partition, maximizing the expected information gain per guess.

The information-theoretic approach to Mastermind treats each guess as a question and each possible feedback as an answer. With 4 positions, there are 14 possible feedback combinations (from 0 black 0 white to 4 black 0 white). An ideal guess would distribute the remaining possibilities as evenly as possible across these 14 partitions, maximizing the entropy (information content) of the feedback. This entropy-maximizing strategy, while not identical to Knuth's minimax approach, achieves an average of about 4.34 guesses to solve, compared to Knuth's 4.48 average. The tradeoff is that the entropy approach optimizes average performance while Knuth's optimizes worst-case performance.

Mastermind has also inspired significant research in computational complexity theory. The general version of the game with n positions and k colors has been shown to be NP-hard to solve optimally, meaning that as the game scales up, finding the optimal strategy becomes computationally intractable. This connects Mastermind to fundamental questions about the limits of efficient computation and the P versus NP problem.