I love my Scrabble app.
After I pick a word, it finds the best word I could have made with my tiles.
I have some rudimentary program skills so it has puzzled me as to how the app can do this so quickly.
I have broken it down in steps in my head.
Sequentially move through my tiles starting with single tiles.
Place the tile or tiles on the Scrabble board in every possible square in every possible orientation.
Compare each new “word” with all the words in an index of Scrabble words.
If it is a word, calculate the point total each time and remember both the point total and placement. I have no clue how that would be done.
Repeat for every single letter tile.
Repeat for a two letter combination and so on until possible seven letter combinations.
It just seems impossible for the app to do all this and do it so quickly. This doesn’t even count the apps ability to add tiles to the beginning and ending of words as well.
What makes this app do it so quickly?
It doesn’t have to wait for you to pick a word in order for it to calculate the highest-scoring word that you could pick, given the configuration of the board and the tiles available to you. It can calculate that very quickly but, more to the point, it can start doing so as soon as it has played its word.
It’s pretty trivial to brute-force, really. The board is 15x15, so there are 225 starting positions. The word can go down or right (if there’s an occupied portion, we just skip over it and continue on the free tiles). And there are at most 5,913 possible arrangements of 7 letters (from 1 to 7 letters). That is an upper bound of 2,660,850 possible moves–a tiny amount for a computer, even a weak one like on a phone.
Of course, many of these moves are obviously illegal, such as ones that start on an occupied tile, fall off the edge of the board, don’t touch any other tiles, etc. And it’s easy to filter out redundant hand combinations.
Once the easy checks are passed, it can check that actual words have been formed–also easy, using a data structure called a hash table. A hash table allows testing for existence (as in the Scrabble dictionary) in constant time. This could be a matter of nanoseconds.
Finally, once you have a list of candidate moves, it can test for the highest scoring one. This is also pretty straightforward math (given that humans can do it in their heads in a few seconds), and for a list of perhaps thousands of moves, it can find the best in a fraction of a second.
Surely there are more clever techniques, but due to the simplicity of the game the brute force technique is more than good enough.
I often wonder how many scrabble players are using programs to help them. I can hold my own up until about a 1550 rating and then I start falling backwards. I seem to go from 1475 to 1600 with low 1500’s being my most frquent zone. I often feel like my opponents are using help programs.
Right. You would still need a heuristic for picking the best move among the candidate moves, and that may not be the highest scoring one. There’s also strategy for denying moves to your opponent. Still, I’d bet that simply picking the highest scoring move would do rather well up until you got to professional play levels.
A lot of string matching algorithms are directly or indirectly based on dynamic programming. You start with a low but sure dynamic programming solution which you then analyze to figure out how to bring the running time down a notch or two.
I think getting your opponent to lose challenges on words like “coniine” would work even better.
But in order for that to work, you have to have an opponent who doesn’t have the dictionary memorized (i.e., not another AI, and not a world-class human player), and they either need to not know of you, or you have to occasionally bluff with words that really don’t exist so they think they can get away with challenging.