The Computer as Master Mind

2026-01-11

During some days off, we played Master Mind with friends.

In Master Mind, two players confront each other. One player, the codemaker, chooses a secret code of 4 positions using 6 possible colours and the other player, the codebreaker, tries to guess the secret within a limited number of turns.

While looking for a strategy, we found out that Knuth - known for his love of fun and games - wrote a paper about Master Mind in 1976, now 50 years ago! In his paper, Knuth proves that the codebreaker can always find any secret in at most 5 guesses.

In this post, we recall the rules of Master Mind and implement Knuth's algorithm in vanilla OCaml. One cool thing about the algorithm is that it is short: our full implementation stands in under 100 lines of code.

Master Mind rules

The codemaker chooses a secret code of 4 positions from 6 colours. Repetitions are allowed, so there is a total of 1296 possible codes. The codebreaker tries to find the secret within a limited number of turns (typically 10 or 12). After each guess, the codemaker responds with black and white hits:

• One black hit for each correct colour in the correct position.
• One white hit for each correct colour but in the wrong position (excluding those already counted as black).

Four black hits means the codebreaker guessed the code and wins.

Example

If the codemaker chooses the secret 🔴🟢🔵🔵 and the codebreaker guesses 🔴🟡🔴🟢 then:

• 🔴 in position 1 is an exact match which counts as 1 black hit.
• 🟡 in position 2 does not belong to the secret code and thus does not count.
• 🔴 in position 3 doesn't count as the secret's red is already matched at position 1.
• 🟢 in position 4 appears in the secret but at a different position: this counts as 1 white hit.

The response given by the codemaker is "1 black hit and 1 white hit". The codebreaker will use this information to prepare its next guess. Notably, the information the codebreaker gained is that the set of candidate codes (the ones that could be the secret) has been pruned to those that would give the same response (1 black hit and 1 white hit).

The game repeats until either the codebreaker guesses the secret code or runs out of tries.

Knuth's minimax algorithm

Knuth proposes a minimax strategy which progressively prunes the set of candidate codes by always choosing the guess that minimises the number of remaining candidates.

More precisely, at each turn:

1. For each possible guess, partition the current candidates by the response they would give. The worst case for that guess is the size of the largest group.
2. Pick the guess with the smallest worst case. When several guesses tie for the best score, prefer one that is still a candidate for the secret code since it could be the secret, winning immediately.
3. Play the guess, observe the response, and eliminate candidates that don't match.
4. Repeat until the secret is found.

Example

We consider a simplified game with 3 possible colours (🔴🟢🔵), 2 positions, no repetitions and we suppose the secret is 🔵🔴.

Turn 1

The initial set of 6 possible codes is 🔴🟢, 🔴🔵, 🟢🔴, 🟢🔵, 🔵🔴 and 🔵🟢.

The codebreaker starts by guessing 🔴🟢 and the codemaker responds: "1 white".

We remove from the set of candidates any code that would not give "1 white" against 🔴🟢:

• 🔴🟢 gives 2 black
• 🔴🔵 and 🔵🟢 give 1 black
• 🟢🔴 gives 2 white
• 🟢🔵 and 🔵🔴 give 1 white

The new set of remaining candidates is 🟢🔵 and 🔵🔴.

Turn 2

We apply minimax to choose the next guess. To do that, for each possible guess, we compute the worst case over the remaining candidates and choose the one with the minimum.

As we can see, several guesses have worst case 1. We prefer a guess from the remaining candidates, so we pick 🟢🔵.

In larger games, it is not always possible to find a guess with the best worst-case score among the remaining candidates. Since the goal is to maximise information gained, we may need to pick a guess outside the candidates.

The codemaker responds: 0 black, 0 white.

We remove from the set of candidates any code that would not give this response against 🟢🔵.

Turn 3

Only one candidate remains, so we guess 🔵🔴. The codemaker responds "2 black hits" and we win.

Implementation

OCaml's type checker is very good at type inference. However I will often explicitly annotate values with types, mostly output types, to make the code more explicit.

