[Home]TadsEmails

Robo Home | Changes | Preferences | AllPages

NOTE: SOME EMAILS ARE SHORTENED TO SAVE SPACE. I'VE LEFT ALL THE THEORY IN AND JUST TRIMMED SOME OF THE GREETINGS AND SUCH. --David Alves

From: Tad Boniecki Sent: Monday, November 18, 2002 2:11 PM To: David Alves Subject: quick question

Hi David,

Seeing you are a Robocode guru I thought I'd ask you a quick question.

My bot keeps getting missed turn events.

Is there a way to debug this?

I'm pretty sure I'm always doing something so it looks like I might be doing too much per tick. How do I find out?

regards

Tad


From: David Alves Sent: Tuesday, 19 November 2002 9:49 AM To: Tad Boniecki Subject: RE: quick question

All bots get skipped turn events. The problem is that the timer which the game uses is only accurate to about 15 milliseconds, so it tends to think your bot took either 0 milliseconds or 15 milliseconds for your turn. When it decides you took 15, you skip a turn. Crappy, but there's no way around it. I doubt you're doing to much per tick. Some of the test versions of Duelist did over 20 times the computation that Duelist 0.1.6 currently does, and they skipped the exact same percentage of turns - aroung .5%

If it really is a problem, one good idea is to cut down on the amount of code you have in your event handlers. If you skip a turn on those you can miss out on events. What I do is add the events to an event queue, then process them later. that way if I skip a turn I don't lose events - they're all still in the queue. You can take a look at SquigBot's source code if you want to see another bot that does this.

I don't really know if it's necessary though. I think people are too worried about having their bot do everything perfectly, when really you can have a lot error and still come out ok if your ideas are sound. For example, when I first wrote Duelist, I got it to beat SandboxLump *before* I realized that I'd forgotten to use setAdjustGunForRobotTurn(true) and setAdjustRadarForGunTurn(true). I kept wondering why my radar was going crazy... :-P

Hope to see a bot by you soon!

David Alves


From: Tad Boniecki Sent: Monday, November 18, 2002 3:17 PM To: 'David Alves' Subject: RE: quick question

Hi David,

One of the things I find frustrating is that after fixing wall avoidance and getting the scanning to work 100% better, plus making the code more logical (I used to spend all the time in OnScannedRobot() ) my bot is now much weaker than it was before. Hopefully a proper go at getting targeting to work will fix this.

I got the old version to be much stronger by setting bullet power to always be 3 and calculating the targeting using linear targeting with a fudge factor (pretending the bullet was much faster than 11).

I spent a lot of effort until I could hit the Walls bot all the time, except when he hit the corners. Then it suddenly dawned on me that no real bot moves in a straight line for long. Live and learn.

It seems to me that linear targeting by itself is no better than just shooting at the other bot's current position plus a fudge factor. Would you agree?

Does your bot scan the opponent every tick? Mine currently scans him 76% of the time. Is that good enough?

thanks again

Tad



Original Message
From: David Alves Sent: Tuesday, 19 November 2002 10:59 AM To: Tad Boniecki Subject: RE: quick question

Don't worry too much about targetting. Movement is the main thing vs. the really good bots. Since their movement is so hard to predict, any bullet that gets in the right general area has the same chance as any other. My bot does about as well vs. SandboxDT when I always fire straight at him as when I use my targetting system.

My targetting is similar to the SandboxLump / SandboxDT method. Here's how it works.

 * 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.
 * Calculate how far backward the other bot could go if it suddenly went top
speed backwards for as long as it would take my bullet to reach the other bot. Call this Point B.

Now take a guess between -1 and 1 at where the bot is going to be. -1 would mean going straight back and ending up at B, 1 means going straight forward and ending up at A. 0 means sitting still. I just keep track of how well different numbers work and fire with the best one. You can find a better description (with code!) at http://www.sandbox.dial.pipex.com/robocode/. However notice that the algorithm that Lump uses (the bit where he says he uses the bot's current accelleration) is a bad idea, because it won't hit bots that sit still for a long time and then suddenly hit the gas. He fixed this when he came out with DT. (And I fixed it in Duelist! :-D) However, pretty much any targeting method will work well enough as long as it isn't simple linear or circular targeting, because some bots (like Fermat) will guess where you would fire if you used circular and dodge accordingly. Good bots for testing targeting are:

