Learn to code a Game AI in Python in under 10 minutes – Part I

Today I will show you how you can create create a game AI in under 10 minutes. All you have to do is bear with me for 10 minutes.

This tutorial assumes that you have only basic knowledge of programming and are familiar with at least one procedural language (because we are going to use Python). If not, no worries. You can learn it later too. Let’s focus on the aim of this tiny endeavor.

Open AI

Open AI is an Open Source project on Artificial Intelligence providing a workspace for programmers (such as yourself) to experiment with AIs without much hassle on your behalf. Designing a Game AI required you to design a Game first. Well, we don’t have time for that… What we are interested in is the AI and not the game. The OpenAI Gym project provides us a set of utilities to incorporate our AI into any supported Games. At the moment, let’s just use a Retro-style Arcade game. Gym comes prepackaged with a set of environments based on Arcade Games but you can install fancier environments later.

Installing Open AI Gym

On Linux (tested on Ubuntu 17.10)

  1. Installing Python: We will be using Python 3 for this project. So, even though most Linux environments ship with Python 2.7 installed, we have to do a clean installation of Python 3. Open Terminal and type –
    sudo apt-get install python3
  2. Making sure pip is installed: Pip is the python command line package management tool which should be installed by default but it’s safe to check.
    sudo apt-get install python3-pip
  3. Installing OpenAI Gym: There are several instructions for installing Gym for several supported systems. Head over to Gym’s Github Page to see the specific instruction for your system. If required you might have to install linuxbrew too.
  4. Installing Python Idle: IDLE is a Python IDE developed by it’s creators. This enables us to run an interactive shell for Python. Let’s install this to check out our cool new playground. Open Terminal (if not already open) and run this code:
    sudo apt-get install idle

On Windows (tested on Windows 10)

  1. Installing Python: This is easy as pie for Windows users. Python now provides GUI Installations for your system. Go to their Releases Page and download the correct executable installer for your System Architecture (x86 if 32-bit and x86-64 if 64-bit) and install. While installing be sure to check the Set PATH variable box.
  2. Installing Gym: Open a command prompt window and type in
    pip install gym

Let’s get started

Now you should be locked and loaded to fire up your first OpenAI environment. Open a new Terminal on Linux and type in “`idle“` and hit Enter. It should open up an IDLE prompt.

On Windows, open up a Command Prompt window and type in “`python“` to open an interactive shell.

Put the following code. (Note: Python  IDLE might show a multiline detected error if you copy and paste the code so you have to type it in manually, no shortcuts 😛 ).

import gym

env = gym.make('MountainCar-v0')

state = env.reset()

env.render()

You should see a screen like this:

Screenshot from 2017-12-05 21-46-21

Environment running on Linux

slide

Same one on windows

The goal in this game is to get this car to the top of that mountain with the Yellow Flag on it. The rules of the game are:

  1. You can only push the car to the left (state 0), not at all (state 1) or to the right (state 2).
  2. There is no penalty for going left
  3. Each step you make gives you a -1 point. So, you have to complete it in the minimum number of steps.

The variables for any environment in OpenAI Gym can be categorised into 2 sections:

  1. Observation Space: The data you get from the state of the environment (e.g.,  current position and velocity)
  2. Action Space: The data you put into the environment (e.g., push direction)

For this game the observation space returns you a list of 2 values.

  1. The first one is a measure of your displacement.
  2. The second one is a measure of your velocity.

You can perform an action by specifying a single variable having a Discrete value 0,1 or 2. A value of 0 means a push to the left, 1 means no push and 2 means a push to the right. By learning to co-ordinate the pushes, your AI must overcome the hurdle of climbing the hill. First let’s use a dummy method to achieve our goal. Open a new file named test.py and paste the following code into it and save:

<pre>import gym

env = gym.make('MountainCar-v0')

env.reset()

state, reward, done, info = env.step(2)

vel = state[1]

accl = vel

for _ in range(1000):

 env.render()

  if(accl >= 0 or state[0] > 0):

    state, reward, done, info = env.step(2)

  else:

    state, reward, done, info = env.step(0)

  if(state[0] >= 0.5):

    break

  accl = state[1] - vel

  vel = state[1]



print('Solved')</pre>

This will do the job. Open a Terminal and type in “`python3 test.py“` and you can see the car in action. But this is just a fix for a particular game. There are several paths you can take from here. For instance, you can apply a Neural Network to simulate more than one episodes and at each state, update the nodes until your NN figures out the problem. Or you can implement a Reinforcement Learning Algorithm like I’ll be showing in the next tutorial to improve this AI. If you are familiar with the basics of AI algorithms, implementing one should not be a problem.

