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 13:06:01
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