My latest project is a fighting game for the Android named “Concussion Boxing“.
The game will be of the Virtua Fighter\Tekkan\Street Fighter genre.
The game I played the most out of these three is Virtua Fighter. What was the most amazing thing about Virtua Fighter was the AI. The more you played against it the better it got and the better it learned your fighting style.
Random button mashing didn’t help in this game.
I don’t know how Virtua Fighter’s AI was done, but I decided to pick Neural Network as the algorithm to implement my own learning and adaptive AI.
Not only did I not know how Virtua Fighter’s AI worked, but I didn’t find almost any article explaining how to use Artificial Neural Networks in a real game. Most of the material on NN was either strictly Academic or didn’t explain the subject with an example of a real game.
I supported a Kickstarter from a guy called Daniel Shiffman who wrote a book about AI in games called “The Nature of Code“. This gave me a good start on the basics of Neural Networks.
(Source code for this article is available at: http://ideone.com/qyeZ1x )
2. The Perceptron
One thing you need to know about NN is that you need to get the algorithm code exactly right. Any small error is gonna make the NN non functional.
It is easy to make these errors when you are new to NN because it is not always clear what is right and what is not.
Lets start with a simple trivial NN called a Perceptron.
A Perceptron is made of a single Neuron, input connections and output connections. Being a single neuron it’s not really a network per se.
A Neuron has a single output but zero, one or many inputs. Each input is connected to the Neuron with a weight.
The Neuron sums the inputs according to their weights, process the result with an Activate function and pass that to the output.
Our Activate function will be simply max(min(x, 1.), 0.) where x is the weighted sum of the inputs for this Neuron.
In the game simulation we feed the input from the game to the neuron, calculate the output and then use the result to control our AI controlled character.
Specifically, in Concussion Boxing we will use the Perceptron to make the enemy boxer maintain a distance from the player character.
xi inputs, wi weights
I mentioned the inputs are weighted, but what weights do we need to use? Different weights will make the Perceptron behave differently and thus the learning part of the NN is to adjust these weights.
So how do we adjust the weights and how learning occur?
We will focus on a learning method called Reinforced Training.
With reinforced learning we will examine the output that was produced with a specific input by our NN .
We will then calculate by other means what is our desired output for this specific input and we will adjust the weight by back propagating the delta between the desired output and the actual output.
For a single Neuron the equation is the following where delta is the output delta and learn is the learning constant.
xi – inputs
wi – weights
Notice we multiply the delta by the input xi. This is because the weighted connection has contributed to the final output of the Neuron by xi*wi.
This works in our case because of the specific Activate function we chose.
In other words we distribute the output delta between the weighted connections according to the input.
It is important to note that the learning phase is only temporary.
The NN is supposed to work with desired results even after we stop backward propagating, if it doesn’t then something is wrong.
Keeping a Distance
In my fighting game “Concussion Boxing” the boxers walk on a 1D axis. They can either go forward, backwards or stay still.
We want our Neuron to control the enemy boxer and make him keep a constant distance from the player boxer.
Our Neuron will have two inputs and thus two connections.
The first input is the distance between the AI boxer and the player boxer and the second input is a constant 1.
In this case our single Neuron system output can be expressed like so:
wi – weights
Our boxers can either go forward or backwards but we cannot tell them which speed to walk at. Instead we only tell them to go either backward or forward but the simulation calculates the speed and acceleration on its own.
We will decided which command to give AI boxer based on the output value.
Given the correct weights our output will be bigger than 0.5 when the distance is bigger than a constant value(the distance we want to maintain) and smaller than 0.5 if the distance is smaller than the same constant.
However, we have an issue. Since we have a range around 0.5 in which the command is ‘still’ the character will not respond immediately when the distance change.
The reason we do want this still range is because we don’t want the character to always flip between backward and forward when it’s really close to the correct distance and we do want the character to sometime be still.
In the training phase for our distance input we will provide the desired result like so:
We will back propagate the difference between the desired value and our current Neuron output.
If distance is bigger than const then the result will be bigger than 0.5 and if the distance is smaller than const it will be smaller than 0.5.
range is not particulary important but it will be useful in the future or for some minor tweaks. The important part is that we get a linear desired output between 0 and 1.
After the training phase we are supposed to get a positive value for the distance input weight and a value for the weight of the constant input that will make the output be around 0.5 when the distance is around the const distance.
Improving maintaining the distance
Our Neuron isn’t so good at maintaining a distance. We have a pretty big latency in the decision of the Neuron to change the walking direction when the boxers suddenly change their direction.
What we want is to have our Neuron take the boxers’ velocity into consideration.
To do that we add two new inputs to our Neuron. The speed of the player boxer and the speed of the AI boxer.
And then… that’s it. Everything else stay the same.
This is the amazing thing! Simply adding two new inputs will already make the Neuron consider the velocities when maintaining the distance even without changing the desired training value.
Lets see in this youtube video the two Neuron systems for maintaining a distance. The counter at the top left of the screen is the number of frames left for the training phase.
The numbers below it are the connections weights.
3. A Network
Up until now we were working with a Perceptron.
A Perceptron is limited to giving a linear solution to the problem.
To be honest, I didn’t have the time to research beyond the Perceptron but I noticed that with a Neural Network of 10 neurons the behavior is more complex and interesting compared to the repetitive behavior of a Perceptron.
I will explain how is a network built and provide the source code but I will not explain the “Why”.
With a Perceptron we had all the inputs connected to a single Neuron and the Neuron had a single output. If we needed more than one output we simply used more perceptrons, one for each output.
A Neural Network adds a hidden layer of Neurons between the input and the output.
The hidden layer is a set of one or more Neurons. Each of these Neurons calculates its output from the weighted sum of all the inputs.
After we calculate all the outputs for each of the Neurons in the hidden layer we use this hidden layer as the input of the Neurons that produce the real output. You can think as if we use Perceptrons on the hidden layer instead of using them directly on the inputs.
Notice that you can have more than one hidden layer.
However, I was told that there is usually little benefit for having more than one hidden layer and you could simply add more Neurons to a single hidden layer network and get the same results.
That’s it. I am hoping that in the future I will update this article or add a new one about NN as I gain more understanding of the subject.
For the sake of completion, here is the code I am using for both a Perceptron and a NN.