Archived talk:GuessFactor Targeting (traditional) 20071112
DuelistMicro uses this to great effect and is open source. Duelist's source has also been released if you want to see the code I was talking about when I wrote this email, but DuelistMicro's is better and smaller. --David Alves
"Calculate how far forward the other bot could go if it suddenly went top speed forwards for as long as it would take my bullet to reach the other bot. Call this Point A."
do you calculate this point with the current enemies heading ? -- deathcon
Yes. Though I don't do it exactly this way in my bots. I calculate the maximum lateral bearing change using the current enemy lateral bearing direction and call this maxBearing. Then I slice the spectra from -maxBearing to +maxBearing in guessfactors from -1.0 to 1.0. VertiLeach uses 17 slices (since it stays so close to the enemy and GloomyDark uses 23 slices, -- PEZ
And my calculation of maxBearing looks like this:
static double maxBearing(double power) {
return Math.abs(Math.asin(MAX_VELOCITY / (bulletVelocity(power))));
}-- PEZ
But if you calculate it that way you DONT use the current enemies heading but a relative angle of 90° i think , dont you? --deathcon
Right. If we use the enemy's current heading and velocity, they could turn or speed up and all of our guesses could be wrong. What you DO want to do is multiply that by something to account for your enemy moving to the left relative to you or to the right. -- Kawigi
what it MAX_VELOCITY ? Is it the maximum speed our enemy can travel with?If so wouldn't it be better if you would calculate the maximumBearing depending on the distance to this bot?
MAX_VELOCITY for a bot is 8. That bearing (Math.abs(Math.asin(MAX_VELOCITY / bulletVelocity(power))) will calculate the max possible angle without knowledge of distance. Bot distance == velocity * bullet flight time and the bullet distance == bullet velocity * bullet flight. This allows us to cancle out bullet flight time leaving Math.asin(8/bulletV). The common misconception (at least the one I had when I started) is that this is a right trianlge and try to use that math. It is not though. I believe this is the Law of Sines in use here. One shortfall is that there is no accounting for accleration. It is assumed that a bot can "suddenly" take off at MAX_VELOCITY and this is not the case. It has proved to be close enough in practice though. -- jim
Actually, it is a right triangle, with the right angle at the enemy bot. The law of sines is relevant, though, but the calculation would be a little different here if we were actually using it. We would use something like
- Math.asin(Math.sin(e.getHeadingRadians() - e.getBearingRadians() - getHeadingRadians()) * MAX_VELOCITY / bulletVelocity(power)))
You would have seen this code in SandboxMini (I remember you asking about it, Jim). The problem is that sometimes our opponent can turn and end up outside the range. It turns out that to make this angle the largest it can possibly be, the thing we're taking the sine of (which is the angle between a line from us to them, and the line they're moving on) is 90 degrees, basically meaning that our enemy is going to move in a straight line exactly perpendicular to our position when we fire. -- Kawigi
From the RoboRumble/RankingChat discussion:
As for weighting the bins in a GF gun... When I was first building my GF gun, I tried coming up with a good concept of picking the angle to shoot at. (This isn't really the same as what you were mentioning, but it kindof applies.) Anyway, at the time, just shooting at the highest bin seemed a little too simple to me to actually work properly (the KISS principle usually hates me (that sounds wrong on multiple levels... lol)). Anyway, so I figured, how about I pick, say, the top 3 peaks in the graph, then do a weighted random selection of the 3. Of course, this is of no real use. Say you have 5 angle bins (I know it's more like 30, but bear with me). 3 of these are empty, bin 'a' has 20 hits, and bin 'b' has 10 hits. Thus 2/3 of the time, the enemy is found at 'a', and 1/3 of the time the enemy is found at 'b'. With a weighted randomization, 2/3 of the time it chooses the 'a' bin, and 1/3 of the time it chooses the 'b' bin. Mathematically, this adds up to 1/2 (or 5/9, I forget) chance of hitting. But just shooting at the highest bin gives you a 2/3 chance of hitting! After more work I ended up just assuming that, provided the distribution of angles is consistent, your probability of hitting the enemy cannot exceed the probability of hitting by always firing at the highest bin. There's my obvious conjecture about GF guns : ). I'm sure there's a mathematical proof for it, but I'm really quite sick of math for a while. There's my blurb on GF guns. I'm going to bed : ) -- Vuen
Shooting at the highest bin might work very well. But I think there are situations where it can be wiser to shoot at the densest part of the curve rather than at the peak. This is what VisitCountStats/Dynamic is about. I have yet to prove that it works though since I have this bug in GloomyDark... -- PEZ
Jekyl use's a simplified kernel density estimator to find the "densest" part of the curve. My implementation of the estimator (called a nieve estimator) buckets a guess factor with some number of neighboring bins that surround it (left and right). I then count all occurances that happen with that range and compare this with all other such "windows" to arrive at the window with the highest probability of occurance. I have implemented it in such a way that I can dynamically adjust the window size on the fly. Currently I use a large window for close range (where it is possible for guess factors to overlap) and a smaller window at longer ranges (where they are less likely to overlap). One un-intended side effect of this is that you need to come up with some algorithm for handling the edges and near edges (-1, +1) as they have no||few left||right neighbors. This tends to concentrate your fire more toward the center. Now that I type this I wonder if this was the reason for SandboxDT 1.91 and lower to default firing at +1/-1 when a target was beyond some set distance. Paul, care to share? A yes or no answer (addressing the +1/-1 statement) is enough for me. -- jim
I believe DT fired at +1.0 when the distance array was out of bounds - in normal battles this never happened because I measure distance as bullet flight time, and over long distances I used fast bullets or no bullets at all. Then the movement challenges came requiring DT to fire 3.0 bullets, and the bug was discovered. -- Paul
Can I suggest you change the window size basd on the number of sampled points you have rather than the distance - with more sample points you have a better chance to find small and thin peaks and reduce the effect of the edges. However I would not reduce the window size to smaller than the apparent width of the bot (you will need to convert your data into guess factor ranges for this. -- Paul Evans
Thats one method that I had not thought to try. I will have to give this a shot (no pun intended) soon. -- jim
Interesting. Now I'm tempted to move Fractal's smoothing functions to make it gather all data normally and smooth on the fly instead of smoothing as it puts it in the bins. However I'm not sure if it will make much difference. I had originally thought of setting the gaussian smooth's deviation factor as a function of distance (i.e. smoothing across the angles that make up the width of the bot), but I guess I never got around to doing it. This does sound like a good idea though. Maybe I'll try that too sometime when I find some time to burn on Fractal. Let me know how varying the window size works for you jim :) and good luck with it! -- Vuen
There are 2 things which need to work together. First is updating all bins where hits for a wave can happen, maybe with different factors varying by how big is the part of bot in that bin. For this part of collecting data one should use fixed bots size of 36 in each direction. You may also try to keep your wave flying for a few ticks after the hit, just to update all possibly successful bins. Then there is another thing when selecting best shooting offset. Here you should adjust for actual bots size as visible by bullet form its angle. I think that is what Paul mean by 'apparent width'. I am doing this, but only for distances less then 300 (I have 30 bins). For larger distances it somehow don't work here. -- Frakir
Vuen FYI DT does it's smoothing whilst it is putting data in the bins. Doing it on the fly would make it very slow indeed. -- Paul Evans
Frakir you are a genious! I wish I had a bugfree gun that I could test that idea with keeping the wave updating all possible bins. Right now I am registering the "hit" when the wave is some 20 pixels from reaching the enemy. I would really need some pseudo code for the part with "factors varying by how big is the part of bot in that bin" though. I somehow have trouble wrappingmy mind around the problem. (Maybe that is because I am up really, really early today...) -- PEZ
I've tried doing this a couple different ways - one is just incrementing buckets every tick a wave would hit an enemy (might make it a circle enemy to make it easier), and not removing it until it has passed all the way through. The other option is to keep an array of booleans and set the ones that hit at any point in time to true (then increment the true buckets after the wave has already passed through). The latter is what I suspect DT does, or did when it first started using waves, because Paul said it was functionally equivalent to the original VB system, and that would basically be the way to do that (treating each wave as an array of VB's, so to speak). -- Kawigi
Ah, thanks Paul. I'll change its smoothing now to set the standard deviation to the width of the tank, and test it out; I may also switch to just using a boolean array finding everywhere it hits, like Frakir suggests, and compare it to the other way. -- Vuen
---
Erm, there seems to be a bug in my code, in GuessFactorTargeting... Guess Factors are not supposed to be greater than 1 or less than -1, right? How am i getting more than 1, sometimes 175 as a guess factor? Right now my basic guess factor formula is:
double guessFactorLength=e.linearAim-e.centralAim; double radiansOff=normalize(e.bearing()-e.centralAim); double guessFactor=(radiansOff/guessFactorLength); System.out.println((int)guessFactor +" , "+ radiansOff + " , " +guessFactorLength);
- added pre-tags for a better readability --deathcon
I assume in the linear aim that the speed of the enemy robot is 8 just for the custom event. Central Aim is the aim i would take without any aid of targeting. I cast to int so i can easily see when my code is producing guess factors above 1. Thanks in advance!
-- DragonTamer
With linear Guess Factors it is more than possible to get Guess factors more than 1.0 and less than -1.0 - this can happen for example if a slow moving bot speeds up after a bullet at been fired. It is therefor possible for a bot to 'trick' this form of guess factor targeting - but it does save having to segment on speed. SandboxMini uses both linear Guess Factors as well as Absolute Guess Factors to avoid this problem. -- Paul
If you're assuming a velocity of 8 (as you say) than that isn't linear GFs, although you may be calculating based on the enemy's heading, which would confuse matters. For absolute GFs (like most bots use, i belive) you need to assume it is going full speed, and assume it is going perfectly perpendicular to you. -- Tango
What different algos do use to calculate the maximal bearing change? --deathcon
Recent versions of iiley's bots use at least two different functions. Marshmallow used something I termed an EscapeArea. Some bots consider the current velocity of the target, some only max speed and some use a rolling average of the enemy velocity. You could also hook up all these different ways in a VirtualGuns array and use the gun with the best virtual hit rate. -- PEZ
For those interested I may have found the cause of the escape area problem. Tell me what you think:
First, we'll make a hypothetical situation involving two bots, (a) and (b), centering the coordinate axis around bot (b), the target bot.
+----------------------------+ | | | | | | | | | | | | | | | |-------------b-------a------| | | | | | | | | | | | | +-------------|--------------+
We'll arbitrarily call the distance between (a) and (b) 10. Bot (a) is stationary and bot (b) is moving flat-out upwards at maximum velocity (beginning as soon as (a) fires his wave). This creates a right triangle.
+---------+ | b | | |\ | | | \ | | | \ | | | \ | | | \ | | +-----a | +---------+
Since robocode is a discrete system, we don't need to use anything fancy here, just a table of values will do. We'll assume the wave travelled at velocity 11, like a power 3 bullet.
| time | wave travel | (b) travel | (a) to (b) dist | 0 | 0 | 0 | 10 | 1 | 11 | 8 | 12.8 | 2 | 22 | 16 | 18.9
We stop here. Looks like the distance is now exceeded by the wave travel, meaning we've hit our target. Funny thing, though, we haven't hit our target exactly at 22 like we've assumed we would, instead we've hit our target at 18.9. Let's compare the two right triangles.
+--------------------------------+ | b b | | |\ |\ | | | \ | \ | |16| \ 18.9 and 16| \ 22 | | | \ | \ | | | \ | \ | | +-----a +-----a | | 10 10 | +--------------------------------+ (as Loki has pointed out, the second right triangle is impossible to begin with)
Using the definition of sin in a right triangle as opposite/hypotenuse we can calculate the sin of the angle in (a)'s corner in each case.
asin(16/18.9) = appr. 57.84 degrees asin(16/22) = appr. 46.66 degrees
16/22 is the same as 8/11, our ideal theoretical proportionality. In making this proportionality we discard, however, that the impact when the bullet has travelled 22 units will take place not at 22 but at
11 < d <= 22
As the distance increases the affect on the angle of varying this number will decrease, because the variance is only one tick of travel in a typically 20+ tick travel time, a small percentage. For this reason we're able to "fudge" our ideal range up by 115 or 120 percent and avoid crashes. Comments? -- Kuuran
what is the Escape Area Problem to which you refer at the top of the section? I agree that most of the time a hit will occur before the bullet reaches the center of the bot, but somtimes it can occur after passing bot center. -- Paul
i think the first figure gives you the correct angle, but at an incorrect time (time is a bit smaller than 2). Figure 2 can't give you the correct angle as you don't have a right triangle. --Loki
I think the referred problem is that the common axiom for calculating max escape angle (around the lines of the maxBearing function above) sometimes gives a too small figure. -- PEZ
PEZ is correct it refers to the use of asin(8/11) for maximum angle of escape. As for your comment Loki, that's true, but most bots will call it one and calculate based on that, check the logic of any open-source stat targeter. Paul, that's not really what I was on about, it's not about where the hit takes place but about why people who have started using waves are ending up with guess factors of 1.2 or 1.3. -- Kuuran
Bot will not necessary move at maximum angle if it moves at straight line. I think it will reach maximum if it moves a litle towards the opponent. However, approximation is probably unavoidable. The simplest calculation I know: assume that bot moves round the circle. Then max escape angle is botSpeed/bulletSpeed (radians, of course). -- asm
Yeah, the asin() seems almost unecessary here. Save me a few bytes, thanks! Please update your wiki Preferences with your wiki name. -- PEZ
Without the asin() you assume an opponent moving a circle around you as the maximum escape angle. The straight tangent line (asin(8/11)) is in fact the largest, however, there's a proof to that effect somewhere on the wiki. The only problem with it is that this angle doesn't neccesarily refer to the center of the bot but merely where some part of the opponent bot intersects the wave, so finding the angle to the center can result in larger than this angles due to forcing impossible values onto a right triangle. See above. -- Kuuran
I do like Jamougha anyway and multiply with 1.2. =) -- PEZ
When segmenting guess factors, does anyone use segments based on the current movement modes they are using? If I was in antigravity mode(not moving much, avoiding bullets) and I switched into random movement mode(all over the place, a few rams) the enemy might react by altering it's movement, giving vastly different hit ratios. -- RobocoderDan
I have done this in the past. Bots which control their distance will move relative to how you do. Try it and see how it works. -- jim
First off, who wrote that? Sign your posts! :-) Many bots keep different data for melee vs. 1-v-1 (I'm assuming you're talking about using AntiGravity in melee and RandomMovement in 1-v-1), but I don't know of any that segment on different things. Sounds like a good area to explore. Melee is much less explored than 1-v-1 at this point. --David Alves
I'm talking about mode changes in melee affecting enemy movement. I have not yet started coding a bot, need to learn some Java first, so I can't try out ideas when I think of them. -- RobocoderDan (...Soon)
Well in most melee bots they dont particularly care about an individual bots movement unless they are shooting at it. Usually enemy movement is most effected by how close you are to it rather than how you get there, and so if one of your modes aims to be much closer to the bot (eg a ramming mode) then it may be useful to see how the bot reacts (possibly moving directly away from you and being easier to hit). The problem with much more detail is that it would require more frequent scans, which isnt always tangible in melee. -- Jokester
My GF gun is having problems (like it can't hit Sitting duck at all), but I don't know what they are. Could someone REALLY GOOD with Java figure out my error? I'm still trying to de-bug it, but any help would be great. See at at UbaGfSource please. --Bayen
double bearingrange =
Math.abs((maxbearing-getRadarHeadingRadians()) * 2);
IIRC, you get your scan event at the end of the turn, so your radar has already swept passed SittingDuck. Thus, getRadarHeadingRadians() is not a good very good measure of opponent's absolute bearing, unless you have a very narrow radar arc. Try
double bearingrange =
Math.abs((Utils.normalRelativeAngle(maxbearing - absoluteBearing)) * 2);
instead. This should be more accurate. -- Dummy
Say you know that your bullet missed your target, and you have your bullet stored, how would you determine the guessfactor that the enemy is now on?
double maxAngle; //Stored from the last fire.
for(int i=0;i < bullets.size();i++)
{
b = (Bullet) bullets.elementAt(i);
//Okay our bullet missed our target, but what factor is the bot at then?
if(Utils.dist(getX(),getY(),b.getX(),b.getY()) >= e.getDistance())
{
factor = //What do I put here to determine the guessfactor
}
}
-- Chase-san
Well, the first thing you need to know is the maximum escape angle. That is to say, what is the maximum angle they could reach, before your bullet hit them. On a field with no walls, this is Math.asin(8/bulletSpeed). So, let's create s utility function that gives this value.
public double getMaxEscapeAngle(double bulletPower){
double bulletSpeed = 20.0 - 3.0 * bulletPower;
return Math.asin(8.0 / bulletSpeed);
}
You'll also need a function for finding the angle from one point to another.
public double absoluteAngle(Point2D.Double origin, Point2D.Double destination){
return Math.atan2(destination.x - origin.x, destination.y - origin.y);
}
So let's say you're shooting at someone. If the current angle from you to them is x and they are moving clockwise around you, then GF1 is x + getMaxEscapeAngle(yourBulletPower) and GF-1 is x - getMaxEscapeAngle(yourBulletPower). If they are traveling counterclockwise around you, those values are reversed. (We define GF1 as as "The maximum angle that they could reach if they keep traveling in the same direction", so the direction that they are traveling affects which way GF1 goes) So the easiest way to track this is with what's called a Wave, which is just an object that records the position of the shooter and the bullet power. Each turn, you update the distance that this wave has traveled by adding the bullet velocity. When the distance traveled by the wave is greater than the distance from the wave's origin (the shooter's position) to the target's current position, the wave has "hit". Now you need to record the GuessFactor that the wave hit at. So, you take the current angle from the shooter to target (use the absoluteAngle function I gave if you don't already have one) and subtract the head-on angle 'at the time the wave was fired'. This gives you the angular difference. Now you divide that value by the maximum angle possible (getMaxEscapeAngle) to get the GuessFactor that he was at, between 1 and -1. Now you would usually put this value into "bins", so using 31 bins as an example (from 0 = GF-1 to 30 = GF1) you'd do something like int bin = Math.round(guessFactor * 15 + 15)
So, here's what the whole thing looks like when you put it all together. This code is from YinYang, so it's a little hard to read.
if ((distanceTraveled += speed) >
shootersPositionAtFireTime.distance(targetsCurrentPosition)) {
int solutionBin = (int)((Utils.normalRelativeAngle(
absoluteAngle(origin, target) - headonAngleAtFireTime))
/ (targetDirection * getMaxEscapeAngle(bulletPowerForThisWave)
/ MIDDLE_GUESSFACTOR)) + MIDDLE_GUESSFACTOR;
//... wave has hit, so update our stats here...
}
Apologies in advance if there is a problem with any of the functions I've typed in, I didn't have time to compile them, but they look right. =) Let me know if you have any questions. --David Alves
(Edit Conflict, but David's response is probably better :P) Knowing whether or not your bullet missed your target is more of a VirtualGuns matter. Anyway, if you record the "direct angle to enemy" on your wave, then once your wave has passed the enemy, the GuessFactor to record for that wave would be: (absoluteBearing(myLocation, enemyLocation) - direct_angle_at_wave_fire_wime / maxEscapeAngleForThisWave) * direction of enemy at fire time. If they were moving at a right angle to you at fire time at full speed, and continued moving in that direction, that would be GF = 1; if they instantly reversed direction and moved at full speed the other way, that would be -1. -- Voidious
Erm, okay just a tad more confused now. I understand the mathmatics involved now, however not how to impliment. Such as I store the absoluteBearing in the wave when my bot fires then once that wave reaches the enemy(and hits?) I take the current absolute absoluteBearing and subtract the waves absoluteBearing then divide those by the maxEscapeAngle? gfactor = (absBearing - w.absBearing) / w.maxAngle; Okay I get all that (I think), but what are these bins and exactly how are they used? e.g. how do I put into them and how to I get stuff from them to use in the GuessFactorTargeting?
I'm trying to understand exactly how this is suppose to work, but its not going so hot. --Chase-san
Wow i'm dense, the anwser to the whole bin thing came to me while I was starting to doze off in my chair after working at hte problem for a few hours. A simple array, 31 slots, with 0 being -1 and 31 being 1. each one of them refers to a section of the GF inbetween, e.g. the more you ahve the more precise it is but the less likely the values will add up correctly and get a relable GF. So you just pile the ones that hit in their respective part of the array then you fire at that GF. If it misses you add the GF that the bot was at when you missed to the bin and pile it on from there. In a one on one match this data will add up and make a very reliable blasting pattern. So am I right? -- Chase-san
Indeed. In fact your summary is better than most. We should use it. -- Voidious 03:46, 13 November 2007 (UTC)
Nah, its just what everyone else said all globbed togeather --Chase-san
Okay, I have been testing a few different methods of storing and retrieving data to and from the bins in a traditional gf gun. I have noticed a difference between many different styles amoung the bots. Mostly it has to do with having or not having the Maximum Escape Angle.
Slightly paraphrased versions of those used in the respective bots. GF_ZERO = bin at which gf zero occurs GF_ONE = bin at which gf one occurs bearingOffset = difference in bearing when wave reaches enemy Cyanide uses a escapeless method: int index = (int)Math.round((1+bearingOffset/Direction)*GF_ZERO); Where as GresSuffurd uses a MaxEscape method: guessFactor = Math.max(-1, Math.min(1, bearingOffset / maxEscapeAngle)) * direction; index = (int)Math.round( GF_ZERO * ( guessFactor + 1.0)); I myself also use a MaxEscape method, as follows: guessFactor = bearingOffset / maxEscapeAngle * direction; index = (int)limit(0, (getFactor(targetLocation) * GF_ZERO) + GF_ZERO, GF_ONE-1);
So all i'm asking, is what is the fundamental and targeting differences between these implimentations? Both as viable as thier are bots using both methods rather high up on the charts. -- Chase-san
Actually, Cyanide uses a max escape angle, it's just a little obfuscated.
enemyDirection = binaryDirection * Math.asin(8/bulletSpeed);
He then sets the wave's .escapeEnvelope to that variable and it's used when determining the GF. It's just a coding style preference here - you really can't do GuessFactorTargeting without a max escape angle.
-- Voidious
- [View source↑]
- [History↑]
