Dr. Carola Winzen
MPI Informatik, Saarbrücken

Playing mastermind with many colors

We consider the generalized version of the classic board game Mastermind with k colors and n positions. It has been known for a long time that for any constant number k of colors, there exist winning-strategies using at most Theta(n/log n) queries. This bound is tight. In this talk, we study the black-peg version of Mastermind with k=n colors. We present a winning strategy that uses only O(n loglog n) guesses for identifying the secret code. This improves the previously best known bounds of Chvatal (Combinatorica, 1983), Goodrich (Information Processing Letters, 2009), and others, which are all of order n log n; both for black-peg and the original Mastermind game. This is joint work with Benjamin Doerr (Max Planck Institute for Informatics), Reto Spoehel (MPI Informatics), and Henning Thomas (ETH Zuerich) and will appear at SODA'13.