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?