AI / Automate: WordGame

After Flappy Bird I sat down and tried to automate an other game. Github provides a search function which helped me locate games with words. A found WordGame by headshota which is a simplified version of Scrabble.

Making AI possible

I didn’t have to change much – basically I didn’t have to change anymore. But because I’m lazy I put the dictionary variable in global scope so that I don’t have to load it myself.

The algorithm

The algorithm is pretty easy. We have two inputs. Firstly, we have some letters. Secondly, we have a dictionary of valid works.

Sort our dictionary

There are several approaches to this problem. I choose one which is pretty easy. So, firstly I created two dictionaries. There’s our common standard dictionaries with English words which is used for the game. It includes words like HELLO or TREE. From this dictionary I created a second one which has sorted characters. So instead of hello it saves EHLLO and instead of tree it stores EERT. I stored this in a list but with the same index as the original. That is when HELLO is the 68th element in the original dictionary EHLLO is the 68th element in the sorted one.

The great thing about this approach is that you don’t need to generate permutations. Instead you can just generate substrings of our available letters.

Generate possible words

Now, we have some available letters. Again, we sort these. Now we have a sorted list of letters. We can take this list and generate all possible subpattern from this list. We can do this pretty easy using suffixes and prefixes. The cool thing is that we don’t have to change the position. Let’s say that we have these letters: AEEMRT.

AEEMRT
 EEMRT
  EMRT
   MRT
    RT
     T

AEEMRT
AEEMR
AEEM
AEE
AE
A

AEEMRT
A EMRT
A  MRT
A   RT
A    T

AE MRT
AE  RT
AE   T

AEEMRT
 EEMRT
 EE RT
 EE  T

You can see that there are basically three operations. Firstly, we generate suffixes, then prefixes and put them together. That’s it. Really easy algorithm.

Are these real words?

The next step is to check if our generated words are actually valid, real words. That’s also pretty simple. You probably remember our sorted dictionary. Now we just have to check if any of our generated words is in this dictionary. For example, we can see that EERT is in our generated words. We check it and see that EERT is in position 68. Now I convert it to it’s English equivalent – index 68 in the dictionary and return the list with valid words.

What’s the best word?

Most likely we can form different words. The next and last step is to find the best word. The rule depends on the game, in this game the rule is that each letter gets one point. So we just sort the list using a comparison function. In this case it’s a simple function that compares word lengths.

legalWords.sort(function(a, b) {
    return b.length - a.length;
});

Now we can just return the first element in our list. An advantage of this approach is that we can easily adjust to the game rules. Let’s say for example, that the letter Z brings additional 3 points. We just adjust the comparison function to include the extra 3 points.

And that’s it. The algorithm, although it’s written in JS, is faster than necessary. So there’s no problem. I actually put it on a half a second timer and sped up the original game’s timers.

Video

Again I recorded this screencapture with recordit which just works out of the box which is great.