Further Reading

Here is a list of resources for learning AI algorithms:

  1. Reinforcement Learning – Wikipedia

  2. Neural Network – Wikipedia

  3. PyBrain

  4. General Game AIs in Industry

P.S., if you have not already seen it, now might be a good time to check out my earlier post about the several Optimization Algorithms. You can also see my Python implementation of such algorithms and try to implement it here. Stay tuned for the next Part to learn how to implement a proper algorithm for such games. Good luck exploring !

If you like this post please do share it and subscribe. If you have a query or would like to add to this post, please comment down below. Thanks for reading.

Advertisements

Our future in the hands of AI

It’s been all over the news. About 3 and a half months before this post, a massive feat was accomplished in the history of AI research, or rather, a popular feat. The Open AI DOTA 2 Bot beat two of the world champions in their own game – 1v1 champ Syed Sumail and Artour Babaev. Now for those of you (including myself) who are not a hardcore DOTA fan, you must be thinking – “Well, ok. What’s the big deal?”. Remember when Deep Blue AI beat Gary Kasparov at Chess? Well, it’s that big a deal. DOTA 2 is one of the world’s toughest MOBA games till date – some would argue it’s “the” toughest. I had a go at it but failed at the basics. It’s just too complex. Mastering the game takes painstakingly long practices. And how would you feel if years of your practice was surpassed by a week-long trained AI ?

Turning now and looking back to the last decade, we have to ask ourselves where we stand today. With things like IBM Watson, Open AI and others, what future are we looking forward to? Is it a dark-deep cataclysmic world full of mindless metal bots hunting for humans, or is it like in Astro Boy? That, only time will tell.

Needless to say, we have been assured that we are not in danger. And in my humble personal opinion, I don’t think we are. Because today, AI research has become very domain specific. While Open AI is a community to further the existing knowledge we have about Artificial Intelligence, IBM Watson (a coginitive platform) is more about the commercial application of that knowledge and integrating it into a business model for better outcomes. We also have Siri, Cortana and Google Assistant which are more focused on personalizing your data using Machine Learning techniques. And after all, none of these are programmed to kill, are they (except, maybe that DOTA2 bot) ?

“Why didn’t you guys just hand the world over on a silver platter?”

“Maybe we did”

I, Robot (2004)

While I agree that we should not hand the world over on a silver platter or a motherboard, it is a fact that most of us today depend heavily on machines to automate our tasks for us – at home, at school and even while searching for a news. I mean, when was the last time you heard something went down and went over the newspaper to find the news? We just don’t have time for that anymore. No, we can just type it in Google and bring up what we need. The only time I wrote a letter was in high school for my English exam. Personal letter just doesn’t exist, substituted completely by e-mails. So just maybe, we did. Has it been a bad experience for us? I don’t feel that way.

The only being capable of destroying humanity, is human himself.

And we are already doing it. We don’t feel the need for an AI to do it for us. Do we? Let me know in the comments down below. And thanks for reading.

P.S. Stay tuned till tuesday for my next post where I will show you how you can create your very own game AI in under 10 minutes.

If you like this please comment and share.

Optimization Algorithms (and their uses)

So I have not written a post in days. Partly because of my workshops and exams and partly because I was indulging myself deeply into studying Machine Learning. One of the ideas that provoked me was this – Which aspect of Machine Learning can we truly call an AI ? Now I know this is not an original question and there must be hundreds of discussion threads on this topic, but I will try and illustrate what I have understood. From one perspective, there is no true ‘best’ Artificial Intelligence technique.

An Optimization Algorithm is one which finds you an optimal solution for a given problem within a particular problem domain. The problem domain may be fixed or might be variable. The same base-algorithm can also be applied to several problem domains. In other words, for a given list of possible ways to solve a problem (or come close to solving it), an Optimization algorithm searches for the way that offers least resistance and most benefit. There are several such algorithms. Which reminds me, there is an entire directory of this over at Wikipedia. You can follow this link

https://en.wikipedia.org/wiki/Category:Optimization_algorithms_and_methods

to read more about them.

