Melee Strategy

From Robowiki
(Redirected from MeleeStrategy)
Jump to navigation Jump to search
This article may require cleanup to meet RoboWiki's quality standards.
Please improve this article if you can.

Building a successful melee bot can be much harder than creating an effective 1-vs-1 bot. This page outlines some of the strategies you can use to make your melee bot stronger.

The timeline of a melee battle

10 bots on the field

The bots in bad starting positions die right away. Hope you're not one of them.

If there is someone close to you, it had better die before you. Most good bots will turn and move away from other bots or from the center in general right away, so if you have some kind of targeting that shoots at the path of least resistance, this is where you'll notice it, but a semi-linear targeting will probably work for that first few seconds in the match.

6-7 bots on the field

Fighting over corners and trying not to get pushed into crossfires.

You'll be happier if you're targeting one bot and no bot is targeting you. You should be able to hit most of the bots you'd reasonably want to target at this point, and you won't be successful with a hit rate of less than maybe 25-30% at this point.

3-4 bots on field

Everyone stays in their corners and snipes at each other. Try to get the other guys to target each other instead of you.

This is where you'll be the happiest with solid targeting. Here's why: when you're down to 4 bots, as David pointed out, there's a really good chance that you're all in corners. If the next bot who dies is the one across from you (the one you probably weren't targeting), you are probably next, because you're the most obvious target for both of the remaining enemies.

Duel

The 1-vs-1 fight at the end of a melee battle.

It should be obvious why targeting is important here. It's your gun against their movement.

What it means

In reality, these stages aren't something you normally put into code when making a melee bot, they're observations about what a battle will look like between several good melee bots. The fact that these stages are defined in terms of position and movement says a lot about what is important in melee. The reason these stages are important to understand is really so that you can analyze your melee bot's performance if you put it in a battle with other bots of a similar level.

How to put together a good melee bot

As with any kind of new robot, the main thing that's useful when making a new melee robot is to have some kind of idea you want to try. It can be original or not, it can be a spin-off of what other people have done, or it could just be in general that you want to try making a melee bot.

Nowadays, most people have some experience with 1-on-1 bots before they go too deep into melee. In reality, melee is just like 1-on-1, except that there's something that supersedes 1-on-1 movement (which is moving in such a way as to not be hit often) - moving in such a way that you aren't being shot at!

The theory of melee movement

You'll dodge every bullet if no one is firing at you, and so most melee movement is centered in one way or another around not getting attacked. This is what makes melee movement so dang interesting. If it is inevitable that you will be targeted, then you can start worrying about just not being hit.

In discussions with (melee legend) ABC, I remember summarizing these two movement goals combine into the balance between "being in the right place" (not being shot at) and "moving in the right direction" (not being hit). Since you can only move in one direction, sometimes you have to choose to either mov toward the right place or move in the right direction. Since different bots prioritize these differently, some will be extremely predictable and easy to hit, but it doesn't matter until someone shoots at them. In fact, in theory, as long as no one is shooting at you, the only reason you really have to keep moving is to make sure they keep not shooting at you (until they're shooting at you again, which would be nice to be able to magically determine).

Common ways of implementing melee movement

There are lots of ways people accomplish the goals of not being targeted and not being hit. Some common examples:

