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

set

**<-**letters**[**1**:**6**]**
# matrix all
possible codes

full

**<-**as.matrix**(**expand.grid**(**set, set, set, set**))**
# compare guess
to hidden code

# black - hit
with correct position

# white - hit
with incorrect position

guessFit

**<-****function****(**hidden, guess**)****{**
count

**<-****function****(**pattern**)****{**
sapply

**(**set,**function****(**x**)****{**sum**(**x**==**pattern**)****})****}**

black

**<-**sum**(**full**[**hidden,**]****==**full**[**guess,**])**
white

**<-**sum**(**pmin**(**count**(**full**[**hidden,**])**,
count

**(**full**[**guess,**])))****-**black
paste

**(**black, white, sep**=**";"**)****}**

# prepare matrix
with all possible

# guess-hidden
combinations evaluation

# this is slow: 5
minutes

all.fit

**<-**mapply**(**guessFit, rep**(**1**:**nrow**(**full**)**, nrow**(**full**))**,
rep

**(**1**:**nrow**(**full**)**, each**=**nrow**(**full**)))**
dim

**(**all.fit**)****<-**c**(**nrow**(**full**)**, nrow**(**full**))**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

minimax

**<-****function****(**possible, indent**=**1**)****{**
# if there is only one possibility we are done

**if**

**(**length

**(**possible

**)**

**==**1

**)**

**{**

**if**

**(**indent

**>**worst

**)**

**{**

worst

**<<-**indent**}**

cat

**(**full**[**possible,**]**, "| *\n"**)**
return

**(**1**)****}**

**if**

**(**indent

**==**1

**)**

**{**

cat

**(**"1: "**)****}**

# for each possible guess find worst case size
of set

splits

**<-**sapply**(**1**:**nrow**(**full**)**,**function****(**guess**)****{**
max

**(**table**(**all.fit**[**guess, possible**]))****})**
# choose guess that minimizes maximal size of
set

best.guess

**<-**which.min**(**splits**)**
out.split

**<-**split**(**possible, sapply**(**possible, guessFit,
guess

**=**which.min**(**splits**)))**
cat

**(**full**[**best.guess,**]**, "|", length**(**possible**)**, "\n"**)**
# recursively construct the decision tree

**for**

**(**i

**in**1

**:**length

**(**out.split

**))**

**{**

# ask additional questions if an
exact hit was not obtained

**if**

**(**names

**(**out.split

**)[**i

**]**

**!=**paste

**(**ncol

**(**full

**)**, 0, sep

**=**";"

**))**

**{**

cat

**(**indent**+**1,":", rep**(**" ", indent**)**,
names

**(**out.split**)[**i**]**, "|", sep**=**""**)**
minimax

**(**out.split**[[**i**]]**, indent**+**1**)****}**

**}**

**}**

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
worst

**<-**0
minimax

**(**1**:**nrow**(**full**))**# this is slow: 2 minutes
cat

**(**"\nQuestions in worst case:", worst, "\n"**)**
sink

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

## No comments:

## Post a Comment