Game AI Problem Solving Challenge, Fall 2015

Design & Code: David Thue (CADIA & SCS @ RU)

Artificial Intelligence (AI) is an important part of many computer games, where it's often used to create dynamic challenges for players to overcome. In this problem solving task, your objective is to create an AI controller for a space ship in a simple 2D game. Survive for as long as you can by dodging incoming hazards, and earn a high score in Challenge Mode by shooting asteroids along the way. Welcome to Code Ship.

The screen is split into two main parts: the Playing Field on the left, and the Code Window on the right. By putting code into the Code Window, you can control the orangey/grey space ship that starts near the bottom of the Playing Field.

The Playing Field shows you the action in the game. Click the Play button to start the action, the Pause button to pause time during a run, and and the Reset button to start a new run. Hovering with your mouse will show tool tips that describe the different buttons.

The game can be run in two modes. In Training Mode, the stream of asteroids that your ship files through will always be the same after each reset. This can be useful while you test your code, but any high scores that you tally won't get counted. In Challenge Mode, the stream of asteroids will be different each time, but your high scores will be saved when your ship meets its end.

The Code Window is your main interface to the game. While it supports the functions of a basic text editor, we highly recommend that you write your code in an external editor (Notepad++ is an excellent free one) and paste the code in for execution. Browsers can crash at any moment, so make sure your code is safe on the outside!

Your code will be executed once every second. If you Pause the game, time will flow forward until the next second, your code will execute once, and then time will stop. Pressing Play at that point will cause time to resume.

To succeed in Code Ship, your AI controller will need to perform two kinds of task: sensing the environment and sending commands to your ship.

There are two things that your code can read about the environment:

• grid[,]: a 2D array of strings with 7 rows and 5 columns. Each string is a single character and represents something on the Playing Field.
• weaponReady: a bool about your ship's weapon.

For example, you can say things like:

  // print out grid cell at column 0, row 0
  print(grid[0, 0]);
  
  // test if the gun has finished recharging
  if(weaponReady)
  {
      print("I can shoot now!");
  }

There are two types of commands that you can send to your ship: movement and weapons

• moveX: an integer between 0 and 4 stating which column the ship should move to.
• moveY: an integer between 0 and 6 stating which row the ship should move to.
• shootFirst: a bool stating whether the ship should try shooting before it moves.
• shootLast: a bool stating whether the ship should try shooting after it moves.

For example, you can say things like:

  // move to column 3, row 5
  command.moveX = 3;
  command.moveY = 5;
  
  // try to shoot before moving
  command.shootFirst = true;     // like Han
  
  // try to shoot after moving
  command.shootLast = true;

Your code will be executed once every second.

Programming in Code Ship should feel familiar to anyone with general knowledge of C, C++, or JavaScript. Technically, it runs a simplified version of JavaScript (JS), so many functions that you could use in JS will work here as well.

Unlike in C or C++, you don't need to declare your variables, and their types will be automatically determined based on the data that you put inside them. Some examples:

  i = 0;            // makes a new integer called i because 0 is an integer;
  posX = 3.5;       // makes a new float called posX because 3.5 is a float
  output = "hello"; // makes a new string called output because "hello" is a string
  shootNow = false; // makes a new boolean called shootNow because false is a boolean

Conditionals are identical to C & C++. An example:

  // test grid location [x, y] and try shooting if there's an asteroid there and our weapon is ready
  if(grid[x, y] == "A" && weaponReady)
  {
      command.shootFirst = true;
  }
  

Loops are almost identical to C & C++; the only difference is that you don't need to declare your variables in 'for' loops. Some examples:

  // print out the grid (the upper left corner is 0, 0)
  // for each row j, step along the columns with i and add the grid cell [i, j] to our output string
  output = "";    
  for(j = 0; j < 7; j++)
  {
      for(i = 0; i < 5; i++)
      {
          output = output + grid[i, j];
      }
      output = output + "\n"; // add a line break in between rows
  }
  print(output);

  // search along row 0 for the first asteroid
  // stop when col points to its column or no asteroid is found
  col = 0;
  asteroidFound = false;
  while(!asteroidFound && col < 5)
  {
      if(grid[col, 0] == "A")
      {
          asteroidFound = true;
      }
      else
      {
          col++;
      }
  }
  

An infinite loop is a loop whose condition never becomes false. Infinite loops will crash Code Ship, and probably your browser along with it. If, for some reason, you'd like to see that happen, try entering the code below. Warning: you will lose everything that you've entered into the game!

  while(true)
  {
  }

If, on the other hand, you would rather avoid this sort of thing, please try to avoid writing infinite loops in your code. If you happen to write one anyway, just refresh the page to start over. (You'll still have a copy of your code in an external editor, right?)

The challenge of controlling an agent in a real-world environment (like a space ship in an asteroid field) is generally really hard, and computer games can provide a nicely simplified training ground for trying out new algorithms. Researchers at Google's DeepMind have been applying an AI technique called “Deep Learning” to this sort of problem, and the results are pretty impressive: the algorithm can “learn” to play Atari 2600 games from only the pixels on the screen and the current value of the score. Here's a video that shows Deep Learning in action, trying to learn Atari Breakout:

Google DeepMind's Deep Q-learning playing Atari Breakout

…and here's an article about it in the journal Nature:

Human-level control through deep reinforcement learning

Good luck!