[somethingsright]

Have the list of choices at each step arrived at by brute-force, or is there some algorithm for that?

I think I read some algorithm for solving mastermind; but never tried understanding mastermind. For the related game of Cows-and-Bulls, there is a elegant algorithm that goes on reducing the list of candidates at each turn. Starting with 9999 potential numbers seems like a lot, but that solution also quickly terminates (7 guesses max, I think).

[hencq]

You can pick a guess for the code and evaluate it against every potential code and see what the reply would be (like BBWW). E.g. I pick 1122 and run it against all possible codes. If you group the number of results for every reply you essentially get a table that tells you for every reply how many possible eligible codes are left. You can then determine for each guess what the worst reply is you could get, namely the one that has the most eligible codes left. For your next guess you pick a code that has the best worst case scenario. Essentially it's minimax.

You can speed up the first step by realizing you don't need to test every code. E.g. 1122 and 1133 are essentially equivalent. You only have five unique choices for the first step 1111, 1112, 1122, 1223, 1234. If you run all codes against those 5, you'll get the first step. Continue doing it for the rest and you'll get the other steps.

[chrisconley]

Knuth worked on ensuring that the max number of guesses never went above 5. I believe that it's an algorithm, but I haven't looked into this enough yet.

Another way to optimize is for the avg number of guesses. The algorithm for this approach is to choose your next guess based on the guess that will give you the maximum amount of information gain (https://en.wikipedia.org/wiki/Entropy_(information_theory)#D...).