Calculating responses

Our first objective is to calculate responses. We start by defining the colours available in the game as a sum type with 6 constructors, a code as a list of colours, and a response as a record type with two integer fields for black and white hits.

type colour = Green | Red | Blue | Yellow | Purple | Pink

type code = colour list

type response = { black_hits : int; white_hits : int }

We then define a module that maps colours to their number of occurrences in codes.

module ColourMap : Map.S with type key = colour = Map.Make (struct
  type t = colour

  let compare = Stdlib.compare
end)

The module ColourMap is obtained by applying the functor Map.Make to a module that implements the OrderedType signature, where t is the type of keys (in our case colour) and compare is an ordering function over them. It returns a module of type Map.S containing all the material needed to manipulate maps indexed by colours.

For simplicity, we use the Stdlib.compare function provided by the OCaml standard library, which can be applied to any two arguments of the same type. Also note that we only need to fix the type of the keys because ColourMap is polymorphic in its value type: a colour map has type 'a ColourMap.t where 'a is the type of the values associated to the keys. For instance, occurrence maps will have type int ColourMap.t because colours will bind the number of times (represented as integers) they appear in a code.

We now define the function to count colours in a code. This function traverses a code and returns an occurrence map. We fold over the code, maintaining an accumulator initialised to an empty map. For each colour, we either bind it to 1 if absent from the map, or increment its count if present.

let count_colours code : int ColourMap.t =
  List.fold_left
    (fun occurrence_map colour ->
      ColourMap.update colour
        (function None -> Some 1 | Some n -> Some (n + 1))
        occurrence_map)
    ColourMap.empty code

Finally, we define calculate_response, which computes the response (black and white hits) given a secret and a guess.

let calculate_response secret guess : response =
  let black_hits, secret_remaining, guess_remaining =
    List.fold_left2
      (fun (black_hits, secret_remaining, guess_remaining) s g ->
        if s = g then (black_hits + 1, secret_remaining, guess_remaining)
        else (black_hits, s :: secret_remaining, g :: guess_remaining))
      (0, [], []) secret guess
  in
  let secret_counts = count_colours secret_remaining in
  let guess_counts = count_colours guess_remaining in
  let white_hits =
    let white_counts =
      ColourMap.merge
        (fun _colour sw_opt gw_opt ->
          match (sw_opt, gw_opt) with
          | None, None | None, Some _ | Some _, None -> None
          | Some sw, Some gw -> Some (min sw gw))
        secret_counts guess_counts
    in
    ColourMap.fold (fun _colour n acc -> acc + n) white_counts 0
  in
  { black_hits; white_hits }

The function starts by counting black hits and separating out the non-matching positions. We use List.fold_left2, which works like List.fold_left but traverses two lists in parallel. We use a tuple accumulator: a counter for black hits and two lists for the remaining colours in the secret and the guess. The accumulator is initialised with 0 and two empty lists. From the remaining colours, we build the corresponding occurrence maps and then merge them with ColourMap.merge as follows:

• If a colour appears in none or only one map, it contributes nothing to white hits.
• If a colour appears in both, we take the minimum of the two counts: a colour can only count as a white hit as many times as it appears in both the secret and the guess. For example, if the secret has two reds and the guess has one red, only one white hit for red positions is awarded.

Finally, we fold over white_counts to sum the total and return the response using ColourMap.fold and return the response.

Finding the best guess

Our next objective is to find the best guess according to the minimax strategy.

Recall that we need to partition the candidates by the response they would give, then pick the guess with the smallest worst case. Again, we define a map module, but this time indexed by responses.

module ResponseMap : Map.S with type key = response = Map.Make (struct
  type t = response

  let compare = Stdlib.compare
end)

We then define group_responses, which partitions the candidates by the response they would give to a particular guess. The returned map binds each response to the number of candidates that would produce it.

let group_responses guess candidates : int ResponseMap.t =
  List.fold_left
    (fun response_map code ->
      let response = calculate_response guess code in
      ResponseMap.update response
        (function None -> Some 1 | Some group_size -> Some (group_size + 1))
        response_map)
    ResponseMap.empty candidates

