Solving mastermind with R

In my last post I have shown a solution to classical sorting problem in R. So I thought that this time it would be nice to generate a strategy for playing Mastermind using R.
It was shown by D.E. Knuth that Mastermind code can be broken in at most five guesses. The algorithm is to always choose guess that minimizes the maximum number of remaining possibilities. Here is the R code that implements it.

The game is played using six colors and codes have length four. First part of the code prepares the data for calculations:


We want to prepare matrix all.fit of all possible guess-hidden code combinations in advance in order to avoid calling guessFit in the main algorithm (WARNING: it takes ~5 minutes on my laptop). Having generated it we can reference codes using their position (row number) in full matrix.

Now let us move on to the main function:


It recursively constructs the decision tree solving the game and outputs it using cat. At each level of the tree first number of the question asked is printed, next the chosen guess and finally either number of remaining options or a star * indicating a hit. Additionally in variable worst we keep the number of questions that have to be asked in the worst case.

Finally we run the prepared code:


I redirect output to a file because the resulting tree is quite big (1710 lines) and we can actually see that the game can be solved in five questions in a worst case.

Finally – the code was prepared to make it easy to experiment with the code by changing number of colors and pegs only by changing variables set and full.