jlm-blog
~jlm

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.

Friendly interface here and to see what’s going on behind the scenes look here.

2 Comments

  1. That Jotto bot was frustrating. I gave up after a few tries. Of course, it could be my bwain.

    Comment by Lonita — 20-Aug-2005 @ 22:43

  2. Hello from Russia!
    Can I quote a post in your blog with the link to you?

    Comment by Polprav — 21-Oct-2009 @ 21:39

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

Powered by WordPress