Archived talk:Virtual Guns 20071129

From Robowiki
Revision as of 04:52, 8 October 2009 by Robobot (talk | contribs) (moved Virtual Guns/Archived Talk 20071129 to Archived talk:Virtual Guns 20071129: move to talkarchive)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

From old wiki's Virtual Guns page

What is VirtualGuns?

VirtualGuns is a way to choose the best aiming method against a given enemy by keeping track of each methods' virtual hit rate (or some other measure). There are obvious advantages:

What are the advantages

  • Enemies tend to move quite differently, VirtualGuns will make your robot adapt.
  • In theory it's can be quite easy to implement.
    • And can be implemented in very many ways. OrcaMs' NNCandidate is one way. MakoHT/Code is another. Marshmallow was my first bot using VirtualGuns and the design is outlined below.
  • You can let your bot explore quite different Targeting techniques, even quite simple ones, in the hope that it will find weaknesses against particular opponents.
    • For example against some bots HeadOnTargeting is better than many other targeting implementations. (Against a truly flat movement it can be better to just guess head-on all the time than risking to guess differently and wrong too many times.)

Disadvantages

  • The main disadvantage is that in practice it can be quite hard to implement.
  • You risk messing up things so that the array performs worse than your best gun would do on its own.

How does it work?

Marshmallow was my first bot using VirtualGuns (ehh, it was my first bot, period). It uses the following strategy for this:

  1. Everytime the robot is ready to shoot it creates an array of virtual guns and aims each of them
  2. When firing it stores this virtual gun array in an event
  3. The event's test() method checks wether a particular virtual gun has either hit or missed (using Waves).
    1. Statistics are updated for each gun which has either hit or missed
    2. When all guns are finished the event is deregistrered and the virtual gun array is disposed.

Note that there's no event handler for this event. I only use it to store the copy of the virtual guns array and to get Robocode to run the test each tick. Like VirtualBullets/VirtualBulletsBot does. -- PEZ

What bots are using this?

