Cheater's hangman

Factual Questions
1

Assume that you’re playing a game of hangman with me. But I’m a morally unscrupulous bastard and I cheat. Instead of thinking up the word before the game, I let your guesses determine which word I finally pick.

For example, if the game board was bea_ and you had two guesses left, there would be no way for you to win the game. If you guessed d and n, I would say my secret word is beat. If you guessed n and t, I would say it was bead etc.

Now, as a cheater, is there any way for me to guarantee that I win the game? Is there a set of moves I could make such that you could never win? Generalising, given a word list and a fixed number of wrong guesses allowed, what’s the algorithm to generate whether this word list favors the cheater or the guesser?

2

This one sounds like a fun problem. I think the key will be deciding what to do on the first few moves. If 2/3 of the words have an s in them, and I guess s, do you say it’s there, or not? If you say it’s there, I get a letter. If you say it’s not, I’ve effectively cut 2/3 of the possibilities out of the running.

Also, for the purposes of this problem, would it be acceptable to say that there are 26[sup]n[/sup] combinations, instead of using an actual word list? If you did that, you’d have to assign a percentage of the likelyhood a letter will be in a given combination.

3

I think you have to consider what fraction of possible words have an S at the same position (and consider words with more than one S separately). Because you have to tell the player the position of the S, not just that it is present. So your choice is between 1/3 of possible words that don’t have an S and, say, 1/6 of words that begin with S.

4

In other words, if the player says “s”, it might just be best to stick it at the end of the word. :wink:

Good point, though.

5

The guesser could eliminate most words by starting with the most commonly occurring letters in English (just as in normal Hangman). Naming the vowels A, E, I and O and the consonants N, R, S and T will enable most words to be identified. So the cheater needs to avoid too many of these. A word like SYZYGY or RHYTHM might be good.

Oh, and the cheater shouldn’t pick a word that is too long, they are more likely to be uniquely guessable with a few letters missing.

6

The point is not to choose a word in advance, though. If you decide on SYZYGY and the player says Y, you’re sunk straight away. You don’t have to settle on the actual answer until the end. The question is how long can you keep the number of possible answers as big as possible.

7

Not really… Picking words where all the vowels are Y is a not-uncommon tactic in Hangman (even the honest kind), so someone who hasn’t gotten any hits with A or E might think to jump straight to Y. And when you’ve got _y_y_y as your word, just how many possibilities are there?

8

You’d probably want to have it such that for any one letter placed, it would run the possibilities on the remaining positions. When the person selected another letter, you’d do it so that if the letter he chose wasn’t the one that left the most possible words there are, then they have to add to the hangman.

Since the goal is to leave the greatest number of possibilities, you’d want to have the number of slots be equally to whatever the greatest number of English words have as their length. Probably five. Whether this would guarantee victory or not, I’m not sure. Probably.

With a program accessible dictionary, you could test/prove it pretty easily.

9

I thought about this too much:
First, the number of guesses has to be less than the number of letters in the alphabet (26 in standard English), otherwise the guesser wins every time. Also, the number of words in the list has to be greater than the number of guesses, or else the guesser wins every time also.

Then the answer of who wins depends completely on the allowable word list. For instance, if the list is all 26 one-letter words, then the cheater can always require 26 guesses (and so always wins). More generally, for any number of guesses (less than the number of alphabet letters), with the number of allowable words greater than the number of guesses, there exist lists that allow the cheater to always win.

On the other hand, for any size of list, a list does exist that allows the guesser to always win in one guess {a, aa, aaa, aaaa, …}. Or, if the words are all the same length, in two guesses {aaaa, aaab, aabb, abbb, bbbb}

So for any non-trivial number of guesses and size of list, there exist lists that allow the cheater to win, or that allow the guesser to win.

It’s possible to check any list to see who would win, but I can’t think of any way other than brute force, stepping through all possible guesses until you get a sequence of guesses that eliminate all but X words, where X< # of remaining guesses, or you’ve gone through every possible sequence of guesses and the cheater has always had at least two possible words left.

10

How many guesses does a person get? 6?

Make your word a four letter word. As they pick vowels always pick the last one they choose. A, E, I, O, U. Make the word _ U _ _. They’ve just knocked out 4 guesses.
E, I, U, A, O. Make the word _ O _ _ . Again they’ve knocked out 4 guesses.

Once they start the consanants there are tons of words that would fit into each scenario. If they pick a letter in one of those words say NOPE and eliminate those words from your list.

There’s no way they could win in six guesses.

11

This sounds like a good strategy. The contestants on Wheel of Fortune usually choose RSTLN as consonants. X/Y/Z are pretty rare…maybe foxy/boxy? Something with a q is tempting, but then you’re committing to U and another vowel.

12

If only six wrong guesses are allowed, then that would work. Back in my hangman playing days ISTR it was more like eleven or thirteen, but you should still be able to force a win.

It’s not always best to hold out until the player forces you to yield another letter, though. If you’re at **TED, say, with all other letters still available, the possible answers are something like

ACTED
BATED
CITED
FATED
GATED
HATED
MATED
MUTED
NOTED
OUTED
RATED
SATED
SITED
VOTED

If the player now guesses A, you’re better off going to *ATED, from which there are still seven possibilities. If you decline the A it only leaves you with six possibilities, some of which can be eliminated in pairs or triples (e.g. player guesses O).

13

Yes, but declining the A also uses up one of the guesses, and earns the guesser a body part on the gallows.

Hampshire’s strategy looks reasonable, but people don’t always go for the vowels first. A guesser might, for instance, reasonably choose to start with ETAOIN SHRDLU. So you decline the E, but what do you do with the T?

14

If you accept the A to go to *ATED, you get a guaranteed run of six wrong guesses. If you don’t, the guesser only has to make two further wrong guesses by my calculations.

We have to establish whether the guesser is aware of the setter’s “cheating”. If so, I think the best approach for the setter as the number of allowed guesses rises is to accept common letters, and place them in their commonest positions, while declining letters like Z which restrict the possible answers too much. The tricky part is what to do with middling letters such as M.

15

As concerns the question of guarantees (forced wins) rather than probable play, it doesn’t matter; just assume the guesser does the worst possible think for the cheating selector at every turn.

16

Er, “thing”, not “think”.

17

The corollary to cheater’s hangman is to prove that hangman is a solvable problem. If even a cheater can’t force you to lose at hangman, then you’re guarenteed a win.

Thus, another way of framing the problem might be: Given a word list, what’s the minimum number of guesses necessary to force a win?