Now if you are familiar with these systems, you can argue that the Neural Networks or the Genetic Algorithm are more suited to any problem domain, but, the counter-argument that they are (fundamentally) less suited to solving problems related to one specific domain seems to surpass it. Suppose I have a game of Chess. I can use a GA-based system and train it for days and I know that still, it won’t be anywhere near today’s Chess AIs which are primarily based on MiniMax or some other variant. This is because in them, the heuristic functions are designed for and only for that game (and none other). You cannot expect a Chess AI to play good Poker, but you should expect it to play veteran chess. So it seems that the problem boils down to what our objective in building the autonomous system is. Unless you want to invent a Terminator, that is what you would do. Pick an algorithm best suited for the task at hand. When I attended my first AI Workshop, I saw the lecturer train the Neural Networks with a carefully chosen sample. But he kept calling it a ‘Random Sample’. At first I thought he was cheating on us because it all seemed counter-intuitive to me. So I went straight to him and asked him. He gave me what I believe is a very precise answer –

“Would I teach you the alphabets A, B, C and D today and expect you to write G and H tomorrow ?”

I realised that even a Random sample must follow certain criteria. The better your training set, the better the results. And as a generalisation of the aforesaid hypothesis, the better suited your algorithm and (if applicable) the better your training set, the better the outcome from the testing set.

I have written seven programs in the past 1 month. I have shared 2 of the most interesting of these over at my website. I have provided the links below.

Please note that I have just started learning AI and as such, there might be innumerous faults in my understanding. I would be grateful if you can help me rectify my misconceptions by suggestions, so, if you have any queries or suggestions please do leave it in a comment below. And finally, thank you for reading. Kudos ! 😉

Grapher (A JAVA desktop application to solve mazes or plot paths)

A tic tac toe game using MaxiMin algorithm and heuristic determination

Simple Path Finder Algorithm in JAVA and Python

The age of AI is upon us and almost in every digital market scenario, we are witnessing the involvement of some form of Artificial Intelligence, either in unremarkable forms or in appraisable forms. Some of the emerging projects in Artificial Intelligence are Google’s DeepMind, IBM’s Watson, Apple Siri (who hasn’t heard that name before?) and Microsoft’s (Halo-based AI) Cortana. Maybe Turing was just a tiny bit off the mark when he said that machines will be able to “answer” like humans by the end of the 20th century. But, only time will judge just how far off the mark he was. This post however, is not about AI, but rather about a specific topic of Rule-Based Expert Systems which are mathematically equipped and programmatically armored to solve certain (and only those certain) problems based on some set rules.

Depth-First Search

For those of you who are still reading this, 😛  if you want to learn about AI, I strongly suggest you subscribe to the MIT OpenCourseWare video lectures on AI over at their YouTube Channel. That is where I learnt all this!

So, we are building a basic Path-Finder, and so we will stick to DFS and not proceed further. What is DFS? DFS is a technique to find a path from one node of an undirected graph to another node of the same graph. How will it help us? It will show us a path that leads from one point on our map to another. We start off at the starting point, navigate through each node until we hit a dead end or the goal. If we hit a dead end, we retrace (called backtracking) our path to the previous node and try another “unvisited” node. If all the nodes of the current node are visited, we backtrack again to the previous node and so on. If we hit the goal, Hurray! We found it!

Show me some codes

For those of you who prefer codes over explanations, here is a class in JAVA that finds the DFS Path for you

 

import java.lang.*;
import java.util.*;

public class DFS{
 private String nodes[][];
 private String visited[];
 private String stack[];
 public DFS(int n, String[][] adj){
     nodes = adj;
     visited = new String[n];
     stack = new String[2*n];
 }
 public boolean isVisited(String node){
    if(Arrays.asList(visited).contains(node)){
        return true;
    }
    return false;
 }
 
 public void setVisited(String node){
     if(!Arrays.asList(visited).contains(node)){
         for(int i = 0; i < visited.length; i++){
             if(visited[i] == null){
                 visited[i] = node;
                 break;
             }
         }
     }
 }
 
 public void addToStack(String node){
     for(int i = 0; i < stack.length; i++){
         if(stack[i] == null){
             stack[i] = node;
             break;
         }
     }
 }
 
 public void popFromStack(){
     for(int i = 0; i < stack.length; i++){
         if(stack[i] == null){
             stack[i-1] = null;
             break;
         }
     }
 }
 
