4 ms·

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 t

by 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.
    - kd5bjo 15y ago
      That's only true if the worst case still lets you win the game. Otherwise, your opponent will pick the worst case word every time and you lose. As a zero-sum game, if the players agree on a dictionary beforehand, there is some Nash Equilibrium; I don't have the skill to figure out what it would be, but there would have to be some nonzero probability of guessing every word in the dictionary before running out of guesses.
      - dlss 15y ago
        Interesting. Thanks for your comment here and the one above. Although I firmly believe that hangman is a game, and hence the assumptions of game theory are in full effect, I had not considered the information theory take on things :) Since you asked about the Nash equilibrium for this case, here it is: In the event that you did not have enough questions to uniquely identify the possible words (and assuming that words with more letters than guesses are not allowed ie every word can be guessed with the right questions), the game becomes a matching game [http://en.wikipedia.org/wiki/Matching_pennies http://en.wikipedia.org/wiki/Matching_pennies]. First both players will work out the minimum number of question paths that can identify every allowed word. Any word in more than one set will be ignored as a dominated strategy by the hosting player. Then the guessing player will pick randomly between question paths, and the hosting player will pick randomly among the disjoint sets of words at the end of those question paths, with the specific word not mattering. You can see that once both players are picking between several options, with the entire game riding on their choice, the actual letter guessing becomes unimportant. The game itself resembles an unfair rock paper scissors. If the players were betting $1 per round, the expected value to the guesser is ($2 divided by the number of disjoint sets) - $1.
        kd5bjo 15y ago
        How does this work if there are multiple covering sets with the same (minimal) number of question paths? Does it matter which minimal covering set you evaluate, or does your strategy need to be some kind of superposition derived from all the minimal sets? Also, if there are some words that are never picked by your strategy, doesn't that open the door for an alternative set of question paths that only covers the now-reduced dictionary? (cue reference to the Unexpected Hanging Paradox) In many ways, the entropy is a heuristic for finding a good question path given the known probabilities for each word in the dictionary. The formula that I quoted above can be trivially extended for nonuniform distributions of the chosen words. It sounds like the Nash equilibrium would be designed such that (after eliminating dominated strategies), the expected information gain at each step would be the same for all question paths. I wouldn't want to have to prove it, though.
Natsu 15y ago
Doesn't this all assume that the opponent is choosing a random word? If they're trying to be evil, I'm sure they can pick words where each letter you get gives little information. For example, which letter do you guess if the puzzle is _og? You still have to go through bcdfhjln even after you've burned however many guesses getting that o & g.
- ars 15y ago
  I once wrong a hangman game that did this in reverse. The computer made sure to make you be as wrong as possible, while still ensuring your guesses were "correct". It had one problem in that it always tried to make sure you guessed wrong, but by carefully choosing your letters you could cause it to exclude tons of words because they contained the letter you guessed, leaving only a small number of possible words. It needed a refinement to occasionally allow you to guess correctly if that maximized the number of possible words remaining that still fit the prior guesses.
Too 15y ago
That would be trading risk for gain. Remember, if you pick a correct letter you will not loose any guesses, in other words you get another guess if your guess is right. It's not about finding the word in a fixed number of guesses. But otherwise you could also extend your method to increase the weight of letters appearing more than once in a word since that gives even more information gain.
tsewlliw 15y ago
I won't call out the company because at least until now they were still using the question (I got accidentally cc'ed on a subsequent candidates email), but last summer I got an interview homework question from a "who is hiring" post that was to solve hangman for a given dictionary. I implemented all of the strategies outlined here, and while they seemed impressed with the execution speed of my solution, they implied it could have scored better, saying it was only "average" in that regard. The thing is, at least for the dictionaries I had available, trying to weight for information gain only considering the guess correctness wasn't all that great a strategy. Even if you know 100% certain that the letter will be correct, its very likely to still cut the search space down by virtue of the pattern of letters, and in aggregate my strategy made no statistical difference. (+/- 1% depending on random seed). If I were going to try and improve my scores, I guess the next thing would be look at the distribution of letter-patterns for each remaining letter, but my intuition is that it just wouldn't be a big deal.

