tag:blogger.com,1999:blog-264226589944705290.post5167975461117723819..comments2023-11-05T03:45:25.001-08:00Comments on God Plays Dice: how many Scrabble racks are there?Michael Lugohttp://www.blogger.com/profile/15671307315028242949noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-264226589944705290.post-33285958975660900032011-12-01T11:54:45.264-08:002011-12-01T11:54:45.264-08:00This is interesting. The real question of course, ...This is interesting. The real question of course, is not how many unique racks are there?, or how long it would take to observe them all on the opening draw from the tile bag? but: "How much luck is involved in playing SCRABBLE(R)?"<br /><br />If there are 3,199,724 unique racks, then a player playing 10 games/day with 15 draws from the tile bag/game would need a minimum of 58.4 years to draw all the unique racks. That's a big IF of course, since it would require the player to draw a new unique rack every time.<br /><br />Using the approximation above to derive some estimate of the sampling time required to actually draw all of the unique racks (n(log(n)) this gives a value of approximately 380 years of random draws, 10 games/day, 15 draws/game. It might require more time, since experienced players manage their racks by saving certain tiles or combinations such as the blank, or ERS.<br /><br />So a hardcore player, playing ten games per day over a 38 year career might see 1/10 of all possible racks. This means that any single player's draws over the players' entire career could possibly all fall at the extreme of one tail of a normal probability distribution, especially if the player played fewer than 10 games/day every day for 38 years. <br /><br />Speculating a little, and assuming an sampling unit of an entire SCRABBLE career, (and not the more appropriate unit of a single draw from the tile bag- a big assumption!) we can get an intuitive feel for the amount of luck involved. <br /><br />If the probability distribution mentioned above was that of drawing "good racks" (i.e. racks of tiles likely to score well given the current configuration of tiles on a game board- the very best racks being distributed toward the right tail of the distribution from the mean), and even if "good racks" comprised 70% of all possible draws over a career (and, again, if it is reasonable to suggest that an entire SCRABBLE career is an appropriate sampling unit) then it is very possible that the hardcore players spending most of their SCRABBLE(R) careers at the extreme left tail of the probability distribution would rarely see a "good rack", and be considered much unluckier than others.<br /><br />Of course, we do not play randomly. The combined effects of rack management skills, the genius of Alfred Butts' choice of tile frequency distribution, and the distribution of letters in words acceptable for play, together very likely increase the probability of spending your career at the more pleasant right-hand side of the "good rack" probability distribution. This analysis highlights the importance of rack management! If you are consistently leaving "bad" tile combinations on your rack you are increasing the likelihood of dwelling in the less pleasant left-hand tail of the distribution!Unknownhttps://www.blogger.com/profile/10257864759186318302noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-71633185997003784502010-03-07T17:07:42.345-08:002010-03-07T17:07:42.345-08:00Generating function solution:
It's coefficien...Generating function solution:<br /><br />It's coefficient of x^7 for the following polynomial:<br /><br />(1 + x)^5 * <br />(1 + x + x^2)^10 * <br />(1 + x + x^2 + x^3) * <br />(1 + x + x^2 + x^3 + x^4)^4 * <br />(1 + x + x^2 + x^3 + x^4 + x^5 + x^6)^3 * <br />(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8) *<br />(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9)^2 *<br />(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 + x^10 + x^11 + x^12)<br /><br />Some explanation: <br />There are 5 letters: J, K, Q, X, and Z that have frequency = 1. So, each rack can have 0 or 1 of each letter. (Those five letters contribute (1+x)^5 to the polynomial)<br /><br />There are 10 letters (including the blank) which occur twice in the set of tiles. So, each rack can have 0, 1 or 2 of each letter.<br />(Those 10 letters contribute (1+x+x^2)^10 to the polynomial).<br /><br />Etc, for other letters of other frequencies.<br /><br />So, the coefficient of x^7 of the expanded polynomial gives you the number of distinct racks with 7 tiles.<br /><br />If you run this in Mathematica or similar, you get the figure 3199724. (As a byproduct, you get every other distinct rack count for different rack sizes.)<br /><br />1 + 27x + 373x^2 + 3509x^3 + 25254x^4 + 148150x^5 + 737311x^6 + 3199724x^7 + 12353822x^8 + 43088473x^9 + 137412392x^10 ...<br />+ x^100<br /><br />As expected, the polynomial is symmetric in that the coefficient of x^y = the coefficient of x^(100-y).<br /><br />So, there's one distinct set of zero tiles and one distinct set of 100 tiles.<br />There are 27 sets of one tile (26 letters + the blank) and 27 ways distinct sets of 99 tiles.<br /><br />The maximum occurs at 50 (as expected): 913,201,857,455,724 (almost 1 quadrillion)<br /><br />This almost fits into the input box for www.wolframalpha.com. If you only care about rack sizes <=7,<br />you can run this modified polynomial (the exponents top out at 7 because you couldn't have more than 7 tiles in <br />a rack of 7)<br /><br />expand (1+x)^5*(1+x+x^2)^10*(1+x+x^2+x^3)*(1+x+x^2+x^3+x^4)^4*(1+x+x^2+x^3+x^4+x^5+x^6)^3*(1+x+x^2+x^3+x^4+x^5+x^6+x^7)^4<br /><br />At time of writing though, WolframAlpha "doesn't know what to do with the input".Unknownhttps://www.blogger.com/profile/01441314014201282316noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-45032757550677355052009-04-19T15:03:00.000-07:002009-04-19T15:03:00.000-07:00I get 3199724 too. But I managed to find a reasona...I get 3199724 too. But I managed to find a reasonably simple way of computing this by hand. I'll try to describe it.<br /><br />The first part is how you think about the rack. In this calculation, I think about it in terms of the form of it's repetition. So the rack specified by the frequency list [3,2,1] refers to a rack where there are three different letters. The first occurs 3 times, the second appears 2 times and the third appears 1 time only. There are only 14 such possible rack specs in a scrabble rack (listed later).<br /><br />In order to know how many ways a spec can be satisfied, it is necessary to know how many different letters can be repeated a given number of times. I denote this fequency by F[] and I have these values:<br /><br />F[1] = 27 (see NOTE A)<br />F[2] = 22<br />F[3] = 12<br />F[4] = 11<br />F[5] = 7<br />F[6] = 7<br />F[7] = 4 (see NOTE B)<br /><br />NOTE A: This counts the blank as a letter.<br />NOTE B: There are only four letters which can be repeated seven times.<br /><br />A further consideration is the number of permutations of the frequencies in a rack spec which would leave the spec unchanged. I denote this number as P[] and list the values of P[] for all possible rack specs:<br /><br />P[7] = 1<br />P[6,1] = 1<br />P[5,2] = 1<br />P[5,1,1] = 2 (see NOTE A)<br />P[4,3] = 1<br />P[4,2,1] = 1<br />P[4,1,1,1] = 6 (see NOTE B)<br />P[3,3,1] = 2<br />P[3,2,2] = 2<br />P[3,2,1,1] = 2<br />P[3,1,1,1,1] = 24<br />P[2,2,2,1] = 6<br />P[2,2,1,1,1] = 12 (see NOTE C)<br />P[2,1,1,1,1,1] = 120<br />P[1,1,1,1,1,1,1] = 5040<br /><br />NOTE A: since the second and third letter choices can be swapped.<br />NOTE B: six ways of permuting the 1s)<br />NOTE C: That's 2*6.<br /><br />Now the question is, given a spec, how many different letter choices does that specification correspond to? Let's take [4,1,1,1] as an example spec in order to demonstrate how to calculate N[4,1,1,1] the number of possible letter choices. First we'll calculate a necessary interim quantity X[]:<br /><br />X[4,1,1,1] = (F[4] - 0) * (F[1] - 1) * (F[1] - 2) * (F[1] - 3)<br /> = (11 - 0) * (27 - 1) * (27 - 2) * (27 - 3)<br /> = 11 * 26 * 25 * 24<br /> = 171600<br /><br />and in general we have:<br /><br />X[n0,n1,...,nK] = (F[n0] - 0) * (F[n1] - 1) * ... * (F[nK] - K)<br /><br />At first glance, this looks like the number we're looking for but not quite. The calculation considers the letter choices (L,A,B,C) as distinct from the choices (L,A,C,B), (L,B,A,C), (L,B,C,A), (L,C,A,B) and (L,C,B,A) but which all actually correspond to the same rack. The number of possible equivalent choices is given by P[4,1,1,1] so in order to get N[4,1,1,1] we must divide X[4,1,1,1] by P[4,1,1,1]. So:<br /><br />N[4,1,1,1] = X[4,1,1,1] / P[4,1,1,1]<br /> = 28600<br /><br />and for some general rack spec, (S), we have:<br /><br />N[(S)] = X[(S)] / P[(S)]<br /><br />Now we're in a position to calculate N[] for all valid rack specs:<br /><br />N[7] = 4<br />N[6,1] = 182<br />N[5,2] = 147<br />N[5,1,1] = 2275 <br />N[4,3] = 121<br />N[4,2,1] = 5775 <br />N[4,1,1,1] = 28600<br />N[3,3,1] = 1650<br />N[3,2,2] = 2520 <br />N[3,2,1,1] = 75600<br />N[3,1,1,1,1] = 179400<br />N[2,2,2,1] = 36960<br />N[2,2,1,1,1] = 531300<br />N[2,1,1,1,1,1] = 1447160<br />N[1,1,1,1,1,1,1] = 888030<br /><br />And totalling all of this to get, N[*], the number of all possible racks is:<br /><br />N[*] = N[7] + N[6,1] + ... + N[1,1,1,1,1,1,1]<br /> = 3199724.<br /><br />Tada!!! :)smh62https://www.blogger.com/profile/03479988855026537639noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-33362194654971746652008-12-06T17:06:00.000-08:002008-12-06T17:06:00.000-08:00Brett,Indeed, a couple days later I came up with t...Brett,<BR/><BR/>Indeed, a couple days later I came up with the same number.Michael Lugohttps://www.blogger.com/profile/15671307315028242949noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-23961245666798949062008-12-06T17:02:00.000-08:002008-12-06T17:02:00.000-08:00I wrote a perl program to calculate the number of ...I wrote a perl program to calculate the number of unique scrabble racks. There are 3199724 racks - your estimation was very close!<BR/><BR/>My program assumes a rack size of 7 and these tile counts:<BR/>A=>9, B=>2, C=>2, D=>4, E=>12, F=>2, G=>3, H=>2, I=>9, J=>1, K=>1, L=>4, M=>2, N=>6, O=>8, P=>2, Q=>1, R=>6, S=>4, T=>6, U=>4, V=>2, W=>2, X=>1, Y=>2, Z=>1, '#'=>2Bretthttps://www.blogger.com/profile/13131308972421165289noreply@blogger.comtag:blogger.com,1999:blog-264226589944705290.post-8175956596807047752007-08-28T08:08:00.000-07:002007-08-28T08:08:00.000-07:00I also found that memorizing words for Scrabble cr...I also found that memorizing words for Scrabble crosses the line between fun and work. I also have a degree in math.<BR/><BR/>Thus, I changed the game to eliminate the utility of memorization.<BR/><BR/>Hope you will take a look.<BR/><BR/>Peter<BR/><BR/>http://www.wildwords.usAnonymousnoreply@blogger.com