# Cheating Hangman

A long while ago, inspired by Nick Berry‘s analysis of optimal Hangman strategy, I worked it backwards to find the hardest words to guess when playing Hangman. This week, I showed these to my colleague Grace – who turns out to be a fan of word puzzles – and our conversation inspired me to go a little deeper. Is it possible, I thought, for me to make a Hangman game that cheats by changing the word it’s thinking of based on the guesses you make in order to make it as difficult as possible for you to win?

The principle is this: every time the player picks a letter, but before declaring whether or not it’s found in the word –

1. Make a list of all possible words that would fit into the boxes from the current game state.
2. If there are lots of them, still, that’s fine: let the player’s guess go ahead.
3. But if the player’s managing to narrow down the possibilities, attempt to change the word that they’re trying to guess! The new word must be:
• Legitimate: it must still be the same length, have correctly-guessed letters in the same places, and contain no letters that have been declared to be incorrect guesses.
• Harder: after resolving the player’s current guess, the number of possible words must be larger than the number of possible words that would have resulted otherwise.

You might think that this strategy would just involve changing the target word so that you can say “nope” to the player’s current guess. That happens a lot, but it’s not always the case: sometimes, it’ll mean changing to a different word in which the guessed letter also appears. Occasionally, it can even involve changing from a word in which the guessed letter didn’t appear to one in which it does: that is, giving the player a “freebie”. This may seem counterintuitive as a strategy, but it sometimes makes sense: if saying “yeah, there’s an E at the end” increases the number of possible words that it might be compared to saying “no, there are no Es” then this is the right move for a cheating hangman.

Playing against a cheating hangman also lends itself to devising new strategies as a player, too, although I haven’t yet looked deeply into this. But logically, it seems that the optimal strategy against a cheating hangman might involve making guesses that force the hangman to bisect the search space: knowing that they’re always going to adapt towards the largest set of candidate words, a perfect player might be able to make guesses to narrow down the possibilities as fast as possible, early on, only making guesses that they actually expect to be in the word later (before their guess limit runs out!).

I also find myself wondering how easily I could adapt this into a “helpful hangman”: a game which would always change the word that you’re trying to guess in order to try to make you win. This raises the possibility of a whole new game, “suicide hangman”, in which the player is trying to get themselves killed and so is trying to pick letters that can’t possibly be in the word and the hangman is trying to pick words in which those letters can be found, except where doing so makes it obvious which letters the player must avoid next. Maybe another day.

In the meantime, you’re welcome to go play the game (and let me know what you think, below!) and, if you’re of such an inclination, read the source code. I’ve used some seriously ugly techniques to make this work, including regular expression metaprogramming (using regular expressions to write regular expressions), but the code should broadly make sense if you want to adapt it. Have fun!

Update 26 September 2019, 16:23: I’ve now added “helpful mode”, where the computer tries to cheat on your behalf rather than against you, but it’s not as helpful as you’d think because it assumes you’re playing optimally and have already memorised the dictionary!

Update 1 October 2019, 06:40: Now featured on MetaFilter; hi, MeFites!

×

1. I love everything about this – it even tells me when I mess up and guess the same letter twice!

2. And thus it was, on the last day of September, 2019, that the AI known as the Cheating Hangman became self-aware.

And the world was changed forever.

3. God it’s absolutely horrible. Well done.

4. Also, I really enjoyed the hangman strategy piece you linked to, although there’s still something about his strategy I’d push back on (for human players): I’d wager humans are better at pattern recognition in hangman when it comes to consonants, less so with vowels. For the word basic, I feel like B___C is easier than _A_I_. He lays out a strong optimal strategy for guessing the most letters in the fewest tries, but then what? Are those letters necessarily the best letters to help you work out the rest of the word?

Anyway, I like your awesome thing a whole lot and it’s super fun.

5. Dan Q says:

Indeed, sugar and confetti, you’re absolutely right (a fact that’s very clear when playing Hangman against any kind of computer player): cognitive factors are absolutely something that really affects how “hard” a game of Hangman is for humans. Those aren’t accurately reflected in the difficulty curve of Cheating Hangman or any other computerised hangman game I’ve seen.

Another bias I find, when I’m playing, is that it’s easier to think of words-that-start-with something than words-that-end-with something. For example, looking at 6-letter words in Cheating Hangman’s dictionary, there are 27 of them that end with “-YING”. There are only 23 that begin with “BAS-“. But I’ll bet that you can think of more of the latter than the former given 10 seconds on each, right? For me, at least, it feels as though words might be stored somewhat like a linked list in my mind, with each syllable hanging-off the one that preceded it. Similarly, playing I Spy with items whose second and third letters are specified instead of their first introduces a significantly heavier cognitive load!

I think you’re right about consonants. It’s probably also true that letters that touch one another, especially if their presumed-sound matches the sound they make in the completed word, help too. I’m really interested in the linguistics of how this affects games in other languages (e.g. in highly phonetic ones like Welsh, Russian, or Lojban), but unfortunately I’ve neither the time nor talent to research it further.

6. Nossidge says:

This is brilliant. My eventual arrival at “tsktsked” was honestly wonderful.

7. I was just checking my Recent Activity, saw Nossidge’s comment and went for another game. The result:

8. That is evil and wrong and ridiculous and great.

9. Theo Honohan says:

Doug McIlroy wrote a paper called “A Killer Adversary for Quicksort” in which the Quicksort algorithm comes up against a diabolical opponent that uses a similar strategy:
https://www.cs.dartmouth.edu/~doug/mdmspe.pdf

10. Dan Q says:

Just enjoyed this Wordle alternative that uses a similar strategy: https://qntm.org/files/wordle/index.html

11. Willy, C says:

It is a shame that there is not an option to NOT use ridiculously obscure words, including ones that definitely are not accepted words in most dictionaries. The cheating/changing the mind aspect would be MUCH more fun to play if it was words we know. But the way it is becomes a matter of just going in order from A to Z or QWERTY….which isn’t fun.

1. Dan Q says:

Not a bad suggestion: I might add that (if I can be bothered to filter the word list!). You’re welcome to fork it and edit the list yourself, of course! Thanks for playing.