... | ... | @@ -4,8 +4,43 @@ TODO: Introduce game rules and related work. |
|
|
|
|
|
## Notations
|
|
|
|
|
|
Let $`N`$ be the number of pegs in the code and $`C`$ be the number of possible colors. A code is a vector in $`\{0, \ldots, C - 1\}^N`$. The number of possible codes is $`M = C^N`$.
|
|
|
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:
|
|
|
* The codebreaker produces a guess code $`g`$.
|
|
|
* The codemaker provides a feedback $`f(c, g) = \langle b(c,g), w(c, g) \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.
|
|
|
|
|
|
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:
|
|
|
|
|
|
```java
|
|
|
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;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
### Implementation details
|
|
|
|
|
|
|
|
|
# Exhaustive strategies
|
|
|
|
|
|
# Evolution
|
|
|
|
|
|
# References |