 public String stackTop() throws Exception{
     for(int i = 0; i  0){
                return stack[i-1];
            }else{
                throw new Exception("No DFS Path found");
            }
         }
     }
     return null;
 }
 public void print(String[] array){
     System.out.print(array[0]);
     for(int i = 1; i " + array[i]);
     }
     System.out.print("\n");
    }
     
 public String[] trimmedStack(){
     int l = 0;
     for(int i = 0; i < stack.length; i++){
         if(stack[i] == null){
             break;
         }
         l++;
     }
     String[] stk = new String[l];
     for(int i = 0; i < l; i++){
         stk[i] = stack[i];
     }
     return stk;
 }
 
 public int visitCount(){
     int l = 0;
     for(int i = 0; i < visited.length; i++){
         if(visited[i] == null){
             break;
         }
         l++;
     }
     return l;
 }
 
 public static void getDFSPath(int num_nodes, String[][] nodeMatrix,String start,String end) throws Exception{
     
     long startTime = System.nanoTime();
     
     DFS dfs = new DFS(num_nodes, nodeMatrix);
     String cursor = start;
     String goal = end;
     dfs.setVisited(cursor);
     dfs.addToStack(cursor);
     boolean check = true;
     while(cursor != goal){
         check = true;
         for(int i = 0; i < dfs.nodes.length; i++){
             if(dfs.nodes[i][0] == cursor && !dfs.isVisited(dfs.nodes[i][1])){
                 cursor = dfs.nodes[i][1];
                 check = false;
                 dfs.setVisited(cursor);
                 dfs.addToStack(cursor);
                 break;
             }else if(dfs.nodes[i][1] == cursor && !dfs.isVisited(dfs.nodes[i][0])){
                 cursor = dfs.nodes[i][0];
                 check = false;
                 dfs.setVisited(cursor);
                 dfs.addToStack(cursor);
                 break;
             }else
                continue;
         }
         if(check){
             dfs.popFromStack();
             cursor = dfs.stackTop();
         }
     }
     long elapsedTime = System.nanoTime() - startTime;
     System.out.println("Total Elapsed Time (nanosecs) : " + elapsedTime);
     dfs.print(dfs.trimmedStack());
 }
}

and the same in Python.

import time
class DFS:
     def __init__(self,n,nodes):
         self.nodes = nodes;
         self.n = n;
         self.visited = [];
         self.stack = [];
     def isVisited(self,name):
         if name in self.visited:
             return 1;
         else:
             return 0;

     def setVisited(self,name):
         if name not in self.visited:
             self.visited.append(name);
     def addToStack(self,name):
         self.stack.append(name);
     def popFromStack(self):
         self.stack.pop();
     def stackTop(self):
         return self.stack[len(self.stack)-1];
     def printStack(self):
         print(self.stack);
     def getDFSPath(num_nodes,matrix,start,end):
         start_time = time.time()
         dfs = DFS(num_nodes,matrix);
         cursor = start;
         goal = end;
         dfs.setVisited(cursor);
         dfs.addToStack(cursor);
         check = 1;
         while(cursor != goal):
             check = 1;
             for i in range(len(dfs.nodes)):
                 if(dfs.nodes[i][0] == cursor and not(dfs.isVisited(dfs.nodes[i][1]))):
                     cursor = dfs.nodes[i][1];
                     check = 0;
                     dfs.setVisited(cursor);
                     dfs.addToStack(cursor);
                     break;
                 if(dfs.nodes[i][1] == cursor and not(dfs.isVisited(dfs.nodes[i][0]))):
                     cursor = dfs.nodes[i][0];
                     check = 0;
                     dfs.setVisited(cursor);
                     dfs.addToStack(cursor);
                     break;
                 else:
                     continue;

             if(check > 0):
                dfs.popFromStack();
                cursor = dfs.stackTop();
         print("---Execution Time is %f seconds ---" % (time.time() - start_time))
         dfs.printStack();

You can see that I put some benchmarking code within the functions. Well, I tested several varieties of DFS and BFS (some other time..) algorithms and compared the execution time. It seems JAVA runs faster than Python does. But I guessed so. Anyways, so now we have a system that can output the path to the goal, given all the nodes and connections. But wait… How do we format the input? Well, it should be pretty clear from the code but just in case, an example function call in JAVA would look like this:

DFS.getDFSPath(5,{{“A”,”B”},{“B”,”C”},{“B”,”D”},{“D”,”E”}},”A”,”E”);

and in Python, it looks like this:

DFS.getDFSPath(5,[[“A”,”B”],[“B”,”C”],[“B”,”D”],[“D”,”E”]],”A”,”E”)

And that concludes our post. Finally, in footnote, try tinkering with it and see if you can make it find the most optimal path to the goal. Paste your code in the comments below so others can see this too. If you feel the post is missing something or something must be changed, feel free to email me or leave a comment below. Thank you for reading. Stay tuned for more of the same..