Introduction
Earlier this year, I spent some time calculating the probability of a Scrabble “bingo:” drawing a rack of 7 tiles and playing all of them in a single turn to spell a 7-letter word. The interesting part of the analysis was the use of the Google Books Ngrams data set to limit the dictionary of playable words by their frequency of occurrence, to account for novice players like me that might only know “easier” words in more common use. The result was that the probability of drawing a rack of 7 letters that can play a 7-letter word is about 0.132601… if we allow the entire official Scrabble dictionary, including words like zygoses (?). The probability is only about 0.07 if we assume that I only know about a third– the most frequently occurring third– of the 7-letter words in the dictionary.
But given just how poorly I play Scrabble, it seems optimistic to focus on a bingo. Instead of asking whether we can play a 7-letter word using the entire rack, let’s consider what turns out to be a much harder problem, namely, whether the rack is playable at all: that is,
Problem: What is the probability that a randomly drawn rack is playable, i.e., contains some subset of tiles, not necessarily all 7, that spell a word in the dictionary?
Minimal subracks
The first interesting aspect of this problem is the size of the dictionary. There are 187,632 words in the 2014 Official Tournament and Club Word List (the latest for which an electronic version is accessible)… but we can immediately discard nearly 70% of them, those with more than 7 letters, leaving 56,624 words with at most 7 letters. (There is exactly one such word, pizzazz, that I’ll leave in our list, despite the fact that it is one of 13 words in the dictionary with no hope of ever being played: it has too many z‘s!)
But we can trim the list further, first by noting that the order of letters in a word doesn’t matter– this helps a little but not much– and second by noting that some words may contain other shorter words as subsets. For example, the single most frequently occurring word, the, contains the shorter word he. So when evaluating a rack to see whether it is playable or not, we only need to check if we can play he; if we can’t, then we can’t play the, either.
In other words, we only need to consider minimal subracks: the minimal elements of the inclusion partial order on sets of tiles spelling words in the dictionary. This is a huge savings: instead of 56,624 words with at most 7 letters, we only need to consider the following 223 minimal “words,” or unordered subsets of tiles, with blank tiles indicated by an underscore:
__, _a, _b, _cv, _d, _e, _f, _g, _h, _i, _j, _k, _l, _m, _n, _o, _p, _q, _r, _s, _t, _u, _vv, _w, _x, _y, _z, aa, ab, aco, acv, ad, ae, af, ag, ah, ai, ak, al, am, an, aov, ap, aqu, ar, as, at, auv, avv, aw, ax, ay, az, bbu, bcu, bdu, be, bfu, bgu, bi, bklu, bllu, bo, brr, bru, by, cciiv, ccko, cdu, cee, cei, cekk, ceu, cffu, cfku, cgku, cgllyy, chly, chrtw, ciirr, ciy, cklu, cllu, cmw, coo, coz, cru, cry, cuz, ddu, de, dfu, dgu, di, djuy, dkuu, dlu, do, dru, dry, duw, eeg, eej, eek, eequu, eev, eez, ef, egg, egk, egv, eh, eiv, eju, eku, ekz, el, em, en, eo, ep, er, es, et, ew, ex, ey, ffpt, fgu, fi, flu, fly, fo, fru, fry, ghlly, gi, gju, glu, go, gpy, grr, gru, gsyyyz, guv, guy, hi, hm, hnt, ho, hpt, hpy, hs, hty, hu, hwy, iirvz, ijzz, ik, il, im, in, io, ip, iq, irry, is, it, ivy, iwz, ix, jjuu, jkuu, jo, kkoo, klru, kouz, kruu, kst, ksy, kuy, lllu, llxyy, lnxy, lo, lpy, lsy, luu, luv, mm, mo, mu, my, no, nsy, nu, nwy, ooz, op, or, os, ot, ow, ox, oy, ppty, pry, pst, psy, ptyy, pu, pxy, rty, ruy, rwy, sty, su, tu, uuyz, uwz, ux, uzz, zzz
The figure below expands on this calculation, showing the number of minimal subracks on the y-axis if we limit the dictionary of words we want to be able to play in various ways: either by frequency on the x-axis, where dumber is to the left; or by minimum word length, where the bottom curve labeled “>=2” is the entire dictionary, and the top curve labeled “>=7” requires a bingo.
Number of minimal playable subsets of tiles in inclusion order on the set of all playable words in OTCWL 2014, restricted by length and/or frequency.
As this figure shows, we benefit greatly– computationally, that is– from being able to play short words. At the other extreme, if we require a bingo, then effectively every word is a minimal subrack, and we actually suffer further inflation by including the various ways to spell each word with blanks.
Finding a subrack in a trie
At this point, the goal is to compute the probability that a randomly drawn rack of 7 tiles contains at least one of the minimal subracks described above. It turns out that there are only 3,199,724 distinct (but not equally likely) possible racks, so it should be feasible to simply enumerate them, testing each rack one by one, accumulating the frequency of those that are playable… as long as each test for containing a minimal subrack is reasonably fast. (Even if we just wanted to estimate the probability via Monte Carlo simulation by sampling randomly drawn racks, we still need the same fast test for playability.)
This problem is ready-made for a trie data structure, an ordered tree where each edge is labeled with a letter (or blank), and each leaf vertex represents a minimal playable subrack containing the sorted multiset of letters along the path to the leaf. (We don’t have to “mark” any non-leaf vertices; only leaves represent playable words, since we reduced the dictionary to the antichain of minimal subracks.)
The following Python code represents a trie of multisets as a nested dictionary with single-element keys (letters in this case), implementing the two operations needed for our purpose:
- Inserting a “word” multiset given as a sorted list of elements (or a sorted string of characters in this case),
- Testing whether a given word (i.e., a drawn rack of 7 tiles, also sorted) contains a word in the trie as a subset.
Insertion is straightforward; the recursive subset test is more interesting:
def trie_insert(t, word):
for letter in word:
if not letter in t:
t[letter] = {}
t = t[letter]
def trie_subset(t, word):
if not t:
return True
if not word:
return False
return (word[0] in t and trie_subset(t[word[0]], word[1:]) or
trie_subset(t, word[1:]))
Enumerating racks
Armed with a test for whether a given rack is playable, it remains to enumerate all possible racks, testing each one in turn. In more general terms, we have a multiset of 100 tiles of 27 types, and we want to enumerate all possible 7-subsets. The following Python code does this, representing a multiset (or subset) as a list of counts of each element type. This is of interest mainly because it’s my first occasion to use the yield from syntax:
def multisubsets(multiset, r, prefix=[]):
if r == 0:
yield prefix + [0] * len(multiset)
elif len(multiset) > 0:
for k in range(min(multiset[0], r) + 1):
yield from multisubsets(multiset[1:], r - k, prefix + [k])
(This and the rest of the Scrabble-specific code are available at the usual location here.)
The final results are shown in the figure below, with convention for each curve similar to the previous figure.
Probability that a random rack of 7 tiles is playable, containing a word in OTCWL 2014 restricted by length and/or frequency.
For example, the bottom curve essentially reproduces the earlier bingo analysis of the probability of playing a word of at least (i.e., exactly) 7 letters from a randomly drawn rack. At the other extreme, if we have the entire dictionary at our disposal (with all those short words of >=2 letters), it’s really hard to draw an unplayable rack (probability 0.00788349). Even if we limit ourselves to just the 100 or so most frequently occurring words– many of which are still very short– we can still play 9 out of 10 racks.
In between, suppose that even though we might know many short words, ego prevents actually playing anything shorter than, say, 5 letters in the first turn. Now the probabilities start to depend more critically on whether we are an expert who knows most of the words in the official dictionary, or a novice who might only know a third or fewer of them.
Possibly Wrong 