Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Using Partial Tablebases in Breakthrough Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Nash Equilibrium in Mastermind

Authors : François Bonnet, Simon Viennot

Published in: Computers and Games

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Mastermind is a famous two-player deduction game. A Codemaker chooses a secret code and a Codebreaker tries to guess this secret code in as few guesses as possible, with feedback information after each guess. Many existing works have computed optimal worst-case and average-case strategies of the Codebreaker, assuming that the Codemaker chooses the secret code uniformly at random. However, the Codemaker can freely choose any distribution probability on the secret codes. An optimal strategy in this more general setting is known as a Nash Equilibrium. In this research, we compute such a Nash Equilibrium for all instances of Mastermind up to the most classical instance of 4 pegs and 6 colors, showing that the uniform distribution is not always the best choice for the Codemaker. We also show the direct relation between Nash Equilibrium computations and computations of worst-case and average-case strategies.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Werewolf Game Modeling Using Action Probabilities Based on Play Log Analysis
next chapter 11  11 Domineering Is Solved: The First Player Wins
Appendix
Available only for authorised users
Footnotes
1
The straightforward proof is left to the reader.
 
2
We use (b, w) since the original game use black and white pins to display the grade.
 
3
A unicolor (resp. bicolor) code is a code with both pegs with same (resp. different) color. There are 3 unicolor codes and 6 bicolor codes. Note that \(3\times \frac{1}{6}+6\times \frac{1}{12}=1\).
 
4
This formula is incorrect when \(k=1\) since there exists a single code, hence a single possible grade (n, 0). For \(k=2\) colors, there are also some unreachable grades such as \((b,w)=(0,n)\) when n is odd.
 
5
To compute WC and AVG, it is sufficient to consider only pure strategies. However for NE, it is required to consider also mixed strategies.
 
6
Pure strategies of the Codemaker are trivially computed. There are exactly \(k^n\) pure strategies, one for each possible code.
 
7
Figures 2, 3, 4 and 5 appear only in Appendix A.
 
8
A full description will be given in a longer version of this article.
 
9
Fortunately, \(4\times 0 + 48\times \frac{2}{345} + 36\times \frac{1}{276} + 144\times \frac{1}{276} + 24\times \frac{1}{345}=1\).
 
10
We could not prove yet the uniqueness for instances (5, 3), (4, 5), and (4, 6), but it should be obtained very soon.
 
Literature
1.
Chen, S.T., Lin, S.S.: Optimal algorithms for \(2\times n\) mastermind games-a graph-partition approach. Comput. J. 47, 602–611 (2004)CrossRef
2.
3.
Doerr, B., Sphel, R., Thomas, H., Winzen, C.: Playing mastermind with many colors. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 695–704 (2013)
4.
5.
6.
Goodrich, M.T.: On the algorithmic complexity of the mastermind game with black-peg results. Inform. Process. Lett. 109, 675–678 (2009)MathSciNetCrossRefMATH
7.
Jäger, G., Peczarski, M.: The number of pessimistic guesses in generalized mastermind. Inform. Process. Lett. 109, 635–641 (2009)MathSciNetCrossRefMATH
8.
Jäger, G., Peczarski, M.: The number of pessimistic guesses in generalized black-peg mastermind. Inform. Process. Lett. 111, 933–940 (2011)MathSciNetCrossRefMATH
9.
10.
Koyama, K., Lai, T.: An optimal mastermind strategy. J. Recreational Math. 25, 251–256 (1993)MATH
11.
Nash, J.F.: Non-Cooperative Games. Ph.D. thesis, Princeton University (1950)
12.
13.
14.
Wiener, M.: Re: sci.math faq: Master mind, post in sci.math newsgroups on 29 Nov 1995 at 20: 44: 49
Metadata
Title
Nash Equilibrium in Mastermind
Authors
François Bonnet
Simon Viennot
Copyright Year
2016
Book
Computers and Games

Print ISBN: 978-3-319-50934-1

Electronic ISBN: 978-3-319-50935-8

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-50935-8_11

Premium Partner

    Image Credits