author: Thomas Brus
title: Predicting the Outcome of Scrabble Games
topics: Algorithms and Data Structures , Case studies and Applications
committee: Arend Rensink
end: January 2015


WordFeud cheat apps essentially let you look up words on the basis of limited information about the letters in that word. Given a dictionary, this is essentially a search algorithm, but the complexity of the task requires that you pick a suitable data structure.

The "limited information" may be given in any of a number of ways:

  • Known placed letters (a pattern W-R- allows WORD, WARS, etc)
  • Known unplaced letters (the letters WR also allow WREN, BREW etc)
  • Forbidden letters
  • Regular expressions (which in fact encompass all of the above)

In this assignment you will investigate the most suitable data structure for this purpose, using as strong a specification mechanism as you can achieve. A good candidate for such a data structure is Multiple-Valued Decision Diagrams.

To carry out the assignment well you must implement and experiment with candidate data structures, in a language of your choice. Optionally, you can make the resulting program available as a web service or app.



Additional Resources

  1. The paper