# Boggle letter probability

How to distribute English alphabet letters among Boggle game dice? How to make rolling for example letter "A" more often than others? How to choose how many copies of each letter to make, and how many copies of them to put on one dice? Can you please answer to these questions?

-
What is Boggle? –  Yuval Filmus May 31 '11 at 18:42
Boggle is a word board game. Wikipedia[Wikipedia] –  myself May 31 '11 at 18:47
What are your goals? If you are trying to duplicate Boggle, then obtain a Boggle set, count the letters on the cubes, and hope Hasbro's lawyers don't find you. If you are trying to optimize your letter distribution with regard to some criterion, then you need to spell out your criterion. –  David Speyer May 31 '11 at 19:03
I'm trying to optimize letter distribution to alternate probability of rolling a certain letter. –  myself May 31 '11 at 19:08
What do you mean "alternate probability of rolling a certain letter"? If you want to maximize it, paint A on all the faces. –  Ross Millikan May 31 '11 at 19:58
show 1 more comment

I think the question you're trying to ask is: 'how can I distribute my letters among the faces of the (16) Boggle dice so as to approximately match English probabilities?' This is actually a more interesting question than it looks at first glance, because the first-order approximation is easy, but subtle 'nonlinear' effects creep in past that first approximation, and I'm not offhand sure how to best handle them (I've coded a small handful of word games, and my answer has traditionally been 'fake it').

To first order, note that you've got 96 (16$\times$6) faces to play with; furthermore (and this is the key point of that first approximation), it doesn't actually matter which faces you put which letters on. Whether you paint all six faces of one die with the letter 'A', or one face each of six different dice, the mean number of 'A's on the board (averaged over many rolls) will be the same: the probability of any given face being an A (6/96) times the number of faces visible in a roll (16) - that is, on average you'll have exactly 1 'A' per roll. To a first approximation, then, you can multiply the basic letter frequencies (which can be found any number of places, or even found by doing a dictionary analysis of your own) by the number of slots to fill (96 for the classic Boggle problem) and, rounding appropriately, come up with an appropriate number of tiles to use for each letter; once you have those, it doesn't matter how you assign them to the faces of the dice.

But again, of course... this is 'to first approximation', with the assumptions that letter probabilities are independent of each other; that the probability that a word has two As in it is the square of the probability that it has one A, or that the probability that a word contains an A and an S is the product of the individual letter probabilities P(A) and P(S). But of course, this isn't true; letter combinations in English are highly correlated. For instance, Q appears so much more regularly with 'U' than without it that virtually every English word game (with the rare and notable exception of Scrabble) pairs the two together into a single glyph. There are plenty of other examples, too: many consonants (and a couple of vowels) are more likely to appear in multiples than single-letter probabilities would dictate; 'H's are often paired with 'T's and 'S's, 'G's with 'N's, etc. What's more, these correlations are inordinately hard to model, because it's not even clear what the appropriate measure is; do you want to know the probability that two letters appear next to each other, or simply the probability that they appear in the same word, or something else entirely? And on the other side, explicit values for the probability of two letters appearing together on your grid are going to be hard to calculate with anything short of simply enumerating all the possibilities. The best approach may be something akin to Dan Brumleve's mention of simulated annealing: start with an arbitrary 'layout' (an assignment of 96 tiles to the 6$\times$16 faces of your dice) and then run a few thousand simulations to get the joint probability for all (or some suitably chosen set) combinations of two letters. Then make a change to your layout, do another simulation run, and if the joint probabilities are closer to 'correct' than they were for the first layout, accept the change; repeat this until you come up with a distribution that offers reasonably good joint probabilities.

Unfortunately, even this still doesn't actually accomodate all of the relevant correlations that occur in the english language. For instance, the probability that at least one vowel occurs in a word is much, much higher than would be estimated either from either individual letter or joint two-letter probabilities, to the extent where (again) dice-based word games often make certain to have one or two dice that are all-vowels (and contrariwise, some dice that are all-consonants) to ensure that at least one vowel will come up and that the variance on the consonant:vowel ratio is lower (as it's relatively low in English). This is really a problem where a little domain-specific knowledge goes a long way, and where there is no hard and fast answer; you're just going to have to test to find out what feels right.

-
+1 Good points. If your first approximation tells you to put 'A' on 6 faces, I suspect you don't want to paint all six faces of one die with the letter 'A'. That would make it impossible to form words with more than one 'a' in them, such as "attack". –  David Cary Dec 19 '11 at 14:08

Let's work with Scrabble tiles (without blanks) instead of Boggle dice, just to keep things as simple as possible. (At the end, you can make your Boggle dice by sticking the Scrabble tiles onto them.) Suppose we have $n$ tiles, with $n \ge 26$, and a table of letter frequencies (for instance, this one), which we convert to probabilities by dividing by 100.

The first thing to do is to pick each letter once (assuming that you want all letters to occur at least once). Then subtract $1/n$ from each letter frequency to account for this, and set $n = n - 26$. This might make some of the letter frequencies negative, so we discard those letters, and renormalise the remaining frequencies so that they add up to $1$ (that is, if $S$ is the sum of the remaining frequencies, we multiply each frequency by $1/S$.)

Now just do the following (Updated to work correctly):

for (i = 1 to n) {
Pick the letter L with the largest frequency
Subtract 1/n from L's frequency
}


That's how I would do it, anyway.

-

Assuming you want it to approximately match the distribution of letters in English words, you can generate a histogram with something like this:

cat /usr/share/dict/words |perl -pe 's/[^a-z]//gs' |perl -e 'print join("\n", split //, <>) . "\n"' |sort |uniq -c

Convert these values into probabilities by dividing by the total, multiply by the total number of dice, multiply by 6, and then round up to an integer so you have at least one instance of each letter. Fudge the numbers so that the total is divisible by 6. Then label each face with those letters in such a way that you minimize the number of duplicate letters on each die.

If we make the problem more specific, there is probably a better (but more complicated) way. If you actually want to maximize the expected number of words that appear on the Boggle board, I think you will have to use some sort of simulated annealing approach to optimize it.

-

I've just written a simple python program to do this, and am looking for the actual letters that occur on the dice.

You want a 16 element array, each element of which is a 6-element array of ints.

import array
lets = [array.array('i',[0]*6)]*16


constructs the required array. Then you put the appropriate character codes in. (Or something like this -- I can't remember the array type codes apart from i, so I just used that, together with

import random
lets[i][j] = random.randrange(26) + 'A'.encode('UTF-8')[0]


this gives each letter equal probability. You then need to replace this line with something that, for each i and j, gets the right letter for an actual Boggle game.

Then you do

a = []
for i in range(16):
a.append(random.choice(lets[i]))


to get an array of 16 letters.

Finally,

for i in range(16):
print(a[i],end=' ')
if i % 4 == 3:
print()


will print out a nice 4x4 grid, like

I O S O
C O O S
C C U P
S U I U


and this final example shows why you need to manually set the letter choices rather than picking random letters from the alphabet.

http://thewikiman.allsup.co/BogglePlay has a complete Python script for this.

-