time.

Also try the nano bots - they're almost all open source and have some cool ideas.

As for radar, yeah I scan the opponent every tick in duels. Turn on visible scan arcs and you'll see Duelist goes back and forth in a tiny arc across the opponent. Here's my radar code. You're free to use it but you'll have to adapt quite a bit. However it should all be legible - I like big fat function names that tell me EXACTLY what the function does. :-P

	double scan() {
		double radarOffset;
		Enemy target = environment.getTarget();

		double scanArcWidth? = .05;

		if (me.getTime() - target.getLastScannedTime?() > 8){ //Scan? out of date, sweep radar in full circle
			return QUARTERCIRCLE;
		}

		//Find? angle to move radar so that it points directly at the enemy
		radarOffset = angularDifferenceBetween?(me.getRadarHeading?(),me.getAbsoluteAngleTo?(environment.getTarget()));

		//Move? radar so it sweeps a little past him.
		if (radarOffset < 0)
			radarOffset -= scanArcWidth?;
		else
			radarOffset += scanArcWidth?;

		return radarOffset;
	}

In case it isn't clear, here's what the variables and functions are:

 * radarOffset: How much we should turn the radar on this turn.
 * scanArcWidth?: How wide the scan ard should be. I use a narrow one because I think it looks cooler but it makes no difference in 1-v-1.
 * Enemy: a class used to represent the enemy. "target" is an instance of enemy with our current target.
 * QUARTERCIRCLE: a constant representing a quarter of a circle.
 * angularDifferenceBetween?(double a, double b): the shortest way to turn from angle "a" to angle "b"
 * getAbsoluteAngleTo?(Enemy e): The angle to our enemy, NOT relative to our current heading. Note that when you do ScannedRobotEvent.getBearing() the number is relative to your current heading, so you need to adjust for this...

If you've looked at SnippetBot by Alisdair Owens, this should look familiar, except that he uses radians and I use degrees.

Hope that helps!

David Alves


Hi David,

You are a generous soul, giving away your secrets like this. I guess you can afford to, being at the top.

I was disappointed by your remarks about targeting, though I too believe one can make movement so random that predictive targeting will have little chance. Essentially you are saying that using a fudge factor is the way to go.

thanks

Tad


From: Tad Boniecki Sent: Sun 12/8/2002 4:55 PM To: David Alves Subject: RE: duel ladder

Hi David,

My own bot is coming along, but I think it will take me another month before it is competitive. I limit my robocode addiction to 3 days per week. This actually works quite well because I use the off days to reflect on ideas rather than fiddling with code.

Thanks a lot for passing on the SandboxLump targeting write up. Not only is it very interesting but it looks like it should be highly effective. I have written the code to implement it, but it isn't debugged yet. I did it my own way, in probably 10 times as many lines and half the elegance, but at least I understand my own lumbering code.

It occurred to me that to minimise the effectiveness of SandboxLump targeting one should make one's bot have a "flat" movement profile, ie give roughly the same number of hits for each virtual bullet, or at least make sure that the two highest peaks in the targeting profile are on opposite sides, ie one is forwards movement, the other backwards.

The other way to cope might be to change movement patterns faster than the retention number used for the rolling average.

You have probably thought of both these ideas but maybe not.

The mental block I have with movement is that it seems to me the bot should essentially move in one dimension ie in a circle around the opponent. This makes sense from the point of view of parallax maximisation but it makes movement pretty predictable ie left or right only. Am I missing something?

How do you cope with "bifurcation creep"? I mean the way you keep finding that you have to deal with negative and positive velocity, left and right, back and forward etc.

regards

Tad


I really do think the Eternal Rumble is better, though I wish that he would run 100 round battles since bots like Duelist don't store data on disk and tend to do poorly for the first few rounds. The main reason I think it's better is that it's more up-to-date and the ability to see a record of all the rounds a bot has been in.

I have no idea why BlotBot is missing.

Bots with fewer battles are chosen so that their total number of battles will go up faster, the accuracy of the rating is highly dependent on the number of battles. Bots with fewer battles probably got added more recently.

As for the flat movement profile... yup. That's what you have to do. :-)

