I have created a Python solution to the cheating hangman problem and posted it there in the comments. I have a follow-up question though. Let us assume both the referee and the player posess the perfect knowledge about the list of words. What are the optimal strategies for both?
Programming Praxis suggests the length of the list of remaining possible answers is the key, the “score”. The cheating referee should keep this value as big as possible and the task of the player is to reduce it. I have a possible counterexample for this strategy at least from the referee viewpoint though.
Let us assume the possible answers are: [ abd, acd, abe, ace, bbb, ccc, ddd, eee, fff ] [ ‘abd’, ‘acd’, ‘abe’, ‘ace’, ‘dde’, ‘ded’, ‘edd’, ‘ede’, ‘eed’ ] and the player selected the letter “a” (please note that it possibly is a suboptimal choice on the part of the player). The referee has the following options:
- the letter “a” is in the word being guessed and 4 words: [ ‘abd’, ‘acd’, ‘abe’, ‘ace’ ] remain in the play
- the letter “a” is not in the word being guessed and 5 words:
[ bbb, ccc, ddd, eee, fff ][ ‘dde’, ‘ded’, ‘edd’, ‘ede’, ‘eed’ ] remain
The “keep word list as long as possible” strategy forces the referee to take option 2, with 5 words instead of 4. In the next step the player posessing the knowledge about the remaining words can select either “b”, “c”, “d”, “e” or “f” and instantly wins. “d” or “e” and the referee cannot cheat anymore.
Had the referee chosen option 1 the player could in its turn ask for either “b”, “c”, “d” or “e”. The optimal referee would respond with “not in the word” and the list of the possible answers would be reduced to two choices, e.g. [ ‘abd’, ‘abe’ ] if “b” was selected. Same in the next step, if the player chose “d” the referee would respond that the actual word was “abe”, similarly for the other case.
All in all the option 1 results in 2 body parts being added to the gibbet, while the recommended option 2 – just one. If this happens in the endgame that’s a difference between life and death 😉
Is this a valid counterexample or is it skewed by the fact that the player’s choice was itself suboptimal (addition: or perhaps all are equally bad)? How to implement the best strategy for the player and the referee? These are open questions for now.
Fixed the counterexample.
From C/C++ to Python 
You said: “In the next step the player posessing the knowledge about the remaining words can select either “b”, “c”, “d”, “e” or “f” and instantly wins.”
Your statement is incorrect. The player will make four more wrong guesses before the referee runs out of options and the player wins on the fifth guess.
If the referee chooses the 4-option, the player will get the answer in two wrong guesses: b will be wrong, c will be right, d will be wrong, and e will win.
Phil
I agree, my counterexample was wrong. I have since found a new one. My strategy finding algorithm confirms it – assuming the algorithm itself is correct.
I imagine that whatever strategy you use there is a counterexample that proves it wrong. However, with a normal English dictionary, the “maximum remaining set” strategy seems to work well. At least, I can tell you that I had a devil of a time testing my program to ensure that it worked properly when the player managed to guess the word!
Phil
[…] HomeAbout From C/C++ to Python Programming, algorithms, coding in practice « Cheating hangman strategy […]