Developer diary August -07 : Brains | August -07 : Brains |
|
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 Artificial IntelligenceMad 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 RevisitedSo, 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, simplifiedThe 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 Turborilla Newsletter
Take care 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.
Get the developer diary in your favourite news reader
|
| < Prev | Next > |
|---|
Turborilla Community
Subscribe
Welcome
Turborilla Newsletter
Copyright © 2009 Turborilla Games
