Sunday, January 3, 2016

A Programmer's Analysis of Boggle

In the era of modern tabletop games such as Apples to Apples, Dixit, Sushi Go, Hive, Zombie Dice, and Tokaido (all great games), the classics are often left behind. While many of these games deserve to be forgotten (Monopoly, Jenga, Risk, Life, and Snakes and Ladders; just to name a few), the venerable Boggle still reigns as one of the few great word games. Boggle has a lot to offer: it is a fast paced game that scales well to many players, everyone plays at the same time, winning requires skill (pattern recognition and a decent vocabulary) and strategy (trying to find words that other players aren't likely to spot) rather than luck, and it has a high replay value (every game is different). It is also easy to level the playing field for younger players, e.g. by counting their words even if found by other players or reducing the value of longer words.

Boggle is interesting from a programmer's perspective as well. While crafting an algorithm to efficiently find all of the words in a Boggle game is pretty straight forward, answering questions such as:
  • What is the average number of words/points in a game and how does this differ between different  sets of dice?
  • What percentage of total points do 3-letter words constitute? 4-letter words? Etc.
  • How can we determine whether a given arrangement constitutes a valid board for a particular game?
  • How many words in a given dictionary cannot be spelled using any possible arrangement of the provided dice?
  • What is the highest scoring Boggle board?
are more challenging and require the use of non-trivial algorithms and data structures. A couple years ago, I wrote a program explore these questions (and others) called Word Game Solver (WGS for short) and documented the results which are presented below. While the details of the program itself will not be the focus here, I will provide the commands used when applicable so that others can reproduce/expand on the results presented and will also touch on the algorithms employed.  Comprehensive pdf documentation is provided with the program (available on GitHub) for those who are interested in the full scope of the functionality provided.