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.

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.

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.

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

Enumerate all possible codes with the given numbers of colors and places

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

This function is called from the cgi-interface.

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.

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.

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.

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.

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.

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