A Pypy Runtime for AWS Lambda

Category : AWS , python

Python is a great language for the on-demand style of Lambda, where startup time matters. In terms of execution speed, there are better choices available. Where computational performance matters one improvement is to use Pypy, the Python interpreter with a JIT compiler. It can execute the same code much faster. There is just a slight penalty in startup time compared to CPython.

I was curious how Python and Pypy would compare on AWS Lambda. As Amazon announced recently, it is now possible to provide your own Runtime for Lambdas.

Creating a Custom AWS Lambda Runtime

Before you can start with creating your own runtime you should have a simple Lambda function. I recommend you start by creating a serverless application. This way you not only get a plain Lambda but also an API Gateway and Cloudwatch logs set up. And it is much quicker to edit code, iterate and put it to version control.

Creating a new runtime is based on a shell script you have to provide. This script will do initialization work, call an interface for requesting the next task/incoming request, dispatch it to whatever runtime you are providing and respond to another interface with either a success or an error message.

Starting from the example is easy. You can quickly set up a test project using serverless that will execute the example bootstrap code. The example runs in an endless loop, working on one task in each iteration. AWS must be starting/killing this loop based on how many tasks are waiting for execution and probably some other factors.

Pypy does not run out of the box. The interpreter has to work on Amazons Linux environment. Unfortunately, downloading a compiled binary didn’t just work for me. And I couldn’t find a version specifically for the Amazon Linux. The problem is that a libbz2 library was not available. In fact, it is available in the environment but Pypy does not find it. The recommended solution to create a symbolic link to the library is also not an option, because the environment is read-only (except for /tmp/). To not spend too much time on this I fired up an EC2 instance with the Amazon default image and copied that library next to the Pypy interpreter into my package.

To create a first “Hello World from Pypy” application running you need to call Pypy from within the shell script and send the response back to the Runtime Interface. There is no error handling yet and starting a new Pypy process on every request is far from optimal, but this is already a working solution.

A better way is to move the processing loop from shell script into Pypy. This way there already is a running process, all imports have been done and if parts of the code use initializers or caching this state will be kept for the next request. The bootstrap script looks a lot simpler now:

The logic is now located in Python code and run by Pypy. With the custom runtime code in place, we can switch between a standard Python3.7 runtime and our own in the AWS Lambda web interface:

Comparing Pypy and Python3.7

So how does the simple Pypy runtime compare to the default Python3.7 implementation? Let’s create an example where the Lambda has to use its CPU. I wrote a simple one-liner to calculate prime numbers from 2 to 200000:

For sure there are better algorithms to do the same thing, but it serves the purpose well. Calculating the prime numbers takes considerably longer with CPython than with Pypy. On my machine, it takes around 1 second with Pypy and 3 seconds with CPython.

In an AWS Lambda environment, both runtimes are executing the same handler.py and calculate prime numbers. This is how long they take to run the code:

Calculating the primes takes more than 5 seconds when executed with python3.7 but only slightly above 2 seconds with Pypy. We have found a case where Pypy is a lot better than CPython. This was my hope when starting to build the runtime.

But, as you can see in the first request, the Pypy runtime takes a long time to initialize. This is logged in CloudWatch as “Init Duration: 1641.69 ms”. In this test scenario, it does not matter because a request takes many seconds to finish. With its better computational performance, the Pypy runtime still comes in first. In a more typical scenario, this Init Duration will be much more important. And this brings us to the downsides of this approach.

Downsides of the Custom Runtime

The initialization phase takes way too long. It is not visible what exactly happens during that time. But the bulky size of the code package will most likely be part of it.

Let’s rerun the same test as before but without the heavy calculation and ignore the Init Duration:

The execution time for a “Hello World” application is higher than with Python. I don’t understand why this is the case. Monitoring Pypy runtime_interface gives me sub-millisecond times for what my code executes. Still, the Lambda execution Duration is reported to be somewhere between 10 and 30 ms. In contrast, executing the function with Python3.7 gives Durations close to 1 ms with only a few spikes. This should be more or less equal. There either is a problem in my implementation or in how AWS handles a Custom Runtime. If you have an idea what goes wrong here please add a comment. In any way, this diagram is much closer to real-world usage. And Python is faster here.

Also, the deployment package is big. Nearly 30 MB are uploaded to S3, even though there is hardly any function code inside. For many cases, this is going to be a showstopper. I believe the package size can still be reduced by specifying in more detail which Pypy files are necessary. If Amazon ever considers this as a default choice it would solve the issue, because then you would not have to upload the interpreter within your package.

Wrap-up

Running Pypy on AWS Lambda as a custom runtime is possible and not very complicated. There is a clear advantage over CPython when it comes to long-running computations. Packaging the whole interpreter bloats up your Lambda package and increases your initial startup time. Typically, being lightweight and having a quick startup is more important than raw computational speed. Therefore, I can only recommend this approach for exceptional cases.

