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

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.

Adversarial Search

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

• alpha / beta pruning is used to reduce the search space without altering the outcome of the minimax search
• the game state consists of the set of letters guessed by Alice, the word partially revealed by Bob, and the number of lives remaining for Alice.
• along with the game state I track the set of all possible words consistent with the information so far revealed by Bob. This is required in order to decide what legal moves Bob has and to tell if Alice has won.
• the values of every node of the game tree evaluated during the search are cached (see: transposition table).
• the performance of alpha / beta search depends upon the ordering used when searching possible moves. I use two simple heuristics that are not very smart but are quick to compute:
  • For Alice's moves I simply pick the first letter of the alphabet that Alice has not yet tried, using the fixed letter ordering "etaonrishdlfcmugypwbvkxjqz" based on letter frequencies;
  • For Bob's moves, I always try the 'no' response first (if this is a valid move), and then the remaining responses in an arbitrary order, if any.

Results

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

Key