View source for Talk:Virtual Guns

Old discussions from 2006, from 2007.

Virtual Bullets

Are you sure we should have Virtual Bullets redirect here? It is not mandatory for a virtual guns system to use virtual bullets - for example, in an upcoming version of Horizon, I plan on implementing a virtual guns system that treats the success rate of a gun as the rolling average of 1 - (abs(predictedGuessFactor - actualGuessFactor) / 2). Obviously, this system will use waves, not virtual bullets. Furthermore, some early GF-like guns used virtual bullets instead of waves for enemy position logging. There are obvious bot design applications where one system does not overlap with the other. --AaronR 20:57, 29 November 2007 (UTC)

Yeah, I was wondering if they should each have their own pages. I'm definitely open to that. But after some consideration when making the page, I was thinking that they are not really describing different things. I definitely think it's worth discussing...

I also implement my virtual guns with waves instead of tracking the frame by frame location of each bullet, but: a) they are still "virtual bullets", in my mind; b) even if virtual guns doesn't need virtual bullets, that doesn't mean virtual bullets can exist without virtual guns. Wouldn't a virtual bullet always come from a virtual gun? Would you not consider those early GF systems to be an array of virtual guns, each aiming at a fixed GuessFactor?

Still, the history of each idea is unique - like you said, the term "virtual bullets" was used in those early GF guns, while "virtual guns" tends to imply a specific algorithm for each gun. But I think it will be tough to really differentiate the concepts. --Voidious 21:16, 29 November 2007 (UTC)

Oh, another factor in my initial decision is that the respective pages on the old wiki seem pretty clearly to define them as the same thing. The top of the VirtualBullets page includes David Alves first showing a picture of different targeting systems firing virtual bullets in a virtual guns array (including linear and head-on), and then a comment describing the old virtual bullet GF system. Actually, I'd really like to hear his thoughts on this. --Voidious 21:44, 29 November 2007 (UTC)

As a kind of side bar to the above discussion: if we do leave these as one page, we should definitely add the original style of GF guns to this page somewhere - perhaps under "common uses" section. --Voidious 19:37, 30 November 2007 (UTC)

Question! What is a "decay rate"? What else do you need, if you keep track of the number of hits for each gun? I think the results would accurately express which gun is better.. -- Josh S 12:38, 27 April 2010 (UTC)

"Decay rate" means a way of making newer data more relevant than older data. For instance, for a hit percentage, if you just used the last 10 shots instead of all of them. Or if you were storing shots fired vs shots hit, dividing both by 10 every 100 shots. --Voidious 13:53, 27 April 2010 (UTC)

Hmm.. OK, I think I understand... So it's sort of reducing the data size, as it gets larger? -- Josh S 01:41, 28 April 2010 (UTC)

Well, it's more about making new/current data count for more. By dividing shots hit and shots fired by 10, you are basically decreasing its weight of that data from normal to 0.1. One of the most common forms of data decay is Rolling Averages, you should definitely take a look at that. --Voidious 01:53, 28 April 2010 (UTC)

Well, you can choose between 'decaying' the date (better for adaptive movement) or just plain accumulated data (better against random mover and non-adaptive movement). It just like GuessFactor gun with and without Rolling Average. --Nat Pavasant 14:36, 27 April 2010 (UTC)

What do you mean by the "date"? By plain accumulated data I suppose you mean hit rates, and the number of shots fired... -- Josh S 01:41, 28 April 2010 (UTC)

Sorry, it should be 'data'... --Nat Pavasant 06:48, 28 April 2010 (UTC)

I thought that Diamond is also using virtual guns in melee (for he is using DisplacementVector in melee for his ASGun, while using GF in 1v1). But the code shows that the VGs is only used when there is only one opponent.

I've been long thinking about melee virtual guns, as nowadays, melee wave surfing is growing in popularity. However, the first difficulty to solve is to make VGs work with Targeting.

Here are the choices I've came up with:

• Keep track of VG ratings for each opponent, and aim with the best gun respectively. Then combine the results as if they were from the same gun, not very different guns. The problem is that swarm targeting may not work properly when internal data from two quite different guns is combined.
• Keep track of an overall rating, considering every opponent. However this method doesn't scale well when the opponents changes, e.g. going from 3 bots melee to 2 bots duel, the rating will remain irrelevant for a while.
• Keep track of VG ratings for each opponent, but aim with the same gun for every opponent (for better swarm targeting). The gun used to aim is chosen so that the overall hit-rate is maxed. This should be the most versatile approach, but not easy to implement.

Any thoughts here?

I think the best would be having individual guns, and using leave-one-out cross validation to test which gun actually gives better results on the historical data at fire time. This would skip needing to track separate hitrates for guns that you don't know where they would fire.

If I understand correctly, for n firing waves w = {w1..wn}, LOOCV involves training the gun with w - {wi}, then test with wi, for all i. For knn guns, this means doing n “(k+1)nn” searches (then exclude wi from result), and for neural networks, this means feeding the network n(n-1) waves in total. Isn’t that costly for robocode? Or may there be some faster ways?

For KNN I think this is fine. I know personally I use a very fast kernel density function (square), so these kind of tests aren't expensive. That said, I haven't tried this technique yet. It might not work well due to other things we haven't spoken of yet.

Agreed though for NN, it is already pushing the limit of what can be processed in a single tick, so there is no way you can take 2x or 3x the processing power.

So do you mean only 2~3 waves need to be tested? I thought we need to iterate through every fired waves and do a knn search for each.