Please add relevant bots to this list.

  • SandboxDT
  • Duelist also uses "virtual guns", it used them to decide how fast it should adapt its aim, ranging from "fire using whichever virtual bullet hit last time" to "fire using the virtual bullet that has been most effective on average over all data vs. this bot". --David Alves
  • Mako, MakoHT
  • OrcaM
  • GB
  • SpareParts has a bunch of them, which help him proof himself against brutally simple robots (I made robots later that did much better against good robots and ranked higher, but couldn't beat Walls).
  • Ascendant
  • CassiusClay (as of this writing in a development version)
  • Dookious presently uses two GuessFactor guns in a VG array. One has a higher depth on the RollingAverages and uses non-firing waves, the other uses only "real" waves and has a much lower rolling depth (aimed at WaveSurfers / adaptive movements).
  • All of Greywhind's bots use VGuns so far - all simple targetings, Laser, GF, and PM are included in Constitution and Strength.
  • GrubbmGrb has a VG array of simple targeters (HOT, CT, random, av velocity CT and orbital)
  • Ugluk has been using multiple simple targeters since before 0.3.0 (first Roborumble entry). I wanted to be able to defeat all sample bots before I entered, and what works for Walls does not work for SpinBot. Ugluk varies as to how many guns he has, but it has been as high as eleven at once.
  • Perpy uses four different guns, using virtual bullets to assess hitrate. Respectively, they are HOT, CT, a GF gun and a patternmatcher.
  • Squirrel uses a pretty big virtual guns array, including 4 GF guns, 3 AntiSurfer GF guns, 1 CT gun, 1 LT gun, and 1 HOT gun.

One detail that I think makes sense is this: weight your VirtualGuns data (hits and misses) proportional to the difficulty of hitting the enemy in that situation. For instance, 12.5% vs 12% at distance of 500 is the same ratio as 25% vs 24% at a distance of 250, but if you have an even number of data from each distance, the latter has more effect on that calculation, while it should be the same. So far, I've been weighting my VirtualGuns data proportional to distance, but I'll be making it bullet time (slightly more accurate) and total reachable escape angle (which I already calculate precisely in Dookious). -- Voidious

Sounds reasonable. Would it also be helpful to take into account the percent of maximum escape angle taken up by the bot at each distance? -- Simonton

The above two factors are actually my attempt to calculate exactly what you said - the average hit rate for RandomTargeting in that situation = exactly proportional to bot width / total escape angle. That percentage is proportional to both bullet time and the total escape angle. Can you think of any other factors? I would definitely add them if I knew them, but I think those two paint the whole picture. -- Voidious

If your escape angle calculation takes into account wallsmoothing, then I can't think of anything else. -- GrubbmGait

  • Yep, Dookious uses precise escape angles that take walls into account. -- Voidious
  • Hmm, hey wait. Distance is a factor in both bullet time and total escape angle, so I may be counting that one more than I should. Maybe it should be just distance and total escape angle? I decided on bullet time instead of distance before adding in the total escape angle thing... -- Voidious
  • Yes, you are right. You're not going to get it exact, because to convert bot width to an angle requires knowing the angle at which the bullet would hit the bot (because the bot is a square) as well as the distance to the bot (which can vary depending on whether the bot advances or retreats, e.g. for wall smoothing), but you already knew that. Anyway (bot-width-angle / escape-angle) or (bot-width / escape-distance) do encompass the whole picture, they're just slippery variables to nail down. -- Simonton

Has anyone tried VirtualGuns within VirtualGuns? I think this could be effective against surfers, because your anti-surfer VirtualGun could choose between pattern-matching, a small DC gun, a lightly segmented GF gun, etc, and your regular gun could be just one, big GF gun. You can choose between your array of anti-surfer guns (which are treated as one gun by the 'main' virtual gun system) and your main gun using gun stats that have a very high rolling depth, but between the anti-surfer guns with a low depth. Because surfers constantly evolve their movement, at different points their movement might be more susceptible to different types of guns. -- Skilgannon

  • I would imagine that a literal implementation of this would be ridiculously slow. However, an equivalent method would be to put all of the guns in a single array and modify the method used to choose between them to consider the anti-surfer guns as a collective group. Only if it picks the group would the choice function look at the individual anti-surfer guns. On the other hand, by itself it is probably really slow to have several pattern-matching guns and DC guns in a VG array, so it might not be practical either way. -- AaronR
  • I understand what you're saying, but I have to ask - when would this ever be preferable to just choosing the best of all your guns? Do you really want to penalize choosing your best AntiSurfer gun by grouping it with your worst AntiSurfer gun in terms of VG rating? Also, I think it's really hard not to lose performance as you add more guns to a VG; often, it's best to cut the weaker guns even if they are better sometimes, because your chooser will never be perfect. -- Voidious

From old wiki's Virtual Bullets page

Virtual bullets sample.png Screenshot of /VirtualBulletsSampleBot on Robocode 1.1.3, showing virtual bullets for the three included VirtualGuns in flight, and # of hits for each Gun. Note that "Really Bad Gun" is initialized with 1 hit, but the robot quickly learns to use better methods. --David Alves

For a simple implementation with debugging graphics, take a look at /VirtualBulletsSampleBot, by David Alves

For an implementation using Robocode custom events check /VirtualBulletsBot, by PEZ

The concept behind virtual bullets is simple. Since the enemy can't tell what angle our gun is pointing when we fire, their reaction is not based on our gun angle. Therefore we can create a "virtual bullet" for each gun offset that we could have had at the time we fired, and keep track of these virtual bullets to see if they would have hit our enemy if we had actually fired at that angle. We can now track the success rate of each firing angle and see how well it is working.

if (bullet hit) 

 raise success rate for aim method used to fire this bullet

else if (bullet missed) 

 lower success rate for aim method used to fire this bullet


For example: DuelistMicro chooses the angle to fire at from -2/3 to +2/3 radians, where 0 is pointing directly at the target, negative is behind them (relative to the last direction they moved if they are stopped) and positive is in front of them. You could also use virtual bullets to track how successful linear, circular, and direct firing are vs. the current opponent. The beauty of virtual bullets is that you'll learn at the same rate no matter how many different aiming algorithms you use - just fire more virtual bullets. :-)

Virtual bullets are used by the following bots:

and many others.

Virtual bullets were invented independently by Paul Evans and Rod Hyde.

--David Alves

Here is Paul Evans' definitive write-up: Virtual Bullets

I don't think Paul Evans or Rod Hyde are the first ones to use VirtualBullets, though. Some older bots like LoneDragon use virtual bullets as well (see LoneDragon 's bot-description http://robocoderepository.com/BotDetail.jsp?id=330 ). I do believe it was Paul Evans' idea to fire multiple VirtualBullets at the same time. -- Dummy

Robocoders were using BulletTracker classes long before Paul and Rod came up with VirtualBullets (See RayBot, TheArtOfWar - How does it fire, How does it dodge bullets, Secrets of the Robocode Masters: Tracking Bullets). Same principle: plot the bullet path, see if it hits, and use the resulting data to improve aiming. Paul's breakthrough was realizing that he didn't have to actually have to fire a real bullet in order to plot its path and he could fire several of these VirtualBullets at one time. -- Ray_Vermette

Paul's breakthrough was also in getting the damn things to work! FiringBD in its various incarnations used what I called "magic" bullets, but my implementation was much less successful. I had lots of different aiming types, most of which were variants of linear and circular firing which used a number of types of moving averages based on heading, velocity, etc. --Rod Hyde

Isn't that some robots use VirtualBullets for enemy bullets as well? I think I've seen it used with AntiGravityMovement. -- PEZ

Yes. Fermat 1.6, which won the Robocode Rumble in the intermediate category, used this AntiGravityMovement with predicted enemy bullets as gravity points. That's why you'll never hit it if you fire using linear, circular, or direct targeting. :-) Fermat has since then been updated to version 2.0, which uses virtual bullets for its own targeting as well as using them for dodging. --David Alves