If Amazon decides to provide Pypy as a default Runtime, this could be different. You would not have to bundle the interpreter and the startup time might become a lot better than now while the computational advantage of Pypy will still be there.

You can find all the code in my Github repository.


Serverless on AWS Lambda

Category : Android

Serverless computing is a cloud-computing execution model in which the cloud provider dynamically manages the allocation of machine resources.

At my current project, I had the freedom to create a new service a service from scratch and to relatively freely choose the technology stack. The only given was that it should either run inside the old datacenter or on AWS.

Serverless

Having experience with administrating root servers in the past, I also know how easy it is to fail at that task. It takes a lot of effort to keep a system up to date, adjust the configuration for changing requirements and handle hardware failures. With serverless services, like AWS Lambda, all this is abstracted away and handled by the Cloud provider. It auto-scales your service on demand when the load increases. Even better, AWS Lambda will only charge you for the number of requests. If you don’t use a service the only thing you pay for is the zip file stored on S3.

Compared to a typical service based on virtual machines or containers, these benefits are huge. However, they also come with a downside. Most notably is the performance impact. AWS will kill idle Lambda instances and spin them up on demand. This means the service has to be loaded from S3, extracted and started when the first request in a longer period of time comes in. There are huge differences in the startup time of certain technologies. Node.js and Python are among the fast end, while Java with Spring takes a lot longer to start.

Caching

As instances can be stopped at any time, this also affects caching strategies. There is a simple cache in API Gateway which caches full responses. It can be activated by checking a checkmark and setting the maximum size. However, many times you don’t want to cache the complete response, but pieces of information required to compute it based on the input values.

It is possible to cache data inside a Lambda, but there is no guarantee about how long it will be available. This depends on the load, access patterns and probably how many resources Amazon currently needs. If you want more control you have to use an additional service like Elasticache. However, this part cannot be started on demand. As a central instance which has to be available and quickly serves requests, the cache has to be up and running all the time and you will be charged even when it is not used.

In the case of my service, the load is high enough to make sure there is one Lambda instance running all of the time. It is not always the same instance, but changes are rare enough to provide a good amount of cache hits.

Wrap up

Going serverless was a great choice and is superior to manually running a service in a container, VM or even the bare metal in many ways. It provides the option of scaling to nearly an infinite amount of requests (whatever Amazon can handle) without the hassle of configuring complex auto-scaling strategies.


Make your website or web-app offline available

Category : Android , web

Android developers vs. web

One great advantage of native apps over web apps is that they don’t depend on an online connection to start. Therefore the startup is fast and you can use them in no-network conditions. Just, web apps can also have this advantage when done right.

If you look at a website like Google Docs, you notice that it appears even when you are offline (given that you have visited the same page before). It is even possible to edit files while offline. You can achieve the same with an HTML5 feature called the Offline Application Cache.

Use the Offline Application Cache

While keeping a state locally and syncing requires more effort, making your web(site/app) offline available is easy. You just have to use the Offline Application Cache. This is a single file with information about everything the client should keep in its local cache.

At first you create a file called cache.manifest with the following content:

CACHE MANIFEST
# Cache version #1

CACHE:
/index.html
/css/style.css
/images/header.png
/images/footer.png
/images/background_portrait.png

Change the resources below CACHE: to the required files of your project. Keep in mind that these resources are not requested again, even if they changed. If you want them to be re-downloaded, you need to change the cache manifest itself. This is the reason for the version counter. Increase it by one to make the clients refresh all resources.

The next step is to add it to your site html tag:

<html manifest="cache.manifest" type="text/cache-manifest">

Save, refresh the website on your client and you now have an offline available app. You can test the Offline Application Cache by switching off your server or internet connection and refreshing again. It will reload despite having no connection.

Network and Fallback

In case you have more dynamic content there are two sections you can use in the Offline Application Cache file called NETWORK and FALLBACK:

# Download default_state.xml to local cache
CACHE:
/default_state.xml

# Resources that have to be downloaded from a server
NETWORK:
/current_state.xml

# default_state.xml is used when current_state.xml is not available
FALLBACK:
/current_state.xml /default_state.xml

In this case, current_state.xml requires an online connection and can not be cached. default_state.xml will be added to the cache and used as a fallback when current_state.xml could not be downloaded.

For example, instead of your state data you can put a “state could not be retrieved” message into the default_state.

Wrap up

It is simple to make your web app offline capable. Most of the hybrid- or web-apps I see on the market fail to work without an online connection. It is a pity, because there is so little work necessary to greatly enhance the user experience.

Dynamic state is a different thing, though. Keeping and syncing state is a hard topic, whether native or on the web. While not simple, it is possible with HTML5 Local Storage.

Still, showing your own website with a message is much better than the default browser error. If you have web parts in your application that come from a remote server, be sure to use the Offline Application Cache, at least for the front page and your resources.

A Beginner’s Guide to Using the Application Cache

HTML Standard Application caches


Native- and Mobile Web Apps

Category : Android , java