The score of a guess, its worst case, is the size of the largest group. We compute it by folding over the response map and taking the maximum.

let score_guess guess candidates : int =
  let response_groups = group_responses guess candidates in
  ResponseMap.fold
    (fun _response group_size max_size -> max group_size max_size)
    response_groups 0

We also need to enumerate all possible codes in the game. Recall that the minimax strategy considers all 1296 codes as potential guesses, not just the remaining candidates since sometimes a guess outside the candidates yields a better score.

let all_codes : code list =
  let all_colours = [Green; Red; Blue; Yellow; Purple; Pink] in
  let rec loop n acc =
    if n = 0 then [ acc ]
    else List.concat_map (fun c -> loop (n - 1) (c :: acc)) all_colours
  in
  loop 4 []

The function loop above recursively builds all codes of length n (in our case n = 4). At each step, it prepends each colour to the accumulator and recurses with n - 1. When n reaches 0, we have a complete code. We use List.concat_map that applies a function to each element of the provided list and then flattens the resulting lists.

Finally, we tackle find_best_guess which proceeds as follows:

1. score every possible code against the current list of candidates,
2. find the minimum score,
3. filter to keep only guesses achieving that score,
4. prefer one that is still a candidate since it could win immediately.

let find_best_guess candidates : code =
  let scored_guesses : (code * int) list =
    List.map
      (fun guess ->
        let score = score_guess guess candidates in
        (guess, score))
      all_codes
  in
  let min_score : int =
    List.fold_left (fun acc (_, score) -> min acc score) max_int scored_guesses
  in
  let min_guesses : (code * int) list =
    List.filter (fun (_, score) -> score = min_score) scored_guesses
  in
  let in_candidates : (code * int) option =
    List.find_opt (fun (guess, _) -> List.mem guess candidates) min_guesses
  in
  match (in_candidates, min_guesses) with
  | Some (guess, _), _ | None, (guess, _) :: _ -> guess
  | None, [] -> assert false (* should not happen *)

Filtering a list is done using List.filter which returns the elements satisfying the predicate passed as argument. Picking a code that belongs to the candidates is done using List.find_opt which returns the first element satisfying the predicate, or None if none exists. Note that to compute min_score we initialise the accumulator with max_int so that any score will be smaller.

I always need to check the documentation to see if List.filter keeps or remove the elements that satisfy the predicate. If you have any mnemonic ways to remember that, please reach out to me :-)

Knuth's initial guess

Knuth found by exhaustive search that the optimal first guess is [Green; Green; Red; Red], the first pattern in numeric order among those minimising the worst case.

let initial_guess = [Green; Green; Red; Red]

Solving

We now have all the pieces to implement the solver. The function solve takes a secret and ends only after finding the secret. It iterates by maintaining the current guess and the set of remaining candidates. On the first turn, we rely on Knuth's initial guess. On subsequent turns, we use find_best_guess. After each guess, we filter the candidates to keep only those consistent with the response.

let solve secret : unit =
  let rec loop guess candidates : unit =
    let response = calculate_response guess secret in
    if not (response.black_hits = 4) then
      let new_candidates =
        List.filter
          (fun code -> calculate_response code guess = response)
          candidates
      in
      let new_guess = find_best_guess new_candidates in
      loop new_guess new_candidates
  in
  loop initial_guess all_codes

Conclusion

We implemented Knuth's minimax algorithm for Master Mind in less than 100 lines of OCaml, as confirmed by cloc. The key insight is that by always choosing the guess that minimises the worst-case number of remaining candidates, we guarantee finding any secret in at most 5 guesses.

$ cloc mastermind.ml
       1 text file.
       1 unique file.
       0 files ignored.

github.com/AlDanial/cloc v 2.06  T=0.01 s (183.9 files/s, 19496.4 lines/s)
-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
OCaml                            1             12              0             94
-------------------------------------------------------------------------------

The full code is available here.