## Mastermind Module

This module contains functions around the Mastermind board game like some well-known strategies like the MinMax, Entropy, ExpectedSize and MaxParts strategies. Mastermind is a simple two-player code-breaking 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.

### Types

 Type Description A GameNode represents a node in a tree that is derived from a strategy. The overall strategy will be represented as an array of such nodes where each node has a unique index in that array. It stores the codes that are still possible at that stages of the game, the code guessed by the strategy, and the successor nodes for the corresponding answers.

### Functions and values

 Function or value Description  AnswerDistribution codeList guess  Full Usage: AnswerDistribution codeList guess Parameters: codeList : seq 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. codeList : seq guess : int[] Returns: Map<(int * int), int>  ComputeAnswer code guess  Full Usage: ComputeAnswer code guess Parameters: code : 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. code : int[] guess : int[] Returns: int * int  ComputeGameTree numColors numPlaces nextGuess  Full Usage: ComputeGameTree numColors numPlaces nextGuess Parameters: numColors : 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. numColors : int numPlaces : int nextGuess : bool -> int[] list -> int[] list -> int[] Returns: GameNode[]  ComputeInitialCases numColors numPlaces  Full Usage: ComputeInitialCases numColors numPlaces Parameters: numColors : 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, three places: 000, 001, 012 four places: 0000, 0001, 0011, 0012, 0123 five places: 00000, 00001, 00011, 00012, 00112, 00123, 01234 As initial guesses, only these have to be considered. numColors : int numPlaces : int Returns: int[] list  EnumAllCodes numColors numPlaces  Full Usage: EnumAllCodes numColors numPlaces Parameters: numColors : int numPlaces : int Returns: int[] list Enumerate all possible codes with the given numbers of colors and places numColors : int numPlaces : int Returns: int[] list  GameTree2Dot ostr gt  Full Usage: GameTree2Dot ostr gt Parameters: ostr : TextWriter gt : GameNode[] GameTree2Dot writes a game tree as computed by ComputeGameTree in dot format. The dot graph is written to the output stream ostr. ostr : TextWriter gt : GameNode[]  MastermindTool qscoll  Full Usage: MastermindTool qscoll Parameters: qscoll : NameValueCollection This function is called from the cgi-interface. qscoll : NameValueCollection  NextGuessEntropy isInit codeList possibleCodes  Full Usage: NextGuessEntropy isInit codeList possibleCodes Parameters: isInit : 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: isInit should be true for the initial guess and false otherwise. If isInit holds, the guess chosen is the best choice from codeList, otherwise, if an equally good choice is preferred from possibleCodes. codeList should be the list of all codes where a guess can be taken from; for the initial guess, it should be reduced to the relevant isomorphic classes (see ComputeInitialCases), and otherwise, it contains all codes (even those that are not possible anymore, but can still be used as good test patterns). possibleCodes must be the list of all remaining possible codes. This list is considered for evaluating all codes in codeList according to the particular heuristic. isInit : bool codeList : int[] list possibleCodes : int[] list Returns: int[]  NextGuessExpectedSize isInit codeList possibleCodes  Full Usage: NextGuessExpectedSize isInit codeList possibleCodes Parameters: isInit : 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: isInit should be true for the initial guess and false otherwise. If isInit holds, the guess chosen is the best choice from codeList, otherwise, if an equally good choice is preferred from possibleCodes. codeList should be the list of all codes where a guess can be taken from; for the initial guess, it should be reduced to the relevant isomorphic classes (see ComputeInitialCases), and otherwise, it contains all codes (even those that are not possible anymore, but can still be used as good test patterns). possibleCodes must be the list of all remaining possible codes. This list is considered for evaluating all codes in codeList according to the particular heuristic. isInit : bool codeList : int[] list possibleCodes : int[] list Returns: int[]  NextGuessMinWorst isInit codeList possibleCodes  Full Usage: NextGuessMinWorst isInit codeList possibleCodes Parameters: isInit : 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: isInit should be true for the initial guess and false otherwise. If isInit holds, the guess chosen is the best choice from codeList, otherwise, if an equally good choice is preferred from possibleCodes. codeList should be the list of all codes where a guess can be taken from; for the initial guess, it should be reduced to the relevant isomorphic classes (see ComputeInitialCases), and otherwise, it contains all codes (even those that are not possible anymore, but can still be used as good test patterns). possibleCodes must be the list of all remaining possible codes. This list is considered for evaluating all codes in codeList according to the particular heuristic. isInit : bool codeList : int[] list possibleCodes : int[] list Returns: int[]  NextGuessMostParts isInit codeList possibleCodes  Full Usage: NextGuessMostParts isInit codeList possibleCodes Parameters: isInit : 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: isInit should be true for the initial guess and false otherwise. If isInit holds, the guess chosen is the best choice from codeList, otherwise, if an equally good choice is preferred from possibleCodes. codeList should be the list of all codes where a guess can be taken from; for the initial guess, it should be reduced to the relevant isomorphic classes (see ComputeInitialCases), and otherwise, it contains all codes (even those that are not possible anymore, but can still be used as good test patterns). possibleCodes must be the list of all remaining possible codes. This list is considered for evaluating all codes in codeList according to the particular heuristic. isInit : bool codeList : int[] list possibleCodes : int[] list Returns: int[]  PlayMastermind ()  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. () : unit Returns: int  SimulateAllGames numColors numPlaces nextGuess  Full Usage: SimulateAllGames numColors numPlaces nextGuess Parameters: numColors : 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). numColors : int numPlaces : int nextGuess : bool -> int[] list -> int[] list -> int[] Returns: (int[] * int[] list * int) list