In AI I've heard this generalized as using "repulsive fields". You could also combine it with attractive fields if you want, but there's rarely a real reason (same goes for tangential fields, for which there is a reason, but the actual implementation is hard to really get right in a pure anti-gravity force-vector sort of way). The basis of it is just like in physics - you define a set of points that have an antigravitational (repulsive) force on them, you add all the force vectors together, and you let them "push" you in whatever direction they push you in. Normally other bots and walls are assigned forces. Sometimes the center of the field has a generic force as well, or even the guessed positions of bullets. A classic example of AntiGravityMovement is TheArtOfWar. A simpler implementation is Graviton, but simpler in this case doesn't necessarily mean more clear (same goes for Escape, which is a more convoluted bot based on Graviton). Hanji's page has a very stereotypical, very clear implementation of antigravity which might be helpful if you are trying to get into it. The biggest challenge in getting AntiGravityMovement right is weighting all the forces effectively, especially when there are more or fewer points on the field (maybe the walls have to push harder when there are more bots on the field pushing you toward them?).
In the early days of Robocode, one of the frustrating things about trying to excel in melee was that the bots that seemed to do the best in battle did stupid little patterns in the corners of the battlefield. This came from the general observation that the bots that lasted to be one of the last standing were the ones that got to the corners the fastest. While this isn't really always true, there are probably fewer bots near you in a corner than in the middle, so the technique works - just go to the nearest corner, keep moving, and kill anything that's trying to take your corner from you. I experienced frustration with this movement when I would watch SandboxLump with his stupidly simple movement kill Coriantumr in so many of my tests. Out of my frustration came Lib, the most complex CornerMovement ever put into a NanoBot (I assume that's still true, it at least was at the time). Traditionally, using CornerMovement will make you specialized as a melee bot, because it tends to work better against the best melee bots than against mediocre ones.
Alot of quite good nano melee bots just dance around in a star shape, or triangle or square. Some of these go in a straight line for awhile first (until they hit a wall or something), so it's closer to a type of corner movement than anything. The virtue of this movement is that you don't move around too much, so you are less likely to have new bots start targeting you because you move into their range, and it does well against the horde of melee nanos with something related to linear or circular targeting (because you change directions relatively often). Gem, Infinity, KomoriNinja and Trigon are good examples of this movement.
MinimumRiskMovement
On the surface, this looks like just an implementation of AntiGravityMovement, and maybe the difference is just nitpicky semantics to some, but I think the way it is implemented is different enough that the only similarity is really the basic fundamentals of melee movement. It also seems much more versatile than AntiGravityMovement and is also less likely to converge at some "happy" local minimum. As I am biased, I think that the best, clearest implementation of MinimumRiskMovement is in Coriantumr and Shiz, although HawkOnFire's implementation is also available now and it is just as effective and maybe slightly more basic. There are two basic parts to MinimumRiskMovement:
  • A Risk Function - Determines how good or bad a point is to go to.
  • A Point-generating function - generates candidates to try in the risk function.
Then you just go to the candidate point with the lowest risk (or highest benefit, although MaximumBenefitMovement probably has more place in Teams). Randomness can assist in either function just as effectively. Also, as an interesting tweak, you need to decide to look for a point to go to constantly rather than only when you reach the last point you were going to. Both strategies have merits - you might get into a rut if you keep changing your mind on points, but you can also more quickly react to changes in the battlefield.
1-vs-1 Movement
If your bot is good at close combat, you might consider chasing one robot at a time with that movement. Chances are that if you are close to one robot, you're far from others (because who's going to go running towards two other robots?) DoctorBob is very successful in this, and it's also one of the reasons Tracker doesn't do too bad in a battlefield full of sample bots at least.

Things to think about in your movement

Being far away from other bots
This one of the easier things to test for, of course, once bots are so far away, it doesn't matter as much if they get further. That's why using the inverse square of the distance to each robot works so well (the threat approaches zero at some point). This will likely keep you out of the action.
Moving perpendicularly/one-on-one-like to other bots
Especially bots that are close to you.
Don't hit walls or other bots too much
It might be tempting ;-) This is possibly a bigger deal in melee, just because you're going to be close to other bots and to the walls alot more than in one-on-one.
Stay out of the middle
People always say this, but in reality it's ok to be in the middle if the battle is still big and all the other bots are on the outside. However, if you're still in the middle with 4 or 5 bots left, you won't likely last long.
Don't stay in the same place for too long
Just as in 1-on-1, this can be quick death. I don't care how great that spot is, someone will get close enough to it to put you in danger in not too much time.
Battle dynamics change constantly
Be capable of adjusting and changing quickly, and don't try to plan too far into the future.

Guess who will fire at you

Note - This is a little more advanced of a topic in melee movement, and it's a little hard to explain clearly, but it's also not impossibly hard to implement. It's also the main secret of the movement in Coriantumr and Shiz. FloodHT does it as well, but its point-generating function is bad, so it doesn't really matter :-p I'm not sure if anyone has really tried too hard to do this before.

