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.