Computer as Master Mind (1976) [pdf] | Hacker News Reader

Computer as Master Mind (1976) [pdf]

cs.uni.edu

33 pointsbrudgers4 comments

I've been studying the game of hangman (somewhat obsessively) for the last 6 or so years. I only recently discovered this Knuth paper via An Optimal Mastermind (4,7) Strategy and More Results in the Expected Case [1].

I think the reason it has captivated me for so long is because of the unexpected insight that choosing a known short-term failure or an increased chance of short-term failure (when optimizing for information gain) will result in quicker paths to your final goal AND decreased amounts of short-term failures.

My repo (currently being reworked) for simulating different strategies in hangman and battleship: https://github.com/chrisconley/hangman

[1] - https://arxiv.org/pdf/1305.1010.pdf

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

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

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.

Reply on news.ycombinator.com