CS 269S, Spring 2013: Theory Seminar
Bren Hall, Room 1420, 1pm
May 31, 2013:

Playing Mastermind with Many Colors

Alexander Nicholas Brown

We analyze the general version of the classic guessing game Mastermind with n positions and k colors. Since the case k ≤ n1 − ε, ε > 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 n2 log log n colors. These bounds are almost tight as the known lower bound of Ω(n) shows. Unlike for k ≤ n1 − ε, 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.

(Based on a paper by Benjamin Doerr, Carola Doerr, Reto Spöhel, and Henning Thomas from SODA 2013.)