Game Simulation

- January 4, 2020

Projects

I have a small set of projects that I’m working on in my spare time. I tend to get easily burned out by projects, so I have to be careful to create simple milestones and avoid open-ended tasks and original research. It’s easy for me to get stuck thinking about grand issues and end up never writing any code. In the long run, I think I’m much better off solving small problems. My hope is that all these small problems will add up to something bigger in the long run.

Game Simulation

One of the topics that I’m interested in is simulating video games using just the available pixel data. There’s a lot of grandiose challenges related to this, like creating an AI agent that can learn to play games using just the pixel data. I’d like to eventually tackle these types of problems - but it’s not the right time yet for me, given my current abilities. And honestly, I’m more interested in making an AI that can understand the structure of a video game, rather than one that learns to play well without any symbolic reasoning for its actions.

To that end, I’ve made a simple game to help me work on this topic. The game itself is not particularly important. There are blocks that move around and interact with one another. They have visible attributes, like position and size, and they have hidden attributes, like velocity, and behavior type. There are actually no user actions for this “game” because that’s not particularly important yet. I’ll add actions in once there’s something to be gained by it.

The goal now is to create a simulation of the game that can set its state using only the pixel data available from each frame. Imagine that you’re playing in a sports game. You’re brain has a model - a set of expectations about how things work in this sport. As you see actions unfold, you anticipate behaviors from the players. As you go to take an action yourself, you anticipate the results of that action. If you mess up the action, you have to adjust your mental model to match the real state of the world instead of what you thought it would be. That’s how I think a simulation of a game should work too.

Now, a game that has no randomness and no hidden state could be simulated with 100% accuracy - but that’s not really the goal. The goal isn’t to recreate all the pixels, but rather to maintain a reasonable representation of the game that is useful for analysis and taking actions. “Reasonable representation” is a bit vague. In truth everyone’s mental model of a game is different, and some may be more useful in particular scenarios. I’d like to come up with a good way to evaluate a simulation based on self-consistency, complexity, coverage, applicability towards goals, etc; but I think I can focus on that later.

As for the simulation itself, here’s a rough outline of how I think it should proceed from frame to frame:

• Assume that we have a set of objects from previous frames which have visible attributes (like position, size, orientation, etc) and hidden attributes (like velocity, type, behavior, etc) - or assume that we have no state if this is the first frame.
  1. Predict: the next set of objects and their states that we expect to see on the next frame of the game - both visible states and hidden states. One way to do this is to use a large set of rules about the results of interactions between objects.
  2. Detect: the next set of objects and their visible states using the pixels in the next frame of the game. Hidden state cannot be detected using only the new pixel date. One way to do this is to use a trained neural net that can recognize objects and their visual state from a single frame.
  3. Resolve: our Prediction with our Detection. Update the visible states with what was detected. Update the hidden states using knowledge from past frames. One way to update the hidden states might be to use our set of prediction rules in reverse over a period of time. Set the hidden states according to what would cause those rules to be applicable.

I’ve listed three steps, Predict, Detect, and Resolve, that we cycle through for every frame. Each step has its own problem that needs to be solved in order to have a simulation run smoothly over a range of inputs. One possible way to create these three functions is to use different machine learning techniques for each step. That may be my end goal, but that’s much too ambitious for now.

Instead, I’m building a program that will help me manually create and evaluate these functions so that I can explore various ways to solve them. The framework allows me to move forward and backwards through the simulation and it shows me all of the current simulated state using a treeview. I still need to add support for modifying the functionality in real-time, without needing to restart the program. And I think I need to add an evaluation score or graph so I can quickly tell how the simulation is performing.

Benefits of a Simulation

For completeness, I’d like to list some of the benefits to having a simulation of a game:

• Add information to help a player make better decisions. A heads-up-display indicating possible enemy hiding locations.
• Determine which actions are good or bad based on simulating into the future. Go this way, not that way.
• Take quick actions for the player in dangerous situations. Break now so you don’t run into the car in front of you.
• Dissect the mechanics of the game to learn new techniques. Running in a particular way helps you move faster.

And of course, I believe I will learn things during the development of this project that will help me down the road. I’d love to end up with a framework that lets me quickly create a simulation from an existing game. And maybe that will require using Machine Learning techniques to speed up that process.