Mark Gritter (markgritter) wrote,
Mark Gritter
markgritter

Hangman

The DataGenetics blog has a bunch of analysis of games (showing off their big-data skills!) but I think this Hangman discussion is off the mark. It assumes that the best strategy is to guess the most-likely letter first.

But, the best strategy is the one which is most likely to win (or wins in the fewest possible moves.) Knowing that 'S' is the most likely letter to occur for a five-letter puzzle does not mean that it's the first guess you should make. Other letters might lower the depth of the search tree by providing a better branching structure.

Here's a toy example to make the point. Say you're playing with only the vocabulary SEE SAW SET SEX TEA ASH PAW SIS

'S' is the most frequent letter (6 words, 7 instances) compared to 'A' (4) or E (4 words, 5 instances). But if you guess 'S' first:

SxS -- SIS
Sxx -- SEE SAW SET SEX (need two guesses--- neither E T or X are sufficient.)
xSx -- ASH
xxx -- TEA PAW (guess 'A' next, done)

then the tree has depth 3. But if you guess 'E' first:
xEE -- SEE
xEx -- SET SEX TEA, guess T next and done
xxx -- SAW ASH PAW SIS, guess S next and done
Tags: games
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment