... | ... | @@ -7,7 +7,7 @@ TODO: Introduce [game rules](https://en.wikipedia.org/wiki/Mastermind_(board_gam |
|
|
Let $`N`$ be the number of pegs in the code and $`C`$ be the number of possible peg colors. A *code* is a vector in $`\{0, \ldots, C - 1\}^N`$. The number of possible codes is $`M = C^N`$. The game is played as follows:
|
|
|
|
|
|
1. The codemaker chooses a secret code $`c`$.
|
|
|
2. The codebreaker tries to guess $`c`$ in as few as possible iterations. At each iteration $`t`$ :
|
|
|
2. The codebreaker tries to guess $`c`$ in as few iterations as possible. At each iteration $`t`$ :
|
|
|
* The codebreaker produces a guess code $`g_t`$.
|
|
|
* 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.
|
|
|
3. 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.
|
... | ... | @@ -36,9 +36,9 @@ int[] feedback(int[] code, int[] guess) { |
|
|
}
|
|
|
```
|
|
|
|
|
|
### Implementation details
|
|
|
### Note for developers
|
|
|
|
|
|
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 classic settings $`N = 4`$ and $`C = 6`$, the code $`0123`$ is represented by $`0 \times 6^3 + 1 \times 6^2 + 2 \times 6^1 + 3 \times 6^0 = 51`$.
|
|
|
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 classic settings $`N = 4`$ and $`C = 6`$, 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`$.
|
|
|
|
... | ... | @@ -49,9 +49,9 @@ The feedbacks are also encoded as integers between $`0`$ and $`F - 1`$, where $` |
|
|
| 2| 1| 2| -| -|
|
|
|
| 3| 0| -| -| -|
|
|
|
|
|
|
Using this encoding, feedback $`0`$ always means that the codebreaker guessed the code. According to the values of $`N`$ and $`C`$, 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.
|
|
|
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 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.
|
|
|
|
|
|
|
|
|
# Exhaustive strategies
|
... | ... | |