MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Doerr, Benjamin
Spöhel, Reto
Thomas, Henning
Winzen, Carola
dblp
dblp
dblp
dblp
Not MPG Author(s):
Thomas, Henning
Editor(s):
BibTeX cite key*:
DoerrSTW13
Title, Booktitle
Title*:
Playing Mastermind with many colors
Booktitle*:
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)
Event, URLs
Conference URL::
http://www.siam.org/meetings/da13/
Downloading URL:
Event Address*:
New Orleans, USA
Language:
English
Event Date*
(no longer used):
Organization:
ACM-SIAM
Event Start Date:
5 January 2013
Event End Date:
8 January 2013
Publisher
Name*:
SIAM
URL:
http://www.siam.org/
Address*:
Philadelphia, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
695-704
Year*:
2013
VG Wort Pages:
38
ISBN/ISSN:
9781627484855
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We analyze the general version of the classic guessing game Mastermind with $n$~positions and $k$~colors. Since the case $k \le n^{1-\eps}$, $\eps>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\'atal (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^2 \log\log n$ colors. These bounds are almost tight as the known lower bound of $\Omega(n)$ shows. Unlike for $k \le n^{1-\eps}$, 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 $\Omega(n \log n)$ guesses.
Personal Comments:
VGWort pages by Benjamin
Download
Access Level:
Internal

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
popular
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{DoerrSTW13,
AUTHOR = {Doerr, Benjamin and Sp{\"o}hel, Reto and Thomas, Henning and Winzen, Carola},
TITLE = {Playing Mastermind with many colors},
BOOKTITLE = {Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)},
PUBLISHER = {SIAM},
YEAR = {2013},
ORGANIZATION = {ACM-SIAM},
PAGES = {695--704},
ADDRESS = {New Orleans, USA},
ISBN = {9781627484855},
}


Entry last modified by Benjamin Doerr, 02/17/2014
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
12/07/2012 01:06:01 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Benjamin Doerr
Benjamin Doerr
Stephanie Müller
Carola Winzen
Carola Winzen
Edit Dates
01/31/2014 12:29:23 AM
01/01/2014 10:56:50 PM
04.02.2013 14:07:32
01/15/2013 11:24:47 AM
01/11/2013 01:37:20 PM