 | 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
if (bullet hit)
raise success rate for aim method used to fire this bulletelse 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.
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
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
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
![[Home]](/images/RoboWiki.png)