Looking at the list of ways one could pick a target, the one you have the most potential control over is whether you're the closest target for any other bot. If I want to pick which point is the best one to be at, a big part of that is counting for each bot how many other bots are closer to them than me. If 0 or 1 bot is closer to that robot than it is to me, that means it's likely to be aiming at me. Combine that with the possible knowledge that that bot has hit you recently, or that you're shooting at that robot, you have a pretty good guess as to whether that bot is likely to be firing at you if you were (or are) at that point.

There are at least two applications of this information:

  1. You want to be at the point where the fewest robots will target you.
  2. You only have to worry about being hard to hit to the robots that are likely to target you (in other words, the direction you move in to get to a given point only matters relative to bots that are likely to target either that point or your current location).

Little melee tweaking notes

A few things that might just get you up a few spots in the rankings:

Melee radar

For Implementations see: Radar#Melee_radars

What you do with your radar really depends on what your targeting strategy is, and whether or not you want to fire blind (firing blind means you don't fire when you can actually see your enemy, but rather in your general run loop or something). If you just spin your radar constantly, you almost need to fire blind, otherwise your gun won't have time to turn before you fire. However, I find (again, if your gun doesn't depend on a spinning radar, like some melee pattern-matchers do) that firing blind reduces my hit rate by a little. I suggest (particularly if you're using a guess-factor gun in melee) using a melee radar lock, which is a trick I learned from PaulEvans (so it must work!) A melee radar lock is spinning your radar until you're getting close to firing, and then lock on your target as if they were the only bot on the field for a couple ticks until you fire. Plus, if you have a radar lock in your code, you can also use it for one-on-one :-)

Melee firepower

Alot of hitting happens early in a melee match, but by the end you can be pretty well drained of energy. Some people take the survivalistic element of melee to mean they should always fire low-powered bullets. This is only partly true - you will likely start the melee battle close to other bots. So close, in fact, that you are very likely rack up alot of hits (either for or against you) in the first 5 seconds of a match. Don't be shy about firing bullets that are more than powerful enough to finish a bot off if they're really close to you (because you still want to finish them off if they hit you or someone else before your bullet reaches them, and if you're REALLY close, that's likely to happen). I've seen some smaller melee bots (I think Graviton and Troodon were two of them) that even multiply their firepower by getOthers(). I also think that you shouldn't make the mistake of having too "merciful" of firepower in the final stages of the battle (meaning you should be aiming to kill when you're shooting at a low-energy target at any point of the battle).

Picking a target

There are so many heuristics that can be dreamed up for this, but one of the easiest and most effective is to simply target the closest enemy. While this is the best general guideline, it might be beneficial to take a few other things into consideration:

Who has the lowest energy? There are a few reasons you might want to target them:

  • To get the kill bonus.
  • If they are at least sort of close to you, and they are in a "safer" part of the battlefield, you might be able to take their place if they die :-) If your movement allows you to get closer to robots with lower energy, you might be more likely to do this.
  • So you can outsurvive them! You get something like 100 points for every bot you outlast in a round. You'd hate to see a robot that had 5 energy when you had 60 end up dying after you because no one shot at it when you could have.
  • If you have a good risk function your bot will attack a low energy bot in case it has a good position on the field so that your bot will get there (important if there are around 4 to 6 bots left).

Who keeps shooting at you? There are two ways to avoid getting shot at - get them to shoot at someone else, or take them out. Yes, killing someone can help you conserve energy!

Try not to thrash between enemies too much, especially when you're ready to fire. If you're only using distance to pick a target, try only switching targets if the new target is 100 pixels closer, or 10% closer, or something. If you have some other kind of "score" technique to picking a target, something similar could be used. Thrashing can cost you, especially early in a battle. Another good technique is to not switch targets if your gun is almost cool (unless your target is dead, of course).

There's a theory that the reason you pick the robot closest to you is because you're more likely to hit them. If you're more likely to hit someone else, maybe you should shoot at them. Of course, don't forget the advantages of having only low-energy (or dead!) bots close to you.

Enemy management

If you're trying to convert a 1-on-1 bot to a melee bot, you'll find out quickly that all the little assumptions you used to make when you coded your 1-on-1 bot are wrong. It can be a big challenge to effectively store volatile information about your enemy (like current position, heading, velocity, etc) as well as persistent information about your enemy (like targeting information). One of the big challenges is how to specify that a given enemy is dead. I stumbled on a great way to do this when I was working on Coriantumr, which was to have an volatile object (class EnemyInfo) in a Map that has position, heading, velocity, and all the obvious stuff in it, as well as a list of waves (note - all these things should go away between rounds). This map doesn't have to be static (although it probably is for codesize reasons), because it's recreated every round. In onScannedRobot, I check to see if the robot I'm scanning is in the map, and if it isn't, I put it in there. Then I get the EnemyInfo object and operate on it all over onScannedRobot. onRobotDeath removes that robot's object from the map if they exist (so the robot no longer exists when I don't care about it anymore). Meanwhile, I have a different map which maps the name to the guess factor stats which is static and isn't reinitialized between rounds.