Both Neptune and Pluto use VirtualBullets for bullet dodging, I call it ShrapnelDodging. They also use something similar to VirtualBullets for aiming, which I call LaserTargeting. --tobe

I have a very hard time hitting Fermat with PatternTargeting as well. But Fermat 2.0 does not have the same problems hitting Marshmallow. VirtualBullets might not be such a bad idea. =) -- PEZ

Don't underestimate Pattern matching - look how well Cigaret is doing... :-) --David Alves

Marshmallow uses VirtualBullets inside its VirtualGuns. There's no opposite relation between PatternMatching and VirtualBullets. Marshmallow uses both. Some people think of VirtualBullets as being GuessFactorTargeting, but they are not the same. Marshmallow will be using GuessFactorTargeting as well soon. -- PEZ

Hmph... I must be the only person online who doesn't like the idea of virtual bullets.

I'm not saying they won't work or they aren't succesfull; Paul and others have obviously proven quite the opposite. It's just that the concept always seemed so limiting and slow (BLARG I can't find my words tonight!). The idea behind virtual bullets is that you fire a virtual bullet at every x angle. The main problem seemed to me that this is such a low-resolution approach: for each x angle, you only get a collision on the closest multiple of the x angle. The problem with speed is you need to calculate a collision for each of those bullets once you've decided that at least one of them has collided.

A more analog approach always seemed more attractive to me; just remember your position, the direct angle to the enemy, and the power of your bullet whenever you fire a bullet. Calculate when the bullet has collided in the same way as VirtualBullets (using the current distance from the enemy to your position when the bullet was fired). When this happens, just find the angle between the logged angle to enemy at the time of firing and the current angle from your logged position to the enemy.

This algorithm would seem to accomplish the exact same task as VirtualBullets, but would be MUCH faster to calculate and with infinite resolution.

The whole 'VirtualBullets' craze always seemed to remind me of all my math and physics and chemistry classes throughout highschool; everybody always seemed so eager to attack a solution by trial and error, or by writing possibilities or cases, or by doing each problem individually. Why? The power of taking a simple derivative or applying the quadratic formula was always unmatched, giving me a general solution beforehand of solving Question 4 a) through q) for example without even having to know the numbers. Solving each set of numbers for a question was simply a matter of punching the numbers into the calculator at the right places in the formula to simply jot the answer on the page. The power of simplifying with algebra to give me a general, algebraic, fully analog solution beforehand has always outweighed doing a) through q) individually, or solving whatever problem by trial and error, or using a bunch of cases and finding the closest one; such is the case in VirtualBullets. Why not just find the solution in real numbers?

-- Vuen

Well, the way you describe it is exactly how I do VirtualBullets in all my bots. I know some people fire lots of VirtualBullets, but I think most such solutions are being replaced by Waves. Which, by the way, are also used by my bots.

Call what you do what you want, to me it sounds like VirtualBullets. =) -- PEZ

Since DT 1.71 I have removed virtual bullets in favor of waves primarily for performance reasons (an other reasons not relevent for this discussion) - it makes little difference to the published guess factor statistical approch - once the wave 'hits' the opponent I have to calculate the minimum and maximum guess factor that would have succeeded in hitting the enemy and from there I need to update the stats on all the guess factors from -1.0 to 1.0. (DT1.71 has 32 distinct guess factor 'bins' and more than one method of calculating guess factor - much more than previous DT's which is why I needed to loose virtual bullets in favor of waves.)

The statistical guess factor approch requires discreate bins of data (I looked in some prety deep math/stat resources to overcome this with no success). It does not matter to the approch whether you separate the hit/miss data with virtual bullets or later with the results from the wave.

At the time of writing my virtual bullet code I was aware I could do it with a more efficient wave method (not that it had been invented then) but with less than 24 hours to go before IBM's Robocode Rumble deadline I went for the easy to debug/check virtual bullet method.

Either method is good as the other for the statistical approch (but waves are more efficient), however, if you want a single accurate hit angle to the center of the enemy (as pattern matchers prefer) then waves does the job better.

-- Paul Evans


Ah, cool. I had not heard of waves before this; turns out waves are exactly what I had described. Bah.

Are you sure there's not some mathematical way to build an actual curve with the data rather than a statistical array? I'm trying to think of a way to regress the data into a curve without losing resolution; the problem is that the data is additive, in that two points near eachother add together rather than emphasize the curve at that point. I wonder if analysizing the data and iterating through it would allow you to find the inflection points in the curve and use them as spline nodes to build a real curve from; this would theoretically generate a curve for you where the data is algebraic and you can pull any point off the spline in real numbers. The problem seems to be the slight additional processor power required, but a curve recalculation can be made to occur only at every few hundred ticks or at the end of every round for example. Finding inflection points would give you direct highs and lows for gun accuracy in real numbers, rather than high and low 'bins' in iterated multiples.

This seems like something I'd like to try; I've been rolling around a new gunning concept in my brain lately, and inflection points is a step forward in an early calculation that would need to have been done anyway for my new gun, so as soon as classes are over I'll see about building this.

-- Vuen

I'm not 100% sure, but I'm fairly sure (but don't let me put you off). One of the problems is that it is not possible to know how many inflection points there are on a graph in advance, you can't therefore do a regression analysis because you don't know the 'polynomial order' of what you are looking for. Some graphs have 5 or 6 max/mins. I looked at using regression analysis as a 'compression' method for data storage, but in the end I developed a lossy system (like JPEG but without the discrete cosine stuff which I don't understand in sufficient detail to test/debug and which is optimised for visual requirments and not robocode requirements).

When I had fewer bins I experimented with calculating a parabolic maximum from the maximum bin and the two bins either side - it did not add much value and in the end I ditched the code in favor of more bins and better compression of the data.

To give you a start on your resarch the problem we have in a statistical gun is that we have many (or somtimes only a few) discrete points into which we want to convert into a smooth 'density' line/surface/blob... The statistitions often have this problem with data and they utilise a 'Density Estimator' method - look it up via Google and see what you think. (If there was "some mathematical way to build an actual curve with the data" I think the statistitions would have found it - and I would have found it on the web). In the end I used some of the concepts of Density Estimators in my post 1.71 Gun's.

Good luck --Paul Evans

Phew. I always knew you were a rocket scientist and brain surgeon in one person Paul. =) -- PEZ

