7 ms·

A Better Strategy for Hangman

• jh3 15y ago
  > There are no two letter words containing the letter C, Q, V or Z. Does 'qi' count? http://www.merriam-webster.com/dictionary/qi http://www.merriam-webster.com/dictionary/qi I know it counts when playing Words with Friends... I also think 'za' is valid when playing Scrabble type games, but 'za' technically isn't a word.
  • streptomycin 15y ago
    qi and za are recent additions to the Scrabble dictionary, but in any reasonable friendly word game they wouldn't count because they're not in common usage. IMHO they also significantly changed the gameplay of Scrabble for the worse by making it much easier to get rid of the z and q tiles.
  • davnola 15y ago
    IIRC "zo" is also valid. It's a Tibetan yak hybrid. Hmmm... Yak butter tea.
    • waqf 15y ago
      In case you cared, "zo" is valid in the UK/international Scrabble wordlist, but not in the US (yet, until we persuade them to use the same wordlist as everyone else).
• squeakynick 15y ago
  Good comments. Being paranoid, I double checked the database I used! Neither 'qi' nor 'za' are in the database I used. I'm not arguing that they are, or are not, words. I'm just saying that they were not in the dictionaty file I used :)
• hythloday 15y ago
  It's an interesting article, but I would have thought that the best* letter to guess is the one that appears in as close to 50% of the possible words as possible, rather than the most likely to appear, given that the hangman is drawn per error, rather than per guess. Is my reasoning wrong? * assuming as he does at the bottom the existence of a computer.
  • Jabbles 15y ago
    It depends whether you care about minimising the number of errors, or just wish to keep it below 11 - thereby minimising your chance of losing. These are subtly different and depend on your "reward function".
    • beza1e1 15y ago
      If you want to minimize the number of errors, you should try the letter with the most information. In other words, minimize the search space. That is what hythloday suggested.
      • Someone 15y ago
        I do not think that is correct. Let's say that, at some time, you know the word has an E, with 99% probability at position 1 and with 1% at position 2. You also know there is 50% chance that the word has an O. I would guess the E, because it comes free, even though it is not the one that gives the most information. You must somehow weigh information gain against risk.
        • kd5bjo 15y ago
          The simplest way I know of to do that is by a weighted linear combination. Both information gain and risk are quantifiable; one in bits and the other in probability (or log-odds which is also bits). Then the problem reduces to finding appropriate weights, which can be done with your favorite n-dimensional search algorithm. It may also be useful to consider how many remaining incorrect guesses there are in the game.
        • beza1e1 15y ago
          Assuming there is always a letter with a 50% chance and we choose wrong 11 times in a row. One more and game over. At this point we have 11 Bits of information, which is enough to distuingish between 2048 words. Actually, we should be correct 50% of the time. Which means 22 Bits of information or 4194304 words. Additionally, we know the length of the word. The english dictionaries seem to have between 400k and 1000k words [0] of all word sizes. With 22 Bits we get 4000k words. We do not have to worry about getting hanged using the information-reduction algorithm. ;) [0] http://hypertextbook.com/facts/2001/JohnnyLing.shtml http://hypertextbook.com/facts/2001/JohnnyLing.shtml
• vasi 15y ago
  This is great, but it's just a first-order strategy! Once your opponent knows you're following these (quite rational) rules, she could pick words where the rules fail particularly badly. I look forward to seeing your analysis of how to deal with that :)
  • jerf 15y ago
    The strategy given isn't to solve the puzzle, but to get at least one letter on the board. So if you look at the table at the end, the worst case is a three-letter word that only contains a K out of the letters given, which is the worst case scenario on that entire board. Assuming your opponent sticks to the dictionary there is no way for them to ruin this strategy, only push you into the worst cases given, which once you figure out what's going on will play to the guesser's advantage, not the word-chooser.
  • user24 15y ago
    I was hoping for a little list at the end saying "By the way, if you're playing against someone who's using this strategy, the best word to play is: xyzzy" (or whatever word it actually would be)
• eshvk 15y ago
  Very cool. I was implementing Hangman a few weeks back and I figured out the first strategy, use the frequency distribution for the specific length to initiate your guessing. However, I thought about but discarded the second strategy of conditioning on the previous wrong/right guesses and selecting words and then doing a histogram of the letters. Thinking back, I find it interesting that thinking about it from a complexity point of view made me dread that approach because it becomes significantly more expensive to do the recomputation of frequency distributions compared to blindly uses the naive independence assumption and I was not sure how much of a win I would get by adding that bit of optimization.
• r00k 15y ago
  I loved this blog post (and the other one I read, about Battelship), so I wondered who was behind these great posts. Their homepage says this "DataGenetics is a technology consultancy specializing in unlocking the value stored in large databases. Using a variety of techniques we can mine the trends in your data to help you maximize your marketing and advertising campaigns." Damn. Yet another group of smart folks focused on more-effective advertising.
  • apawloski 15y ago
    That's where the money seems to be. It's a shame, but I can't blame groups like these.
    • rbarooah 15y ago
      Why not? Do you think people have no responsibility for their choices other than to maximize their financial gain?
      • apawloski 15y ago
        No. I don't believe that a person's intelligence level makes it appropriate for any other party to decide what she should and should not do. I also question what "responsibility" an intelligent person has in their career choices. Responsibility to whom? Society? Should they be out curing cancer instead? I cannot accept the notion that people in the aforementioned position have a responsibility to anybody but themselves and their families.
        • rbarooah 15y ago
          I never said anything about intelligence level or other parties deciding what people should do. Are you able to consider the idea that someone's responsibility to themselves and their families might lead them to make decisions other than maximizing financial gain? Also - I'm curious as to why you think family members are a special case?
• rgejman 15y ago
  This seems like a problem ripe for solving with a markov model.
• rgejman 15y ago
  This seems like a problem ripe for solving with a markov model.
• onemoreact 15y ago
  Cool, but assumes all words have an even probability. Vs a week player the ideal word list should only include 'common' words. Vs an ideal player you need to assume they will pick from the list of words that you least likely to guess using optimum play. Generically, optimum play ends up with a somewhat random list, aka 90% of the time pick E, 10% of the time pick I etc. PS: Actually generating this list is a 'hard' problem and vary dictionary dependent, but you can probably get reasonably close using some sort of genetic algorithm and a enough simulation time.
  • eru 15y ago
    > PS: Actually generating this list is a 'hard' problem and very dictionary dependent, but you can probably get reasonably close using some sort of genetic algorithm and a enough simulation time. Sounds like a challenge. I don't think, given a dictionary, finding the ideal strategy for both parties will be that challenging. It's a fairly straightforward two person zero-sum game. You can either model it assuming hidden information, or concurrent play. (Which is basically the same here.) As an interesting variation, you might allow the chooser to cheat: I.e. don't make them write down the word in the first place, just require their play to be consistent.
• nraynaud 15y ago
  Playing hangman against Sheldon Cooper was a mistake in the first place :)
