[history, rules, variations, etc]
Mastermind is a game played by two players, the code maker and the code breaker. At the beginning of the game, the code maker thinks of a secret codeword with \(p\) pegs and \(c\) colors. Then the code breaker begins making guesses.
For each guess, the code maker responds with a feedback in the form of xAyB to describe how close the guess is to the secret. Here \(x\) is the number of correct colors in the correct pegs, and \(y\) is the number of correct colors in the wrong pegs. The game continues until the code breaker finds the secret.
The standard Mastermind game is played on a board with four pegs and using six colors. A codeword can contain the same color more than once. A popular variation of the rules is called GuessNumber, also known as Bulls-n-Cows. Under these rules, no repetition of colors is allowed in the codeword.
[introduce the strategies, and introduce a table that describes how many codewords need to be solved in how many steps). [secrets be revealed]
There are three types of strategies for the code breaker:
Simple strategy. (Ch02) The code breaker just makes a random guess, as long as the guess will bring some information. A natural choice could be the first codeword from the remaining possibilities. These strategies obviously perform poorly in that it usually takes many steps to find the secret, but they are simple and fast and thus can be used as a benchmark for other more sophisticated strategies.
Heuristic strategy. (Ch03) The code breaker evaluates each potential guess according to some scoring criteria, and picks the one that gets the highest score. These strategies are fast enough for real-time games, and performs quite well. Most research in this field focuses on finding a good heuristic criteria, and a number of intuitive and well-performing heuristics have been proposed. For more details, see heuristic strategies.
Optimal strategy. (Ch04) Since the number of possible secrets as well as sequence of guesses are finite, the code breaker can employ a depth-first search to find out the optimal guessing strategy. The optimal strategy minimizes the expected number of guesses, optionally subject to a maximum-guesses constraint. Finding such a strategy involves exhaustive search, and therefore is too slow to be suitable for real-time application. For more details on the implementation, see optimal strategies.
Chooses the first possibility. Here first depends on the order of the list. We can let it be lexicographical first.
However, an algorithm that depends on lexicographical ordering is not very ideal. See comparision of heuristics in chapter 2 for a discussion.
A standard strategy tree contains the strategy starting from the initial state.
An extended (or adaptive, full) strategy tree contains a strategy for every possible state of the game.
Introduce the notations (Irving) to aid the reader in reading the classical papers.