Of course, even if what you're storing is discrete, the comment about efficiency (basically that it's more efficient to fire one wave bullet than 30 or 40 discrete virtual bullets) still holds - in fact you started doing that as well in 1.71, too, I believe (and probably used it for that Density Estimators stuff). -- Kawigi


Yes - when I said Post 1.71 I ment Post & including 1.71. -- Paul Evans


Hmm; you're probably right. What angle multiple does SandboxDT use for its bin frequency? I figure using say a bin every 1 degree would allow for lots of room to work with, and would allow the bot to find the inflections it needs without needing an actual spline curve. The data can be compressed by finding the inflections and handles from the bins themselves and writing those rather than writing actual bin values, so compressing this much data should not be much of a problem. I've started building my new bot, and will begin with a bin system in one of it's pattern analysers as soon as I program it to shoot :). I will probably also begin building an applet alongside the bot to graph and verify the curves it finds, much like liley's SmogPainter, but integrated into it's webpage button. Anyway, back to my bot... :)

-- Vuen

I use 32 bins (and 13 distance ranges) each bin has an angle dependent on the bullet speed and guess factor calculator. For a simple absolute angle guess factor calculator the bin angle would be 2.9 degrees with 3.0 bullets (2*asin(8/11)/32), 1.5 degrees for 0.1 bullets (2*asin(8/19.7)/32). at a distance of 500 - 2.9 degrees is eqivalent to 0.32 of the width of a bot - more than accurate enough. Also most good bots have fairly smooth curves one point is almost as good as it's neighbour, bots with sharp points aren't a problem.

-- Paul Evans

Ha! Paul Evans also came up with asin(8/bulletv)! (We've had discussions over what the maximum offset can be before). -- Kawigi

Hey, one thing - how does this density estimator stuff perform against robots with a highly irregular curve? (i.e. - if they somehow had a really high negative spike and a high positive spike) -- Kawigi

As with standard guess factor guns there is no problem - to get a sensible curve you have to tune somthing I think was called a "kernal wavelength" based on the number of data points you have and the distribution of those points - (this appears where alot of work goes into density estimators - too small a wavelenth and you get a graph with too many spikes, too large and you 'blend' out important information/peaks. Unfortunatly it appears that there is no easy way to calculate the optimum kernal wavelength (and also I did not see anything on the web as to how to add new data to existing desity estimates). But note my earlier comments - I only used some of the concepts of density estimators, they are computationally too intensive for robocode. -- Paul Evans

Back when I was trying to build a Bayesian statistical gun I also experimented with the idea of kernel density estimators based on gaussian curves. Unfortunately, after running many sets of data with DT through an industrial-grade data mining ap they turned out to be basically useless, in addition to horrendously slow. (Nor did any other standard data mining technique work, btw. Since coming to robocode I am beginning to think that virtually everything ever written on the subject is bunk. :-\) - Jamougha

I was thinking that if you wanted to represent a curve by an arbitrary amount of points, wouldn't that be a perfect application for a self organizing map (SOM) neural net? Something like the "Growing Neural Gas" at http://www.sund.de/netze/applets/gng/full/GNG-U_0.html JHH

Retrieved from "http://robowiki.net/w/index.php?title=Archived_talk:Virtual_Guns_20071129&oldid=13163"