[CaptainNegative]

I don't understand the point of this article, as it doesn't define an objective function. It just states a strategy that is only practically implementable for small board sizes (given the cited NP-completeness result) and then calls it good sans theorem or even conjecture.

I believe it is provably not the optimal algorithm for solving the problem under the minimax objective, and I have a hunch that (due to rounding issues) it is also not optimal for minimizing the expected number of guesses under even a uniform prior. So what does this actually accomplish?

[nsomani]

I agree with you. I agree with OP in the following sentences:

>We have now landed on our final strategy: start by figuring out the number of possible secret codes n. For each guess, calculate the number n_i' of codes that will still be viable if the Code Master gives response i in return. Do this for all possible responses.

But then I don't agree with:

>Finally, calculate the entropy of each guess; pick the one with the highest.

Why wouldn't we just pick argmin_{guess} sum{i in possible responses}{Pr[i] * n'_i} = sum{i in possible responses}{n'_i/n * n'_i} = sum{i in possible responses}{n'_i^2}? This is the guess that minimizes the expected size of the resulting solution space.