[Math] winning strategy for Scrabble

combinatoricscomputational complexitygame theoryreference-request

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?

Best Answer

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!

Related Question