Scrabble

I posted the “Puzzles” blog entry to LinkedIn and Supriyo SB Chatterjee responded by noting that “solving for Scrabble is a CSP too”. (Some time ago Supriyo won the New England Regional Colleges Scrabble Championships.) Indeed it is, an interesting kind of CSP.

When it is your move you need to make a choice that satisfies a number of constraints. You can only use letters from your tray (which you then replace). You have to form a word in the Scrabble Dictionary. You have to place the word to link up properly with what is already on the board. And your move changes the board (and your tray), so you have a “sequence” of problems to solve, where each problem in the sequence is dependent on your solution to the previous one.

I thought of calling this a “sequential CSP”. Of course, there have been many variants of CSP, including some with some form of “sequential” nature. Sequentially Dependent Meta-Constraint Satisfaction Problem: An Application to Video Games seems particularly relevant here. I thought of the acronym “SCSP”, but it has already been used at least twice, for Semiring-based CSP and for Structural CSP. So then I thought “SQCSP”, even though that risks confusion with Quantified CSPs. But there is the Semi-Qualitative Constraint Satisfaction Problem (SQCSP).

Of course, there is another aspect of Scrabble: it is a game, with two adversaries. So actually the adversarial constraint satisfaction paradigm seems relevant here. Looking back I see that Ken, James, Paidi and I didn’t actually use the “ACSP” acronym when we wrote up adversarial constraint satisfaction for ECAI 2004. Perhaps just as well: “a CSP”?

So one outcome of this was the thought that it could be useful to have some kind of list, taxonomy or categorization of the many variants of constraint satisfaction problems. Perhaps even a survey. I’ve posted on the Constraints Google Group asking people to provide pointers to CSP variants and hope to assemble a list to make available at the constraints Resources site.

Back to Scrabble, beyond just finding moves that satisfies the constraints, there are interesting issues of optimization and strategy. For example, do you want to go for a lower value move now to try to set up a high value one later or to prevent your opponent from using a potentially valuable position? I imagine there are books on Scrabble strategy.

Scrabble certainly has been computerized. In a match held way back in 1998, MAVEN defeated World Champion Joel Sherman and runner-up Matt Graham, playing together. But perhaps Scrabble can still inspire new ways of thinking about constraint satisfaction.