Skip to Content

… And Scrabble Proved PSPACE-Complete

Following news that Pac-Man is NP-Hard, theorists determine the computational complexity of Scrabble.

Having been invented in the US in the mid-20th century, Scrabble is now available in dozens of languages and sells in numbers measured in hundreds of millions. That makes it one of the most popular games in the world.  

That has naturally piqued the interest of game theorists. “Since Scrabble is such a successful game, it becomes a natural question to determine the computational complexity of finding an optimal play,” say Michael Lampis at the KTH Royal Institute of Technology in Sweden and a few pals. 

The same question has been successfully asked of many board games, such as chess, Go and Othello, which tend to be PSPACE or EXPTIME-complete. But Scrabble is trickier because players do not know the order in which the tiles will be drawn meaning that chance plays a greater role.

The question that Lampis and co attempt to answer is this: given a Scrabble position how hard is it to determine the best playing strategy? 

They point out that in any given round, a Scrabble player is confronted with two tasks: deciding which word to form and deciding where to place it on the board. These tasks are related because the words that can be formed depend on the position of letters on the board. 

But which of these task is it that makes Scrabble hard? What Lampis and co show is that both are hard and give a proofs of each to back up their claim. That’s impressive because it allow us to ‘see’ why Scrabble is hard. 

“We establish that during the course of a game, 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,” they write.

That’s not to say computational complexity theorists are done and dusted with Scrabble. Their next task is to discover whether there is a polynomial-time algorithm to determine the move that would maximize the score achieved in this round.

Now that would be handy! 

Ref: arxiv.org/abs/1201.5298: Scrabble is PSPACE-Complete

Keep Reading

Most Popular

still from Embodied Intelligence video
still from Embodied Intelligence video

These weird virtual creatures evolve their bodies to solve problems

They show how intelligence and body plans are closely linked—and could unlock AI for robots.

pig kidney transplant surgery
pig kidney transplant surgery

Surgeons have successfully tested a pig’s kidney in a human patient

The test, in a brain-dead patient, was very short but represents a milestone in the long quest to use animal organs in human transplants.

conceptual illustration showing various women's faces being scanned
conceptual illustration showing various women's faces being scanned

A horrifying new AI app swaps women into porn videos with a click

Deepfake researchers have long feared the day this would arrive.

thermal image of young woman wearing mask
thermal image of young woman wearing mask

The covid tech that is intimately tied to China’s surveillance state

Heat-sensing cameras and face recognition systems may help fight covid-19—but they also make us complicit in the high-tech oppression of Uyghurs.

Stay connected

Illustration by Rose WongIllustration by Rose Wong

Get the latest updates from
MIT Technology Review

Discover special offers, top stories, upcoming events, and more.

Thank you for submitting your email!

Explore more newsletters

It looks like something went wrong.

We’re having trouble saving your preferences. Try refreshing this page and updating them one more time. If you continue to get this message, reach out to us at customer-service@technologyreview.com with a list of newsletters you’d like to receive.