As a native apps developer since 2008, I have seen time and time again the wish to develop everything with one toolset. Most often, the toolset of choice is the web, or HTML, CSS and JavaScript. In all cases I have experienced, this was a wrong move and users never liked the web app. Therefore, I say that native apps are superior to what a web app can achieve for most mobile use-cases.

Web vs. Native

However, that does not mean the web technology is a bad platform. It was just designed for different devices and use cases. For example, it is incredibly easy to show rich documents with web technology. This would be a hard task in native development and quite often a web view is embedded into native for that reason. Over the last decade(s), many great use cases have been enabled in web technology that were unthinkable a few years ago. Think of Google Maps, Live chats on websites, Youtube, 3D-Content, etc…

But there are important mobile aspects where the web still fails to deliver. First and foremost there is no layout mechanism that matches Androids way of developing for multiple screens. Unlike on a desktop, where pixel density has been relatively stable for a decade, on mobile devices it can be completely different. A normal phone screen might have a resolution of more than full-HD, while a 10″ tablet still has a HD-ready resolution. A single pixel is much much smaller on the phone than on the tablet. If you are designing your website with pixel sizes, your graphics might have the right size on either of them, but not on the other.

The normal solution in the web world is to use percentages of the screen size instead of hard coded pixels. This solves the problem above, but introduces a new one. What is the right image to show if it stretches to some percentage of the screen? It should be big enough to use the great phone screen, but not bigger than necessary to save bandwidth and keep page loading times low.

A related problem is to size a button correctly. You want to have the size of a button approximately match the size of a fingertip, so it can be pressed easily without taking too much screen space. This works neither with pixels, nor with percentages of a screen.

If we want to solve this problem, we first have to understand that this is not a one-dimensional problem. Size is not the only parameter we have. A users device can be on any position in these two dimensions: [small – large] X [low dpi – high dpi]. Android uses resource folders for both dimensions, where each device chooses its correct format. There is an explanation in the designing for multiple screens documentation.

Another thing is integration into the system. How do you create an Intent? How do you set an alarm? What about receiving Push Messages? If your app doesn’t need these features that is fine. But working around the limitations of a web container with native bridges enforces you to maintain both native for several platforms and web content.

And finally the promise of “develop once, it works everywhere” is simply not true for web technology. Different browsers behave differently and websites are cluttered with special case handling for certain clients. You still have to test and maintain how your web app looks on iPhone, iPad, several Android phones, browsers and other platforms you care about. And I am not yet talking about a platform-specific look and feel.

The right tool for the job

However, there are certainly cases when a web application makes a lot of sense. If you are mainly mirroring website content, it probably is a good idea to reuse much of your existing website. Even I, as a strong native promoter, have chosen to develop a web application in my last project.

The project was about using a tablet for controlling hardware, in this case to control several lights and display videos in a car prototype. Besides the pain points explained above a web application has its own strengths like being available without installing.

Another reason for not using a native approach was the server part. If there is a (web) server anyways, it can as well serve web content instead of just data and instructions. A native app would require one more layer on top of everything.

Most drawbacks mentioned above don’t apply for this case. The system includes one specific set of tablets, so it doesn’t have to adapt to multiple screens. The simple layout does not depend much on resolution and dpi, because most of it is text and vector content. The only image used is the background. And there is no system integration necessary.

Not just a boring website

Above is a simplified version of the app, that I use for development. It is connected to a 4-channel LED (red, green, blue, white) to generate different colors. With the Administratormodus, you can modify color values of each channel.

To make it feel more like a native app, it has a homescreen button and no url bar on top. The application uses the whole available screen, except for the notification bar and the navigation buttons. It also features a splash screen while loading. This is easy to achieve, but goes a long way in making your web app feel like it belongs to the platform. Read more about it in Making Fullscreen Experiences.

Wrap-up

For this project, I believe it was the right approach. The customer is happy with a lightweight and clean solution. But it was a special case in a well defined environment. For most consumer apps I still recommend native development.


This website switched to HTTPS

Category : web

My webhoster 1blu has finally added the possibility to get a free LetsEncrypt SSL certificate for this website. So www.ulrich-scheller.de is now available via HTTPS.

Let’s Encrypt

With LetsEncrypt getting an SSL certificate is free. There are many reasons for using HTTPS but hardly one against it. This is especially true whenever you enter credentials for logging into your website. In case of this blog and profile page it didn’t matter too much, because the only person with a login is myself. All the content was and is available publicly, so there is no need for a high security level. However, HTTPS is also one of many ranking signals for search engines. And it is just good practice to use encryption wherever it doesn’t hurt.

Simple but not that simple

Moving your website over to HTTPS is very easy. Usually, you just tell your webhoster to get and install a certificate. Or, in case you are hosting yourself, you have to do these steps on your own.

