This module contains functions around the Mastermind board game like some wellknown strategies like the MinMax, Entropy, ExpectedSize and MaxParts strategies. Mastermind is a simple twoplayer codebreaking board game invented in 1970 by Mordecai Meirowitz, an Israeli postmaster and telecommunications expert. It may have been inspired by moo, a program developed by J.M. Grochow at MIT in the late 1960s. In the game, one player is the codemaker and the other is the codebreaker. The codemaker secretly selects a code consisting of an ordered sequence of four colors (c_1,c_2,c_3,c_4), each chosen from a set of six possible colors, with repetitions allowed. The codebreaker then tries to guess the code by repeatedly proposing a sequence of colors (g_1,g_2,g_3,g_4). After each guess, the codemaker tells the codebreaker two numbers (b,w): the number of correct colors in the correct positions (p) and the number of colors that are part of the code but not in the correct positions (w). For example, if the code is (1,2,3,3) and the codebreaker's guess is (3,2,4,3), then the codemaker's response would be (2,1), since the codebreaker has guessed the 2 and the second 3 correctly and in the correct positions, while having guessed the first 3 correctly but in the wrong position. The codebreaker continues guessing until she guesses the code correctly or until she reaches a maximum allowable number of guesses without having correctly identified the secret code. Note that w can be computed as w=(sum_(i=1)^numColors min(c_i,g_i))b, where c_i is the number of times the color i is in the code and g_i is the number of times it is in the guess.
Function or value  Description 
Full Usage:
AnswerDistribution codeList guess
Parameters:
seq<int[]>
guess : int[]
Returns: Map<(int * int), int>

AnswerDistribution computes for a given guess the distribution of the answers, i.e., for all possible codes in the codelist given, it computes the answers, and will then yield a map that assigns each answer the number of codes in codeList that would yield that answer for the given guess. The general idea is thereby to find a guess such that the information contained in the answer is maximized, and that information is the entropy of the answer distribution.

Full Usage:
ComputeAnswer code guess
Parameters:
int[]
guess : int[]
Returns: int * int

The next function computes the answer of the opponent player who knows the secret code when (s)he sees the guess. The answer is a pair (p,w) where p is the number of colors in correct places and w is the number of remaining colors at wrong places. More precisely, w can be computed as w=(sum_(i=1)^numColors min(c_i,g_i))p, where c_i is the number of times the color i is in the code and g_i is the number of times it is in the guess.

Full Usage:
ComputeGameTree numColors numPlaces nextGuess
Parameters:
int
numPlaces : int
nextGuess : bool > int[] list > int[] list > int[]
Returns: GameNode[]

ComputeGameTree computes a tree that encodes the entire game strategy. The tree is encoded as an array of type GameNode where each node stores the possible codes, the guess made according to the strategy and for each possible answer the corresponding successor node in the game tree.

Full Usage:
ComputeInitialCases numColors numPlaces
Parameters:
int
numPlaces : int
Returns: int[] list

ComputeInitialCases computes relevant initial guesses, i.e., one code of each equivalence class where all colors are ordered and the colors with lesser color are not in minority. For example,

Full Usage:
EnumAllCodes numColors numPlaces
Parameters:
int
numPlaces : int
Returns: int[] list



GameTree2Dot writes a game tree as computed by ComputeGameTree in dot format. The dot graph is written to the output stream ostr.



Full Usage:
NextGuessEntropy isInit codeList possibleCodes
Parameters:
bool
codeList : int[] list
possibleCodes : int[] list
Returns: int[]

NextGuessEntropy computes the entropy as a measure of information that is contained in the answers for a guess. Informally, the entropy can be viewed as a measure on how equally distributed the answer distribution as computed by function AnswerDistribution is. The goal is to choose a test pattern that generates an answer distribution with maximal entropy (information content). Using this strategy, all codes for six colors and four places can be broken with a total of 5722 moves and for all codes at most six moves using no more than five guesses are sufficient to break the code. As for all nextGuess functions, the arguments are as follows:

Full Usage:
NextGuessExpectedSize isInit codeList possibleCodes
Parameters:
bool
codeList : int[] list
possibleCodes : int[] list
Returns: int[]

NextGuessExpectedSize computes the expected size of a entry of the answer distribution of a test pattern, i.e., its cardinality multiplied with the probability that this answer will be given. The goal is to choose a test pattern such that the expected number of the remaining codes is minimized. Using this strategy, all codes for six colors and four places can be broken with a total of 5696 moves and for all codes at most six moves using no more than five guesses are sufficient to break the code. Only three codes require six guesses, namely 0541, 2331, and 4422. Hence, this strategy is in the worst case almost as good as the best worst case optimizing strategy (NextGuessMinWorst), while being better in the average case. As for all nextGuess functions, the arguments are as follows:

Full Usage:
NextGuessMinWorst isInit codeList possibleCodes
Parameters:
bool
codeList : int[] list
possibleCodes : int[] list
Returns: int[]

This strategy chooses a next guess that minimizes the maximal number of remaining codes for each possible answer in the answer distribution associated with a guessed code (the answer distribution is computed by function AnswerDistribution). So, after each guess, it creates a new answer distribution for the remaining possible codes, and selects a suitable guess that minimizes the maximal element in the distributions. Using this strategy, all codes for six colors and four places can be broken with a total of 5801 moves and for all codes at most five moves using no more than four guesses are sufficient to break the code. As for all nextGuess functions, the arguments are as follows:

Full Usage:
NextGuessMostParts isInit codeList possibleCodes
Parameters:
bool
codeList : int[] list
possibleCodes : int[] list
Returns: int[]

NextGuessMostParts chooses a test pattern that will lead to an answer distribution where as many answers as possible may appear, i.e. occur for at least one code. Using this strategy, all codes for six colors and four places can be broken with a total of 5668 moves and for all codes at most six moves using no more than five guesses are sufficient to break the code. Only seven codes require six guesses, namely 2125, 2155, 4232, 5131, 5450, 5531, and 5551, while the average number of moves is almost optimal, i.e., 4.37345679. As for all nextGuess functions, the arguments are as follows:

Full Usage:
PlayMastermind ()
Parameters:
unit
Returns: int

This function can be used to play Mastermind in an interactive shell where the computer is the codebreaker and the human user is the codemaker. Given a strategy nextGuess, the computer will guess some codes until the code will be broken. Output is written to the output stream and inputs are expected via the input stream.

Full Usage:
SimulateAllGames numColors numPlaces nextGuess
Parameters:
int
numPlaces : int
nextGuess : bool > int[] list > int[] list > int[]
Returns: (int[] * int[] list * int) list

Using a heuristic nextGuess to choose a next test pattern, this function computes all possible game plays for numColors and numPlaces. The first guess is chosen from the initial isomorphic classes, and otherwise from all possible codes evaluated by heuristic nextGuess regarding the remaining possible codes. A game is terminated as as soon as the code becomes known; this may happen since the last guess was the code or since only one code is left in the possible remaining codes. In the latter case, the number of moves is by one more than the number of guesses. The function returns a list of triples (c,gl,ml) where c is the code to be broken, gl the list of guesses made by the codebreaker, and ml the number of moves of the game (as explained this is either the length of gl or one more than this).
