Space Race Extra: Making the Computer Player

Despite being a ground-breaking first in video game history, Space Race is a distinctly tedious affair. The original developers were limited by what they could squeeze onto a circuit board, but we have no such constraints.

So what can we do to make this game more interesting?

We can start by adding a one-player mode. Adding the logic necessary for a proper computer player would have been… challenging without a CPU. But we're using Python, not diodes and transistors (well, ok, we are using diodes and transistors, but in a different way).

Unlike in Pong, making a challenging computer player is not just a matter of whipping out our middle school math textbooks. The reasoning that goes into navigating the asteroid field is complex enough that you might be tempted to reach for a machine learning algorithm. But let's see how we can do with a less black boxy approach. The AI described below is the same one used in the BrowGames version of Space Race.

Just don't Crash

As a first try, let's be naive and just tell the computer to move forward at all times as long as it's not about to hit an asteroid. In other words, we'll only look one frame ahead and stop the ship if it's about to hit something. Here's what that looks like (note that any asteroids that the AI recognizes as an obstacle are colored red):
A Space Race computer player with very simple logic that avoids head-on collisions.
It definitely sucks. The most obvious shortcoming is that it doesn't anticipate asteroids hitting it from the side as it moves into an open space. It actually does make it to the top on occasion, but not enough to present a serious challenge to a human player.

Antici–pation

To make the AI smarter, we need to scan the asteroid field in front of it before making a move. The most direct way to do this is to take the known speeds and positions of all asteroids and project them forward in time some specified number of frames. If I find that moving the ship forward will cause any of those asteroids to enter its space (an invisible rectangle around it), I tell the ship not to move. Once the space ahead is safely clear again, the ship can move.

This more conservative approach will slow the ship down a bit, but avoid most of the collisions it suffered from before. I chose for the computer to look 20 frames ahead (⅓ second) because that is how long it takes to move by its own length. Here's what happens when I pit this more cautious algorithm against my "just don't crash" player (you can watch a similar match-up using the "Simple Computer Race" preset in the BrowGames menu):
A Space Race computer player that looks for collisions 20 frames ahead competing with one that just looks one frame ahead.
It's a considerable improvement and will probably be able to beat novice players. However, this is a little deceptive.

The original Space Race was designed such that the asteroids all had the same speed and wrapped around the screen at a constant rate, so players were always faced with the same pattern of obstacles. This makes the gameplay repetitive, and makes for a poor test of my AI.

Let's change the game a bit for the sake of testing our computer player. Instead of keeping the asteroids at the same speed, I'm going to randomize it such that the asteroid can be going slower or faster than the original speed by as much as 25%. Let's look again at our 20-frame lookahead computer player.
A Space Race computer player that looks for collisions 20 frames ahead, with variation in asteroid speed.
Suddenly, our cautious computer player is less impressive. It will avoid moving into areas where asteroids are close to hitting it. However, if an asteroid is, for example, 1 second away from hitting the ship and the ship is forced to stop because of other asteroids up ahead, the ship will eventually get hit.

Duck and Weave

I tried fixing this problem by making the computer look even further ahead before moving, but it didn't improve its score. The cost of increased caution is a slower pace of movement, and the benefit doesn't always outweight the cost.

Instead of making the computer player more cautious, let's try giving it more options. At every frame, it will go through the following options, in order, until it finds an acceptable one.
  1. Check for asteroid collisions if the ship continually moves forward for N frames. If no collisions are found, move forward.
  2. Check for collisions if the ship sits still for N frames. If none are found, sit still.
  3. Check for collisions if the ship moves backwards for N frames. If none are found, move backwards.
If the computer finds collisions in all possible actions, it will just move forward and hope for the best.

Here is an example of how our new computer player handles a particularly difficult asteroid pattern.
A Space Race computer player with complex logic that considers three possible actions.
It is always trying to move forward, but corrects itself when it runs into trouble.

Seems like it would be pretty tough to beat. Well, it is tough, but not impossible. Here I am competing with it in a 30-second game (I'm on the left).
A human player (left) competes with a computer player in Atari Space Race.
You'll notice that it can still get trapped on occasion, so it's not perfect. But I still lost to it most of the time.

There are ways I could make it better; for example, instead of just assuming the player is doing the same thing for N frames, I could account for more complex combinations of actions over that timespan. However, there are diminishing returns with increasing complexity, so I made the "Duck and Weave" computer player the default in the BrowGames version of Space Race.

Comments