However, keep in mind that this doesn’t magically fix all the problems. After you got your installed certificate and HTTPS running, there is more to check:

  • Links on your website should not point to HTTP urls. Make sure any internal link does not start with “http://”. The best way to fix it is not to change http to https, but instead leave out the complete protocol & domain part. This way links will still work, even if you would move back to http or change your domain. You can use www.whynopadlock.com for checking the links on your site.
  • Change the url of your Page in WordPress to https://
  • When another blog linked to your page, this link will continue to point to the HTTP version. For search engines, your HTTP website is different from the HTTPS site. To prevent losing a good ranking, make sure to redirect from your HTTP to the HTTPS version. This also ensures your visitors will use the secure protocol from now on.

There can be much more, depending on your setup. Read through this detailed guide to see what else might apply in your case. WordPress and a professional web hosting simplifies much of that work. However, most of the time it also limits how far you can go. For my page, I had to wait multiple years until Let’s Encrypt became available. Features like HTTP2 support are still not available.

Now I need to go ahead an fix the links on this site. If you see anything else that is breaking encryption on my site, please tell me in the comments.


Virtual Reality Experience with Google Daydream VR

Category : Android , java

Virtual Reality is a hot topic these days. A few weeks ago I had the opportunity to test an Oculus Rift with Touch Controllers. PlayStation VR and HTC Vive have also been released lately. Android Developers like me have their Cardboards, which are a very low-cost option.

Daydream VR

With the release of their Pixel devices, Google announced the Daydream VR. Similar to the Cardboard, you place your mobile phone in the VR headset and don’t need additional high-end hardware. For 70€ it is still a low-cost solution, if you don’t factor in the expensive phones.

My first attempt at trying Daydream VR unfortunately was not successful. I got the small Pixel phone, which worked flawlessly except when being used in the Daydream VR headset. It had regular reboots, a problem many others around the web have as well. And even worse, it had extreme visual drift as you can see in the video below.

It is hard to tell how bad that visual drift is. Your vision turning around while your body tells you there is no change in orientation makes you feel sick within a minute.

So after playing around an making a factory reset, I decided to return the device and get the Pixel XL instead. Turned out this was a good choice. With the Pixel XL everything works flawlessly. Head tracking has no noticeable delay and the touch controller works great.

Experience

Compared to a Cardboard this setup is a great improvement. A Cardboard only has a single button for user interaction. The touch controller gives navigating a whole new dimension. In games it is used as a magic stick, for controlling a steering wheel or tilting a playground to move a ball around. Every game seems to have its own way of navigating around. I believe we will see a lot more navigation styles before a few will crystallize as standard.

While Daydream with the controller is much better than before, you also see what is still missing. Turning your head around works great, but moving is not possible at all. In a VR world like Fantastic Beasts I want to move around and look at the beasts from all sides. In most of the applications this is not possible.

Graphics are pretty good with the right game/application. The detail level is impressively close to an Oculus Rift. However, in both VR systems you recognize single pixels. Even a resolution of 2560×1440 pixels is not much in VR mode, because it has to split for two eyes and fill the whole viewport. But every current VR system has this problem.


Personal Jenkins Server with Docker

Nowadays, every software development team should have a continuous integration server like Jenkins. This is as true for Android developers as for any other platform. It makes sure the current source code compiles and all the tests succeed, so nobody is blocked by a broken build. A CI also forces you to have a build in one step and to perform it regularly, usually on every commit.

Most often a continuous integration platform is used for development teams. However, it also gives many benefits to single developers. Multiple times I had the problem that old projects would not compile or work after switching to a new computer. Also, I often forgot to run all tests if they seemed unrelated to my code changes. And last but not least there is the deployment-pain when the last time was long ago.

Where to host?

A Jenkins build server would solve all these problems. But I didn’t want to spend a lot of money on hosting, because it is for private, closed-source projects with no profit. And running Jenkins on my development machine does not help, because it is still the same environment as in my IDE. My first idea was to use a RaspberryPi server. While this is not a fast computer, it runs on very little power and would have more than enough time for builds.

After playing around with it, I discarded that option again. Jenkins on a RaspberryPi works – but it is not an x86 device. So if you are not using the Android SDK, a Raspberry might be an option. For me it is not, because the Android SDK is not available on ARM systems.

Another low-cost option is VirtualBox. You set up a linux server inside a virtual machine and host Jenkins in there. Although the virtual machine is hosted locally, it can easily be transferred to anywhere if necessary. I had this option in mind for a while. But I didn’t like the overhead VirtualBox brings into it.

So when Docker announced their MacOS release, I was eager to try it.

Set up Jenkins

Installing Docker is an easy task. There is a good Getting Started guide on their website. You will learn using the docker command and how to run containers. It turns out there already is a working Docker container with an installed Jenkins. Run it with

docker run -p 8080:8080 -p 50000:50000 jenkins

This starts up a new container with Jenkins running on port 8080. You will see the following website:

Docker Jenkins first login

For getting the initialAdminPassword you have to access the running container.