Medina currently implements the third approach, but it only uses a HOT and a PIF gun, which implies in no improvement, but is meant to be a place to work on in the future. It uses different ratings depending on the number of enemies alive.

That’s inspiring. Btw, how do you keep track of hitrates for individual enemies? Are you assuming it were in 1v1 when testing hitrate?

And how do you combine hitrate for individual enemy and estimate swarm hitrate?

I don't believe that any common targeting can outperform PIF in melee, and that's why virtual guns won't improve your gun. Of course there are special cases, e.g. I think Portia has a feature that it treats disabled bots differently, and that might be a useful improvement compared to mere PIF.

Well, I see many bots treating disabled bots differently, and that’s not hard to be implemented with swarm targeting.

While PIF guns play a dominant role in melee, similar to 1v1, there are two types of PIF guns, one tuned to hit the majarity, the other tuned to hit adaptive movement.

Although there are not so many adpative bots in melee comparing to 1v1, they still contribute more score diff per bot than those you can easily hit. So if we were able to hit adaptive movement better, in melee, the score improvements should be noticeable.

Also melee adaptive movement is growing in popularity — virtual guns with swarm targeting will one day be an essential part of state-the-art bot.

Combat uses oldskool GF with swarm targeting in melee.

Uses a disabled dimension to account for disabled bots. And uses data decay to account for adaptive movement.

Well that seems a good alternative to VGs in melee

Interesting found! Maybe we could use knn to predict hit-rate in melee, just as bullet power is predicted in 1v1.

Take time, bots left and more into account, then maybe you can predict your hit-rate pretty well, and choose guns wisely.

I take it as a given that we all choose the wrong gun pretty frequently. I use precise intersection and normalize hits by distance and MEA. So a hit percentage of 12% from distance 400 is rated the same as 6% from distance 800, for instance. I think this is all pretty optimal, but we still just don't have much data. There's the option of firing a virtual bullet every tick, but this seems inaccurate.

I got the idea to not just fire a virtual bullet for the best angle produced by each gun, but also for 2nd best, 3rd best, etc, with progressively lower weights into the VG stats. I felt this had a lot of promise and I spent a few days tweaking various configurations, disappointed to find no improvement in my test bed. But I liked the idea enough that I figured I'd give it one shot in the rumble before moving on. I'm not convinced this isn't random fluctuation or a side-effect of the Anti-Surfer gun changes, but 0.1 APS improvement: [1]. Anyway, just thought I'd share. Maybe I'll revert the VG changes in .14 for a direct comparison.

In my humble opinion the best virtual gun array is no virtual gun array. It add's a great deal of complexity for marginal benefit in most cases. Just try to make the best gun better.

In order to hit both DrussGT and RandomMovementBot12345, you're going to make a trade-off somewhere, whether it's by adding a VG or by sacrificing performance against one to hit the other when tuning a single algorithm. I don't consider it that complex. Improving my Anti-Surfer gun is what got me beating Shadow, which is reason enough for me to have one, and more than a "marginal benefit" in my eyes.

Hmm, while such a trade-off has to exist in some form, a VG array is not the only way to handle minimizing that sacrifice.

The primary trade-off in the "DrussGT and RandomMovementBot12345" case is the question of whether old data should be kept. In some things like a NN targeting system, you could have methods of adjusting that learning parameter besides VG, based on some characteristics of the data. That's just one example, and there are many other ways the sacrifice could be minimized within a single gun. I think that is something that hasn't been nearly as explored as it could be.

Anyway, on the topic of "multiple virtual bullets", I have tried something like this before, except I took it to the extreme. What I did in some versions of RougeDC is equivalent to what you suggest except with infinite differently weighted bullets. It integrated the result across the angles.

My experience is that this method was much faster adapting than the conventional single bullet approach. It was very useful against surfers that you need to adapt quickly against (i.e. swapping targeting systems when they've learned one too well). The disadvantage, is that it converges to a less accurate result.

That's interesting to hear. I definitely considered some extreme cases - for instance, for the hit angle, take the normalized score for that angle (eg, kernel density / max kernel density) as the amount of a virtual bullet hit to count it as. Is that something like what you did? Obviously that's biased towards a gun with a pretty flat graph, but even after normalizing I'm not sure if it would favor one of my guns, which have very different looking graphs.

I have a hunch that this type of system should break down (ie, become so noisy that it's counter-productive) very quickly beyond the first few angles - if it helps at all in the first place. But, not being sure on the theoretical level, I definitely felt that on the experimental level, if I couldn't find benefit in using only 2nd/3rd best angles (which also by far carry the most weight), I would not find it by going beyond that.

In any case, I found no improvement in anything I tried, including the variation I'm trying right now that I thought fixed a flaw in 1.6.13's setup. So I'll probably try 1.6.14 with the old VG and see how that goes. I do still think there's potential here.

I've had a problem with the way we normalise our data - I think it should be normalised so that the area underneath the graph is 1, not the maximum value is 1. This would make this technique more useful, as you could simply integrate each gun over the hit area and use that as its hit ratio. I've also had the idea of dividing all my VG hit ratios by the random hit ratio - so that the gun hit-ratios are measured in a useful metric that adapts across bots. But back to designing my genetic gun-weight tuning algorithm!

Yep, I do normalize against the random hit ratio, in effect, by scaling with distance and precise MEA whenever I log a hit. Regardless, 1.6.14 looks well within the margin of error of 1.6.13, which is in line with all my tests of the multi-bullet VG, so I'm happy to revert a bunch of worthless code. =)