Friday, January 27, 2012

How Complicated is Scrabble?


According to new research, pretty complex. Word lovers have long touted the cleverness required to win scrabble matches. Now they have proof.

Theoretical computer scientists have crunched the numbers to determine the computational complexity of a player's decisions in the classic board game. Researchers have investigated numerous other board games for awhile. And now scrabble has been proven to be PSPACE-complete, the most difficult status within the realm of PSPACE problems.

So what makes Scrabble difficult? The researchers suggest that it comes down to two things the player has to consider:

1. Players have to choose where to use their tile on the board and account for the other pieces on the board.

2. Players have to decide which of their own tiles to use and form a word to play.

In the paper published on the arXiv preprint server, the authors write, "Scrabble players need to perform not one, but two computationally hard tasks, which is probably the reason why Scrabble is so much fun to play." You can certainly debate the entertainment value of scrabble, but the complexity proof is solid.

What the researchers ultimately proved can be quite technical, but it's a useful tool for theorists trying to measure complexity. But the researchers did have to make a few assumptions for the proof. For instance, it was assumed that each player knew which tiles would come out of the bag next. Consequently, they would know each other's letters—an unacceptable condition for die-hard scrabble aficionados. But for the sake of the mathematical proof, it doesn't really matter.

So now when Alec Baldwin's Words with Friends habit gets him into trouble, he can cite this research as proof that he was working on important, complex work.

For more information on PSPACE-completeness in board games, check out this site.

3 comments:

  1. a lot of strategy and tile withholding happens in pro play, players don't always play the highest possible play from their rack.

    ReplyDelete
  2. Hi, thanks for your comment and glad you found the post useful.

    Word Scrabble Finder

    ReplyDelete
  3. One thing I know is that sites like freescrabbledictionary.com and wordmakerscrabble.com (cheat sites) can make the word choosing easy for the tiles you have, but its hard to play someone when they are using them. I know I have played in games where our cell phones had to be turned in before we could start lol

    ReplyDelete