Ulrichs-MBP:~ uscheller$ docker ps
CONTAINER ID        IMAGE               COMMAND                  CREATED             STATUS              PORTS                                              NAMES
82812e782a95        jenkins             "/bin/tini -- /usr/lo"   7 minutes ago       Up 7 minutes        0.0.0.0:8080->8080/tcp, 0.0.0.0:50000->50000/tcp   stupefied_bell

will show you all running containers. Look up the name of the container, in my case it is stupefied_bell. Edit the following command with your container name:

docker cp stupefied_bell:/var/jenkins_home/secrets/initialAdminPassword . && cat initialAdminPassword && rm initialAdminPassword

This prints the initialAdminPassword for logging in. If you enter it on the website, you can continue the setup process and have a running Jenkins in Docker.

Useful commands

You can stop your running machine with

docker stop stupefied_bell

When you want to start it again, don’t use the docker run command from above. It would create a new instance. Instead, simply use

docker start stupefied_bell

Get a shell on this container as user jenkins

docker exec -it stupefied_bell /bin/bash

Get a shell on this container as root

docker exec -u 0 -it stupefied_bell /bin/bash

Install Android SDK from shell

Docker Speed

Performance-wise this setup is great. The docker container starts and stops within seconds. The only delay is caused by Jenkins startup-time, showing the please-wait message. My Jenkins is not yet overloaded with plugins and jobs so it takes less than 15 seconds for everything to be available.

I tested the build-performance with my Android project Laska:

gradle clean build test

The time for executing this command on my native machine is around 2 minutes 34 seconds. The Docker container takes only 1 minute 54 seconds. In multiple runs the outcome was always in favor of Docker. I can not explain why this happens, as native should be the fastest. It might be a configuration setting on my machine.

Wrap up

Using Docker to host Jenkins is a great solution for solo developers. It is easy to set up, especially with a pre-packaged Jenkins container, and can be transferred to a dedicated server if necessary. Build speed is the same as in a native environment.


Should you go for self-employment?

Category : career

I am now 9 months into my career as a freelance consultant and would like to share my experiences with it. The question if you should make that switch too depends on many factors and can not be answered in general. Much of it is about yourself rather than the outside world.

Did it work out?

This is the important question to ask when someone created a company. During the last 9 months I had a constant stream of work which was paid much better than all my time before. And this is despite me stepping back from managing teams of 20 developers to writing software myself.

Because a developer has less responsibilities and less meetings than a team lead, it is much easier to take a day off. This is very valuable to me as a paraglider, as it strongly depends on weather conditions. Last year I had several incredible (for myself) flights and great experiences. Before, I was trying to achieve this year after year as an employee, but there was always some important meeting or another reason preventing it from happening.

On the other hand I sometimes miss being important. I enjoyed creating teams of developers and optimizing the way we work on many layers. I also enjoyed being responsible for products with millions of active users. However, this is not typical for most employees but rather a special case of my previous role. And the fun was declining more and more at the end in favor of company politics, pushing Excel-Boxes and taking part in software-design-committees.

So overall, yes, it worked out very well. I am much more relaxed, more happy and being self-employed gave me the biggest income-boost I had by far.

Is it hard?

This depends a lot on what you already know and what type of person you are. Obviously there are some hard parts to creating your own company. The hardest is that you will be responsible for everything. You have to find customers yourself, sell yourself as valuable to their project, handle all the paperwork and taxes and never break any law.

Many of us hate responsibility. I am not talking about being responsible for finding a restaurant for dinner tonight. I am talking about make a big mistake and you go to jail-responsibility. If you are that type of person, you will probably find it difficult.

I was lucky to be responsible for several teams of developers in my last job. So my mind was already prepared for having lots of responsibility. Additionally, I have been self-employed part-time during university. So when I tell you it is not hard at all, take this into consideration. For many developers this might be a bigger change.

Keep your eyes open

In Germany, there is a subsidy for founders coming out of unemployment called Gründungszuschuss. I urge anyone interested to further look into this, as it basically is free money for nothing in return. The Gründungszuschuss is an incentive for unemployed people to start their own business. I will not go into more detail here, but it is pretty easy to become temporarily unemployed.

I knew this subsidy existed but I never believed I would be eligible for it. I needed my tax advisor telling me that in fact I was. You probably need the same in other cases. Talk to people in a similar situation and read about it. But most importantly, once you choose to become self-employed, take action.

Next steps

So currently I am really happy with my situation. I have a lot of personal freedom, 3 days of home office per week and a good pay.

The next optimization I wish to make is breaking the money-for-time relation. But this is another topic for another post at another time 🙂

Should you do the same? That depends on your own situation, but in many cases it is a big win. Drop me a note if you are considering it.


Implement a turn based game AI with optimizations

Category : Android

My last post about implementing a turn based game ai became famous on Reddit/Programming for one day. It looks like many developers are interested in this topic. Some readers, with more knowledge of the topic than myself, have added interesting insight that I would like to share with you here. If you haven’t read the first post, you might want to have a look there first.

Minimax algorithm

