Last fall, I finished the MIT Challenge [1]. While the challenge was exciting and educational, the tight deadline didn’t give me any time for extracurricular projects. When I finished, I wanted to work on a small and fun project that would test some of the things I learned.
The result was WordSmith, a program that lets you play the game Scrabble [2] against a computer. I’ve made the project free and open-source, so anyone can play it and also see how it works. Visit the download page [3] to try it out.
For the rest of this article, I’m going to explain how the program works. While it’s not tremendously complex, it does show a little of the computer science knowledge I picked up through the MIT Challenge. If CS or Scrabble don’t interest you at all, feel free to skip this article, as I’ll be back next week with my normal writing.
Building an AI that Plays Scrabble
I’ve always enjoyed the game Scrabble. The game requires a mixture of vocabulary, strategy, pattern-recognition and luck. Unlike chess, AI-researchers’ favorite game, luck and outside knowledge play a role. Even a perfect Scrabble player may still lose due to unfortunate letters or an unlikely countermove.
Because of this, I wanted to see if I could make a computer that plays Scrabble. Not only because then I could play a game I enjoy without needing a ready opponent, but also because a strong computer opponent would teach me more about the game.
So, I built WordSmith. It was a fun project, not only because I enjoy Scrabble, but because the problem was interesting enough to require clever algorithmic tricks, but not so tricky I couldn’t do it part-time over three weeks while on vacation in Paris.
How WordSmith Plays Scrabble
WordSmith plays by searching the board for all possible tile placements and then chooses the best one. It evaluates this not only based on how many points a particular move gives, but also by using heuristics to avoid technically higher-scoring moves which are probably detrimental in the long-run.
When playing the AI, you’ll notice a blue progress bar as the AI “thinks”. What it is actually doing is trying every combination of letters it can play and keeping track of which moves are both valid and score enough points. I’ve built the AI to give up after 15 seconds (which is why the blue bar doesn’t always finish), but at least on my computer it does retrieve the highest possible scoring word over 95% of the time.
This doesn’t mean WordSmith is impossible to beat, however. I’ve beaten it roughly 10% of the time in the matches I’ve played. Scrabble is a lot of luck and often the technically best word isn’t considerably higher scoring than one an advanced player would pick.
WordSmith also uses heuristics [4]. A heuristic is a fancy CS way of saying “rule of thumb”, meaning a simplified rule that will tend to increase performance when applied. I had started developing this capacity in the program, but there’s always the possibility of better heuristics, so this can give human players a strategic advantage.
The only heuristic I’ve tested that has made it into the final build of WordSmith is one that is conservative when playing good tiles. Blanks and high-point letters (Q, Z, X and J) are incredibly valuable, so if WordSmith can’t find a good use for it in the first turn it finds one, it will wait.
This omits some of the obvious rules of thumbs that human players actually use. Leaving a triple-word score spot open is dangerous, but WordSmith is oblivious to this misstep. Similarly, playing long words opens up more possible countermoves than defensive, compact playing.
In technical terms, ignoring the timeout feature, WordSmith is statically-perfect, but not dynamically-perfect. This means a clever player can outmaneuver WordSmith even though WordSmith never fails to recognize the highest-scoring word.
How I Built the Program
Now that I’ve explained how WordSmith works, I’m going to explain how the algorithm was actually designed. I’m going to try to be as non-technical as possible, but I want to also try to cover some interesting details.
The first step was to build a program that allows humans to play Scrabble. This was not too difficult, although the scoring algorithm was more complex than I had anticipated.
Once I could play Scrabble by myself, and ensure the rules were upheld, it was time to build a computer that could do the playing automatically. The basic algorithm is fairly simple:
- Make a set of “slots” where all possible moves can be placed. Don’t consider the individual tiles yet, just look at where it is possible to place tiles in a valid move and make a list of these.
- For each slot, try placing all permutations of your tiles onto the board. For blanks, that also means trying every single one of the 26 possible letters.
- For each possible play, check whether it forms all valid words (not only in the principle direction, but in all new crosswords) and calculate the points. Keep track of the highest scoring play while you proceed.
This uses a very common AI strategy called searching [5]. If you can visualize this algorithm, it is as if the computer is scanning through the space of all possible moves and looking for the best one.
Speeding up the AI
There’s just one problem with this approach—it’s incredibly slow. Mid-game plays may consider a few thousand slots, for each of these there are over 5000 permutations and over 3 million if we consider blanks. The scoring algorithm is not trivial either, so this means that considering all options in a brute-force way can take several hours or more on a modern computer. I wanted an AI that could play in around a dozen seconds.
From here a lot of tricks were used to prune the search space. I’ll briefly describe a couple:
- Scoring is complex, testing whether the main word is valid is easy (O(1) hash-table lookup, for the CS geeks). Only words that were valid along the principle direction would be scored thoroughly.
- Before placing a blank, figure out if there are any words which match that blank configuration. X_YGYK doesn’t mean anything with any letter, so we can skip trying all 26 times.
- Since blanks have zero points, we only need to figure out if one letter assignment is valid, since all others will result in the same score. WI_ is the same whether you played WIZ or WIN (provided all crosswords are also valid in both cases).
- The algorithm for calculating possible slots can produce duplicates, so making sure every slot is unique can cut the processing by 30-50%.
All of these algorithmic optimizations are still correct—they will still always produce the best scoring word, no exceptions. Even so, because the algorithm depends on the number of possible tiles (and blanks), considering every possible option can still take a long time in extreme cases.
I didn’t want to ever have to wait a few minutes to play my turn, even in an unusual case. To fix this, I set a time limit that the computer cannot exceed when deciding its move.
This also made use of another trick. By sorting the tile slots by length, I could make sure the small words (which are much faster to compute all possibilities for) are tested before long words. Using this method, I could then calculate that the algorithm is perfect 95% of the time with a time limit of 15 seconds on my machine.
This type of algorithm is also a common CS trick, very similar to the idea of lossy compression [6]. The idea is that if you can still preserve most of the information (or in this case, computation) but you drastically reduce size or processing time, the tradeoff can be worth it. This is one reason why videos load so much faster than GIFs—one is intelligently compressed and the other is not.
Statistics and Other Fun Stuff
Once that was complete, the program was essentially finished. I expanded it to include a few other cool tricks that can give some insights into how to win at Scrabble.
One question I considered was, what are the most important words to know in Scrabble?
Now that I had a program that played each Scrabble move (statically) perfectly, I could actually test this. So I had the AI play against itself for nearly a sixty thousand moves and compiled the results. Some interesting factoids:
- The most useful word in Scrabble is ‘QI’. (An accepted spelling of chi, the Chinese life force). This is followed by RE, ER, YE, IN, IT, TI, ZA. In fact, ‘QIS’, ‘QAT’ and ‘AYE’ are the only three-letter words to break the top 100.
- Short words are far more useful to know than long ones. The most-used 5-letter word was 50x less common than the most-used 2-letter word.
- The blank is the most useful tile, worth on average 12.9 more points. The letter ‘G’ is the least useful.
These statistics helped me train the algorithm. By collecting tile worth, I developed a heuristic which discounts high-value tiles so the computer won’t waste them in play. I then ran this modified AI against its predecessor a few hundred games and could show that its win-loss ratio was statistically significant.
I had hoped to build other heuristics, such as one that would avoid playing words that enabled high-point countermoves (such as leaving a precious triple-word score vulnerable). However testing these heuristics showed the AI performed worse, meaning either my formulation of the heuristic was misinformed, or that rule of thumb is less useful to my AI than I had previously believed.
One unfinished feature in the program was going to be a sliding difficulty scale. I had considered trying to limit the computer’s vocabulary to use only commonly known words. My strategy involved using Google’s n-gram library [7] to set a threshold vocabulary so the computer wouldn’t use unusual words.
Scrabble and Having Fun
I didn’t make this program for any reason other than for the fun of making and playing it. As such, I’m releasing it free and open source [3].
The game isn’t as polished as many commercial applications. Mostly because UI design isn’t my specialty and I did all the graphics and sound myself. Also because working on the AI was what interested me for the application, so I didn’t spend much time making it pretty.
The code is also a lot messier than I had hoped. This was partially some poor planning, and partially because the algorithm grew more complex than I had expected as I added heuristics, statistics and other details.
The program is open-source, so if anyone wants to make improvements or modifications to it, feel free to send them to me [8]. If they are worthwhile I’ll be happy to showcase them along with my own edition. In particular, I’m interested to see if anyone can demonstrate if different heuristics can reliably outperform my own WordSmith without changing the timeout on the algorithm.
However, if you just want to play the program, that’s fine too. I’ve even included a training mode that lets you check what the computer thinks you should play, so don’t worry if you’re not the best Scrabble player. Just go to the download page [3] to get a copy.