Introduction

TODO: Introduce game rules and related work.

Notations

Let

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$
   :

• 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.

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;
}

Implementation details

Exhaustive strategies

Evolution

References