The algorithm that I presented is called Minimax and is famous in academia for creating turn based game AIs. It has this name, because one player tries to minimize the getValue() result and another player tries to maximize it.

For improving the AI strength you either have to improve your getValue() function, or increase the size of your decision tree. Usually, getValue() can only be improved to a certain point which is far from perfect. Therefore, at some point you want to focus on increasing the tree size. This means looking more half-moves into the future.

We can increase the tree size simply by using a higher recursionDepth value. It depends on your game, which value is good enough for a strong computer AI. Laska is using a recursionDepth value of 4 for the strong computer player, 2 for medium and only 1 on easy. This is good enough, because I want my users to win most of the time. I want them to enjoy beating a hard computer opponent if they are good players.

If your AI should be more competitive, you need a higher recursionDepth. The problem is, that you will soon have a high runtime complexity and calculation time. If we have a Branching Factor of b and a recursionDepth of d, we have a complexity of O(b^d). So let’s say Laska has 4 possible moves on average and I am using a depth of 4. Then my AI is crunching through 4^4 = 256 situations, calculating and comparing their value. This is not very much and also the reason I never had to optimize.

On the other hand, if you are implementing a chess AI the branching factor is 35. There is much more competition in this game and you might want to have a depth of 8. Then you are looking at 35^8 = 2.251.875.390.625 situations, which obviously is too much.

Alpha-Beta Pruning

In this case you should focus on further optimizations. The most important is called alpha-beta pruning. It will cut off subtrees whenever they can not influence the root decision (making a single half-move) anymore.

When can this happen? Every move could turn around the game instantly. In chess, you could be way behind in everything regarding your getValue() and still make a checkmate within a few moves. So how can you ever discard a whole subtree?

It is true that at some point you have to consider every possible move. However, when we know there is a winning path, we don’t need to figure out if there are more in this subtree. If we have a winning path down the tree, we just start with the first move. This goes both ways. If we have a path that definitely gives us a loss, our opponent will choose exactly that path.  We don’t need to evaluate any other moves from his side.

This is not restricted to winning moves. If we have already found out, that move 1 gives us a minimum value of 5 we can use this knowledge and stop evaluating move 2 once we know it is worse. We know move 2 is worse when our opponent can force it to a value below 5 with optimal moves on his side. This is best described in the following gif from Wikipedia:

alpha-beta pruning

Alpha-Beta Pruning in action

On the left side we have the situation described above. The rows in red mark red moves and the ones in blue stand for blue moves. Blue is minimizing the value, while red is maximizing it. So on the lower left side, when blue has to choose between 5 and 6, we know that he will choose 5. In the next subtree, blue can choose between 7, 4 and something else. We can already stop at 4, because whatever number comes, this is already the preferable subtree for blue. We don’t need the correct value, as long as we still get the optimal move.

Alpha-beta pruning makes a huge difference when the decision tree is large. According to this link, it reduces the number of leaves to the square root. So if we use the previous example with 2.251.875.390.625 leaves, we only have to check 1.500.625 situations. That is still a high number, but not impossible anymore.

Example Code in Laska

So how does the alpha-beta pruning look in a game like Laska?

public Move bestMove(int recursionDepth) {
	int maxValue = -SOME_HIGH_NUMBER;
	Move bestMove = null;
	Vector<Move> possibleMoves = field.getPossibleMovesOfActivePlayer();
	if (possibleMoves.size() > 1) {
		for (Move move : possibleMoves) {
			LaskaField nextField = getNextField(field, move);
			int value = -alphaBeta(nextField, maxValue, SOME_HIGH_NUMBER, recursionDepth - 1);
			if (bestMove == null || value > maxValue || (value == maxValue && new Random().nextInt(2) == 1)) {
				maxValue = value;
				bestMove = move;
			}
		}
	} else {
		bestMove = possibleMoves.firstElement();
	}
	return bestMove;
}

The bestMove() method still looks much like the old version. It now calls alphaBeta() instead of getValueOfMove(), but both will return the value of a given move. The alphaBeta() value is negated and the method takes parameters for alpha and beta, in this case +/-SOME_HIGH_NUMBER.

public int alphaBeta(LaskaField currentField, int alpha, int beta, int depthleft) {
	if (depthleft == 0) {
		int value = currentField.getValue(currentField.activePlayer);
		value -= currentField.getValue(1 + (currentField.activePlayer % 2));
		return value;
	}
	Vector<Move> possibleMoves = currentField.getPossibleMovesOfActivePlayer();
	if (possibleMoves.size() == 0) {
		return -1000;
	}
	for (Move move : possibleMoves)  {		LaskaField nextField = getNextField(currentField, move);
		int score = -alphaBeta(nextField, -beta, -alpha, depthleft - 1);
		if (score >= beta)
			return beta; 
		if (score > alpha)
			alpha = score;
	}
	return alpha;
}

Also alphaBeta() didn’t change too much. At first, there is the recursion termination. When depthleft equals 0, we just calculate the current value and return it.

