AI: Bejeweled

After WordGame I took a few week break and sat down to automate a Bejeweled clone. Again I took a HTML/JS version of the game because interjection JS is pretty easy. I liked the version by alkaruno.

Making AI possible

I actually didn’t change much. I only changed a bit of the cosmetic because I was writing it and starting at the screen for a while I changed the graphics to just simple colors and the background to white – so that it was less heavy. Then I injected my ai.js and it ran.

The Algorithm

Here’s the general idea: We try out all the moves and find the move which maximizes our additional points.

I just adopted the scoring function used by the game. Therefore, we have perfect knowledge about the score of our action. Next I found all possible moves. In case you never played a game like this. You can switch bricks. But a switch is only legal if it causes a line (horizontal or vertical) of 3 bricks to connect.

So, we see what happens if we swap positions. I recorded the swaps in a map / object. Then I calculated the resulting points and compared it to the current best move, so far.

You can see that the moves is optimal for each round, however it doesn’t have to be optimal in the long run. New bricks will be added randomly and these could change the outcome.

And that’s the algorithm basically.

Then I injected it into the game and added buttons for starting and stopping the AI. Also I created a slider which adjusted the time the AI stops before making a move. You can see in the video that if I make the delay between moves too low the game bugs out and square won’t get filled up.

Video

I recorded this video like usually with recordit.

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.

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.

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.

AI / Automate: Flappy Bird

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:

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:

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:

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.

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:

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.

Weka for Java noobs

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:

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

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

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

Classification algorithms (examples)

Bayes Functions Trees Meta
NaiveBayesLibSVMJ48 Additive Regression
BayesNetMultilayerPerceptronM5 Model trees Bagging
Bayesian Logistic Regression Linear Regression RandomForestRandom Subspace

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

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.

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.

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:

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.