Playing mastermind with many colors

We analyze the general version of the classic guessing game Mastermind with n positions and k colors. Since the case k ≤ n^1-ε, ε > 0 constant, is well understood, we concentrate on larger numbers of colors. For the most prominent case k = n, our results imply that Codebreaker can find the secret code with O(n log log n) guesses. This bound is valid also when only black answer-pegs are used. It improves the O(n log n) bound first proven by Chvátal (Combinatorica 3 (1983), 325-329). We also show that if both black and white answer-pegs are used, then the O(n log log n) bound holds for up to n² log log n colors. These bounds are almost tight as the known lower bound of Ω(n) shows. Unlike for k ≤ n^1-ε, simply guessing at random until the secret code is determined is not sufficient. In fact, we show that any non-adaptive strategy needs an expected number of Ω(n log n) guesses.