View source for Talk:Bullet Shadow

Cut from Talk:Diamond/Version_History#1.6.0

Very nice score increase indeed. As a heads up, Chase-san has made "cs.Nene MC58k7" the second robot in the rumble to do passive bullet shadow surfing, haha. Also... hmm... it seems bullet shadows will now go on the looooong list of things for me to include on my next surfer. --Rednaxela 06:23, 22 August 2011 (UTC)

Oh, a question about implementations: are you calculating where bullet shadows will be before the bullets pass through the waves, or are you only updating shadows once the bullet actually hits the wave? Currently I'm doing the latter, but I suspect the former may improve scores a bit. Also, precalculating hits may be nasty once actual bullet hits start happening - keeping track of which bullets (which may now be gone) improved which waves (which may now be gone) and in what order is a bit of a nasty. (this question goes for you too, Chase) --Skilgannon 07:33, 22 August 2011 (UTC)

At the moment I only add the bullets once they actually pass the wave, as this was much simpler to add. — Chase-san 10:21, 22 August 2011 (UTC)

Why would order matter? The shadows exist for every pair of bullet/enemy wave until/unless there is a BulletHitBullet, then you can recalculate them all. I still say it's not nasty, despite the fact that I moronically forgot to remove the destroyed bullet before recalculating in 1.6.1. --Voidious 16:03, 22 August 2011 (UTC)

Yeah, but the destroyed bullet might have created shadows by passing through waves before it was destroyed. If you remove it entirely then you'll lose out on those shadows. --Skilgannon 06:48, 23 August 2011 (UTC)

Yeah the new Nene version takes this into consideration. Only waves that it has yet to pass through is it removed from. Since the older ones have been already been proved to be safe. — Chase-san 06:53, 23 August 2011 (UTC)

Oh yeah - duh. I'm sure eating my words about this not being kinda complicated... ;) --Voidious 12:07, 23 August 2011 (UTC)

It doesn't have to be that bad - the nice thing about precise prediction is that you can exactly reverse what you've done before. Just redo the calculation on waves that haven't hit yet and subtract what you added. --Skilgannon 13:56, 23 August 2011 (UTC)

Oh I agree, it was like 3 lines of code. (I still just recalculate them all, but I track when the bullet "dies" and check against that when calculating shadows.) But I've still found 2 big bugs in my code since I dismissed your claims that it could get nasty. ;) --Voidious 14:04, 23 August 2011 (UTC)

Lol @ "death blow". =) Yes, I calculate as soon as a bullet or wave is added. And as of 1.6.1 (which sadly seems to be exploding somehow on Darkcanuck's client) I recalculate all bullet shadows from onBulletHitBullet. It's not really that nasty. I have my lists of active bullets and active enemy waves - when I add one, I loop through the other, and onBulletHitBullet I loop through both, clearing the old shadows first. --Voidious 09:26, 22 August 2011 (UTC)

Congrats. Looking at your debug graphics are the dangers of the dots the actual dangers you use to calculate movement or do you just use those for painting and not use bins for you surfing? I don't use bins in Gilgalad to make the botwidth more precise, but this makes it difficult to mark an area on a wave as safe.--AW 13:37, 22 August 2011 (UTC)

I don't use bins - indeed I do just calculate the danger at 51 specific points for the debug graphics. --Voidious 13:44, 22 August 2011 (UTC)

Well for marking areas as safe without bins, I believe there are two ways:

1. The simple way: Just scale the risk depending on the proportion of the botwidth that is covered by the shadow. (Potential trap of getting caught by bullets near but outside shadows, but Nene MC58 shows this simple method is better than no bullet shadows)
2. The accurate way: Ensure you have a risk function that works with the guessfactors ranges rather than just the center. Then ensure your risk function satisfies the criteria "risk(A to B) + risk(B to C) = risk(A to C)". If your risk function is defined that way, you can subtract the risk of the overlap with the shadow (be sure to not double-count multiple overlapping shadows on the same wave)

--Rednaxela 14:16, 22 August 2011 (UTC)

Rednaxela's #2 is clearly the most accurate way, but seemed really hard. My two approaches were his #1, and since you're dealing with raw firing angles already when you don't use bins, just ignore any angles that fall within a bullet shadow when doing kernel density to calculate danger. Both of those options performed about the same, but somewhat shockingly, doing both was almost twice as good in my test beds. --Voidious 14:26, 22 August 2011 (UTC)

Exactly what I was thinking (re: accurate but difficult), but I have an idea on how to approximate it. The reason it is hard is that we want the danger to push us as far as possible from the firing angles, and to do this, you can use bins (less accurate) or as we do, some smoothed kernel density estimation. So basically we want to approximate the integral of the kernel density estimation across the bot width and use that for our danger. To mark an area as safe, we need to find the danger on the intersection of the interval we will mark as safe and the interval the bot will cover and subtract that from the danger of this movement option as calculated without bullet shadows. So the question is now: "how do you approximate the integral?" Because the danger function is smoothed relative to our bot width, we previously used the center of the bot to approximate danger, but we can do it differently without using much more CPU time. We can approximate the danger by taking the Riemann sum (average the upper and lower for more accuracy) of the kernel density estimation on the interval the bot will cover (for more accurate calculations use more points.) Approximate the danger on the intersection using the same method, subtract this from the movement option's danger, and use this new value. I hope that was clear enough.--AW 15:13, 22 August 2011 (UTC)

Also, if anyone can understand / clarify the algorithm above, should it be added to Bullet Shadow--AW 15:17, 22 August 2011 (UTC)

I think that is very similar to using bins =) The difference being using bins only for the bullet shadow, not the danger function... --Skilgannon 15:37, 22 August 2011 (UTC)

