Mastermind (board game)

Mastermind or Master Mind (Hebrew: בול פגיעה, romanized: bul pgi'a) is a code-breaking game for two players invented in Israel.[1][2] It resembles an earlier pencil and paper game called Bulls and Cows that may date back a century.

Mastermind
A completed game of Mastermind
DesignersMordecai Meirowitz
Years active1970 to present
GenresBoard game
Paper & pencil game [root]
Players2
Setup time< 5 minutes
Playing time10–30 minutes
ChanceNegligible
Age range8 and up

History
Invicta Electronic Master Mind game

Mastermind was invented in 1970 by Mordecai Meirowitz, an Israeli postmaster and telecommunications expert. After presenting the idea to major toy companies and showing it at the Nuremberg International Toy Fair, it was picked up by a plastics company, Invicta Plastics, based near Leicester, UK. Invicta purchased all the rights to the game and the founder, Edward Jones-Fenleigh, refined the game further. It was released in 1971–2.[1][2][3]

The game is based on a paper-based game called Bulls and Cows. A computer adaptation was run in the 1960s on Cambridge University’s Titan computer system, where it was called 'MOO'. This version was written by Frank King. There was also another version for the TSS/8 time sharing system, written by J.S. Felton and finally a version for the Multics system at MIT by Jerrold Grochow.[4]

Since 1971, the rights to Mastermind have been held by Invicta Plastics. (Invicta always named the game Master Mind.) They originally manufactured it themselves, though they have since licensed its manufacture to Hasbro worldwide, with the exception of Pressman Toys and Orda Industries who have the manufacturing rights to the United States and Israel, respectively.[5] Chieftain Products acquired the rights to manufacture in Canada in 1972, they went out of business in 1996.

Starting in 1973, the game box featured a photograph of a man in a suit jacket seated in the foreground, with a young Asian woman standing behind him. The two amateur models (Bill Woodward and Cecilia Fung) reunited in June 2003 to pose for another publicity photo.[6]

Gameplay and rules

The game is played using:

  • a decoding board, with a shield at one end covering a row of four large holes, and twelve (or ten, or eight, or six) additional rows containing four large holes next to a set of four small holes;
  • code pegs of six different colors (or more; see Variations below), with round heads, which will be placed in the large holes on the board; and
  • key pegs, some colored (red in the image, though often black) and some white, which are flat-headed and smaller than the code pegs; they will be placed in the small holes on the board.

The two players decide in advance how many games they will play, which must be an even number. One player becomes the codemaker, the other the codebreaker.[7]: 120  The codemaker chooses a pattern of four code pegs. Players decide in advance whether duplicates and blanks are allowed. If so, the codemaker may even choose four same-colored code pegs or four blanks. If blanks are not allowed in the code, the codebreaker may not use blanks in their guesses. The codemaker places the chosen pattern in the four holes covered by the shield, visible to the codemaker but not to the codebreaker.[8]

The codebreaker tries to guess the pattern, in both order and color, within eight to twelve turns. Each guess is made by placing a row of code pegs on the decoding board.[7]: 120  Once placed, the codemaker provides feedback by placing from zero to four key pegs in the small holes of the row with the guess. A colored key peg is placed for each code peg from the guess which is correct in both color and position. A white key peg indicates the existence of a correct color code peg placed in the wrong position.[9]

Screenshot of software implementation (ColorCode) illustrating the example.

If there are duplicate colors in the guess, they cannot all be awarded a key peg unless they correspond to the same number of duplicate colors in the hidden code. For example, if the hidden code is red-red-blue-blue and the player guesses red-red-red-blue, the codemaker will award two colored key pegs for the two correct reds, nothing for the third red as there is not a third red in the code, and a colored key peg for the blue. No indication is given of the fact that the code also includes a second blue.[10]

Once feedback is provided, another guess is made; guesses and feedback continue to alternate until either the codebreaker guesses correctly, or all rows on the decoding board are full.

Traditionally, players can only earn points when playing as the codemaker. The codemaker gets one point for each guess the codebreaker makes. An extra point is earned by the codemaker if the codebreaker is unable to guess the exact pattern within the given number of turns. (An alternative is to score based on the number of key pegs placed.) The winner is the one who has the most points after the agreed-upon number of games are played.

Other rules may be specified.[11]

Algorithms and strategies

Before asking for a best strategy of the codebreaker one has to define what is the meaning of "best": The minimal number of moves can be analyzed under the conditions of worst and average case and in the sense of a minimax value of a zero-sum game in game theory.

Best strategies with four holes and six colors

With four holes and six colors, there are 64 = 1,296 different patterns (allowing duplicate colors but not blanks).

Worst case: Five-guess algorithm

In 1977, Donald Knuth demonstrated that the codebreaker can solve the pattern in five moves or fewer, using an algorithm that progressively reduces the number of possible patterns.[12] Described using the numbers 1–6 to represent the 6 colors of the code pegs, the algorithm works as follows:

  1. Create the set S of 1,296 possible codes {1111, 1112, ... 6665, 6666}.
  2. Start with initial guess 1122. (Knuth gives examples showing that this algorithm using first guesses other than "two pair"; such as 1111, 1112, 1123, or 1234; does not win in five tries on every code.)
  3. Play the guess to get a response of colored and white key pegs.
  4. If the response is four colored key pegs, the game is won, the algorithm terminates.
  5. Otherwise, remove from S any code that would not give the same response of colored and white pegs.
  6. The next guess is chosen by the minimax technique, which chooses a guess that has the least worst response score. In this case, a response to a guess is some number of colored and white key pegs, and the score of such a response is defined to be the number of codes in S that are still possible even after the response is known. The score of a guess is pessimistically defined to be the worst (maximum) of all its response scores. From the set of guesses with the best (minimum) guess score, select one as the next guess, choosing a code from S whenever possible. (Within these constraints, Knuth follows the convention of choosing the guess with the least numeric value; e.g., 2345 is lower than 3456. Knuth also gives an example showing that in some cases no code from S will be among the best scoring guesses and thus the guess cannot win on the next turn, yet will be necessary to assure a win in five.)
  7. Repeat from step 3.

Average case

Subsequent mathematicians have been finding various algorithms that reduce the average number of turns needed to solve the pattern: in 1993, Kenji Koyama and Tony W. Lai performed an exhaustive depth-first search showing that the optimal method for solving a random code could achieve an average of 5,625/1,296 = 4.3403 turns to solve, with a worst-case scenario of six turns.[13]

Minimax value of game theory

The minimax value in the sense of game theory is 5,600/1,290 = 4.3411. The minimax strategy of the codemaker consists in a uniformly distributed selection of one of the 1,290 patterns with two or more colors.[14]

Genetic algorithm

A new algorithm with an embedded genetic algorithm, where a large set of eligible codes is collected throughout the different generations. The quality of each of these codes is determined based on a comparison with a selection of elements of the eligible set.[15][16] This algorithm is based on a heuristic that assigns a score to each eligible combination based on its probability of actually being the hidden combination. Since this combination is not known, the score is based on characteristics of the set of eligible solutions or the sample of them found by the evolutionary algorithm.

The algorithm works as follows, with P = length of the solution used in the game, X1 = exact matches ("red pins") and Y1 = near matches ("white pins"):

  1. Set i = 1
  2. Play fixed initial guess G1
  3. Get the response X1 and Y1
  4. Repeat while Xi ≠ P:
    1. Increment i
    2. Set Ei = ∅ and h = 1
    3. Initialize population
    4. Repeat while h ≤ maxgen and |Ei| ≤ maxsize:
      1. Generate new population using crossover, mutation, inversion and permutation
      2. Calculate fitness
      3. Add eligible combinations to Ei
      4. Increment h
    5. Play guess Gi which belongs to Ei
    6. Get response Xi and Yi

Complexity and the satisfiability problem

In November 2004, Michiel de Bondt proved that solving a Mastermind board is an NP-complete problem when played with n pegs per row and two colors, by showing how to represent any one-in-three 3SAT problem in it. He also showed the same for Consistent Mastermind (playing the game so that every guess is a candidate for the secret code that is consistent with the hints in the previous guesses).[17]

The Mastermind satisfiability problem is a decision problem that asks, "Given a set of guesses and the number of colored and white key pegs scored for each guess, is there at least one secret pattern that generates those exact scores?" (If not, then the codemaker must have incorrectly scored at least one guess.) In December 2005, Jeff Stuckman and Guo-Qiang Zhang showed in an arXiv article that the Mastermind satisfiability problem is NP-complete.[18]

Variations

Varying the number of colors and the number of holes results in a spectrum of Mastermind games of different levels of difficulty. Another common variation is to support different numbers of players taking on the roles of codemaker and codebreaker. The following are some examples of Mastermind games produced by Invicta, Parker Brothers, Pressman, Hasbro, and other game manufacturers:

GameYearColorsHolesComments
Mastermind 1972 6 4 Original version
Bagels[19] 1972 10 digits 3 Also played as a word game with 2- or 3-digit numbers
Royale Mastermind 1972 5 colors × 5 shapes 3
Mastermind44 1972 6 5 For four players
Grand Mastermind 1974 5 colors × 5 shapes 4
Super Mastermind (a.k.a. Deluxe Mastermind; a.k.a. Advanced Mastermind) 1972[20] 8 5
Word Mastermind 1975[lower-alpha 1] 26 letters 4 Only valid words may be used as the pattern and guessed each turn.
Mini Mastermind 1976 6 4 Travel-sized version; room for only six guesses
Number Mastermind 1976 6 digits 4 Uses numbers instead of colors. The codemaker may optionally give, as an extra clue, the sum of the digits.
Electronic Mastermind (Invicta) 1977 10 digits 3, 4, or 5 Uses numbers instead of colors. Handheld electronic version. Solo or multiple players vs. the computer. Invicta branded.
Super-Sonic Electronic Mastermind (Invicta) 1979 10 digits 3, 4, 5, or 6 Identical gameplay to the 1977 Electronic Mastermind. Super-Sonic version adds a sixth digit to potential codes. Gives an audible signal when the correct code is tried, or the code is revealed via the Fail key. Displays the length of time to reach a solution.
Walt Disney Mastermind 1978 5 3 Uses Disney characters instead of colors
Mini Mastermind (a.k.a. Travel Mastermind) 1988 6 4 Travel-sized version; room for only six guesses
Mastermind Challenge 1993 8 5 Both players simultaneously play code maker and code breaker.
Parker Mastermind 1993 8 4
Mastermind for Kids 1996 6 3 Animal theme
Mastermind Secret Search 1997 26 letters 3-6 Valid words only; clues are provided letter-by-letter using up/down arrows for earlier/later in the alphabet.
Electronic Hand-Held Mastermind (Hasbro) 1997 6 4 Handheld electronic version. Hasbro.
New Mastermind 2004 8 4 For up to five players
Mini Mastermind 2004 6 4 Travel-sized self-contained version; room for only eight guesses

There was also a version called Super Code produced in East Germany by VEB Plasticart.

The difficulty level of any of the above can be increased by treating “empty” as an additional color or decreased by requiring only that the code's colors be guessed, independent of position. In Mini Mastermind the colored code pegs are the same size and shape as the colored or white key pegs so the difficulty can be increased by permitting the key pegs to be used as code pegs for two additional colors.

Computer and Internet versions of the game have also been made, sometimes with variations in the number and type of pieces involved and often under different names to avoid trademark infringement. Mastermind can also be played with paper and pencil. There is a numeral variety of the Mastermind in which a 4-digit number is guessed.[22] The 2021 web game Wordle has been compared to Mastermind.[23]

The game was included in the compilation party video game Clubhouse Games: 51 Worldwide Classics for the Nintendo Switch under the name "Hit & Blow".[24]

Reviews

See also

Explanatory notes
  1. Adapted for the ZX81 home computer by Vortex Software in 1981.[21]

References
  1. Nelson, Toby (9 March 2000). "A Brief History of the Master MindTM Board Game". Archived from the original on 6 September 2015. Retrieved 6 August 2014.{{cite web}}: CS1 maint: unfit URL (link)
  2. "Mastermind Board Game". Board Game Geek. Retrieved 6 August 2014.
  3. "Invicta Toys and Games". 12 August 2007. Archived from the original on 12 August 2007. Retrieved 26 December 2017.
  4. Francis, John (January 2010). "Strategies for playing MOO, or 'Bulls and Cows'" (PDF). Archived from the original (PDF) on 25 April 2012. Retrieved 26 December 2017.
  5. "Invicta Toy History page". Archived from the original on 12 August 2007. Retrieved 7 August 2012.
  6. "Landmark Reunion for Mastermind Box Models". Invicta Plastics. June 2003. Archived from the original on 29 June 2004.
  7. Fullerton, Tracy (2008). Game design workshop (2 ed.). Morgan Kaufmann Publishers. ISBN 978-0-240-80974-8.
  8. "Industrious". Retrieved 7 July 2014.
  9. "Wolfram". Retrieved 9 July 2012.
  10. "Archimedes". Retrieved 7 October 2012.
  11. "Bulls and Cows & co". Retrieved 7 July 2012.
  12. Knuth, Donald (1976–1977). "The Computer as Master Mind" (PDF). J. Recr. Math. (9): 1–6. Archived (PDF) from the original on 4 March 2016.
  13. Koyama, Kenji; Lai, Tony (1993). "An Optimal Mastermind Strategy". Journal of Recreational Mathematics (25): 230–256.
  14. Knuth, Donald (2011). Selected papers on fun and games. Center for the Study of Language and Information. p. 226. ISBN 9781575865843.
  15. Berghman, Lotte (2007–2008). "Efficient solutions for Mastermind using genetic algorithms" (PDF). K.U.Leuven (1): 1–15. Archived from the original (PDF) on 9 September 2014.
  16. Merelo J.J.; Mora A.M.; Cotta C.; Fernández-Leiva A.J. (2013). Nicosia, G.; Pardalos, P. (eds.). Finding an Evolutionary Solution to the Game of Mastermind with Good Scaling Behavior. Springer. pp. 288–293. doi:10.1007/978-3-642-44973-4_31. ISBN 978-3-642-44973-4. Retrieved 22 December 2021.
  17. De Bondt, Michiel C. (November 2004), NP-completeness of Master Mind and Minesweeper, Radboud University Nijmegen
  18. Zhang, Guo-Qiang; Stuckman, Geoff (13 December 2005). "Mastermind is NP-Complete". arXiv:cs.CC/0512049.
  19. "Bagels (1972)".
  20. In Poland - Copyright Invicta 1972 in cooperation with Krajowa Agencja Wydawnicza "BoardGameGeek". boardgamegeek.com.
  21. "Vortex Software – Company". The Centre for Computing History. 26 February 2018.
  22. "Bulls and Cows Classic". Archived from the original on 22 July 2011.
  23. Pisani, Joseph (31 January 2022). "Wordle Has People Digging Out Old Games. Mastermind or Jotto, Anyone?". The Wall Street Journal. Dow Jones & Company, Inc. Retrieved 19 February 2023. Jan. 31, 2022 9:00 am ET Wordle fans are returning to childhood games including Mastermind, which tests players' logic skills using color codes, similar to what Wordle does with words and letters.
  24. "Nintendo Shares A Handy Infographic Featuring All 51 Worldwide Classic Clubhouse Games". Nintendo Life. 25 May 2020. Retrieved 21 July 2020.
  25. "GAMES Magazine #3". January 1978.
  26. "Games and Puzzles 1973-04: Iss 12". A H C Publications. April 1973.
  27. "GAMES Magazine #20". November 1980.
  28. "Games and Puzzles March-April 1974: Iss 23". A H C Publications. March 1974.
  29. https://archive.org/details/playboywinnersgu00free/page/156/mode/2up
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.