If we are not in a leave node we calculate all possible moves. If there is none, the current player has lost the match and we can return a -1000 here. Otherwise we continue walking through the tree. Just this time we pass parameters for alpha and beta.

Alpha notes the highest value of a move we are interested in and beta the lowest. If the current move has a score higher than beta, we can prune the graph here and stop calculating further, because the other player will not let us make this move. Otherwise, if the score is higher than alpha, we have found a better move and need to save it.

Laska now has an unbeatable level, using a depth of 8

Laska now has an “unbeatable level”, using a depth of 8

Runtime comparison

To see how much the alpha-beta pruning impacts performance, I ran a test case with the old algorithm playing against the new version with increasing depths of the decision tree. In the following diagram you see the time used for playing a complete game (up to 100 moves or until we have a winner).

runtimes of minimax vs alpha-beta pruning

runtimes of minimax vs alpha-beta pruning

As you can see, there is no visible difference for depths up to 5. Alpha-Beta is considerably faster at depth 6 and it totally owns Minimax on depths greater than this.

Further improvements

While this improvement is dramatic for higher depth levels, we can still do much better. Some further improvements are independent from your game, some depend on special knowledge about it and others trade a little accuracy for increasing the depth of your tree.

The next optimization you might want to look into is ordering of moves for improving alpha-beta pruning. How you order your possible moves impacts how well the alpha-beta algorithm prunes the graph. If you start with best moves first, it can cut off more of the tree later on.

There is a great overview of further improvements on StackOverflow. You can dedicate a lot of time to this. However, don’t forget to check if your algorithm is already good enough. Because if the main task is not beating Garry Kasparov, you probably should improve user experience, design, marketing, etc.. first.


Implement a turn based game AI (on Android)

Category : Android , java , machine learning

Game AI

Developing a game AI can be as much fun as playing, especially when creating your own computer opponent. I am going to present you a simple pattern that works for nearly all turn based game ai’s, especially where there is a defined set of possible moves. This pattern is powering my own Laska for over 6 years already and I have been using it before for personal 4-Wins and Tic-Tac-Toe games.

For this you don’t need a perfect solution, but something that can win against most human players. It should prevent making obvious mistakes and the strength must be easily adjustable. I will show an algorithm that works for two players, but can easily be extended to more.

Basics

In a turn based match we always have moves made by every player. When saying move, what I actually mean is a Ply, or half-move. That is, the move of only one player. Our game AI will look a defined number of half-moves into the future and find the best possible move.

Your game should have a state which can be classified as good or bad. So in chess, we have a winning situation when the King will be taken out in the next move. This is great for one player, and really bad for the other one. There is also a lot in between. Let’s say one player has more Pawns than the other. This would be a good indicator that he is in a stronger position. In Laska, a winning situation is when the other player has no more possible moves available.

winning situation in laska

The blue player has won. Note that this simple situation is faked and can never happen in the real game.

Algorithm

There is a simple pattern that works for all these round based games. It is based on a decision tree of all possible moves and the classification value of the game situation.

From the starting position in Laska, there are four movers with six possible moves. Every move will lead to a forced jump. After that, there are either two possible jumps or three possible moves, depending on which Pawn was moved at the beginning.

starting position

starting position with four possible moves

If you can attach a value of the game situation to each node in the graph, it will be easy to select the best move. You need to figure out the subtree with the best worst-case situation.

 

For this, all your game has to provide is two methods:

  • getPossibleMovesOfActivePlayer(field), which will return all the possible moves for the active player on a given field.
  • getValue(field), which will return a useful value of the situation. It should be high positive when player 1 has won and high negative when player 2 has won.

With these methods available, you can find out what is the best move:

public Move bestMove(int recursionDepth) {
	int maxValue = Integer.MIN_VALUE;
	Move bestMove = null;
	Vector<Move> possibleMoves = field.getPossibleMovesOfActivePlayer();
	if (possibleMoves.size() == 1) { 
		// if there is only one possible move - no need to calculate the value
		return possibleMoves.firstElement();
	}
	for (Move move : possibleMoves) {
		int value = getValueOfMove(move, recursionDepth);
		if (value > maxValue || (value == maxValue && new Random().nextInt(2) == 1)) {
			maxValue = value;
			bestMove = move;
		}
	}
	return bestMove;
}

The method starts with an initial value of Integer.MIN_VALUE. Then it considers all possible moves. If there is only one move available, this is automatically the best option. This is an optimization which gives tremendous speedups when using a high recursionDepth. The recursionDepth indicates the size of our graph. The more we look into the future, the stronger our ai gets.

In all other cases, where we have more than one possible moves, we calculate the value of all of them with the specified recursionDepth. The part with Random().nextInt(2) is included to make the ai less predictable. If you leave out this randomness, the computer will always play the exact same game, if you do so as well.

So what does getValueOfMove() do?

