So today I had the idea that an interesting project would be to build an app which can provide ‘assistance’ with scrabble like games — or cheating if you like. In particular I’d like to set it loose on Words With Friends in the first instance. Words With Friends is a Zynga game which is very similar to Scrabble but has a different board layout and number of tiles (presumably for legal reasons). It’s available on mobile devices as well as via Facebook and is very widely played.

What I want to be able to do is to take an image of the board position along with my tiles and make a recommendation as to where to play for a maximum score.  The output should be an image of the board as captured with the tiles to be played and their locations indicated.

The basic pipeline is:

  1. Capture the image
  2. Parse the image into a data structure amenable to search and scoring
  3. Using the players tiles, and an appropriate dictionary, work out the highest scoring move possible
  4. Render an output image with the best move played.

Moving beyond Words With Friends, once the initial framework is in place, it should be possible to snapshot a real life Scrabble board and do the same kind of thing. If I can get the code fast enough, ideally I’d like to be able to make this real time as an AR application processing realtime video from a mobile phone camera and showing the move overlaid on video of the board.

But one step at a time…I’ve decided to start with Words With Friends because it’s very easy to capture an image directly from the iPhone so I can focus on the harder parts of the code.

After a bit of Googling I’ve decided to build an implementation of Andrew Appel and Guy Jacobsen’s paper The World’s Fastest Scrabble Program as my WWF solver engine. My target platform is going to be iPhone initially and the aim is to have the whole app onboard. Depending on dictionary size, this may be a little enthusiastic so I may end up requiring a server side component but we will see.

Here’s my vision of how the app will work:

Picture of words with friends board and tile rack

Input Image including tiles

Picture of words with friends board showing best move

Output image showing best move

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s