|
Its been awhile since I have popped in, but I have the itch again, so I read up some more, [here] is a intro to ANN's for those whose minds just cannot grasp the massiveness that are ANN's right away (like me). Enjoy. --Chase-san |
Bots using NeuralTargeting:
Please, add any other links you consider interesting.
How it works (one of the many possible approaches)
First some mathematics:
There is the famous Tankens demonstration that says (basically) that given a deterministic serie x(1), x(2), ... , x(t) there is an embed E (vector lenght) a delay D (time delay) and and a function F such that:
x(t) = F(x(t-1*D), x(t-2*D), ... , x(t-E*D))
By knowing E, D and F you could predict the future values of the series (ie. future enemy velocity and heading change). But the problem is that you don't know E, nor D, nor F, and you are not sure these series are deterministic!!!
Now some engineering:
Forget about determinism, just assume they are. Pick up some arbitrary E and D (ie. 20 and 2) and adjust them by trial and error. The only part remaining is F. We will use a neural net to aproximate it, and will train the net with the enemy bot movements.
The result is as follows:
-- Albert
Comments
Unfortunately, the assumption that bots' movements are deterministic is just plain wrong. All good bots use a good amount of indeterminate (random) movement, and this is precisely why I have given up on neural networks and FIR filters for enemy movement prediction (the networks always diverge because of the indeterminancy). The only use I see now for neural networks in a bot is as classfiers (see Kohonen networks), especially for putting enemy movement into different categories that can then be studied by a statistical representation of a bot's movement (i.e. virtual bullets or wave systems).
I am currently working on a bot that categorizes virtual bullet buckets by pattern-matching. I'm not sure if anyone has tried this yet, but it seems to show promise so far.
-- nano
Just take a look into BestPSpace, it has a similar approach.
-- Albert
This neural net thing is really fun. Thanks for pointing me to the NRJLIB. Now I am trying to squeeze it into a MicroBot. It can be done, but it still doesn't beat the pattern-matchers. Well, I have some long days ahead :-) -- Tobe
Some tests related to NeuralTargeting
I just uploaded the following image to demonstrate how effective NeuralTargeting can be:
Data is from ScruchiPu ploted using RobocodeGLV014. The green dots are the predicted bearing (to fire) and the white lines are the right bearing to hit (ie. when the green dots are between the lines, you will hit). Graphs are for SpinBot, Moebius and Sandbox. The first two have an almost deterministic behaviour, and ScruchiPu gets almost a 100% hit rate on them. Sandbox has a quite complex movement, with lots of randomnes, but the NN still gets some good prediction power (of course, some times fails completely, and other times it only manages to get the general movement but in an unprecise way...) -- Albert
I downloaded the picture onto my webspace at school that doesn't mind cross-linking (it won't show up the first time if you link a picture on Geocities from another website). -- Kawigi
Is this a graph of leading factor (from -1 to 1 where one is maximum lead) over time? If so, how many rounds did you have to let your gun run to get these results? If this is the first round, I'm switching guns :) -- Miked0801
It shows in green the relative bearing to fire over time (relativeBearing + enemyBearing = GunBearing?). It ranges from (-0.81 to 0.81) which is the maximum a bot can travel before a bullet hits it. The white lines are the bearing you should fire to hit it. For spinbot or moebius, it needs no more than one round (well, and additional one makes it perfect) to learn. Don't be impressed by the graphics. As you can see, NeuralTargeting is really effective with "deterministic" patterns even if complex, but it needs to improve when dealing with more random movements... -- Albert
Could you make a graph like that on Ares as well? Since it has some quite determenistic patterns, but seems to have quite a few of them. Orca can easily learn it's StopAndGo thingy, but it's wide oscillation movement is much harder. -- PEZ
ScruchiPu beats Ares 6030-2539. A curious effect is that the more the net lears about oscillating and corners movement, the worst performs agains stop and go movement (it gets almost a 100% on it during the first rounds, then degrades). Probably it is some kind of interference between patterns. The good thing is that it seems that the network is able to store differnt patterns at once, and use them as needed. FYI, the network I'm using is a little bit different from ScruchiPu 0.7, because I tried it with development version. -- Albert
Thanks! I haven't had the patiance yet to run that many rounds against any bot. And Orca's movement sucks so I can't compare wins really. But I have seen the same behaviour with almost 100% on the stop-and-go first and then it degrades. Are you saying that your network manages to gain back it's perfomance on the stop-and-go if you just give it some time? -- PEZ
More questions. Does ScruchiPu get that 6030-2539 score against Ares when starting from scratch? Orca is currently running a 6000 round match (don't ask why 6000, my tired head misuncerstood your score figures...). Anyway, after 1400 rounds it shows no signs of improving its lousy score, 250 wins only. I'm confident Orca will win on points, but the fact remains that Orca's NN doesn't seem to cut it against Ares. I will come back with whatever conclusions I can draw when the battle is finished. -- PEZ
... well, I'm running it on a laptop computer of some age so I interupted the battle after 3368 rounds of which Orca won only 593. No signs of improvement. I think maybe my simplistic approach to NN might be too simple for any serious bots. But I'll experiment some more. If anyone has any suggestion son what inputs they think would be worth trying please holler at me. -- PEZ
Yes, the results are for the first 50 matches (no data stored previously). It takes no more than 10 round to have a good aiming against Ares (for some bots you need more rounds - against DuelistMini, for example, it seems to keep learning for 50-100 rounds). I don't think NN performance will improve after many rounds, unless you create a topology "big" enough to store all the patterns Ares uses. My development version of ScruchiPu is currently using a 120-15-15-2 topology (input-hidden-hidden-output). Note that the number of entry nodes will somehow define the width of the movements your bot will be able to recognize, and the number of hidden layers and nodes the number and complexity of the patterns it can recognize (as an inconvenient, the more layers and nodes, the slower it learns). Another factor that may be we should consider is the learning rate (you can modify it using the NrPop? class). I think the default learning factor is quite big, so it could be interesting to reduce it after the first rounds, to try catching subtler patterns. Quite interesting ... --Albert
Ahhhh it was only 50 round! I thought those figures was number of wins! Gah! I'll run 50 rounds and just check the score then. =) Thanks for telling about how the topology will affect the behaviour of the net. I'm trying with more inputs now. -- PEZ
One thing to keep in mind when tweaking the network topology is that the nets easily can get rather big when on file. Even with Albert's zip addition I have managed to create saved files of about 75kb! I now have a smaller net which "only" takes 8kb. It's in the new Orca just uploaded to the RobocodeRepository. -- PEZ
Which version of Moebius is that? Each version moves in different ways (Earlier version moved in a near box or triangle, later in a random sine oscollation.) -- Miked0801
I can't remember, but was moving in triangles. -- Albert
Ok then, not the newest which oscollates at 90 degrees bearing with a bit of random thrown into the period and velocity. I'd be curious to see that graph ;) --Miked0801
Some considerations related with NN performance.
In response to the comment waaay up top there, Albert, don't undersell your creation. :) One of the strong points of neural nets is that they can take fuzzy input and return hard numbers (similarly to statistics), so if patterns aren't entirely deterministic it shouldn't matter, the randomness will weed itself out given some time to learn. However, I've been running ScruchiPu against just about everything in my library, and I've noticed a trend you might be able to reproduce: he peaks in targetting within the first 50 or so rounds, then he actually begins to target less and less effectively. If I had to take a shot in the dark, I'd say he's overfitting, that is, memorizing exact patterns instead of learning general trends.
You can combat that a little with the error term, and more effectively with some others methods, see: ftp://ftp.sas.com/pub/neural/FAQ3.html#A_over and http://www.mathworks.com/access/helpdesk/help/toolbox/nnet/backpr15.shtml for something more in-depth on it. -- Kuuran
Hmmm, there seems to be a lot to learn if the net should be effective. I did manage to make one that quickly learnt the movement of Walls. Then it turned out that it learnt the movement equally well if I fed random numbers as input. Very good! The output should be constant... -- Tobe
I saw that performance downgraded after some time, but I didn't want to believe it. Thanks for pointing it. I'w take a look to the articles and see if I can improve the net. I didn't expected it to overfit, since I use every observation only once to train the NN. -- Albert
This happens to Orca as well. Can someone tell me how I could interpret the error value returned by the training methods? It seems it should be possible to use it to know when to stop training the net. -- PEZ
The error is the (squared?) difference between the expected outputs and the predicted values. The error decreases as you train the network, but the decrease slows down at a certain point. You could define a threshold and stop training the network when the decrease is less than this. Note that this method is quite empirical, and you will not be sure if you stoped at the right time. -- Albert
Glad to be of potential assistance ;) I don't know for sure if it's overfitting, but that's my guess. I guess the way to find out would be introduce a method of combatting overfitting and see what happens. I find myself in a position where I can argue both that it is and isn't overfitting, so I'm afraid it's nothing more than a general suggestion.
Umm.. the error threshold stopping method will work to a degree, but as you said, it's rather difficult to make a solid bot from such an empirical method, unless you want to manually tweak it for every opponent ;p Personally the weight decay (see articles) method looks appealing to me, but I also saw an article somewhere outlining a method that determined if the function was both "trained enough" and "general enough" yet, then stopped learning. It might've been Bayesian learning, which does something like that, but I can't recall the details of either well enough to match them up. I'm not sure if learning would re-start upon a switch to an entirely new opponent movement that hadn't been seen before, though, and if it doesn't you have some potential for serious problems :( -- Kuuran
When I was building a bot using neural nets, one of the main features was that it used hot-swappable nets. If you have one movement type figured out, and the bot switches to a completely new movement type, you shouldn't destroy your old neural net to learn the new movement. You should save the old one, and start over with a fresh neural net (or better, a duplicate of a saved neural net that predicts the new movement the best). You periodically test your neural nets, and keep switching to the one with the lowest average error. If none of the neural nets has a low enough error, you create a new one for the particular type of movement your enemy is using, based on a duplicate of the neural net with the lowest error. Make sense? This would make ScruchiPu much more effective against bots like PrairieWolf that change movements constantly. Although ScruchiPu learns fast enough that it might not be a huge gain, it would help some I think. -- nano
A version of Orca (called OrcaM at the moment) tries this. Though I never figured out a way to choose starting on a new net. I guess the lowest squared error could be the way to do it. You can't afford training the saved net when you suspect it is a different movement, can you? Now, I think Orca proves that I do something very wrong with my attempts on neural targeting all together so I guess I shouldn't draw to large conclusions on the failiures of OrcaM. =) I'll open source it and let you others have a go at it. Watch this space. -- PEZ
OK. It's on the loose now. Download it from the repository. Source is included. I'll write more about it tonight. -- PEZ
I'm not sure you need different networks for different movements. In theory, the network should be able to identify the correct patterns and predict accordingly. See the graphs above (there is a link to display them) about Ares; the same network is able to predict the 3 patterns. The only problem I see for bots using multi-movement is that the NN can "forget" a type of movement, if it has not been used for a long time and you keep training the network (just because it will adapt to the new movements). But this problem could be overcomed by storing some old data and "refreshing" the network by introducing it into the training process. -- Albert
Yes, and even with several networks we still have the problem with how to choose the right network to train and not destroy a network aimed at another movement style... Anyway OrcaM seems to be quite effective against some enemies. Maybe it's just that it quickly can disregard any network that has "gone astray"? Try it against GlowBlow for instance. I just posted the source on OrcaM/Code. -- PEZ
Different networks for different movements IS an improvement on a single network, because neural-networks have a finite amount of "memory". If a bot uses many different kinds of movements, the neural network will have a tougher and tougher time remembering them all (due to overlap, and the difficulty of having a finite number of weights store a large number of patterns). If all of the weights in a network are used to store a single pattern, the end result will be more accurate than storing many patterns at once. -- nano
But good luck finding the rule for switching nets. I had this running through my mind for awhile and haven't come to a solution yet. Unlike VirtualGuns, you can't simply aim a net and see what hits, you have to figure out which net to start teaching without knowing what the end result is supposed to look like, where the end result is what's telling you what net to pick. Basically, since the only really good selection criteria for which net is which pattern the opposition bot is on, and determining that requires having the net already trained, this isn't the winning approach. -- Kuuran (cont'd after following section)
Yup, I think movement classification could be one of the very best uses of NNs. -- PEZ
I'm now very busy but i like to contribute. There is an open source NN package http://sourceforge.net/projects/jsomap/. It is SOM type of NN which is good for classifcation. May be it is possible to make an implementaion by using that package and an open bot which uses pattern matching. The pattern in puts can be the inputs for training. SSO?
Please hack away on OrcaM. -- PEZ
The only really viable solution I see in the direction of multiple nets is an augmented VirtualGuns system where each net is tied to a gun, and whichever gun is hitting the most has a net associated with it activated. That way you have customize each gun on the fly and learn, the advantages of the neural net, with the selection advantages of the VirtualGuns. You could fire from both, teach the net, and when the net beats the gun in hit rate switch over. Any pattern that your VirtualGuns can't figure out would just go to your direct or pattern guns, and those nets would be the fallback nets for all the weird movements that you can't really categorize. It might actually be a useful system to try, but it's definitely not going into my todo list. -- Kuuran
This is in parts what OrcaM does. It tries to overcome the problem with look-ahead by saving a back-up of each net before starting a training session. Then if it appears to be the wrong pattern it restores the old net. The mechanism for deciding if it was the right network or not is very clumsy at the moment, but I think that someone with a better understanding of the neural network thing than I have could figure out a more theoretically sound solution. -- PEZ
I just found this page and enjoyed reading it. About the problem of identifying the perfect NN for the current opposition, why not just let the NN find it out. Isn?t it possible to add the hashed name of the targeted robot to the input of the neural network? -- Dries
Well, it's not easy, Certainly possible. But that's not the problem I think. The problem is momentarily in the fight to pick the best NN for the given situation. (Like enemy close to the corner, have just moved leftwards and towards you and at a rather long distance...). See SSO?s comment about using NNs for classification. I think that is the way to go. -- PEZ
I don't like that solution at all. In order to classify the movement they have to be able to learn which movement is which, which brings you back to the problem of setting them up to learn that. In the solution to that setup probably lies a much simpler system for the classification in the first place. -- Kuuran
Well, the classification phase could be carried out in the lab before the bot gets out in real battles. And it could maybe be quite iterative and use same Temporal difference kind of mechanism to give feedback about which choice was good and which was bad. Anyway, since so many bots are open source you can maybe create a mega-multi-mode bot that sports lots and lots of movement systems. Then maybe you could use the Team interfaces for the classifyer and the target. The target could pick movements at random and tell the classifyer what movement it uses and the classifyer could use this correct answer to train its net. I'm certainly ready to contribute to the movement-bot as long as one or some of you rocket scientists take care of the classifier business. -- PEZ
The SOM type of NN is differrent than the BPN type. I find some where a simple difference: "One of the most interesting aspects of SOMs is that they learn to classify data without supervision. You may already be aware of supervised training techniques such as backpropagation where the training data consists of vector pairs - an input vector and a target vector. With this approach an input vector is presented to the network (typically a multilayer feedforward network) and the output is compared with the target vector. If they differ, the weights of the network are altered slightly to reduce the error in the output. This is repeated many times and with many sets of vector pairs until the network gives the desired output. Training a SOM however, requires no target vector. A SOM learns to classify the training data without any external supervision whatsoever." Than the question remains; based on which criterias we shuold classifiy the movements. An intresting criteria could be based on the enemy distance away from us by using delta speed, delta angle, etc. (SImmilar to the patterns matchers) -- SSO?
An example of a self-organizing map (SOM) is the Kohonen network, which I mentioned earlier, and which is specifically designed to segment data into classifications without supervision. This is what I meant when I said that I believed this is the direction that neural networks should move in bots. Props to the first person to implement a Kohonen map to categorize robot movement. -- nano
Well, unsupervised classification sounds great for the purpose. Maybe we could use input similar to what ScruchiPu uses today? -- PEZ
the version 0.7 uses
//Input? Vel. Scale factor
//Input? Hed. Scale factor
//Output? Vel. Scale factor
//Output? Hed. Scale factormay be we need more info The questions are -what parameters we can use to classify the movements
direction, distance, heading difference, location, ....-what are the possible move types
ossilation, lineer,...
Any more inprovements? SSO?
Maybe since the classification is unsupervised and automatic it doesn't matter what possible types of movents there are? Wouldn't the output just be like movement1, movement2 etc and then we could just train specific targeting neural nets based on the classification? More possible inputs:
Kohonen's aren't the most reliable classification by far. Play with [this] awhile and you'll see it takes minimal modification for it to misclassify everything, and it's pre-trained. -- Kuuran
Second note: You may also have far more luck with a Hopfield than a Kohonen. Kohonens are for pattern classification like identifying a noisy image of a letter as being the letter. Hopfields are better for associating patterns, and are also unsupervised learning nets. Hopfields are also far simpler. -- Kuuran
A Kohonen network is exactly what is called for to solve this problem. Hopfield networks are for pattern recognition. Kohonen networks are for pattern classification. Hopfield networks aren't meant to classify -- they're meant to reproduce the closest stored pattern to the input. The Kohonen network you linked to does not misclassify based on noisy input. On the contrary, it correctly returns the closest classification for the given input, regardless of noise. If you look at the number of pixel differences between the inputs, you will see that the network is correct. -- nano
I found several instances where it misfired, but that's all academic. Before you go on too much on the topic, try to set one up and see the details unfold. I think you'll see where my misgivings lie. -- Kuuran
Okay, I donno much about neural networks, but couldn't you say have a different network for each of the like values you get from the enemy then just recombine them to fire sorta like segmentation in a guess factor gun. e.g. a network to learn and monitor the bots distance, one for the acceleration, one for how it turns and stuff, then one network to pull it togeather and make the decision how to combine all that neural know how.. to me as far as what I know about NN this sounds possible but as I haven't even rad a single one of the aritcles I wouldn't know. Just putting in my 2 cents. -- Chase-san
Isn't this similar to PM? --Starrynte
Neural networks are effectively function estimators. So... given a set of parameters (distance, velocity, accelaration, etc...), a properly constructed and trained neural network might be able to tell you the next likely robot bearing. Neural networks are mostly another way of modeling probability. They're definitely not like pattern matching. Simple pattern matching is deterministic - you either find a finite match or you don't. Neural networks are 'fuzzier'. Academically, there's no good way to tell why they're working or not working. You just have to experiment. Good luck. --Corbos
All in all, getting NeuralTargeting to work is a long and tendious process, and it takes even longer to get them to work "right" if there is such a thing for it, currently I see neural networks as just a play thing for people with far to much free time (like me) or people who can really make them work (like wcsv). If your just starting out, and haven't worked on Neural Networks in some other capacity, I would try some of the other options first. But thats just my opinion and you can do whatever you wish in whatever order you please. -- Chase-san
I have done some more work with Kohonen map's lately, as I feel that I am getting better at udnerstanding these advanced concepts, I can tackle on of the biggest. I have an idea for a Kohonen map that will replace the bins in a traditional gf gun. It will also be a little like DC aswell, as the weights will be recorded as numbers 0 to 1. I wanna see if this will work, however, I have a stumbling point, though while it keeps the data, on movement and relates it to gf, I am wondering how to effectively store the gf in these, as 'pulling' the gf closer to the bmu may vary well turn out to be the very worst possible thing to do, so I will try it, but any alternatives to this very sloppy move will be appreciated. --Chase-san
Its been awhile since I have popped in, but I have the itch again, so I read up some more, [here] is a intro to ANN's for those whose minds just cannot grasp the massiveness that are ANN's right away (like me). Enjoy. --Chase-san
![[Home]](/images/RoboWiki.png)