• lorax 15y ago
  An even better strategy would be to weight your guesses towards the most information gain. If a letter appears often, but is in the same position most of the time, getting it won't help you as much as getting a letter that appears in fewer words but in more varied positions. Doing a quick check of 5 letter words in my /usr/share/dict/words file I find: S: 659,62,267,260,2282 E: 122,829,448,1254,679 A: 252,1201,678,410,307 That is, S, when it appears, is heavily skewed towards the last letter in the word, finding it won't help you figure out the word nearly as well as finding the more evenly distributed E or A.
  • dlss 15y ago
    This is a good insight. To formalize it: each question segments the words into 2^max_word_length groups of various sizes, and we seek to minimize the worst case number of questions still needed, regardless of which answer we get back. Which, for the ispell words list, appears to be 'e' :( edit: which was the solution found for the suboptimal method in the article, and which is not present for words in the corpus 25% of the time code at http://pastie.org/3693750 http://pastie.org/3693750
    • kd5bjo 15y ago
      Not quite; you don't want to minimize the worst case, but the expected case. That comes from maximizing the entropy of the result set ( https://en.wikipedia.org/wiki/Entropy_(information_theory) https://en.wikipedia.org/wiki/Entropy_(information_theory) ). To calculate this, take the sum of -p * log(p) for all patterns of the guessed letter, where p is the proportion of words in the candidate set that have this pattern.
      • eru 15y ago
        > Not quite; you don't want to minimize the worst case, but the expected case. That depends on your opponent. In game theory you often assume that your opponent plays against you and as good as they can, so you'd go with the worst case.
        • 15y ago
• jtheory 15y ago
  I kept waiting for the other foot to drop, and it never did. This is great if you're playing hangman against a computer. Probably, you're not. You're playing against a person, who probably has some sense of your strategies. Even when I was a kid, we didn't play hangman by choosing random words. What's the fun in that? You notice how the other person plays, and in the next rounds you pick words that break their strategies. You notice they are doing the "common letters" or even "common vowels" strategy, and you give them "lynx". Or you trick them with a word that has a few easy-to-get letters, but is going to be hard to guess the last few because there are so many possible matching words -- I had a great one that I forget now... maybe "budder"? Did everyone really play with randomly-chosen words? What a waste.
  • eru 15y ago
    You can repeat a similar analysis like they did against an opponent who chooses carefully and knows your strategy. With the theory of two person zero-sum games you can even prove that there's a perfect strategy both for the guesser and the chooser each that doesn't get worse if the other party knows it. (Hint: the strategies will involve random selection with carefully weighted probabilities.)
  • hluska 15y ago
    Great comment - in hangman, choosing letters solely on the basis of data (no matter how complete the data or how compelling the study) is a highly predictable (and thus highly defeatable) strategy. Of course, this analysis has a counterpoint. If I try to pick words strategically, I suspect that my words would begin to follow patterns...
    • jtheory 15y ago
      To be sure. I recall we'd mostly stick with the two strategies I mentioned (words with most rare letters, or words in very common patterns)... then when you're settling into a pattern (and your opponent's first guesses are "x" or "q" or similar), throw in something like "teat" to throw them for a loop. We did have one minor rule change -- definitely more than 11 line segments to hang the man. If you had a really good word, and wanted to draw out the torture, you'd start drawing in facial features, fingers... It also adds a bit of artistic fun to the game; you don't even have to be hanging a "man" if you want to get creative; it could be a giant insect, horse, whatever. It would still be pretty clear who was "winning" by how long the string of crossed-out letters were by each round.
• grandalf 15y ago
  Does this mean that RSTLNE on wheel of fortune is non-optimal too?
  • lorax 15y ago
    If you aren't taking into account the length of the word, then it looks like the optimal choice of 5 consonants and 1 vowel. Look at his section titled "First refinement" the most common letters were (in order) "ESIARNTOL" Eliminate all but the first vowel and you get ESRNTL, the same as WoF.
  • dwd 15y ago
    Given your perception can generally fill in the vowels - picking any early on would seem non-optimal.
    • grandalf 15y ago
      I think it's more a goal of eliminating uncertainty about which letter occupies a slot. For example, if I have guess T and E and see _ _ E as the word I know it's not the word "The".
• kd5bjo 15y ago
  This came up as an pre-interview employment challenge that I did a few months ago. I've uploaded my code here: https://gist.github.com/2242816 https://gist.github.com/2242816. I could make good arguments for both "most likely to be present" and "most information gain", so I implemented a mixed strategy. I calculated the information gain (in bits) and the probability of a correct guess, then used a linear combination of them to determine which letter to guess. Additionally, the weights changed over the course of the game so that correct guesses were valued more as incorrect guesses became more scarce. To determine appropriate weights, I ran a crude Monte Carlo simulation. The final weights I ended up with were 0.60:0.03 with no incorrect guesses and 0.54:0.69 once there aren't any strikes left. (bits information gain : p(correct guess))
• brownbat 15y ago
  There are lots of good further caveats in this thread. We should have a hangman AI tournament.
• K2h 15y ago
  Two possible improvements, that I think may be original (thought I probably missed it in the article and comments) 1) A hit or miss of a letter tells you a lot about what the new subsequent optimal guess is. You could make a flow chart (a really big one) that shows you the optimal letter to call out next based on what has hit and missed. 2) the position that a letter has hit tells you a lot about the target word. if you have a computer, the regex becomes trivial to identify the next optimal letter to guess. an 'optimal' table could be generated based off this pattern, and it would be a huge table. I kept feeling like every step of the way it was an infomercial, 'but wait... there's more!' and I like that, it got me thinking. I'd love to have my hangman bot go head to head with yours on random words. that would be a fun little project.
• hammock 15y ago
  Instead of a table at the end, what if you were to boil it down to a single list of letters that I can easily memorize? You could do this by weighting the final table with the number of 1-, 2-, 3-, etc -letter words in the dictionary. Put another way, what are the letters I should guess when I don't know the length of the word? While it wouldn't be perfect strategy, it would be easier to execute.