Site icon R-bloggers

Solving mastermind with R

[This article was first published on R snippets, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
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:

# vector with possible peg colors< o:p>
set <- letters[1:6]< o:p>

# matrix all possible codes< o:p>
full <- as.matrix(expand.grid(set, set, set, set))< o:p>

# compare guess to hidden code< o:p>
# black – hit with correct position< o:p>
# white – hit with incorrect position< o:p>
guessFit <- function(hidden, guess) {< o:p>
    count <- function(pattern) {< o:p>
        sapply(set, function(x) { sum(x == pattern) })< o:p>
    }< o:p>
    black <- sum(full[hidden,] == full[guess,])< o:p>
    white <- sum(pmin(count(full[hidden,]),< o:p>
                      count(full[guess,]))) black< o:p>
    paste(black, white, sep=“;”)< o:p>
}< o:p>

# prepare matrix with all possible< o:p>
# guess-hidden combinations evaluation< o:p>
# this is slow: 5 minutes< o:p>
all.fit <- mapply(guessFit, rep(1:nrow(full), nrow(full)),< o:p>
    rep(1:nrow(full), each = nrow(full)))< o:p>
dim(all.fit) <- c(nrow(full), nrow(full))< o:p>

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:

# apply mini-max rule< o:p>
minimax <- function(possible, indent = 1) {< o:p>
    # if there is only one possibility we are done< o:p>
    if (length(possible) == 1) {< o:p>
        if (indent > worst) {< o:p>
            worst <<- indent< o:p>
        }< o:p>
        cat(full[possible,], “| *\n”)< o:p>
        return(1)< o:p>
    }< o:p>

    if (indent == 1) {< o:p>
        cat(“1:    “)< o:p>
    }< o:p>

    # for each possible guess find worst case size of set< o:p>
    splits <- sapply(1:nrow(full), function(guess) {< o:p>
        max(table(all.fit[guess, possible])) })< o:p>
    # choose guess that minimizes maximal size of set< o:p>
    best.guess <- which.min(splits)< o:p>
    out.split <- split(possible, sapply(possible, guessFit,< o:p>
        guess =which.min(splits)))< o:p>
    cat(full[best.guess,], “|”, length(possible), “\n”)< o:p>
    # recursively construct the decision tree< o:p>
    for (i in 1:length(out.split)) {< o:p>
        # ask additional questions if an exact hit was not obtained< o:p>
        if (names(out.split)[i] != paste(ncol(full), 0, sep = “;”)) {< o:p>
            cat(indent + 1,“:”, rep(”    “, indent),< o:p>
                names(out.split)[i], “|”, sep=“”)< o:p>
            minimax(out.split[[i]], indent + 1)< o:p>
        }< o:p>
    }< o:p>
}< o:p>

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:

sink(“rules.txt”) # save output to a file< o:p>
worst <- 0< o:p>
minimax(1:nrow(full)) # this is slow: 2 minutes< o:p>
cat(“\nQuestions in worst case:”, worst, “\n”)< o:p>
sink()< o:p>

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.

To leave a comment for the author, please follow the link and comment on their blog: R snippets.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.