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.

I am sure many of us are addicted to the popular Facebook app: Words with Friends, which is basically an online version of Scrabble. In Playing Games with Algorithms:Algorithmic Combinatorial Game Theory by Demaine and Hearn (2008), the authors examine various games, but upon reaching crosswords and scrabble they conclude that they are not sure if any work has been done on the complexity of the game:

A related open problem is Scrabble, which we are not aware of having been studied. The most natural theoretical question is perhaps the one-move version: given the pieces in hand (with letters and scores), and given the current board configuration (with played pieces and available double/triple letter/word squares), what move maximizes score? Presumably the decision question is NP-complete. Also open is the complexity of the two-player game, say in the perfect-information variation where both players know the sequence in which remaining pieces will be drawn as well as the pieces in the opponent’s hand. Presumably determining a winning move from a given position in this game is PSPACE-complete.

Any reference, if not the answer(!), will be very much appreciated?

share|improve this question
1  
Scrabble appears only twice in Math Reviews, and neither reference is about strategy. You may find something useful in the AI literature, e.g., Brian Sheppard, World-championship-caliber Scrabble, Artificial Intelligence Volume 134, Issues 1–2, January 2002, Pages 241–275. –  Gerry Myerson Jul 6 '12 at 6:45
    
Thank you. Here is the direct link to Gerry's reference. –  Sniper Clown Jul 6 '12 at 6:53
1  
You might want to look at this open source Scrabble move analyser: people.csail.mit.edu/jasonkb/quackle –  Sarastro Dec 3 '12 at 6:50
add comment

2 Answers

For a given combination of board size/rack size/dictionary size, there is obviously an optimal strategy for Scrabble, because the number of positions is finite. If the sequence of tiles is known in advance, then by "optimal strategy" I mean the strategy that maximises your final winning margin (or minimises your final losing margin); if the tiles are drawn at random, then you have to choose: do you want to maximise your expected winning margin, or maximise your chance of winning? But in any case the existence of a strategy is not in doubt.

But when you bring complexity into the picture, things get messy. There are too many parameters: board size, rack size, alphabet size, dictionary size, total number of tiles.

We might as well assume that the board is infinite in all directions, because the playing area is limited by the total number of tiles.

Now the big question is, are we using a fixed dictionary? If so, then the alphabet size is also fixed, and the only variables are rack size and total number of tiles. Then we have a simple polynomial-time algorithm for finding the highest-scoring move in a given position: for each starting square, and each direction (horizontal/vertical), and each word W in the dictionary, decide whether W is a valid move with the given rack; and choose the highest-scoring valid move. With a few obvious optimisations, this is not so very different from the actual algorithm used by the Scrabble program that I co-wrote 25 years ago, and it was lightning fast on a regular Scrabble board.

But this depends on the dictionary being in a nice format (e.g. a Directed Acyclic Word Graph). If the dictionary is allowed to vary, then I don't know if a polynomial-time algorithm is possible.

But in general, of course, the highest-scoring move is not always the best move. You must also try to maintain a playable rack, and avoid leaving high-scoring options for your opponent. The problem of finding the best move in this sense, even if the sequence of tiles is known in advance, is presumably NP-complete. Nevertheless, our Scrabble program was able to play the two-player endgame perfectly once the tile bag was empty!

share|improve this answer
add comment

The deterministic version of the 2-player game is proven to be PSPACE-complete for a made-up dictionary even for constant size alphabet and rack and no special tiles, see 1.

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.