My personal opinion is: If you don't know which power to fire, fire power 3. It will hurt more if you are good hitting your enemy, or it will lower your energy as soon as possible if you are not good at it (thus reducing the maximum bullet damage the enemy can score). Of course, it is valid only for 1vs1 (maybe it is true also for melee, but I don't know).
When do I fire?
It seems clear that it makes no sense to fire if you are not going to hit. But where is this limit? Which is the minimum expected probability necessary to make a shot profitable?
The easier way is to model it is as a gain function:
G = (4p + 2(p-1))*a + 3p*a - p //p is the power of your bullet, and a the expected probability to hit
The first term is the energy the enemy loses (assuming you fire a bullet with power (1..3)), the second one the energy you gain by hitting, and the 3rd one is the energy you lose by firing. Not that if the gain is greater than 0, then you expect to gain some energy (relative to your enemy). If lower than 0, you expect to lose some energy. Now, you zero it to get the minimum probability.
G = 0 = (4p + 2(p-1))*a + 3p*a - p ==> a = p / (9p-2)
The minimum probabilities are 12% (power 3), 12.5% (power 2) and 14.2% (power 1). Note that you expect to get more energy when the bullet is more powerful. For example, you will fire a power 3 bullet if the expected probability is 13%, but you will not fire a power 1 bullet if the probability is 13%.
Note that the previous function is only good for 1vs1. The previous strategy can lead to a situation where your energy level goes down (simply because it makes the enemy energy level to fall faster than yours), but you probably don't want it in meele. The following function is probably more appropiate for meele:
G = 3p*a - p ==> a = 1/3 = 33% (note that it is independent from fire power).
Which fire power do I use?
Well, now things get more confusing. First of all, the probability to hit is related to the fire power. Second, you have to take into account that the enemy is firing at you, so may be the most energy-efficient strategy is not the best strategy...
Currently, the only bots of mine that use a fire power selection strategy are Mamba's. Depending on the version, they maximize the following functions.
Calculating energy gain per time unit
To calculate this gain, the approach is similar to the one used previously. You simply have to add a factor to take into account that a higher power means less shots (because you need more time to cool down your gun) and also that the probability to hit is a function of the power you use (you should also consider the distance, but of course, you are taking the decision for a given distance, so what you need is to keep statistics for different ranges).
G = (9 * p * a(p) - 2 * a(p) - p) * (1/(10+2*p)) //a(p) is the probability to hit based on the power used
Note that this function is almost the same one used before, but multiplied by the inverse of the number of turns you will need to cool down your gun.
a(p) is unknown, so we have to estimate it. The easier way is to make a linear approach like this:
a(p) = a - b * p a is the probability to hit with a bullet of power 0 (ie. of velocity 20). b is the decrease in the probability by increasing the fire power by 1. Example: If you have a probability to hit of 30% with fire power 1 and of 10% with fire power 3, then a = 0.4 and b = 0.1
You can collect data from your previous shots and easily calculate this parameters.
Now, the easiest way to calculate the best fire power is to iterate some values of fire power (ie. from 1 to 3, steps = 0.5) and to select the one with higher gains.
Another way, more accurate, is to calculate the máximum of this function by derivating and finding the zeros of the derivative. I'w not do it here (I posted a link in Math section that does it for you, but I'w post the final formula.
Best Power = p = [(2b+9a-1) + Sqrt((1-9a-2b)^2 - 4*9b*2a)] / (2*9b) Note that this function can have result higher than 3 (use 3 instead) or lower than 1 (remember that G has a range for p = (1..3)).
As an example, for a = 0.4 and b = 0.1 the best firepower is 2.79.
In a competition situation it might pay off to implement a strategy to deny the other bot points by wasting energy. In melee it might be important to kill off bots, both to get the bonus and to deny other bots the bonus.
In one-on-one SurvivalBattles? it is much easier to calculate the fire power to be used. You should fire so that you hit one shot out of eight. This fact is used in Pandora which is a PerceptualBot designed for SurvivalBattles? and uses RandomFiring?.
In Relativity, the primary tuning factor for firing is the time in flight of the bullet, which is closely related to the hit probability. The desired flight time of the bullet is then adjusted for each hit and for each miss so that the hit-rate stabilizes at the desired ratio.
In ordinary battles for points, the general rule discovered by Stuart Holliday is "always fire 3". This is probably not entirely correct, but given that you get bonus points for damage done and also deny the other bot points by wasting your own energy, the rule holds fairly well. --tobe
Yngwie (winner of the original Robocode Rumble) observed that it's generally a waste of energy (especially in melee) to fire a bullet that is more powerful than can finish its target off. It fired a lot, and fairly confidently, but it was still interested in not wasting energy. Just for the sake of simplicity, I don't figure out the exact bound, but I fire no more than 1/4 of my opponent's energy. As a survivalist, I don't ever fire harder than 1/5 of my own energy, either (or .1 if that's all I have left). -- Kawigi
If you want, the exact solution is something like this:
bulletPower = Math.min(bulletPower, event.getEnergy() >= 4 ? (event.getEnergy() + 2) / 6 : event.getEnergy() / 4);--nano
Actually, if there is no previous bias to the bulletPower, it seems to be this (eliminating the Math.min part): bulletPower = (event.getEnergy() > 4) ? (event.getEnergy()-6)/10:event.getEnergy()/4; Does that sound right at all? I'm taking damage = 4*power+(power-1)*6 and solving for power. --Kawigi
Ah, my (power-1)*6 is part of my conception of 6=4+2 (it should be 2, and 4 is what power was already multiplied by). My mistake :-p --Kawigi
In my test league that I'm running with the dev version of FloodHT right now, if all ER rankings depended on how you did against the 'hourly build' of FloodHT, Marshmallow would be staying at 6th, or if only the latest build counts, Marshmallow would be king of the ER. It appears that 1.7 still doesn't have as good of movement against more conservatively-powered bullets. Of course, that's just based on my experiments with bullet power/energy management. With a very survivalist system I tried, I did better against Chameleon, CigaretBH, Marshmallow, Tron and Princess, but with a more damage-oriented system I tried, I did better against DT, FloodMini, Cigaret, and GlowBlowAPM. The margin of difference seemed to favor the more aggressive system. I'm trying using a system that is fairly middle-of-the-road (after trying to intelligently choose one or the other, that didn't work incredibly well), but still somewhat aggressive. I'm still running tests on it, but it appears to be even better against DT and Chameleon, but worse against Marshmallow, who may be well on its way to being the biggest drag on the next version of FloodHT's rating. It appears that another factor that should go into play with selecting fire power is whether the author of the robot used StatistRobot and SmogPainter to assist in tweaking the movement. If they did, fire lower-powered bullets, because they have great movement against power-3 bullets :-p -- Kawigi
Maybe it's time for something like DynamicFirePower?. That way your bot would be able to capture M's weakness for weaker bullets while being able to gain the advantages of shooting hard against many of the top ER bots. I can't try it with M since it would slow down its learning rate even more... -- PEZ
Exactly the problem. One observation is that it can be good to use my energy-conserving system if both robots' hit rates are extremely low. That way my energy goes down slower and I have the advantage at the end of the round when neither of us have hit each other ;-) But that logic doesn't seem to stand completely. I'd actually be interested in seeing some of the logic that DT uses for selecting fire power, since he seems to use a pretty arbitrary selection. -- Kawigi
Is that optimal for like, how to put out energy the fastest? I am really clueless when it comes to deciding firepower. I'll go read up more on deciding firepower and see what I can come up with... -- Vuen
=) I am pretty clueless myself. Some month ago I started to figure about it and draw some curves on bullet damage in relation to max escape angle. This is the graph:
It suggests that after 1.72 something you start to get harder to hit the enemy in relation to how much you can gain on hitting it. I think. What's your thoughts on the graphs story? -- PEZ
Well, my thoughts are that your graph assumes a movement that's Flat with Flat juice on top no matter how you split it up. What if your targeting algorithm is more likely than just random to hit? -- Kawigi
I totally agree with Kawigi. Besides, there is whole 'game theory' related issue. What would change if survival bonus was 200? Or damage bonus 45% instead of 20% ? When to start endgame and limit your shooting power even more? When to delay shooting to conserve power? Your solution is 'one fits all', probably good against flat movement and game where bots start with 10000 power. -- Frakir
I don't quite follow. What if my algorithm is better than just random? I haven't proposed a solution. (Unless you count the not-so-seriously-intended "optimal fore power 1.72. =) I just want to hear what you think is the conclusions one could draw from the graph's story, The graph does not assume anything really. It's just probabilities I guess. Selecting fire power is tricky. You need payback on power consumed, right? Let's say you start out with 1.7 while you don't know anything about your enemy's movement. And then you can adjust this if you find out you can get payback enough with another power level in certain segments. I'm just brainstorming here. -- PEZ
What might be more significant here is figuring out what your actual chances are of hitting at the current distance in the current direction at the chosen bearing, and see if such a graph would show a different optimal value for you in that specific situation. After that, the only thing you have to worry about is if the answer is not time efficient, which I suspect is a minor issue, particularly if your movement is remotely good. -- Kawigi
But such a graph could be expressed as a deviation from the general graph above, right? In Marshmallow I have the kind of stats you suggest I think (rating the VirtualGuns). How would I deduce from that what bullet power I should choose? I don't understand the part about time efficency. Can you elaborate some? -- PEZ
I think you could use VG stats for this, or it may make sense to keep more detailed stats (or more segmented stats) than you use to choose VG's. The way to deduce bullet power is to figure out at what power the greatest margin of benefit is. For example, if you have probability of hitting with a certain power is p, the margin of benefit of firing at that power (assuming a 1-on-1 battle) is (your gain in energy + their loss in energy-power)*p-power*(1-p). Basically, the potential "net gain" from hitting times the probability of hitting minus the potential loss times the probability of missing.
The time efficiency I was referring to is maybe some lower power is more beneficial by this definition, but a higher power would still be almost as good, and if you always fire at a lower power, your opponent may win because they just finish killing you faster by using higher-powered bullets. -- Kawigi
I knew this would quickly become rocket science. One size fits all isn't too bad I think. At least as long as you haven't collected enough data to apply the brain surgery on. Quite often before the advice for people who don't want to introduce complexety here has been to shoot with power 3 here. Just maybe it is better to shot, say, 2.2 instead? -- PEZ
Maybe. The main disadvantage of the method that I discribed above is that it may require too many additional calculations to be worth it. The idea, though, is basically like the idea of DynamicDistancing in concept, and is also based on the idea of how much energy advantage you would lose or gain if you fired a certain power 100 times in this same situation. -- Kawigi
The thing I don't get is, how do you figure out what firepower to shoot AFTER selecting the graph segment you're deciding on? Choosing a different firepower based on the graph you find varies the bullet travel time, which varies the segment, so your graph is useless. The only way seems to be pulling off a graph in each segment of bullet travel time, calculating the chances and gains based on firepower for each and every graph, and then comparing them from there. Just seems like a LOT of work, and that usually ends up badly for my robots anyway; besides, in this case you'd be better off segmenting on power and distance rather than flight time. I created a simple firepower selection algorithm in Fractal, and it seems to improve its performance, but I'm sure as soon as I upload it it'l turn to crap. I'm tempted to write a quick firepower optimizer that bases itself on a Flat curve with Flat juice on top; that or I'll change my bullet flight time back to straight distance and just segment on firepower instead, and just compare all the segments of firepower instead of flight time. I'll see what happens. -- Vuen
Yeah, Vuen, that's what has prevented me from doing choosing firepower based on the segment when I'm segmenting on bullet travel time. Of course, a study needs to be done on the value of using that vs. using distance I think... -- Kawigi
There are two cases: trying to maximize energy gain or trying to get as much score for damage as possible. Let's say you have a function to calculate hit posibility with certain firepower. p - probability to hit (0<=p<=1). Probability to miss is 1-p. 1) If you hit: enemy loses Damage, you gain power_returned-firepower. If you do not hit: you gain -firepower. To sum up: F = p*(Damage+power_returned-firepower) - (1-p)*firepower. 2) If you hit: you get score Damage, and you lose firepower energy, so maximum opponent damage is reduced by firepower, you get +firepower score difference. If you miss: you lose firepower energy, +firepower score diference. F = p*(Damage+firepower) + (1-p)*firepower. You may chose one of these strategies depending on robots' energy. If there is a huge energy difference, it is unworthy to try to win, and so on. It is possible to combine both methods. pWin(myEnergy, opponentEnergy) returns the probability of winning the round using robots' energy. You may use some kind of statistics or anything you can think of. If you hit: you get 120*pWin(my_e+power_returned-firepower, opp_e-Damage) on average (50 for survivor, 10 for the last survivor. You get 60 or opponent gets 60, that makes the difference 120), and you get Damage+firepower score difference for damage (see case 2). If you miss: 120*pWin(my_e-firepower, opp_e) + firepower. F = p*(120*pWin(my_e+power_returned-firepower, opp_e-Damage)+Damage+firepower) + (1-p)*(120*pWin(my_e-firepower, opp_e)+firepower). Maybe you can simplify a little: F = 120*pWin(my_e, opp_e) + <score difference for damage>, but I don't know how much accuracy you may lose (probably not much). You need to maximize F. Possible solution could be calculate all firepower values with certain step (for example, calculate F with firepower 0.1, 0.2, 0.3, ... , 2.9, 3.0). asm
After PEZ's successful experiment with an always-fire-2.4 strategy, I've been playing around with various bullet power strategies and looking at what ought to be optimal, from a theoretical point of view. There are some surprising results....
To maximize bullet damage; the formula for bullet damage per unit time should be (1/Math?.ceil(10 + power/.5))*p*(6*power - 2) for 3 >= power > 1, where p is the probability of hitting the opponent. Of course p is not independent of bullet power. However, if we assume that the opponent's movement profile is no better at any one range or bullet power than any other, then p is proportional to atan(18/enemyDistance)/Math?.asin(8/(20 - 3*power)) - that is, the angular bot width over the escape area. This assumption will probably be false for a given opponent, but true when averaged over the general population - people tune for a variety of bullet powers.
I ran this equation through a program to find it's value for a given range. The maximum lies at one bullet power for all ranges; that bullet power is... 2.5. A bullet power of 2.5 gives you both a smaller escape angle and faster gun cooling than 3.0, and they balance the slightly higher damage. There are local maxima at both 3 and 2. Interestingly the theoretical difference between the maximum bullet damage and the damage at 2 is always < 7%.
Always-fire-2 seems like a crazy strategy, so I ran some tests against VertiLeach; one with Raiko always firing power 3, one power 2.49 and one power 1.99. Each was over 250 rounds. In each case Raiko's bullet damage was the same to within < 4%, wich is probably margin-of-error; it was actually highest at 1.99. This is at very close range, almost always less than 300.
Interestingly the score was also almost exactly the same, even though survival went up at lower bullet powers. Why? Because Verti's bullet damage also went up... obviously, if I run out of energy faster, then the opponent has less chance to score bullet damage points, which balances the extra survival score.
Conclusion: you can fire pretty much whatever bullet power you like, but 2 isn't a bad number at any range other than point-blank. -- Jamougha
If you are referring to Aristocles 0.3.0 as my "experiment" I must just make clear that it is not the first time I try with "only power 2.X" where X is on the low half towards 3. Griffon does this too. I think it is firing only power 2.2. I have never really figured out why it works so well. As you can see above my only theoretical approach to this problem has lead me to propose maybe the optimum fire power is 1.7 or there about. But you don't see any of my bot fire that low powered bullets. Thanks for sharing your theory and your empirical findings. This gives me some rest in trying to figure this out. "It doesn't really matter much" is the lesson I should have learnt from all my experimentation. But I have been too stubborn and too thick headed to grasp it. Now to a question. The way Tityus gun works is to use a fixed bullet power at each distance index in its segmentation. This to avoid segmenting on bullet power. You know this I see since you have kept this property of the gun. But, if it doesn't matter much what bullet power you use at given distances. Is it worth while to lower your bullet power with distance like Tityus and its descendants do? -- PEZ
Good question... inside a bullet travel time of about 5 it should be possible to write a linear prediction gun with near 100% hit rate, since the opponent just cant change direction or velocity quickly enough. Here it's better to fire power 3, if you have written such a gun... but I haven't, yet. :-) Still, with long learning times firing 3 inside distance 100 is probably a good idea. At very long ranges it might also be worthwhile to fire lower power, so as to increase survival. However between 100 and ~600 I'm pretty certain than constant firepower is just fine, and since 2.5 and 2 are generally 'good' values for bullet damage I'm inclined to pick one and stick to it. Especially in a microbot, where it's saving me enough codesize to introduce wall segmentation and finally thrash Sedan. ;-) - Jamougha
damage / escape_angleratio PEZ"? =) -- PEZ
It seems like there's some merit to your theory about maximizing the
damage / escape_angle ratio, PEZ. I know I've started using 1.9 in Cyanide. -- Alcatraz
Thanks! It took many months for someone to give me those words. And some begging. =) -- PEZ
Well, i already said "Thanks, PEZ!!", but since i really think that it was brilliant there it goes: it seems like there's some merit to your theory about maximizing the
damage / escape_angle ratio PEZ! -- Axe
I think the graph is misleading, but I did do quite a bit of tinkering in Excel to find what I think should be a magic number. I did factor in damage, escape angle, and some other stuff. I have plans to factor in some dynamic information as well, but a fixed number will do for now. Previously I was iterating through several firepowers and comparing the damage potential to my historical hit percentages at that range. I'm going to redesign my virtual guns statistics so it is time to revamp my firepower selection, which should speed up my bot quite a bit as well. -- Martin / Ugluk
How do you find out the specific probability for a firepower (to use the formula on top)? --Starrynte
Is it p = atan(18/enemyDistance)/Math?.asin(8/(20 - 3*power));?
Do you mean the probability that it will hit the enemy at a certain distance with a certain fire power? If so, I think that would be (approximately)
(18 / distance) / Math.asin(8 / bulletVelocity(firepower)), which is the angle that half a bot takes up at a certain distance divided by the angle they could move in one direction (at any distance). Bullet velocity is (20 - 3 * power). -- Voidious
I wonder... currently I'm pondering a way to really make a good firepower selection... Right now I'm thinking of tracking a special "hitrate relative to nominal" based where have counter 'a', and 'b'. Every time I hit, 'a' and 'b' are both incremented by (1 / (angular botwidth / max escape angle)), and when I miss only 'b' is incremented. The theoretical hitrate at a given distance and bulletpower is subsequently calculated from ((a/b)*(angular botwidth / max escape angle)). In order to select optimal bulletpower, I'll combine that later equation with the gain function at the top of the page, and do a little calculus/algebra to solve for the maximum gain. I think that would create a bullet power selection that should be optimal at any hitrate/distance and consider how distance affects hitrate. The only catch is it does not consider things like how a fleeing bot may be easier to hit, to take that into consideration would require integrating learning stats as well which I I'm not sure if I'd trust to be robust enough. Any thoughts on this idea for selecting bulletpower with consideration for both hitrate and distance? -- Rednaxela
Sounds like you have it pretty well figured out. One other thing you may want to consider is the height of the spike that you are shooting at in your gun stats. As to whether it is robust enough, there's only one way to find out =) Hack up a messy implementation, and see where it gets you =) If it helps, integrate it a bit better. Good luck, wish I had time at the moment to do something like this. -- Skilgannon
Haha, well, I was thinking of something like that with the height of the spike in gun stats, but the problem is that after some of my crowdtargeting experiments, I'm not sure I 100% trust gun stat data besides the location of the peak. I'll probably first start with a basic version without consideration for gun stats. Actually, another problem with using gun stats, is when some of your segments are influencthed by the bulletpower you select (I use wall segments measured in GF units, and some other people segment on bulletpower or bullet-travel-time I think), you'd run into a chicken and the egg problem. And time? I won't have time for something like this until winter break. For the moment I'm just hyping :) One other note, is besides that 'optimal formula' I plan to also make special conditions for some "game theory" considerations mentioned earlier on this page by Frakir, which come into play in the 'endgame' (i.e. if the opponant can be finished off, our own energy gain isn't really important and a chance for a finishing blow might be worth sacrificing a little hitrate for?). Maybe I'm dreaming, but I think that better firepower selection might really boost RougeDC's rank... after all it's default bulletpower of 2.5 I believe seems sub-optimal against bots it can't hit well. I first intended for RougeDC Classic to be the final release of RougeDC, but I think it's the best way to test my theories for selecting firing power... I suppose this, and maybe a related dynamic distancing plan, will be a last-ditch effort to raise RougeDC into the top-10 before I focus on my other plans like how to smear the wall with current-generation learning bots. </rant> -- Rednaxela
Yeah, I hear that base powers of either 2 or 1.9 are quite common among strong bots, but I think, if I'm going to fix RougeDC's bullet power, why not go all the way with an adaptive 'optimal' solution? After all it's not as if keeping the necessary counters would be difficult :) -- Rednaxela
Oh... Haha... I did mess up my description of how to do it above. Counter 'b' should just be incremented by 1, not the fancy number. :) -- Rednaxela w Haha, only now did I read into Albert's text block further, and realized that what Albert was using in Mamba was far closer to what I propose than I thought, with the only difference being that instead of the "a(p)" function he uses, I use an a(p, d), where d is distance and the function is based on 'maxescapeangle' and considers the bot's angular width. Funny how I failed to notice the section of the page where Albert talked about maximizing gain and got lost in my own thoughts about it. Still, it's likely RougeDC may soon have the most advanced bullet power selection out there :) -- Rednaxela
So for a quick test here, I made RougeDC use a bullet power of 1.9 normally instead of the 2.5, and in a quick battle I scored 49% against Shadow instead of about 39% which is a big difference! It's looking like at very least, RougeDC could become a top-notch PL contender with even minor tweaks to bulletpower... I wonder if I should release the 1.9 bulletpower version before I get the fancy dynamic bulletpower finished. -- Rednaxela
Update: Well after additional trials, I found that the 49% was partly luck, but still 1.9 was an improvement over 2.5. I just got the adaptive firepower working based on the normalized-hitrate/botwidth/escapeangle/energygain/etc. and against Shadow it was choosing anything from about 0.35 to 1.6 for most of the match, depending on the exact moment. The end result on score? Worse overall scoring, similar to the old 2.5, however execelent near 1:1 survival ratio. Against Cunobelin 0.2.2, once it's stabalized it seems to select bullet power more in the 1.35 to 1.9 range, scoring a little better overall, but cutting Cunobelin's survival to about 2/3rds of what it used to be. After I get this survival mechanism perfected... I'll make a modified mechanism in the same spirit only designed for score... :) -- Rednaxela
Well I haven't yet made a method that optimizes for score logical semi-formal way, but what I have found is that optimizing 2/3rds for energy gain and 1/3rd for bullet damage seems to yield a decent result again Shadow.
|Rank||Robot Name||Total Score||Survival||Surv Bonus||Bullet Dmg||Bullet Bonus||Ram Dmg * 2||Ram Bonus||1sts||2nds||3rds|
|1st||abc.Shadow 3.83c||2719 (50%)||750||150||1642||177||0||0||15||20||0|
|2nd||ags.rougedc.RougeDC (dev)||2703 (50%)||1000||200||1329||174||0||0||20||15||0|
Cool! Good work. It should be fine having 3 versions at once, as long as they're temporary. It'll be interesting how your weighting system ends up, the kind of bullet powers it finds optimal, etc. -- Skilgannon
Alright the 3 new versions are up there now. Well, one thing I noticed is the "balanced" one that I just mentioned seems to like bulletpowers in the 1.8 to 2.3 range against most medium to subtop movements, in the 2.3 to 3.0 range against the very most easy to hit things (rambots, spinbots), and more like 1.35 to 1.9 against the top movements that my gun really can't hit well. Overall it seems to confirm that the 1.9/2.0 values are quite sane usually. Feel free to try yourself if you want to, it does output it's bulletpower selections in the robot console, among other debugging spamminess I should really remove. Anyways, will be interesting to see how the rankings of these versions will compare. -- Rednaxela
Interesting how bp1.9 dominates the other 3 in the PL, while balance gets the highest score. -- Skilgannon