My view is... why bother with the mess of doing a approximations of integrals? Using the exact formula is not hard. Just design a risk function for "probability they fire at a given angle", do a proper integral of that, and just start using it. No need for the extra coding complexity of iterative approximations. It's really not difficult at all, so long as you have a well defined risk function in the first place. If your kernel density function for "probability of where they fire" is the sum of gaussian curves, the integral over a botwidth is made up sums of the "error function". It seems to me, that doing it in an accurate way is only difficult if your risk function is not well-founded in the first place. --Rednaxela 15:56, 22 August 2011 (UTC)

Agreed, I didn't realize how easy it would be to get the actual value.--AW 21:21, 22 August 2011 (UTC)

Actually Rednaxela's full method is more or less precisely what Nene did originally, however it required changing my risk function, the new risk function did not perform as well as the older one did, meaning it gained an overall drop in score. I have attached a little doodle I drew detailing about how it works.— Chase-san 15:23, 22 August 2011 (UTC)

http://img189.imageshack.us/img189/4650/bulletshadowintegrals.th.png

Even with bins it's a complicated story. Because of the finite number of bins, there are obviously cases where bins are only partially covered. So what do you do? Round it at 0.5, take the risk and act like they're empty? Act conservatively by using floor and ceil and not take advantage of that extra half bin that could have been safe? Obviously, the larger the number of bins the better, but isn't it always like that... right now I'm weighting the bin by the portion that was covered, but I don't really like it. According to MC2K7 it worked just a smidgeon better when rounding, but not against the weak bots - I lost 0.3 on average compared to partial bins. The possibility for tweaking is endless...--Skilgannon 14:58, 22 August 2011 (UTC) s

Funny you should say that about endless tweaking. This struck me as a super straightforward feature that you'd implement, collect your 0.8 APS, and move on. :-) Well, before considering more strategic applications where you modify when/where you fire. I may try doing the integral thing to subtract the exact danger in the shadowed region, but I don't expect much gain from that, if any. And it seems non-debatable that that's the most accurate way of modeling the impact on surfing dangers, right? The approximation of 171 bins can't be too far off. --Voidious 18:07, 22 August 2011 (UTC)

Aaargh, you did it! During my holidays before I could implement it myself! I know I should have kept my mouth shut about this idea I had since Moxiebot came around. Although my idea was much more rudimentary and the original idea is probably almost as old as Robocode itself. Oh well, the implementation still has to be done in my case. --GrubbmGait 19:03, 26 August 2011 (UTC)

Size of the Shadow

Is there somewhere that describes how Robocode decides if two bullets collide? Details on this would seem to be required in order to calculate the angles for the shadow. Unless all of you are just treating the shadow as a estimated single point (or small fixed width) that does not grow as the bullet wave expands outward. -- Skotty 16:17, 2 September 2011 (UTC)

