Training a computer to play Jotto
I've always liked word games like Scattergories and Scrabble, they tend to be a good mix of creativity and strategy. When I had to decide on a final project for a graduate-level artificial intelligence class last term it was a perfect opportunity to make a program that played a word game. But Scattegories and Scrabble are both trivial for machines to play—their decision trees are narrow enough that you can easily perform an exhaustive search for the best possible move. One of my teammates introduced a much more interesting game for computers to play: Jotto.
How to play
The rules of Jotto are very simple. You and your opponent each pick a five-letter secret word and write it down. The goal is to guess your opponent's secret word before he or she guesses yours. On your turn, you guess a five-letter word and your opponent tells you how many letters it has in common with the secret word you're trying to find. For example, if the secret word is "apple" and you guess "popes", that's three letters in common (two p's and one e). Players take turns guessing words until one of them figures out the other's secret word.
It's a very simple game to learn, but the strategies can get kind of complex. Most importantly, there's no clear "best move" on each turn, which makes it an interesting problem for AI.
The greedy best response algorithm
My team designed a greedy algorithm to choose which word to guess. Put simply, the computer has a dictionary with 8,861 five-letter English words to choose from and tries to eliminate as many of them as possible each turn, so it can narrow in on the human player's secret word. The algorithm works similar to a minimax search to provide the best approximate response for the agent. It uses several subroutines to pick the word that is expected to narrow the list of possible words the most based on the probability that the opponent chose each word.
This probability distribution is based on word frequency analysis of a large dataset of English writing (we used a set of 25,000 IMDb movie reviews). We also used a flat distribution for testing, and it tended to perform worse than the distribution based on actual word usage.
To impose a limitation on the computer we prevented it from spending more than two seconds per move. This only ended up mattering in the first few turns when the list of possible words is still quite large.
When tested on words picked by humans the computer guessed the correct word in an average of 10.9 moves, often beating human players. You can try it for yourself online to see if you can beat the computer, or check out our implementation in TypeScript on GitHub.