Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Tonight a game of Scrabble ended in what I consider a very unusual graph structure, unlike this generic web image, which seems more typical:
            
Let us call the Scrabble graph the one whose nodes are tiles, with two tiles connected by an arc in the graph if they share a side. The unusual graph that occurred contained a long snaking chain that consumed most of the board. This made me wonder if anyone has performed a statistical analysis of "average" Scrabble graphs; for example, their diameter, or their cycle structure? No doubt these properties depend on the skill of the players, but it seems within some reasonable parameters, there are perhaps answers of sorts. I would be curious to hear of any data in this direction. Thanks!

Afterthought. Maybe equally interesting: What is the largest diameter legal, achievable Scrabble graph?

share|improve this question
4  
It turns out testae does not mean what I would have expected. –  Will Jagy Jul 21 '12 at 2:18
2  
There is a database of scrabble games available at cross-tables.com/annolistself.php –  A.Schulz Jul 21 '12 at 6:43
1  
It would also be interesting to consider the following graph: The vertices are the words on the final board, and two vertices are joined by an edge, iff they share a "letter piece". Of course, both graphs are somehow related. –  A.Schulz Jul 23 '12 at 19:07
add comment

3 Answers 3

up vote 23 down vote accepted

Methods

Starting from the base url http://www.cross-tables.com/annotated.php?a=1 I used a combination of Python's urllib, multiprocessing and BeautifulSoup to extract the first 10000 games. The games were parsed and turned into numpy 15x15 Boolean matrices. The matrices were then turned into graphs making an edge if two adjacent cells in the matrix were both active. Graph properties were then analysed with networkx

Of the 10000 games, only 9966 were usable. Some games did not start on the center title, while others ended so quickly and strangely they did not behave properly. Fortunately these games were rare enough that the sample should give a robust estimation of the true distributions.

Methods (Update)

There was a bit more data cleanup needed. I had not taken into consideration challenged moves, leading to games that had >100 tiles used. In the process, I noted false moves and fake games. We may have to live with a bit of uncertainty in the data, such is the cost of true empirical data.

Results

The first interesting piece of information is the board frequency - this gives a nice spatial connection to the graphs we are about to study. Notice that, due to how the game is played (and how we read left to right and top to bottom) the board is asymmetric.

Board frequency

From here we can answer the question,

"What is the distribution of graph diameters and radii for an average Scrabble game?"

enter image description here

A scatter plot versus the graph size reveals a bit more information for the smaller $N$ values:

enter image description here

Results (Update)

Based of a comment, I plotted the radius vs the diameter, giving a mostly linear relationship of 1 to 2 except for a range of games with some variance. Feel free to make some observations on the significance of this in the comments.

enter image description here

Quick Conclusion (TLDR)

From the data studied, there were mostly full games played ~100 tiles with an average graph radius 18 and a diameter of 36. Further work is needed to compare these results to random graphs with the same size and edge counts but different edge distribution.

share|improve this answer
    
Please leave a comment if you would like any more statistics to be run against the data and I'll add it in. –  Hooked Jul 26 '12 at 14:01
    
This is cool. Could you also generate statistics, considering the graph of words, instead the graph of tiles (see my second comment of the question). –  A.Schulz Jul 26 '12 at 14:52
    
Aside from your interesting results, your analysis is based on an impressive piece of programming, using many tools masterfully---Kudos! It is at least pleasing that the radius is half the diameter. :-) One question: How can $N$ exceed 100, as there are exactly 100 tiles? –  Joseph O'Rourke Jul 27 '12 at 0:18
1  
@JosephO'Rourke and in looking at those extra challenge words I come across games like cross-tables.com/annotated.php?u=1952#22#. I'm not a linguist, but I think that the English Stack Exchange folks will tell me that "joohampers" and "reactivevolosts" are not in the Scrabble dictionary, never mind the fact that the record points to an excess number of tiles being used. Point being, some games must not be valid. I only counted 4 of these in the dataset. –  Hooked Jul 27 '12 at 14:10
1  
@aromero All plots were made with matplotlib (pylab) on Python. As suggested by Rahul, a hexplot in the pylab library might be better for the scatter plots. –  Hooked Jul 29 '12 at 4:31
show 3 more comments

It turns out that the maximum possible diameter uses the full hundred tiles! My friend Carl illustrated this in 2008 in a game he made up, here: http://www.cross-tables.com/annotated.php?u=2493#0# .

Thanks for the question!

share|improve this answer
    
Very clever!!! $\;$ –  Joseph O'Rourke Jul 29 '12 at 17:39
add comment

If you require the viable dictionaries that are allowable for scrabble, they are available on the http://www.lexicalwordfinder.com/about/ site (Lexical Word Finder website).

An interesting experiment: Assuming most people do not play expertly, you can use the generated list from Lexical Word finder to play medium words to see what the average graphs look like. It would be nice to also see what the "best" moves at each turn produce as well.

Interesting use of networkx.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.