Bad screwups, deadline woes, and the training of a brain. Information about the AI techniques being used in Mad Skills Motocross and a crash-course in Neural Nets.

Warning, complicated stuff

Not much has happened since the last diary entry. It’s summer and I’ve been away on vacation for two weeks. One big decision has been made, though: I have decided to push the release date two months forward. This was a tough decision, but I am certain it is the right move to make. Read on to know all about how I screwed up so badly.

Artificial Intelligence

Mad Skills Motocross needs AI opponents so that you, the player, can race against the computer. And the way I was planning to implement “AI” was naïve at best.

This was my plan: Since AI for Mad Skills Motocross would be hard to implement properly, and I was eager to finish the game, I decided at some time that computer opponents would actually be replays of me playing. I would play a track 20 times and save all those replays and then the computer opponents would race exactly like that. Simple, and with enough replays no-one would have to notice that the computer sometimes played the exact same way more than once. Perfect! I stored it in the back of my brain and started to work on other things. I should have analysed this solution much more thoroughly

So, much later, I implemented the replay system (it will still be used, for ghost racing and for sharing replays on Turborilla.com) and recorded some replays of me driving. Each replay saved to disk was roughly 3 megabytes each. Simple math told me that for 20 replays for each of the 100 tracks, I would need 3*20*100 MB = 6 GB for the replays alone! That’s way too much to download. I would prefer to keep the game below 40 MB in total.

That the game will contain 100 tracks is not written in stone, and I doubt it will have that many tracks. Let’s say 50 tracks, which gives 3 GB of replays. Then I optimised the saved data some more, and finally got each replay down to 0.5 MB. That’s not bad, considering it was six times bigger just an hour ago. With a bit of more tweaking and 7zip compression, I estimated that I could get the total size down to 250 KB.

For fifty tracks, that gives us 0.25*20*50 = 250 MB. Nowhere near 40 MB, and that’s when it hit me: I could easily have foreseen this just by thinking a bit more. A quick estimation could have told me that this solution was not very good since the size of the replays would quickly get out of hand.

Well, the replay system will still be used, so I haven’t lost any time. But the AI will take longer to finish, much longer. That is why the release date will be delayed by two months. Release is now scheduled for February. I hope you all can forgive me and be happy about the fact that the AI will hopefully be much more interesting. More on this below.

Artificial Intelligence Revisited

So, how to implement AI?

Rule-based: Simply define situations and reactions. “When both wheels are touching the ground, give full gas unless front suspension is fully compressed which would mean a disastrous over-wheelie if gas is applied”. “When only front wheel touches ground, do not brake”. “When only back wheel is touching ground, give gas unless bike is on the verge of tipping backwards”. And so on. This quickly gets out of hand for a game with complex physics, where boundaries between situations are fuzzy. Not an option.

Neural Nets : The voodoo of AI. Neurons and synapses connect in a complex system to form an entity capable of learning by watching. Opposed to popular belief, this does not have much in common with a human brain except for where the inspiration came from. The clever naming of the components has given this technique quite a bit of undeserved PR. Nevertheless, Neural Nets (NNs) has a, for me, astonishing ability to detect patterns in fuzzy data with lots of noise. The problem is to find a brain capable of learning this particular problem. This became my choice.

Genetic Algorithms : Darwinistic “learning”. Make an algorithm with lots of parameters. Randomise those parameters a few times to make a group of algorithms that will compete. The best algorithm in that group mates with the second best (there are many options for deciding which ones to mate) and introduce mutations. So, these two algorithms will have a group of children with varying amounts of parameters from the two parents (genetics) and a few randomized parameters (mutations). This new group will now compete. Rinse and repeat until they are good enough. This is a really interesting approach that I will try if the NN path fails to deliver. Especially interesting results can apparently be obtained by applying the Genetic Algorithms thinking to a group of competing NNs.

These three techinques are the ones I have seriously considered, and I chose to start with Neural Nets. I have no prior experience in this field, and I will enjoy every minute of learning NNs.

Neural Nets, simplified

The particular technique I am currently working on is called Feed Forward Multilayer Perceptron Networks . This means that data propagates forward in the net, and a signal can never pass the same perceptron (neuron) twice in the same cycle. Techno-babble aside, this is a good set of nets for learning by watching.

Now, a perceptron is a unit which can take several inputs from other perceptrons (via synapses) and give an output. That output depends on the bias of the input synapses. And that is the parameter which will change while the network is learning. So, for every connection between perceptrons there is a value that will change in ways decided by the learning algorithm.

For every cycle during learning, data is being fed to the perceptrons in the input layer and the output of the perceptrons in the output layer is compared to the desired output for those inputs. The difference between the output and the desired output is used to change the biases of the synapses.

Between the input layer and the output layer lies the hidden layer, and the number of perceptrons placed in this hidden layer is very important for the learning ability of the net. Not too many, and not too few. Research has been conducted to try to find some kind of rule of thumb based on the number of inputs and the number of outputs, but not much progress has been made.

One has to find a good “brain” by trial and error, and the problem is that it takes a lot of time and CPU power to find out if a brain is good. It has to be trained, and evaluated. A good brain can be trained on a set of tracks, and will be able to generalise what it has learned and use that on a different track, which it has never seen before.

Constructing a clever brain

The variables in this problem are many. Firstly, I have to find a good set of inputs to use. I currently have 19 of them: The height of the track at different distances from the bike (which will hopefully enable the brain to “see” the jumps), the speed, the height of the rear and front wheels, the tilt of the bike, the angular velocity of the bike, the stance of the rider, time airborne, and so on.

Secondly, I have to have a good number of perceptrons in the hidden layer. Currently I have experimented with between 20 and 60.

Lastly, I have to train the brain enough to make it good, but not train it too much since that destroys its ability to generalise to unknown tracks (so called over-training).

The outputs are just that which a human would “output”: gas, brake, lean the rider.

I am using Joone, A wonderful Neural Net solution for Java. I can construct and train brains in a nice application and then import the brains into Mad Skills Motocross without problems. It works like a charm and the code makes me ashamed of my own. Check it out if you feel like diving into this strange and rewarding field of computer science: www.joone.org

To be honest, I am not even close to finding a good brain and I think the problem lies in my inputs. The brain, I suspect, cannot generalise the track data to see the jumps while handling the other inputs as well. I am thinking about connecting two brains, the first brain classifies jumps (NNs are really good at classifying stuff) and the second brain takes that as input together with the remaining data. If any of you knows anything about NNs, I am happy to take advice from you.

I will find a clever brain, though. It is just a matter of time. Time that I thought I would be using for other parts of the game by now.

Discuss this diary entry in the forums. I would love to hear your thoughts on the content and on wider issues as well. Was this too complicated?

Next entry will contain new screenshots, I promise. Check back on September 1st.

{mosloadposition contymlp}

 

Take care
// Tobias
Turborilla Entertainment

These diary entries are here for you, the readers. So I would like to know what you think, what you would like to see in the future, and any ideas and questions you might have really.

I have created a forum topic just for this diary entry: discuss here

 

{mosloadposition contrss}