I expected to find it on Robocode/Game Physics, but Waves/Precise Intersection seems to have the best description of it. On each tick, bullets move forward by their speed and a line segment is formed between the two locations. Any two bullets whose line segments intersect will collide. So yeah, I simulate wave and bullet movements tick by tick and make shadows for the angles that would cause a bullet collision - where ever a bullet line segment falls between the corresponding pair of wave circles for that tick. --Voidious 16:26, 2 September 2011 (UTC)

Er, obviously that page doesn't talk about bullet collisions, but talks about the bullet line segment stuff, and precise intersection of wave/bullet is similar to wave/bot. --Voidious 16:31, 2 September 2011 (UTC)

I handle it exactly like I do precise intersection cover area, but with just a single line instead. — Chase-san 17:22, 2 September 2011 (UTC)

Bullet collision is handled the same way with bullet/robot collision. If bullets' line segments intersect each other, the bullet colloid. The only problem with this method is that if the bullets are in exactly same angle, they won'y colloid... (I believe Robocode use Line2D.intersect, so using that would be safe) --Nat Pavasant 13:26, 3 September 2011 (UTC)

I used to think that bullet collide detection works like:

1. all bullets move 2. detect every collection

but it actually works like this: (can be found in robocode BulletPeer.java)

1. first bullet move, and detect collision with the rest 2. second bullet move, and detect collision with the rest 3. etc.

as the order is randomized each tick, each moved bullet has 50% chance of colliding with a bullet that is not yet moved.

This sounds as a bug in the game logic.

I was about to go crazy trying explain why there are bullets in my precalculated bullet's shadows.

Well, I don’t think this is a bug, since everything in robocode is handled like this.

And this behavior wont’t affect the shadow we calculated — such area still have 100% collision probability.

Don’t mind there are still bullets in your shadows, if anything got deviation from your prediction, this could happen.

Anyway, make sure that you marked the actual area that two bullets collide, and your bullet is still alive when doing so. This very easy to get an area larger than the real, or off by 1 tick, shifting the shadows.

I see robots creating a bullet shadow every time a bullet passes a wave but there is a chance that it doesn't create a shadow. For example, when two TrackFire fires at each other, the bullets don't collide. Probably I didn't understand the strategy but I just wanted to learn.

Sorry, I think I understood it. Bullets don't collide by their positions. They collide by the line(?) between it's current position and old position.

Exactly, when the lines cross then there is a collision.

The statement is true, however since in that case the shadow size is zero — it won’t hurt so no branching is really needed.

I just spent a fruitless day trying to get some anti-bullet shadowing going to boost my PL score against a few specific bots ;-) I am admitting defeat however, as so far it's done nothing for my scores. My idea: By seeing where they move to, I can figure out where the bullet shadows are, and thus where they are shooting.

When one of my bullet waves breaks on the enemy, assume they are in a shadow. Play the shadow backwards to see where it intersected with all of the enemy waves (the waves they shot), and log all of those shadow/wave intersections to my flattener for that position/wave combination.

Perhaps somebody else will figure out something more accurate... I haven't put any sort of threshold in to only take the shadow into account if it is above a certain width, and I haven't tried running a simple (Raiko-like) gun to see whether they are in a 'dangerous' position for no apparent reason. Either of these has the potential to make this a valid idea, but I thought that I'd throw the idea out before working on it too much more =)

Interesting concept! My suspicion is this ultimately can only provide a very small effect though.

The problem I see, is that the times when the bullet shadows affect movement most noticably (when they are "in a dangerous position for no apparent reason"), are also the times when actual bullet collisions are most likely, and in those situations it doesn't help to know where their bullet is anyway.

(I don't think the term "anti-bullet shadows" is ideal, since it's just taking advantage of leaked information. "anti-foo" makes me think of something directly countering "foo", when this just takes advantage of it rather than countering)

Yeah, I also wasn't completely happy with the name but I wasn't quite sure what else to call it. ABS was the best I could come up with.

So I was curious what this new segment in 2.4.6 might be and I diffed DrussGT 2.4.5 vs 2.4.6 and noticed you decided to keep all this anti-Bullet Shadow stuff in there? I have to wonder if something you did here is what yielded that 0.25 APS gain, since I was a bit shocked that tuning your anti-surfer gun vs Diamond and Tomcat could do that. =)

I was still testing against 2.4.5 and was up to ~50%, but 2.4.6 looks a lot worse. Now I'm curious if that's the gun tuning or the ABS...