title: Optimal Algorithm for Winning Hangman
body: <p>In the game Hangman, is it the case that a greedy letter-frequency algorithm is equivalent to a best-chance-of-winning algorithm?</p>
  
  <p>Is there ever a case where it's worth sacrificing preservation of your remaining lives, for the sake of a better chance of guessing the correct answer?</p>
  
  <p>Further clarification of the problem:</p>
  
  <ul>
  <li>The selected word to be guessed has been taken from a known dictionary.</li>
  <li>You are given N lives, and thus have to maximise the probability of guessing all the letters in the word without making N <em>mistakes</em> (i.e. you may have an unlimited number of correct guesses).</li>
  <li>Each word in the dictionary has equal probability, for the sake of this exercise (i.e. the word is chosen randomly)
  <ul>
  <li>a harder exercise would be to come up with a strategy against a malicious, omniscient word-chooser (I am not asking that here)</li>
  </ul></li>
  </ul>
  
  <p>Motivation: This question is inspired by the interesting discussion at <a href="http://www.datagenetics.com/blog/april12012/index.html">http://www.datagenetics.com/blog/april12012/index.html</a></p>
  
  <p>They suggest an algorithm for solving the word game "Hangman" optimally.</p>
  
  <p>Their strategy can be summarised thus (edited for clarification):</p>
  
  <ul>
  <li>We can assume the word is drawn from a particular dictionary</li>
  <li>We know the number of letters in the word</li>
  <li>Eliminate all words in the dictionary that do not have the correct number of letters.</li>
  <li>Choose the not-yet-guessed letter which occurs in the largest number of words in the remaining subset of the dictionary.</li>
  <li>If this letter occurs, we know its location.</li>
  <li>If this letter does not occur, we know it does not occur in the word.</li>
  <li>Eliminate all words in the dictionary subset that do not fit exactly this correct pattern, and repeat.</li>
  <li>If there are 2 (or more) letters appearing equally often, the algorithm may perform a deeper analysis of the positions to determine which one is preferred (if that is reasonable?)</li>
  </ul>
  
  <p>At each stage, we are guessing the letter (not previously guessed) which occurs in the largest number of remaining possible words.</p>
  
  <p>There is some motivation to like this algorithm - we are always minimally likely to lose a life. </p>
  
  <p>But, it strikes me that this isn't necessarily the best solution: if we're trying to guess the word (within a certain number of lives), it's not necessarily always the case that the most frequently occurring letter is the most useful letter to distinguish between the remaining available words. </p>
  
  <p>I'm not sure, though, as it does seem opportune to avoid losing a life wherever possible. Will it ever be the case that optimal strategy permits us to sacrifice a life for a better opportunity to win?</p>
  
  <p>Question: is it the case that this greedy algorithm is equivalent to a best-chance-of-winning algorithm, or not?
  And can you prove it? </p>
  
  <p>An example dictionary+game would be ideal to show a disproof.</p>