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.

So I had the urge to program something yesterday and somehow decided to take a look at flappy bird. I used a HTML5 version by uralozden. I wanted to write an algorithm that plays flappy bird.

The first idea was to try random moves and record the good ones. But before that I changed the game a bit so that I can get access to the flap() function and interject an AI function. This version of flappy bird is written with Phaser.

Making AI possible

I created a Timer which looks like this:

    aiTimer = new Phaser.Timer(game);
    aiTimer.onEvent.add(randomAI);
    aiTimer.start();
    aiTimer.add(0.2);

In line 2 I insert my function which handles the AI in this case randomAI.

Creating the random AI
The basic idea of the random AI is super easy. Pseudo code looks like this:

If best score > current score:
    use saved moves
else:
    use random moves

I used this approach so that I won’t take forever to get a good enough series of moves. How do we get saved moves? It’s pretty easy. I added code to the score function which works as follows:

if best score > current score:
    do nothing
else:
    best moves = current moves

At that’s basically it. Here you can see at video of the bot playing (started recording mid simulation). It’s a bit laggy but super easy to record thanks to recordit.co:

Using (perfect) information

This version didn’t work so great. The timing was really important. Even if the timer had a few milliseconds lag the bird didn’t make it. You can see this in the video pretty good. The great thing is that we can get access to all the data. Two things would interest us especially. Firstly, the y coordinate of our bird and secondly, the y coordinate of the pipes.

Again I looked around and we can get access to these two data points pretty easily.

birdie.body.y // position of the bird

fingers.forEachAlive(function(finger) {
    finger.y // position of all pipes
}

I don’t want to get into details but Phaser has some internal workings which doesn’t makes it so easy to access the next finger aka. pipe.

The next step was to write a function which controls our height, which basically looks like this:

if(birdie.body.y + offset > goal) {
    flap();
}

Super easy. Nothing special. If we are too low, flap otherwise do nothing. So how does this AI perform? Take a look at the video:

Looks pretty good, eh? I let it run for a while and it stopped because there was an error in the original game which created pipes which were so high that it was impossible to flight through the gap. It was around a score of 99. I’m satisfied.

For the one project I talked about a wanted to do some prediction. The data set had about 50k entries and 200 attributes and first I tried caret for R. It was incredible slow. Matrix operations are fast but it other algorithms are just slow. So I looked around a bit for alternatives. I knew some people use C# for such tasks but not working on Windows I didn’t thought that this was the ideal setup.

Lately, the JVM had received a lot of attention so I looked for ML libraries for Java, Clojure and Scala and settled on Weka. I used it a few years ago but only with its GUI.

I never really programmed in Java thus here are the first step in Weka for Java noobs.

Install Java and Weka

I work on Linux for most of the data work. If you work on Debian or ubuntu you have to install the following packages:

sudo apt-get install java-common

This package installs the JRE (Java Runtime Environment) which allows you to run .jre files.

sudo apt-get install openjdk-7-jdk openjdk-7-source openjdk-7-doc openjdk-7-jre-headless openjdk-7-jre-lib

This installs JDK (Java Development Kit) which includes the headers and all that stuff.

sudo apt-get install weka

Finally you can install weka which includes tons of different algorithms. Here’s a short overview:

Classification algorithms (examples)

[table]

Bayes, Functions, Trees, Meta

NaiveBayes,LibSVM,J48, Additive Regression

BayesNet,MultilayerPerceptron,M5 Model trees, Bagging

Bayesian Logistic Regression, Linear Regression, RandomForest,Random Subspace

[/table]

Full list: Classification schemes in Weka

Then there are clusters (EM, Simple K Means, Hierarchical Clusterer, …), algorithms for attribute selection like PCA,Stepwise, Forward Selection and for preprocessing: Resampling, Stratification, Normalization, etc. It’s pretty mature.

Set the right class path

export CLASSPATH=".:/usr/share/java/weka.jar"

Now I had, at least, to set the CLASSPATH for java to find my libraries. Also you have to add the current directory (“.”) so that java finds the files you want to open.

Convert your data

Weka uses its own file format called arff. It’s basically a csv file with a header which defines the data-types of each column. If you are working with CSV files Weka provides an easy way to convert your files.

java weka.core.converters.CSVLoader data.csv > data.arff

Write your environment

Now you can load the file into java, apply preprocessing and estimate and output a model. Here’s a complete example using a M5 rules to estimate a numeric value.

import weka.core.Instances;
import weka.classifiers.rules.M5Rules;
import weka.core.converters.ConverterUtils.DataSource;


public class M5Test {
    public static void main(String[] args) throws Exception {
        // read file
        DataSource source = new DataSource("./data.arff");
        Instances data = source.getDataSet();
    
        // set outcome (which column? starts with 0)
        // for last column use data.numAttributes() - 1
        data.setClassIndex(0);

        // set up classifier (see the doc)
        String[] options = new String[1];
        options[0] = "-R";


        M5Rules rule = new M5Rules();
        rule.setOptions(options);
        rule.buildClassifier(data);
        System.out.println(rule.toString());  



    }   
}

You need to import weka.core.Instances and import weka.core.converters.ConverterUtils.DataSource for reading the file. If you file is read the next step is to set the outcome, i.e. which column do you want to predict. Afterwards you set the parameters for your classifier. You have to first import it with import weka.classifiers.rules.M5Rules in this example. Then set up the options which you can find in the dev doc.  If you are done with this you can create a classifier object, set its options and build the classifier. Afterwards you can easily output your model using the toString() method. This is the a basic file which just works.

Compile and run your code

Now you can save your .java file, compile and run it with:

javac ClassName.java && java ClassName

After a few seconds you should get your model. And that’s all.

More information

For more examples and ideas on how to use preprocessing and testing check out: Use Weka in your Java code.

Also the development docs come in very handy which lists all functions and its API specifications.