Using information theory to solve Mastermind

Summary

How you've just played optimal Mastermind Mastermind is a game all about information. The Code Master selects one of \( 6^4 = 1\,296 \) secret codes. Each incorrect guess gives us information by eliminating some of these; the more codes that are ruled out, the more information that guess has provided. Let's quantify this insight! Suppose a guess gets some response that reduces the number of possible keys from some number \(n\) to a smaller \(n'<n\). The convention in information theory, a branch of mathematics and computer science dealing with just this type of question, is to define the information \(I\) provided by this guess and response as \[ I := \log_2 \frac{n}{n'}. \] The unit of information (with respect to the base-2 logarithm; other bases can be used) is called bits. One bit of information corresponds to reducing the number of possible keys by half; a guess-response pair providing two bits of information reduces it by \( (1/2)^2 = 1/4 \). There are good theoretical reasons for adopting this admittedly unintuitive apparatus. For our purposes it is enough to note that information is additive. If a first guess provides one bit of information, and a second two bits, the number of possible codes has been reduced by \( 1/2 \times 1/4 = 1/8\); in total the two guesses have provided \( 1 + 2 = 3\) bits of information! We can now come up with a simple strategy for playing Mastermind: always make that guess which provides the most information. But we don't know the information of a guess in advance, since it depends on which response the Code Master will give us, and therefore on what the true secret code is. Let's suppose that the Code Master selects a secret code uniformly at random, with no code being more likely than any other; this is in fact what the program does under the hood. We then want to make the guess which provides the most information on average. The probability of getting a certain response to a guess is \( n' / n \), since this is exactly the propo...