by lorax 15y ago

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.
  - kd5bjo 15y ago
    That's only true if the worst case still lets you win the game. Otherwise, your opponent will pick the worst case word every time and you lose. As a zero-sum game, if the players agree on a dictionary beforehand, there is some Nash Equilibrium; I don't have the skill to figure out what it would be, but there would have to be some nonzero probability of guessing every word in the dictionary before running out of guesses.
    - dlss 15y ago
      Interesting. Thanks for your comment here and the one above. Although I firmly believe that hangman is a game, and hence the assumptions of game theory are in full effect, I had not considered the information theory take on things :) Since you asked about the Nash equilibrium for this case, here it is: In the event that you did not have enough questions to uniquely identify the possible words (and assuming that words with more letters than guesses are not allowed ie every word can be guessed with the right questions), the game becomes a matching game [http://en.wikipedia.org/wiki/Matching_pennies http://en.wikipedia.org/wiki/Matching_pennies]. First both players will work out the minimum number of question paths that can identify every allowed word. Any word in more than one set will be ignored as a dominated strategy by the hosting player. Then the guessing player will pick randomly between question paths, and the hosting player will pick randomly among the disjoint sets of words at the end of those question paths, with the specific word not mattering. You can see that once both players are picking between several options, with the entire game riding on their choice, the actual letter guessing becomes unimportant. The game itself resembles an unfair rock paper scissors. If the players were betting $1 per round, the expected value to the guesser is ($2 divided by the number of disjoint sets) - $1.
      - kd5bjo 15y ago
        How does this work if there are multiple covering sets with the same (minimal) number of question paths? Does it matter which minimal covering set you evaluate, or does your strategy need to be some kind of superposition derived from all the minimal sets? Also, if there are some words that are never picked by your strategy, doesn't that open the door for an alternative set of question paths that only covers the now-reduced dictionary? (cue reference to the Unexpected Hanging Paradox) In many ways, the entropy is a heuristic for finding a good question path given the known probabilities for each word in the dictionary. The formula that I quoted above can be trivially extended for nonuniform distributions of the chosen words. It sounds like the Nash equilibrium would be designed such that (after eliminating dominated strategies), the expected information gain at each step would be the same for all question paths. I wouldn't want to have to prove it, though.

Natsu 15y ago

Doesn't this all assume that the opponent is choosing a random word? If they're trying to be evil, I'm sure they can pick words where each letter you get gives little information. For example, which letter do you guess if the puzzle is _og? You still have to go through bcdfhjln even after you've burned however many guesses getting that o & g.

ars 15y ago
I once wrong a hangman game that did this in reverse. The computer made sure to make you be as wrong as possible, while still ensuring your guesses were "correct". It had one problem in that it always tried to make sure you guessed wrong, but by carefully choosing your letters you could cause it to exclude tons of words because they contained the letter you guessed, leaving only a small number of possible words. It needed a refinement to occasionally allow you to guess correctly if that maximized the number of possible words remaining that still fit the prior guesses.

Too 15y ago

That would be trading risk for gain. Remember, if you pick a correct letter you will not loose any guesses, in other words you get another guess if your guess is right. It's not about finding the word in a fixed number of guesses. But otherwise you could also extend your method to increase the weight of letters appearing more than once in a word since that gives even more information gain.

tsewlliw 15y ago

I won't call out the company because at least until now they were still using the question (I got accidentally cc'ed on a subsequent candidates email), but last summer I got an interview homework question from a "who is hiring" post that was to solve hangman for a given dictionary. I implemented all of the strategies outlined here, and while they seemed impressed with the execution speed of my solution, they implied it could have scored better, saying it was only "average" in that regard. The thing is, at least for the dictionaries I had available, trying to weight for information gain only considering the guess correctness wasn't all that great a strategy. Even if you know 100% certain that the letter will be correct, its very likely to still cut the search space down by virtue of the pattern of letters, and in aggregate my strategy made no statistical difference. (+/- 1% depending on random seed). If I were going to try and improve my scores, I guess the next thing would be look at the distribution of letter-patterns for each remaining letter, but my intuition is that it just wouldn't be a big deal.