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.

Felton, for Unix by Ken Thompson,[4] and for the Multics system at MIT by Jerrold Grochow.

Starting in 1973, the game box featured a photograph of a man in a suit jacket seated in the foreground, with a young woman standing behind him.

The two amateur models (Bill Woodward and Cecilia Fung) reunited in June 2003 to pose for another publicity photo.

An extra point is earned by the codemaker if the codebreaker is unable to guess the exact pattern within the given number of turns.

[13] Described using the numbers 1–6 to represent the six colors of the code pegs, the algorithm works as follows: 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.

The quality of each of these codes is determined based on a comparison with a selection of elements of the eligible set.

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"): 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.

[18][better source needed] 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?"

In December 2005, Jeff Stuckman and Guo-Qiang Zhang showed in an arXiv article that the Mastermind satisfiability problem is NP-complete.

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.