Introduction

Hangman

Alice and Bob decide to play a game of hangman. Bob thinks of of a word which Alice attempts to discover by asking Bob a sequence of questions. Both players agree on a dictionary of valid words, the number of 'lives' Alice is allowed, and the length of Bob's word. The game consists of a number of rounds until either Alice or Bob is declared the winner.

Each round, Alice selects a letter from the set of twenty six lower case English letters {a, ..., z} and asks Bob if his word contains that letter. If Bob's word does not contain the selected letter, he must answer 'no', and Alice loses a life. If Alice has no lives remaining the game immediately stops and Bob wins the game. If Bob's word does contain the letter, he must answers 'yes', and then reveal to Alice the positions of all instances of the selected letter in his unknown word. Alice immediately wins the game once there is only one possibility remaining for Bob's word.

Worst-Case Hangman

The conventional approach to the game of hangman requires Bob to fix his word in advance. In this case there is no strategy involved on Bob's part during each round of the game. The only decision Bob makes during the game is his initial word choice.

However, the rules of the game provide no means of enforcing that Bob actually commits to a particular word! Bob is free to respond to Alice's queries however he chooses, provided his sequence of responses are always consistent with at least one possible word of the agreed length from the chosen dictionary.

The Worst-Case Hangman Problem

Assuming Bob does not commit to any particular word until forced, and that Alice and Bob both play optimally, who wins the game of hangman?

The outcome of the game depends upon the dictionary of words, the length of the unknown word, and Alice's budget of lives.

Solving It

Word Dictionary

I used this dataset of over 350,000 English words. To normalise the dataset I transformed all the words to lowercase and discarded any word that included characters outside of {'a', ..., 'z'}. This resulted in a dataset of 351,075 words after discarding duplicate words. Note that some of the remaining words are still rather dubious. For example:
  1. each individual letter "a", ..., "z" is a word of length 1;
  2. there are two seven letter words containing no vowels or 'y's: "pgnttrp" and "tsktsks". The latter is arguably reasonable while I imagine anyone attempting to play the former word during a game of scrabble might get a hard time from the other players.
Nevertheless, I blithely proceed using this dataset as the standard dictionary of words for hangman.

Adversarial Search

The problem can be posed as an adversarial search problem. I use a variety of approaches:
  1. Maximum depth minimax search over the game tree
  2. Brute force enumeration over Alice's strategies when Bob plays the fixed strategy of answering 'no' to all questions
  3. Solving it manually
Some details of the implementation of the minimax search approach: The second approach of brute-force enumerating over Alice's moves cannot solve the problem in general since Bob is restricted to playing a fixed strategy that may not be optimal. But in special cases where Alice has a sufficiently small number of lives it may provide a quick (faster than minimax) demonstration that Alice cannot possibly win.

Results

Here's the table of results obtained so far. See below for the key.

LivesWord Length
12345678910111213141516171819202122232425262728293031
0LLLLLLLLLLLLLLLLLLLLLLLLL-LLL-L
1LLLLLLLLLLLLLLLLLLLLLLLLL-LLL-W
2LLLLLLLLLLLLLLLLLLLLLWLWW-WWW-W
3LLLLLLLLLLLLLLLLLLLWWWWWW-WWW-W
4LLLLLLLLLLLLLLLWWWWWWWWWW-WWW-W
5LLLLLLLLLLLLWWWWWWWWWWWWW-WWW-W
6LLLLLLLLLWLWWWWWWWWWWWWWW-WWW-W
7LLLLLLLLLWWWWWWWWWWWWWWWW-WWW-W
8LLLLLLLLWWWWWWWWWWWWWWWWW-WWW-W
9LLLLLLL?WWWWWWWWWWWWWWWWW-WWW-W
10LLLLL??WWWWWWWWWWWWWWWWWW-WWW-W
11LLLL???WWWWWWWWWWWWWWWWWW-WWW-W
12LLL????WWWWWWWWWWWWWWWWWW-WWW-W
13LLL???WWWWWWWWWWWWWWWWWWW-WWW-W
14LLL???WWWWWWWWWWWWWWWWWWW-WWW-W
15LLL??WWWWWWWWWWWWWWWWWWWW-WWW-W
16LLL??WWWWWWWWWWWWWWWWWWWW-WWW-W
17LL???WWWWWWWWWWWWWWWWWWWW-WWW-W
18LL???WWWWWWWWWWWWWWWWWWWW-WWW-W
19LL??WWWWWWWWWWWWWWWWWWWWW-WWW-W
20LL?WWWWWWWWWWWWWWWWWWWWWW-WWW-W
21LL?WWWWWWWWWWWWWWWWWWWWWW-WWW-W
22L?WWWWWWWWWWWWWWWWWWWWWWW-WWW-W
23L?WWWWWWWWWWWWWWWWWWWWWWW-WWW-W
24LWWWWWWWWWWWWWWWWWWWWWWWW-WWW-W
25LWWWWWWWWWWWWWWWWWWWWWWWW-WWW-W
26WWWWWWWWWWWWWWWWWWWWWWWWW-WWW-W

Key

SymbolDescription
'W'Alice (guessing player) wins
'L'Alice (guessing player) loses
'-'no words of this length
'?'game outcome unknown