I've thought of changing movement patterns, but I like the idea of having one algorithm for all situations. DuelistMiniMelee, for example, uses a single movement algorithm all the time, unlike SandboxMiniMelee, which has separate ones for corner movement, 1v1, and general melee movement. By factoring in the relative importance of staying out of crossfires, staying away from enemies, staying perpendicular to any enemies that are probably firing at my bot, and preventing bots that aren't probably targeting me from aquiring me as a target, I ended up coming with an algorithm that does well in all scenarios. In fact, it uses random aim... and still is the #8 1-v-1 bot, beating out Fermat, TheArtOfWar, JollyNinja, etc. :-)

As for staying perpendicular making your movement predictable, well, yes. It is a good bet that the other bot will stay perpendicular. But knowing this doesn't help them hit you. Essentially, bullets are travelling outward from a point, the other bot's location. Any movement towards or away from that point doesn't help you avoid bullets. No matter what distance you are from the other bot, your bot is occupying a portion of the arc of possible locations. No matter what your next position is, it will be somewhere in that arc. Ok, I'm starting to confuse myself, so I'm attaching a pic. Movement towards or away from your target means you're still in the same tiny arc, so most of his bullets will hit. You want to move perpendicular so that the arc of bullets that might hit you is as wide as possible. Predicting that your bot will move perpendicular won't help anyone hit you - they have to guess where in that arc to fire at.

Why am I not #1? Well, SandboxDT is better than Duelist 0.1.6, no question. The only thing that annoys me about the rankings as they are is that I'm not #2... Duelist beats Shera quite handily in 100 round battles. I can only guess that the reason Shera is higher ranked is because it takes Duelist a few rounds to adapt its aiming, since it doesn't store any data. If the rounds were run 25 or 50 at a time, I suspect Duelist would be significantly higher.

I'm not really sure what you mean by bifurcation creep... All of my movement functions just have a formula for determining how good a given point is , then I just move to the best one out of a set of test points. Here's the code to drive to a point:

double dir = -1; // direction of travel, -1 = backwards

double ang = normalizeRelativeAngle(absBearing(myX, myY, destinationX, destinationY) - getHeadingRadians()); //angle to turn if (ang > Math.PI / 2) {

	ang -= Math.PI;
} else if (ang < - Math.PI / 2) {
	ang += Math.PI;
} else {
	dir = 1;
}

setTurnRightRadians?(ang); setAhead(dir * getRange(myX, myY, destinationX, destinationY));

absBearing, getRange and normalizeRelativeAngle are pretty standard functions that everyones uses. They are:

double absBearing( double x1,double y1, double x2,double y2 ) {

	return Math.atan2(x2-x1,y2-y1);
}

double getRange( double x1,double y1, double x2,double y2 ) {

	return Point2D.Double.distance(x1, y1, x2, y2);
}

double normalizeRelativeAngle(double ang) {

	return (ang + (9 * Math.PI)) % (2 * Math.PI) - Math.PI;
}

If you ever become interested in writing minibots (bots restricted to a certain size), the versions I've given you are the smallest possible ones. :-)

(EDITOR'S NOTE: Pretty darn sure of myself, wasn't I? Actually the code to drive to a given (x,y) point has been trimmed to less than 1/2 the size of the code here... check out Troodon or DuelistMicroMelee for the new version.)

David Alves


And there you have it! Of course, now the roles are reversed - now he's the one with the super-powered bot while I'm watching all mine get whooped on. :-P

--David Alves

I can't let that stand. DuelistMicro is currently #3. I think I am lucky to get to #14 as my bot really does not perform well in 10 round battles. It needs about 1,000 rounds to come into its own. I wish there were a league with longer battles. Any volunteers? -- Tad


What can I say, this is an overwhelming amount of knowledge you share with us. Thanks and thanks again! Now we should probably move this information around to their respective sections on this wiki. Anyone with a spare minute can maybe help copy a topic or two? We can leave this page as it is since it's kinda nice with this correspondence form of things as well. Besides it's easy to print as well. -- PEZ

Robo Home | Changes | Preferences | AllPages
Edit text of this page | View other revisions
Last edited May 19, 2005 19:24 EST by Pogsquog (diff)
Search: