Algorithms (for Hanging) with Friends

Posted: January 15th, 2012 | Author: Alex | Filed under: Fun and Games | 2 Comments »

For the past few months, I’ve been playing Hanging with Friends with a few friends of mine. Hanging with Friends is a modified version of Hangman: your opponent gives you a word with one of the letters filled in and the rest left as blanks, and you have to guess the word one letter at a time without making too many mistakes. Once you try solving a word, you’re given a set of letters that you can use to construct a word that your opponent in turn tries to solve. The first person to fail to guess five words loses.

On a recent long, boring drive up I-5 I found myself thinking about Hanging with Friends, and what it would take to have a computer both solve Hanging with Friends puzzles well and come up with good puzzles of its own.

Solving Puzzles

Solving Hanging with Friends puzzles is pretty straightforward from an algorithmic point of view, as long as you have the dictionary of possible words handy. The program is given a template for a word as input (?op?er in the above example, where ? represents an unknown letter) and is expected to produce the next letter that the player should guess. One possible solution starts by filtering the dictionary for words that match the template; in the above example, “copter” would match the template but “spam” or “bacon” would not. It then counts the number of times each guessable letter occurs in this set of candidate words, and returns the letter with the largest count. The idea here is that an incorrect guess eliminates the largest number of candidate words.

If you don’t have a dictionary (or have to operate on the assumption that the dictionary isn’t perfect), things get a lot harder. You could do arbitrarily sophisticated things here; one thing that comes to mind is using a dictionary to learn what groups of English words tend to go together and guess those in an intelligent way. For example, if you’re given a word whose last three letters are “i??”, you might want to guess n, g, n, t, m or e because of the common word groups “ing”, “int”, “ine” and “ime”, or if you’re given a word where the revealed letter isn’t a vowel, you might want to guess each of the vowels. You probably would want to take frequency of occurrence of these common word groupings in the dictionary into account here as well. What you’d probably want is to train some sort of learning system to do this; there are a ton of different possibilities here.

Making puzzles

Picking good words to give your opponent is a little more tricky. Abstractly, you may want to pick words that are hard to solve. Typically these are words that are long, probably uncommon, and have a large number of distinct letters, since those words give your opponent more opportunities to make a mistake. You might also want to pick words with high scores. Hanging with Friends rewards you with some amount of in-game currency for each 200 points scored when creating puzzles for your opponent (using Scrabble-style scoring with letter scores and position-based score multipliers). This in-game currency can be exchanged for power-ups that make a word easier to guess by eliminating letters when you’re the one solving, or feeding you hard-to-solve words when you’re making the puzzle. In-game currency can also be used to purchase various cutesy avatars and whatnot in their in-game store. Of course you can purchase in-game currency with real money (this is where Zynga’s signature brand of devious social engineering rears its ugly head), but with two copies of an algorithm like this and a colluding friend, you could mine in-game currency as efficiently as possible. Not that I’m suggesting such a thing, of course.

To keep things as generic as possible, what you’re really looking for is the ability to pick a word with the maximum value for some cost function from the set of words that can be generated using the tiles you’re given. The algorithm when cast this way is also pretty straightforward if you have a dictionary at hand: filter the dictionary to the set of words you can legally play, give each word a score, and pick the highest-scoring word.

On Word Commonness

One additional ingredient that’s missing from the above algorithms is some notion of the commonness of a word. Intuitively, words that aren’t commonly used are harder to guess; in the above example of “?op?er”, I’m more likely to guess “copter”, “copier”, or “gopher” than I am to guess “mopier” or “dopier” because I use the former set of words more often than I use the latter. Word commonness is a tricky thing to get right; even if you had a corpus of information the size of the Internet from which to draw (which companies like Google do), the problem is complicated by the fact that many people have trouble with spelling and sometimes use one word when they mean to use another. Another complication is that the frequency of some words can vary substantially based on context; for example, computer scientists use the words “ping”, “packet” and “hash” more frequently than other people do. That said, a good first approximation would be to count the frequency of each of the dictionary words in the largest corpus of English text you could find.

The Code

I went ahead and implemented a simple version of the algorithms described above and put it on GitHub as hanging-tools.

Disclaimer (so that people won’t immediately stop playing Hanging with Friends with me): I didn’t use these tools to cheat in any of my Hanging with Friends games, although I did feed it old puzzles as test cases.

If you’re interested in playing around with this (or fixing my bugs!) I’d be interested to see what you do with it. That repository also comes with a copy of the ENABLE dictionary, which Zynga apparently uses as the basis for their word database.

No related posts.

---