| c | h | r | i | s | . | m | a | k | e | s | . | s | t | u | f | f |
Word Soup Solver
A lot of pubs in England have a "pub quiz machine" or Itbox in them. It functions a bit like a fruit machine - you pay £1 or 50p to play, and you can win money. Instead of straight gambling, you can choose from a selection of skill and knowledge based games.
The selection of games varies by pub, but almost all of them will have Word Up or Word Soup. In Word Soup you are given a certain amount of time to find words in a grid of letters.
In 2013, I thought that Word Soup would be a good candidate to make a phone app to cheat with. My smartphone at the time wasn't especially powerful, so it was an interesting challenge to make fast enough algorithms for;
- Recognising the letters
- Finding the highest scoring words
This video (filmed 2013) shows the first viable version of the app running on an HTC Desire S and scoring highly against an Itbox emulator. You can see it correctly identifies every letter and then identifies the highest scoring word as 'CHILLIER'
At the time there weren't any general purpose OCR libraries that could run fast enough on a phone. This algorithm I came up with myself and it would make occasional mistakes (accuracy was probably around 99%). It compared the captured frames to the actual sprites used in the game - which meant it would break on different versions of the game which used slightly different fonts.
In 2017 I decided to rewrite the app as a way to learn about Machine Learning. The video below shows me using the latest version to win some money on a real machine. The app now incorporates a 'learn' mode where the user provides the correct letters for a few grids, and this is used to train a softmax linear classifier to identify the tiles.
The accuracy of this method on a 'good' screen capture (without glare) is about 99.9%.
Unfortunately a pub quiz machine basically pays out a fixed percent of the money it takes in, so if you start scoring very highly it will jack up the amount of points you need to win money. This game scores 1675 points which is top of the hi-scores but only good enough to win £1
The algorithm for finding the best word to play is an interesting problem on it's own. This is solved using a prefix map (like a trie) which jumps from any prefix to a list of all paths in the grid which spell it out. Extending the prefix map is efficient because you just have to check the ends of each path.
A more complicated problem is planning a strategy to completely clear the grid and win the 500 point bonus. There is some discussion of optimal tactics on the website of legendary* Word Soup player VBOB. Currently the app uses a greedy strategy although it priorities "time bonus" letters if the clock is running out. I imagine a full blown CNN similar to DeepMind's Atari playing AI's could solve this fully.
P.S. After completing the first version of this project, I later discovered that the identical problem (although not on a phone) had been completed already as a Part II project by a Compsci student at Cambridge (Beating Word Soup, Andrew Lewis, 2010). This was totally coincidental (apart from the popularity of Word Soup in college bars around that time!).
*among people with an unhealthy Word Soup obsession.