I became obsessed with Jotto when I learned it from some friends in high school (the friends had learned it, for some reason, in Latin class). Jotto is a word game where two players try to guess each other's secret five-letter word. Each guess must be a valid five-letter word, and a guess is scored by reporting the number of letters in common with the secret word. Unlike Mastermind, order is not important (I plan to address secret words with anagrams in a later post). Here is a sample (naive) game, from the perspective of one player:
guess score ----- ----- sport 2 spore 3 spare 2 pared 2 scare 2 scape 1 joker 3 loner 3 grove 4 gorge 3 hover 4 mover X
That's how I played the game for quite a while. At some point, in an effort to make the game more of a challenge, I came up with a variant that I call Twisted Jotto. In Twisted Jotto, each guess you make must be a possible secret word based on the information from the previous guesses. So in the above game, "spore" would not have been a legal guess in Twisted Jotto, since its score against "sport" is 4, not 2. Here is a sample Twisted Jotto game (borrowed from my article in The Perl Review):
guess score ----- ----- trios 1 false 3 slang 2 swell 2 passe 3 abase 2 pleat 4 paler 5 pearl X
It didn't take me long to realize that Twisted Jotto enabled me to make fewer guesses to find the secret word (even if it took more time to come up with a guess). Twisted Jotto then became just the smart way to play Jotto (although the smart player will abandon it in certain situations, for example, when you know four letters and there are a number of possibilities for the fifth).
Another variant of Jotto is to play with different word lengths. I first did this with six-letter words, and my friend Matt named this Count Rugen (the six-fingered man in The Princess Bride). Using six-letter words is certainly more challenging than using five-letter words. Here's a sample game (using Twisted Jotto rules, of course):
guess score ----- ----- clamps 1 boughs 1 trines 3 sevens 3 defies 3 bindle 4 belier 2 ceding 5 inched X
And of course one could keep increasing the number of letters, making the guesses harder and harder to find. That is maybe more challenging but is starting to seem more like work than fun. Enter another variant. My friend Debby came up with this one, called X-Jotto. In X-Jotto, the number of letters in the secret word is unknown. I decided that the word length could be from three to eight letters. So, even if the word has eight letters, you can test letters by guessing a three-letter word. Here are some sample X-Jotto games (for sanity's sake, I didn't use the Twisted Jotto rules):
guess score ----- ----- flack 1 trudges 3 hominy 0 wares 3 pared 2 frees 2 berserk 4 levers 6 revels X guess score ----- ----- flank 0 trudges 4 chimp 1 boxy 1 crusty 2 brides 4 showered 6 reshod 6 horsed X guess score ----- ----- flank 0 trudges 1 chimp 1 boxy 0 pew X
Now, if you study the above games closely, you will see that I started out the same way in all three games, guessing three or four words that have no letters in common (flack, trudges, and hominy for the first game and flank, trudges, chimp, and boxy for the other games). This gives a minimum number of letters that the secret word must have, which makes it a bit easier to think about (and led me to a five-guess win in the third game).
Now, while this might make it easier to think about, is it a good strategy for minimizing the number of guesses? To find out, I had my Jotto program play itself at X-Jotto 100 times with two different guessing strategies. The first strategy is simply Twisted Jotto rules: it eliminates any words that don't score correctly, and then it randomly picks one of the remaining words. The second strategy is the same except that the first four guesses are always the set of four words from the second and third games above.
The first strategy found the word in an average of 9.15 guesses (standard deviation = 1.97), and the second strategy found the word in an average of 9.76 guesses (standard deviation = 1.95). Now, I don't know much about statistics, and it is a small sample size, but my gut tells me that the purely random method is going to be better overall. However, that less-than-one-guess difference might make it worthwhile to use a starting set of words, so that you can more easily get your brain around the search space. More tests are in order (the first one being trying the three-word start from the first game above).
I know this blog isn't really about word games, but I thought I'd put this up and see if anyone else has the kind of interest in word games that I do. Unless I get smacked down for posting about this, I'll do a few more Jotto-related posts, and possibly some related to other word games. If nothing else, it's made me pick up my Perl Jotto programs again, which has been a lot of fun.
The version of Jotto that I've played was much more Mastermind-like.
Each letter in both the hidden word, and the guesses had to be unique (So 'weird' is valid, but 'which' isn't). The response was also not just a simple number, but a pair of numbers representing the number of correct letters in the right place, and the number of letters in the wrong place.
I've heard of playing it where there could be no repeated letters, but I hadn't heard of the Mastermind-like scoring. Certainly would be a different game.
An entertaining twist on Mastermind. I'll have to play it with friends sometime.
As an AI programmer it would seem to be a simple decision tree problem. For each guess you compute the set of words it could be and then for each word you compute the subsets of words that would be generated for each possible response. The best guess is the word which creates the most balanced division, based on expected information gain.
So, for a 2-letter example, in my /usr/dict/words there are 67 words:
ad ah am an as at ay be by cs dB do eh em es ex fa go gs ha he hi ho id if in is it kW kc ks la lo ls ma me mi ms mu my no nu of oh on or ow ox pH pa pi re rs sh so ti to ts uh um up us vs we ya ye yo
If we guess 'to' we get three sets:
result: 0
words: 51
ad ah am an as ay be by cs dB eh em es ex fa gs ha he hi id if in is kW kc ks la ls ma me mi ms mu my nu pH pa pi re rs sh uh um up us vs we ya ye
result: 1
words: 15
at do go ho it lo no of oh on or ow ox so ti ts yo
result: 2
words: 1
to
Before the guess infomation (taking log base 2):
H_before = -log 1/67
= 6.07 bits
Assuming all words are equally likely to be chosen, after the guess we would expect to have information
H_after = - 51/67 log 1/51 - 15/67 log 1/15 - 1/67 log 1
= 5.19 bits
Which indicates an information gain of 0.87 bits.
You could then repeat this process for every other word and find the one with the biggest information gain (left as an exercise to the reader). If you suspected your opponent was biased towards some particular words, you could weight the probability distribution in the H_after calculation appropriately.
This is still only doing 1-step greedy search and so isn't optimal. There may be some sequence of guesses that give a combined improvement that far exceeds their apparent individual values and these strategies will not be found.
Kevin, I dunno why you'd worry that word-game posts wouldn't be welcome here. The Gameshelf in interested in the study and critique of the whole field of games, and word games are a venerable and important part of it.
Malcolm, thanks for the AI lesson (a field I am very ignorant about). I had tried something similar the last time I got the Jotto programming bug (just for the normal version, not X-Jotto), but testing made only a slight difference over the dumb version, and it took so bloody long to calculate that I ended up giving up on it. I've had thoughts lately about precalculating the score of every word against every other word, since I assume a lookup would be a lot faster than scoring the words every time (the easy five-letter dictionary has about 4000 words, and the full five-letter dictionary has about 12,000 words). This would then let me experiment more quickly with various tweaks to algorithms. If I get that going again, I'll post results and ask for advice.
Jason, yeah, I wasn't actually worried. It was more a rhetorical device as some kind of attempt to ward off any possible questions of people not being interested (and possibly with a smidge of comment-fishing). As I thought about it more after posting, I realized that of course this kind of obsessing about a game, even a fairly simple word game, would be welcome here. You can expect further similar posts from me in the near future.