# Introduction

TODO: Introduce game rules and real word applications (diagnostics). Related work.

## Notations

Let `N`

be the number of pegs in the code and `C`

be the number of possible peg colors. We will call a game with these particular parameters a `(N, C)`

-game. A *code* is a vector in `\mathbb{C} = \{0, \ldots, C - 1\}^N`

. The number of possible codes is `M = C^N`

. The game is played as follows:

- The codemaker chooses a secret code
`c \in \mathbb{C}`

. - The codebreaker tries to guess
`c`

in as few iterations as possible. At each iteration`t`

:

- The codebreaker produces a guess
`g_t \in \mathbb{C}`

. - The codemaker provides a feedback
`f(c, g_t) = \langle b(c,g_t), w(c, g_t) \rangle`

where`b`

is the number of pegs which are correct in both color and position and`w`

is the number of pegs which are correct in color but not in position.

- The game ends when the codebreaker guesses the secret code (gets feedback
`\langle N, 0 \rangle`

) or when a predefined maximum number of iterations`T`

is reached.

The notion of "correct in color but not in position" is a bit tricky because color repetitions are allowed. To avoid ambiguity, here is a possible feedback implementation:

```
int[] feedback(int[] code, int[] guess) {
int[] vCode = new int[C]; // count vector of colors in code
int[] vGuess = new int[C]; // count vector of colors in guess
int black = 0;
for (int i = 0; i < N; i++) {
if (code[i] == guess[i]) {
black++;
} else {
vCode[code[i]]++;
vGuess[guess[i]]++;
}
}
int white = 0;
for (int c = 0; c < C; c++) {
white += min(vCode[c], vGuess[c]);
}
int[] f = {black, white};
return f;
}
```

### Technical note

For performance reasons, we represent codes as integers between `0`

and `M - 1`

. Writing the code in base `C`

we obtain the vector of peg colors. For example, in the classical `(4, 6)`

-game, the number `51 = 0 \times 6^3 + 1 \times 6^2 + 2 \times 6^1 + 3 \times 6^0`

represents the code `0123`

.

The feedbacks are also encoded as integers between `0`

and `F - 1`

, where `F = \frac{(N + 1)(N + 2)}{2}`

. To reduce the size of arrays indexed by the possible feedbacks, we use the fact that `b + w \le N`

. Here is an example of encoding for `N = 3`

.

b\w | 0 | 1 | 2 | 3 |
---|---|---|---|---|

0 | 6 | 7 | 8 | 9 |

1 | 3 | 4 | 5 | - |

2 | 1 | 2 | - | - |

3 | 0 | - | - | - |

Using this encoding, feedback `0`

always means that the codebreaker guessed the code. According to the situation, some of the feedbacks above are impossible. For example, the codebreaker can never get a feedback `\langle N - 1, 1 \rangle`

. This encoding tries to find a good trade-off between implementation simplicity and memory economy.

The class `CodeToolkit`

makes these encodings more or less transparent. The main method is `int feedback(int code, int guess)`

. For performance reasons, feedbacks are precomputed and stored in a `M \times M`

symmetrical `feedbacks`

matrix. The class also contains some methods for encoding, decoding and displaying codes and feedbacks. The sketch `test_toolkit`

shows how to use this class.

# Exhaustive strategies

TODO. Partitions and guesses that optimize different score functions :

- Minimize the maximum partition size (Knuth)
- Minimize the expected partition size (Irving)
- Maximize the number of Partitions (Kooi)
- Maximize information gained (Bestavros & Belal)
- Use only consistent guesses or the whole set
`\mathbb{C}`

Tables with average and maximal number of guesses for different `(N, C)`

. To be used as reference for comparison with our results.

# Evolution

TODO: related work. Some evolutionary strategies in the literature. They evolve a set of guesses to be used by the breaker.

Our goal is to evolve a *breaker*. Deliberately we will use a very few knowledge about the game. Our breakers know very few things:

- The set of possible codes (and guesses)
`\mathbb{C}`

- A feedback
`\langle N, 0 \rangle`

means that they guessed the code - The fact that the feedback is deterministic. In particular, this means that it is useless to make the same guess more than once during a game, because this will not bring any new information.

Note that the breakers do not know the meaning of the feedbacks (except of the winning one) and hence they can play only trial and error strategies.

## Breaker representation

