# Mastermind

an algorithm for the generalised version of the Mastermind game

## Table of Contents

## Technical notes

This document is intended as a suplementary description of my solution to the 3rd assignment of module *Introduction to Computing at Imperial College London*.

When dealing with code, `C++`

is assumed and used, unless stated othwerwise. `C++11`

features are used.

The **sourcecode** is accesible in my github repository.

**Typographical notes**

*Cursive*signifies terms specific to this document and solution,singnifies a definition of such a term,*Bold and cursive***bold**is used for general highlighting, or small headlines.

## Introduction

### Mastermind rules

In the beginning the ** code maker** generates a valid

*code*, which will be refered to as

**.**

*codeword*A valid ** code** is any arbitrary sequence of $n$ non-negative integers (

*colors*), each from the range $[0,k)$. Since in the original version of Mastermind the codes consist of “colors” instead of non-negative integers, in this document we will use the term

**as a shorthand in a similar meaning. Also, in the original version the parameters are kept constant as follows: $n=4, k=6$, this document, however, considers the general case.**

*color*Following this, the ** code solver** can

**a valid code of his choice and is given a**

*query***of two integers $b$ and $w$. These correspond to the**

*response**black and white pegs*in the original game.

**The objective of the game** is to guess the *codeword* in the least possible number of *queries*. A game is only considered as **finished** after the *solver* has *querried* the correct *codeword*, even if he might have deduced the *codeword* from his previous *querries*.

### The objective of my solution

The objective of my solution is to twofold: Firstly, it is to guess the *codeword* in the least amount of *queries*, but also to provide an algorithm suitable for large $n$ and $k$, with realistic computational complexities.

### Formal definitions of $w$ and $b$

$b$ is always equal to the number of correctly guessed *colors* (*i.e.* correct *colors* on the correct position). Formally: Let the code maker’s *codeword* be $c_1 c_2 c_3 … c_{n-1}$ and the *queried* code $a_1 a_2 a_3 … a_{n-1}$. $b$ equals to the number of indeces $i$ such that $c_i = a_i$.

Commonly and vaguely, $w$ is defined as the number of incorrectly positioned colors in an *query*. Formally: Let $C_i$ and $A_i$ be the number of occurences of *color* $i$ in the secret code and the *query* code, respectively. Then:

$$ w = \biggl( {\sum_{i=0}^{k-1} min(C_i, A_i)} \biggr) - b $$

## The code maker

Let us begin with the *code maker* as this player needs a significantly simpler algorithm.

The approach for $b$ is self evident. The calculation of $w$ is done by implementing the definition formula above. This algorithm can be **optimized** by calculating `color_count_codeword`

at the beginning.

```
// n and k is given, as above
int black = 0;
int white = 0;
std::vector< int > color_count_codeword = std::vector<int>(k, 0)
std::vector< int > color_count_query = std::vector<int>(k, 0)
for(int i = 0; i < n, i++){ // n - length of codeword
if(codeword[i] == query[i]){
black++;
}
color_count_codeword[ codeword[i] ]++;
color_count_query[ query[i] ]++;
}
for(int j = 0; j < k, j++){ //k - number of colors
white += min(color_count_query[i],color_count_codeword[i]);
// either use std::min() or own implementation
}
white -= black;
/* done, return black and white */
```

### Complexity of the *code maker’s* algorithms

The complexity of the two algorithms is:

- Time complexity: $O(n+k)$
- Space complexity: $O(k)$

One can hardly optimize these complexities. Also, it is not a goal of my solution to do so, as the *code maker’s* response is considered to be a rather externally given mechanism. It certainly could be optimised by omitting white pegs - as we will be shown later -, but again, this would be an interference with the external mechanism and the rules of the game.

## The code solver

In the rest of this document we will predominantly speak in terms of number of *queries* (*query complexity*) and will distinguish distinguish this term from *time complexity* and *space complexity*.

### Review of strategies

The strategies on the Internet and in research papers can be divided into 2 main approaches:

- Approach for small numbers: $n,k \leq 10$
- Approach for large numbers: $n,k > 10$

**Approaches for small numbers** aim to find a optimal or suboptimal strategy, and therefore often feature algorithms iterating trough the whole space of possible *codes*, which is $k^n$. Consequently, these algorithms only work for small numbers, hence my naming of this approach. Some examples are:

**Knuth’s algorithm**
Although being a subotimal strategy for $n=4, k=6$, the research paper provides some hints on how to generalize.

**Player that never makes mistakes**

Is an approach in which the *solver* only queries codes which are not ruled out by his previous attempts. The query generation may be random or deliberate. Often is combined with the ** minimax** method, which makes the query generation process deliberate for the price of $O((k^n)^2)$ time complexity.

**Approaches for large numbers** are characterized by systematic guessing, often resulting in overheads for small numbers. A good example of this kind of approach is the algorithm proposed by **Doerr**, Benjamin, et al. “**Playing mastermind with many colors.**“.

The following two sections will go trough the details and specific implementations of these 2 different approaches. The proposed solutions are my own.

### Approach for $n \leq 10$: Player that makes no mistakes

The chosen algorithm for small numbers is the pure *player that makes no mistakes* algorithm. A pseudo description of the algorithm may be seen as follows:

- Let $b(A, B)$ and $w(A, B)$ be the functions returning the $b$ and $w$ values for two
*codes*$A, B$. And let $S$ denote the*secret codeword*geenrated by the*maker*. - Create a set of
*codes*$PossibleCodes$ and fill it with all the possible*codes*. - Select (randomly) a
*code*$C$ from $PossibleCodes$ and query it’s $b(C,S)$ and $w(C,S)$ from the*code maker*. - Remove all codes $X$ from $PossibleCodes$ which do not satisfy $b(C,S)=b(X,S) \land w(C,S)=w(X,S)$.
- Repeat from step 3, until $b \neq n$.

#### Generating a set of possible codes

The generation of a set of possible codes can be implemented in a particularly elegant way using recursion as follows. The function requires a `std::vector<int>`

of size $n$ supplied.

```
void generate_possible(
int n,
int k,
std::set<std::vector<int>> & possible_codes,
std::vector<int> & code,
int depth = 0
){
for (int color = 0; color<k; color++){
code[depth]=color;
if(depth == n-1){
possible_codes.insert(code);
}
else{
generate_possible(n,k,possible_codes,code,depth+1);
}
}
}
```

#### Elimination of codes

The following segment of code is given the `black_hits`

and `white_hits`

values and it removes all impossible *codes*. The `evaluate`

function returns the $b, w$ values to the `black_measured`

, `white_measured`

variables.

```
int black_measured;
int white_measured;
for(std::set<std::vector<int>>::iterator code_it=possible_codes.begin();
code_it != possible_codes.end();
code_it
){
evaluate(C,*code_it,black_measured,white_measured);
if(black_hits!=black_measured || white_hits!=white_measured ){
possible_codes.erase(code_it++);
}
else{
code_it++;
}
}
```

#### Complexity and performance

The time complexity has taken into account the time complexity of iterating trough a `std::set`

, which using “any kind of iterator” according to § 24.2.1 of the Standard for Programming
Language C++11 is is $O(n)$ and therefore submissive to $O(k^n)$.

- Time complexity: $O(k^n)$
- Space complexity $O(n*k^n)$

Due to the demanding time complexity, this algorithm is unsuitable for large numbers of possible codes. As a general rule of thumb $k^n < 100 \space 000$ can be used as a condition approximating the feasibility of the computation. For my solution a similar condition is used. Exceeding that condition the program chooses to go with the strategy, described in the next section.

### Approach for $n>10$: Binary search

#### Stage 1: Monochromatic queries

The first stage is rather simple. The code solver queries $i, i \epsilon [0,k)$ queries each consisting only of *color* $i$ (** monochromatic**).

##### Example

Let $n=4, k=6$ and let the secret *codeword* be:

```
1 4 4 2
```

Stage 1 would look like this:

```
0 0 0 0 Black: 0, White: 0 // color 0 is present 0 times
1 1 1 1 Black: 1, White: 0 // color 1 is present 1 times
2 2 2 2 Black: 1, White: 0 // color 2 is present 1 times
3 3 3 3 Black: 0, White: 0 // color 3 is present 0 times
4 4 4 4 Black: 2, White: 0 // color 4 is present 2 times
5 5 5 5 Black: 0, White: 0 // color 5 is present 0 times
```

From these information we can set up an array of frequencies of colors which we will utilise in later stages.

##### Complexity of Stage 1

- Query complexity: $O(k)$
- Complexity of generating each query:
- Time complexity: $O(n)$
- Space complexity: $O(n)$

#### Stage 2: Finding a dummy

We will consider a ** dummy code** any

*code*that gives a response of zero black pegs. A trivial

*dummy*might be a

*monochromatic*sequence tried in

*stage 1*. Since nothing guarntees that such a

*monochromatic*query will exist, this shortcut is implemented just as an

**optimisation**.

To **guaranteedly find a dummy** we

*query*$n$

*codes*with one

`1`

on position $i, i \epsilon [0,n) $, and the remaining $n-1$ slots filled with `0`

-s. Let $C_0$ be the number of `0`

-s in the *codeword*and $c_i$ the i-th

*color*of the

*codeword*. Than for each value of $i$ three cases are possible based on the number of black pegs $b_i$ received as

*response*to such a

*query*:

- $C_0 < b_i \implies c_i = 1$
- $C_0 = b_i \implies c_i \neq 1, c_i \neq 0$
- $C_0 > b_i \implies c_i = 0$

Another **optimization** is implemented: if this stage **is** taken (*i.e.* no *dummy* found in stage 1), we discover the positions of all `0`

s and `1`

s and in the next stage we don’t have to deal with them.

##### Example

Let $n=4, k=6$ and let the secret *codeword* be:

```
3 1 0 5
```

Note, that this stage would have been skipped in this case, although we will pretend that the optimization was not implemented. In stage 1 we already tested `0 0 0 0`

with result `Black: 1, White: 0`

.

The queries stage 2 would be:

```
1 0 0 0 Black: 1, White: 1 // position 1 is neither 0 nor 1
0 1 0 0 Black: 2, White: 0 // position 2 is 1
0 0 1 0 Black: 0, White: 2 // position 3 is 0
0 0 0 1 Black: 1, White: 1 // position 4 is neither 0 nor 0
The codeword is: X 1 0 X // X = unknown
A dummy code is: 0 0 1 0
```

##### Complexity of Stage 2

- Query complexity: $O(n)$
- Complexity of generating each query:
- Time complexity: $O(n)$
- Space complexity: $O(n)$

#### Stage 3: Binary search

The dummy sequence is a profoundly useful tool. It enables us to query the number of occurences of color $C$ in arbitrary ranges of positions. We can do this by submitting the following query:

```
D0 D1 C C C D5 D6 D7
```

where `D`

-s are the *colors* of the dummy code. The *response* $b$ for this q*uery* would represent the number of occurences of color $C$ in range of positions $2$,$3$ and $4$.

##### Interval tree

Stage 3 consist of $c, c \epsilon [0,k)$ ** substages**. Each

*substage*finds all the positions of color $c$. It does so using a

**as follows:**

*Interval tree*```
struct interval_node{
int min; // values from (including)
int max; // values upto (including)
int remaining; // count of potentially
// present colors c under this interval
interval_node * left; // interval [min,floor((min+max)/2)]
interval_node * right; // interval [ceil((min+max)/2), max]
interval_node * parent; // pointer to parent, NULL for root
};
```

This data structure satisfies the following criteria:

- Binary tree
- Search tree (ordered)
- Interval (segment) tree
- Upwards and downwards traversible tree

The following conditions will be always true for this *interval tree*:

- In the beginning each interval has a
`remaining`

equal to the number of occurences of the given*color*. - A interval
`A`

’sshould be the value equal to*span*`A.max-A.min+1`

- An intervall shall be called
if all its ancestors have*accesible*`remaining > 0`

. - After an interval
`A`

was*querried*then`A`

‘a*sibling’s*`remaining`

is set equal to`A.parent->remaining - A.remaining`

. - From the latter follows that if an interval was querried, it’s
*sibling*is considered, and both may be said to have been*effectively querried*.*effectively querried* - A interval
`B`

of positions is*discovered*(contains only*color*$c$) if`B.remaining == B.max - B.min + 1`

. Then,`B.remaining`

and all`B`

’s parents’s`remainings`

are reduced by`B`

’s*span*. - It follows that if all instances of color $c$ are
*discovered*the root interval node’s`remaining`

is 0 and the algorithm can proceed to the next*substage*.

Now only one last piece of information is missing, which is: **which interval should be querried next?** From now on many possible implementations are possible, important should only be that the next interval should always be a

*accesible*interval which’s

*parent*has already been

*efectively querried*. Note, that from the recoursive nature of this statement it follows that a

*querried*interval’s all ancestors exluding the

*root interval*have been

*querried*. (Note, again, that the last note is not entirely true as the

*root interval*has “effectively” (now using this term in it’s original meaning) already been querried in stage 1! 😜 )

After each *querry* the *response of black pegs* has to be *teached* to the *interval tree* in accordance with rules 4, 6, ( and 7).

The above mentioned rules are implemented in my program and for simplicity, their implementation won’t be shown here. For the interested readers, the code is on my github repository.

##### Complexity od Stage 3

- Query complexity of stage 3: $O(n \log_2n)$
- Time complexity of generating each query: $O(\log_2n)$
- Time complexity of generating the interval tree for each color $O(n)$
- Overall time complexity (including
*code maker’s response*): $O(k * n + n^2 \log_2n)$

#### Complexity of the Binary search algorithm

A summary of *query complexity* of each stages:

- Stage 1: $O(k)$
- Stage 2: $O(n)$
- Stage 3: $O(n \log_2n)$

The * overall query complexity* reduces to:

$$O(k+n \log_2n)$$

With a * total running time complexity*(including

*code maker’s response*) clearly dominated by stage 3 :

$$O(k*n + n^2 \log_2n)$$

As we can see a $k >> n$ would only have effect by prolonging stage 1. Also, research literature on this topic devotes attention mainly to the “*prominent*” case when $k \approx n$ as otherwise the game has lots of unused colors, or on the contrary many repetitive color. The latter results in a possible optimization of skipping stage 2, the former is exploited by the *interval tree*. For these reasons $k=n$ is assumed for comparing the complexities of algorithms of this kind.

##### Comparing with other systematic algorithms

This algorithm features a rather modest space complexity ( $O(n+k)$ since we only need to maintain a $n$ sized binary interval tree and a constant number of arrays of size $n$ and $k$), compared to the algorithms in the recent research papers, most prominently Doerr, which maintain a set of *colors* of size $k$ for each position ($O(k*n)$)!

In my personal opinion the achieved *time* and *query* complexity can be seen as a good result given the lightweight nature of this approach. On the other hand the *query complexity* of Doerr is silghtly better: $O(n \log_2 \log_2 n)$, compared to mine $O(n \log_2 n)$.

##### Optimizations and performance boosts

“Premature optimization is the root of all evil” — D. Knuth

A **significant query complexity optimization** could be achieved by restricting the binary search to positions which have not been determined yet. This would however require a very much different interval tree, and possibly its re-building for each

*color*. Therefore this optimization was not implemented.

The following two ** query complexity optimizations** were implemented because of their very simple implementation:

- Finding all
`0`

-s and`1`

-s during stage 2 - Skipping stage 2 if a
*monochromatic dummmy*is found in stage 1. (common for $n \lessapprox k$)

Performance can be significantly boosted by **omitting the printouts** of the queried array ($O(n)$ time complexity). The difference is demonstrated below:

**Binary search strategy on $n=100, k=100$,**

*with*printouts [gif]**Binary search strategy on $n=100, k=100$,**

*without*printouts [gif]#### Performance and summary

Time has come to combine the two strategies. The following two graphs compare the average (32 samples) number of queries for $n,k \leq 20$:

**Average [32] number of**

*queries*for * Plaer that makes no mistakes* algorithm for $n,k \leq 20$By carefull inspection, one can see that even though for smaller $n,k$ the *binary search* method has large overheads in terms of queries, it can cover a substantially larger range of $n,k$.

**Average [32] number of**

*queries*for*Binary search*algorithm for $n,k \leq 20$…indeed, this graph shows the performance of Binary search algorithm for $n,k \leq 100$. And that is not all: the *binary search* was tested up to $n,k=10 \space 000$.

**Average [32] number of**

*queries*for*Binary search*algorithm for $n,k \leq 100$A combination of the two algorithms (*Player that makes no mistakes* and *Binary search*) guarantees for $n,k \leq 100$ a running time $<1s$!
The following table provides a informative overview of running times depending on $n,k$.

$n,k \leq $ | Running time | Notes |
---|---|---|

$6$ | $5 sec$ | nomistakes algorithm |

$100$ | $1 sec$ | binary search algorithm |

$1 \space 000$ | $1 min$ | binary search algorithm |

$10 \space 000$ | $5 min$ | binary search algorithm |

#### Notes on design patterns used

The `mm_colver`

class-structure vauely implements a **strategy design pattern** by transfering the `create_attempt()`

and `learn()`

calls to the appropriate `strategy`

call.

The `Strategy_binary_search`

class implements a *finite state pattern*.