Targeting algorithms in melee

HeadOnTargeting in melee

Always a good place to start. On a related note, I've heard of melee targeting which targets the rolling average of the robot's position, since it is common for a robot to stay near the same place for awhile. Not sure how this really compares in general to just firing right at the target.

LinearTargeting/CircularTargeting and variants

You can go far with some kind of percent-of-linear targeting, or using circular targeting in melee. It has been observed that if you are close to an enemy, you have really good odds firing with linear targeting, and if they're further away (say moving around in a corner or something), you have pretty good odds with head-on or somewhere near that. Take a look at Infinity for a really elegant solution to this observation. Another thing that might work well is velocity-averaging. Some more observations could certainly be collected to create a generally good melee gun that is simple to understand and code and is *very* resiliant to missed scans.

PatternMatching in melee

Be careful to make your targeting algorithm resistant to not having constant scans. If you spin your radar, you will get a scan on a given robot every 8 ticks on average. Occasionally (ok, actually somewhat often), you'll scan a bot two ticks in a row, and that should throw your targeting off. Often, you'll scan the robot again after 7 or 9 ticks. If your targeting algorithm absolutely requires scans every 8 ticks, you'll have to make it realize that the world isn't perfect. In my opinion, pattern-matching has been slowly becoming obselete in one-on-one in its purest form (note that there are ways of making it last in the realm of random movement), but is still definitely alive and kicking in the melee world, if only because melee isn't as well developed.

GuessFactorTargeting in melee

FloodMini from the start has had a wave implementation that was really good about missed scans, mainly because its radar was far from perfect. The same idea is in Coriantumr's gun, which is to interpolate missed scans linearly and check at each interpolated position/time if the wave hits. This is probably the trickies part, along with how to store the waves (see the Enemy Management section above). In general in melee, you're pretty safe firing a wave on every scan of a robot, not just when you fire at them, but realize that robots might be moving different relatively to you if you're not shooting at them (or likely to shoot at them anwyays). Segmenting on distance and possibly battle size can help compensate for this problem, as well as segmenting on lateral direction (are they moving roughly perpendicular to you, toward you, or away from you?) Acceleration segmentation can be a little harder to do in melee, since you aren't getting consecutive scans for all of your waves, but I've observed that if the sign of the enemy's velocity is opposite of the previous scan, they're probably accelerating (unless they are already at velocity 8).

Also, I recommend using a melee radar lock for GuessFactorTargeting (see Melee Radar above).

For any of these techniques, you should consider making sure you don't fire off the battlefield at a or in a direction that can't possibly be reached by your target. This sounds obvious, but I don't know how many times I've seen a robot aiming at another robot that was moving toward a wall, and the shooting robot just shot right into the wall, which is a complete waste of a shot. This is one of the improvements I made in Coriantumr from 1.0 to 1.1.

Evaluating your Melee bot