protected synchronized int getValueOfMove(Move move, int recursionDepth) {
	int player = field.getPawn(move.from).pawnOwner();
	LaskaField nextField = new LaskaField(field.getFieldClone(), field.activePlayer);
	nextField.movePawn(move);
	LaskaAI nextAI = new LaskaAI(nextField);
	int value;
	if (recursionDepth > 1) {
		Move bestMove = nextAI.bestMove(recursionDepth - 1);
		if (bestMove == null) return 1000; // when game is won
		value = -nextAI.getValueOfMove(bestMove, recursionDepth - 1);
	} else {
		value = nextAI.getValue(nextField.field, player);
		value -= nextAI.getValue(nextField.field, 1 + (player % 2));
	}
	return value;
}

First it creates a clone of the field object for further calculation. On the cloned field (nextField), the given move is applied and the active player changed to the next one. With this new field, we now calculate the value of the following field. The simple case is when recursionDepth is exactly 1. Then we add the field value for the active player and subtract the field value for the other player. In my case, the getValue() method only factors in the Pawns of one player. Therefore it has to be called twice.

The more complex case is when recursionDepth is greater than 1. Then we recursively call the method bestMove() from above with a recursionDepth reduced by one. If there is no possible move and the bestMove is null, then the active player has won the match. So we return 1000, a very high number that can only be reached in a winning situation.

If there is a bestMove, this is what the opponent will choose to do. So for our move, this bestMove is the worst case that can happen to us. Because the value of the bestMove us calculated from the other players point of view, we have to negate it with value = -nextAI.getValueOfMove(bestMove, recursionDepth – 1);

Calculating the value

As mentioned above, you need to provide the getValue() method specific to your game. It receives the game state as input and returns an integer describing how “good” it is for the current player. In the case of Laska it returns values in the range of -1000 to 1000. Most likely there will be no perfect or correct return value. You have to create your own method and fine tune it over time. The better your getValue() method gets, the stronger your AI will be and you don’t need to use a high recursionDepth.

The weakest getValue() method will only return a negative number for a lost match and a positive number for a won match, otherwise zero. In this case you would have to use a recursionDepth that calculates all possible moves until the end of the game. In some cases this might be an option. The perfect getValue() method will already know all possible outcomes and give you perfect values. Your algorithm therefore only has to use a recursionDepth of 1.

Since most of the time it is neither possible to calculate all possible moves until the end nor to create a perfect getValue() method, we have something in between. In Laska the values are calculated like this:

  • For all of my pawns add 10
  • Add 5 for every of my pawn slices below the top, until there is an opponents pawn slice
  • If pawn is an officer add another 20
  • Add 2 if a pawn is on an outer field, instead of in the middle
red_has_value_37

Red has a value of 37, because there is a red pawn (+10), it is an officer (+20), there is another red pawn slice below (+5) and it stands on an outer field (+2)

For other games, think of indicators that obviously help towards winning. If pawns are taken out of the game compare the number of pawns. If you need 4 in a row to win give some value to 3 in a row, at least if there is still space for a 4th.

Unit Testing

AI is a poster child for using Unit Tests. In fact, you will have a hard time if you leave them out. Especially annoying are minor mistakes, that don’t break your algorithm but weaken the ai significantly. I have started without proper testing and ran into that problem far too often. Some years ago I realized the value of testing and can iterate much faster now.

You can easily test all the methods with synthetic input. Does field1 give a higher value than field2? Make sure the best move in field1 for player 1 is X. Whenever you think My AI should make this move now but it is not, create a test case and fix it. Either you will find the mistake, or realize that the AI in fact was correct and you were wrong. This way you will soon have a stable and strong AI.

Another cool and fun usage is to let one version of the game AI play against an improved one. During optimizing the getValue() method, I could only believe a change would make the computer stronger. This was until I created a test that played 100 matches of the new version against the old one. Now there is an evaluation of the strength and I can be sure whether my change is an improvement or just a change.

Optimizations

The algorithm above is not meant for winning a competition or to be perfectly efficient. If you want this, you can start with Peter Norvigs Artificial Intelligence: A Modern approach and read through some current papers. However, the algorithm is a pattern that works for nearly all turn based games and gives decent results, so you can move on creating all the other important aspects.

Some things that can be improved:

  • In every getValueOfMove() the whole field object is cloned. While this wastes some computation time, I found that the algorithm is still fast enough even on mobile phones. The field objects are not too big and cloning them simplifies the following steps. Also this makes it more easy to parallelize computation if that would be necessary.
  • After bestMove has been calculated, the value is calculated by stepping into the same recursion again: value = -nextAI.getValueOfMove(bestMove, recursionDepth – 1);
  • You can tune the randomness in bestMove() by collecting all moves of the same value and make an equally weighted choice between them.

If you can think of more, please tell me in the comments.

Wrap Up

As you can see, implementing a computer opponent in a turn based game is no rocket science. You only need to supply two methods and find the optimal move from the resulting tree as described here.

If you want to see the described algorithm in action, download Laska from the Play Store.


Recent Posts

Tweets