We will represent a breaker as a rooted tree. Each node of the tree is a guess. The subtrees are labeled with the possible feedbacks of this guess. Here is an example of such a tree for the (3, 3)-game:

Nodes where the breaker gets the winning feedback are drawn with bright colors. We will call them *terminal nodes*.

The first guess of the breaker is the root node. After getting a feedback, it goes down to the corresponding child node and emits the next guess. It stops when it gets the winning feedback. So for a given code `c`

, the game is described by a path starting at the root, following the corresponding feedback edges at each node and finishing at `c`

. We will call this path *a game path* for `c`

.

**Example.** Let the secret code be RRR. The first guess is BRG and the breaker gets feedback `\langle 1, 0 \rangle`

. The second guess will be GBB with feedback `\langle 0, 0 \rangle`

. This feedback leads to a guess RRR and a winning feedback.

Of course, not all trees with the above structure are valid players. To represent a valid breaker, a tree must contain a game path for each possible code.

**Example.** The following tree does not represent a valid breaker:

To show this, consider again the secret code RRR. The first guess is BRG with feedback `\langle 1, 0 \rangle`

. Going down on the corresponding branch, the second guess is BBB with feedback `\langle 0, 0 \rangle`

. Then the third guess is GGG and the feedback is again `\langle 0, 0 \rangle`

. Now the breaker does not know how to play because the node GGG does not have a subtree labeled `\langle 0, 0 \rangle`

.

## Generating a random population

We will construct a valid tree by playing games for each possible code. At each game the breaker will follow a path in the tree while this is possible. Then it will complete the path with random not yet used guesses.

- Start with a tree containing only a root node with a random guess.
- Play a game for each code
`c \in \mathbb{C}`

- Start at the root node.
- Get a feedback
`f`

for the current node's guess. - If
`f = \langle N, 0 \rangle`

, stop. - If the current node has not a child labeled
`f`

, create this child and initialize it with a random guess not yet used in this game. - The child labeled
`f`

becomes the current node, go to step 2.2.

The trees created by this algorithm are rather deceiving:

However, there is an obvious way to significantly reduce their height. Notice the long paths without branches consisting of many wrong guesses followed by the right one. Consider for example the leftmost one starting at RRB and finishing at RBB. These paths correspond to situations where there is only one code consistent with the previous guesses. We can shrink each path of this kind to a single node:

There is another way to optimize the structure of our trees. A common pattern is a triangle formed by a non terminal node with two leaf children. There are seven of them in the picture above, rooted (from left to right) in RGR, GGB, BRB, BRG, RBB, RGR and BBR. These triangles can be transformed as follows:

- Replace the father's guess by the guess of one of the children
- Remove this child
- Relabel the remaining child to match the new father's guess

Here is the result after transforming the seven triangles from the previous example:

The last tree has 1 terminal node at level 1, 2 terminal nodes at level 2, 16 terminal nodes at level 3 and 8 terminal nodes at level 4. So the average number of iterations to guess the code is

`\frac{1 \times 1 + 2 \times 2 + 3 \times 16 + 4 \times 8}{27} = 3.15`

We will use this average as a measure of the *fitness* of a player.

The table below shows the fitness of a randomly generated population of 1000 individuals for different types of games. For comparison we give also the fitness of exhaustive players.

`N` |
`C` |
Min | Max | Avg | `\sigma` |
Exhaustive |
---|---|---|---|---|---|---|

3 | 3 | 2.74 | 3.96 | 3.13 | 0.19 | ~2.70 |

4 | 6 | 5.25 | 6.18 | 5.48 | 0.11 | ~4.40 |

TODO: Re-implement exhaustive breakers and measure their fitness. Add more `(N, C)`

.

The fitness of our population is much worse than the fitness of the exhaustive players but this is not surprising. The next step is to evolve them and to obtain better fitness.

### Technical note

Tree generation is implemented in the class `Node`

and in its wrapper class `Breaker`

. Playing a game for a given code is implemented in `followPath()`

and `buildPath()`

methods. Using the characteristic vector of the `used`

codes in the first phase and the list of `unused`

codes in the second phase, a game is played in `O(M)`

time. Thus the tree is constructed in `O(M^2)`

time. The post-processing takes place in `shrink()`

and `triangleOpt()`

methods. The sketch `random_breaker`

generates and draws a random breaker at each mouse click. The sketch `random_population`

computes the data for the table above.

## Crossover

Coming soon

Coming soon ...

# References

TODO: add papers to the repo