Before I get too far into this, I want to emphasize that the number one way of figuring out where you can improve is by critically watching the battles. The first thing to do is to create a test bed. Find a bunch of bots that are at least in the same neighborhood as you as far as ability, some better and some worse. I also make a text file where I log battles and what tweaks I made between them. Of course, don't give too much credit to the scores, since they often vary wildly. If you start to beat your test bed consistently, upgrade it.

It is a good idea to keep track of how long you're staying alive. I like to add this code into my bot for testing: 

//global declarations:
static int[] finishes;
.
.
.
//beginning of run():
if (finishes == null)
	finishes = new int[getOthers()+1];
.
.
.
//somewhere:
public void onWin(WinEvent e){onDeath(null);}
public void onDeath(DeathEvent e)
{
	finishes[getOthers()]++;
	for (int i=0; i<finishes.length; i++)
		out.print(finishes[i] + " ");
	out.println();
}

This will print out a list of wins, 2nd places, 3rd places, etc. at the end of each match. Obviously, you want to maximize the wins ;-) Of course, what you want to do first is make sure this gives a regular, smooth distribution over time. You can analyze where some of your weaknesses (relative to the stages to a melee battle at the top) by where the highest numbers are. For instance:

  • If you have alot of last and next-to-last finishes, maybe you don't do well at close quarters or get out of tough starting situations very well. Try to get to the best place you can and get other bots to target each other instead of you.
  • If you are dying alot in a part of the battle where there are still alot of bots, but it's not the beginning really, you might just need to be more random/harder to hit. In a standard 10-bot battle, this is probably about 6th-8th place finishes.
  • If you tend to have hugely more 5th and 6th places than 3rd and 4th, it could be you don't get out of the middle soon enough.
  • If you have way more 3rd places than 4th or 2nd, it probably means that you're not good at getting rid of one of the guys closer to you at the end of a battle.
  • If you have way more 2nd places than 1st, it could be that you have lower 1-on-1 strength than the other bots. On the other hand, it could be that you're barely surviving before that. Watch a few battles to figure it out. I see HawkOnFire finishing off Shadow at the end quite a bit simply because it has 4 times as much energy when they get down to 1-on-1.

Some tips:

  • Just like in 1-on-1, every tweak counts, even the tiniest change to your power management can be catastrophic or miraculous.
  • Make up other techniques to help you test the parts of a battle that you're not as good at. For instance:
    • If you do well getting into the last 4, but have trouble making into the last 3, you could try tweaking in 4-bot battles, or you could try tweaking in 10-bot battles on a 2000x2000 battlefield (which might have a similar strategic effect). This can also expose what your bot does if it can't see anyone (which only rarely happens on a 1000x1000 battlefield, probably only when it gets down to 1-on-1).
    • If you have an abnormal amount of last place finishes, you could try testing on a point-blank melee (10 bots on 400x400? That's just like doing the start of a battle for the whole battle). If you try that with today's top melee bots, you'll find that Coriantumr and bots with iterations of his movement are the best at this, hands down (let me know if you can find anyone who can beat it). Again, this also might expose some of the other problems you have with your movement that make your bot too specialized (or just less versatile).
    • If it's that stage between the beginning and half way that gets you down, the point-blank melee thing can also help. Try even upping the stakes and see how you perform at close range (say 20 bots on a 400x400 battlefield. This can be pretty funny to watch).
  • You might want to delete saved data if you test with bots that save data to disk (SandboxDT or SandboxLump, for instance).
  • If you're looking at your RoboRumble problem bots, realize that some of them might be a problem bot for you because they do better against lots of other bots than you do, not because they're a direct problem for you. Also, PBI's are deceptively low in melee, because there are 8 other bots in every battle who affect the performance for each of you.
  • WATCH YOUR BOT. Get a feeling for your bot's behavior. Worked fine for Aleph.
  • Make a battle with 10 of your bot. If the scores are somewhat similar, that's good. If the scores are hugely different, luck might play a factor in your bot's score. You might want to tweak a little bit in that case.
Retrieved from "http://robowiki.net/w/index.php?title=Melee_Strategy&oldid=37396"