20-Aug-2005

Information theory applied to word puzzles

Filed under: math — jlm @ 19:12

You know those coin weighing puzzles? For the most part they can all be solved easily by using elementary information theory: At each step just make the weighing which maximizes your expected information gain. But what about word puzzles, can the math help us here?

Well, lately I’ve been playing this word game sometimes called “Jotto”. The idea is you pick a six letter word, and the person you’re playing against also picks a word. Then you each try to guess the other’s word. You do this by selecting a word, then they tell you how many letters match their secret word.

For example, if my word is “spaces” and you guess “guests”, I’d tell you that 1 letter was right. Then I’d get a chance to guess your word.

But what’s a good strategy? Well, I often try “throw out a lot of vowels” then once I think I have those pegged I play hot-and-cold with the rest of the word. But more ideally, you’d pick a word which divides up the word space as evenly as possible so you’ll get to small sets of possibilities quickly. Or put another way, you want to maximize the amount of information you acquire at each guess. Now, estimating information content is hard to do (how many words are one-letter matches of “spaces” as compared to zero-letter matches? Now take the logarithm…) but it’s easy enough for a computer to calculate, so I built a “Jotto Bot” which does just that. It plays pretty well — sometimes amazingly, but it doesn’t learn, so once you’ve found a word in the information boondocks, it’ll always do poorly on it… for now.

You can play with it here. Nicest is “you vs. computer”, but “computer guesses your word” shows you what’s going on behind the scenes.