|
Though I was not around for this, I have read about the timeframe that Cynical was released, which had a very hard to hit (at the time) movement style, and didn't bother to fire. He'd win battles through attrition, presumably prompting the introduction of points awarded for bullet damage to discourage the mockery. So the present assumption is that you need to actively attempt to damage your opponents to compete effectively. I am now wondering if that applies in Melee. In the early stages of the battle you definitely need to lay out as much damage as you can, because your opponents have less room to move and even misses are still likely to hit someone else. But later on, as the Last Man Standing bonus of 90 points is in sight, it may be time to be very conservative with your shots. Just a thought. -- Martin |
David Alves's Stages to a melee battle (from the Melee page):
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 very good melee bots. The fact that these stages are defined in terms of position and movement says alot about what is important in melee, but let me add my feelings about the importance of targeting in these stages:
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 (say half better and half worse, but all as close in ability as possible),
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 supercedes 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!
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).
There are lots of ways people accomplish the goals of not being targeted and not being hit. Some common examples:
AntiGravityMovement - 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?).
CornerMovement - 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.
Moving in a small, simple pattern (for lack of a better name for it) - 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:
OneOnOne 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.
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:
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.
![[Home]](/images/RoboWiki.png)
//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:
Megathanks for making this page Kawigi! Good reading. I'm not sure I agree I wouldn't put the different stages into code. Some of the ChironexFleckeri versions did that even. CF also segments it's movement and targeting stats on this. Even if the latest version only separates the melee stages from the duel one. But that's mostly a codesize issue. It seems CF is using MinimumRiskMovement as you describe it. Though I think that name is too general. I would say WaveSurfing is minimum-risk too. -- PEZ
Indeed very good reading. A real melee-movement (read: AntiGravityMovement or MinimumRiskMovement) goes up to #3 on my prioritylist, a one-on-one PM-gun just has to wait a little longer. -- GrubbmGait
I definitely think that WaveSurfing is a simulation-involved form of MinimumRiskMovement, in fact, I've even tried (unsuccessfully, but I think I know what my mistakes were) to implement a flattening movement with minimum-risk concepts. As for not coding the different stages, I'm specifically referring to movement - I would encourage targeting based on those phases, because segmentations are all about the observation of different movement patterns in your enemy. Since robots who weren't even coded to care how big the battle is move differently with 4 robots than with 8, it's very reasonable to segment on that. As far as coding it in movement, I think that's dangerous, mostly because it can unnecessarily specialize your bot. I think I remember David Alves saying that he preferred using fluid functions to if statements if he could help it, and this is a good example - if you have a risk function that you want to emphasize some feature more when you have more bots, you can put getOthers() into the function, or if it's something that isn't relative to specific bots, you can make it not scale to getOthers() (what I mean is that if your risk function has a part that involves iterating enemies and a part that doesn't, if you don't multiply the part that doesn't by getOthers(), it will automatically have more bearing with fewer bots on the field, because the total numbers will be smaller). -- Kawigi
I totally understand what David means by fluid functions rather than if statements. I think many of my bots are extremes of that. Aristocles, Pugilist and CassiusClay all have very little of conditionals and work without special cases as much as they can. However, optimal melee behaviour between 10 and 4 bots might not represent a fluid change of state. I say "might" since I have very little experience with this. -- PEZ
I guess that I'm more of the opinion that a fundamentally sound movement implementation will act optimally (albeit differently) in these very different cases, because the goals are primarily the same. Added a few more sections. -- Kawigi
Again thanks! This is a candidate for the "best Robowiki page ever" title. -- PEZ
You're welcome. Added a bit more content (can you tell I'm having trouble focusing on work?). -- Kawigi
Quote: 'Add any other tips that seem to work for you ' End Quote.
What other tips, are there any tips left somewhere. This is the most informative page I have seen sofar. Although most information can be found elsewhere scattered on this wiki, this is the best concentration of useful information I've seen. It feels like I have still to write my first melee-bot. You have my vote. -- GrubbmGait
Oh, there are plenty more development tests which can be applied to melee, I'm sure I haven't exhausted them all (or even remembered all of the ones I've used). Also, is there some place where you're voting for best pages? I think if this is one of the best pages, it's because (at least when I started trying to do it) there just is a lack of information about melee here. There's a few people who are really good at it, but not alot of idea-sharing and implementation sharing. In fact, before I released Coriantumr and Shiz, I think Nimrod and TheArtOfWar were the only top-10 melee bots that were even open-source (and I think most people are a little intimidated trying to read TheArtOfWar's code, simply because of it's mass and complexity). So I guess this is a tribute to the black hole and the prying I did to get information out of the top melee guys when I was newer to it. -- Kawigi
A real pleasure to read this page. -- rozu
Indeed. It's not only because melee info was so scarce before. This page is so well written and composed too. You should consider a writer's career Kawigi. =) -- PEZ
Well, I do think I write clearly (and not all of this is easy to explain!), and an extra read over the more complicated parts usually reveals a better way to explain something. While clear writing is a forte, however, conciseness isn't, so if I get to really trying to explain something (example: the old FloodHT hype page), you should expect to read something long, clear, and often full of rambling and rants. I think that both my clarity and verbosity are partly a result of being an educated native English-speaker (in "programming" circles, this isn't critical, but some people do still have trouble expressing themselves effectively in English. That's why we don't have a big clear disertation like this on what "Wave" pattern-matching is - I'm almost positive Iiley has written one in Chinese on his site, though).
Another thing I've sacrificed for the sake of clarity and organization is order - some of you read this all the way through the first time I posted it, and I've added things to it since then, not necessarily at the end. The diff functionality of the wiki helps reduce the disadvantages of this, though :-) At any rate, I think that this page has stablized a bit, and the last set of links I added will be what really makes it more in-depth. -- Kawigi
I don't think there is such a thing as Wave-PM. Unless the mega-failure Resin counts. =) -- PEZ
That's because semantically, you think of any gun for which the shot bearing is calculated from a wave as statistical. Iiley didn't think that way (and I agree with him on this). His gun was very much a pattern matcher (just as much as NanoLauLectrik's gun) - It matched a single pattern. It wasn't a pattern projector - the way it actually calculated the bearing to fire at was unrelated to the pattern, it was the bearing of a wave fired at the point in time of the end of that pattern. -- Kawigi
No, I don't, sementically, think of any gun using waves for shot bearings as statistical. Resin should prove this. And Ali/BumbleBee uses a very Cigaret like gun. Very similar actually. (Though that's a coincident if there ever were one.) It's still statistical. As is Cigaret's. In theory you could take any PM gun and use GFs for projection instead of pattern-replay. It would still be a PM gun. If Cigaret's gun is a PM gun then so are all my Tityus derived guns and FloodMini's too. The only difference is that FloodMini stores the segmented data for much faster access. Look at how the latest version of ChironexFleckeri stores its GF's and you will see a gun that could be tweaked to act exactly like Cigaret's only order of magnitudes faster.All Cigaret is doing is asking "what GF did the enemy end up at last tick that looked like this one?". That's what CFis asking too. FloodMini makes it "ticks" (plural) and uses the most common answer. Where, going from FloodMini to Cigaret, does things turn PM? But hey, remove this babbling! It's now cluttering your excellent melee strategy page. =) -- PEZ
Where, going from FloodMini to Cigaret, does things turn PM? - at the point where it's storing the last 3500 ticks of arbitrary information (plus whatever has been collected this round) and comparing each consecutive group of 72 ticks with the last 72 ticks to find the closest match, it turns into a PM (actually, it looks like he compares every 6th tick back 12 times, probably for performance reasons). Note: Feel free to move this to another, more appropriate page :-) -- Kawigi
I think the important difference between PM and Statist is the sorting. Pure PM sort every pattern to a single unique pattern, and Statist sort all patterns to be a certain number of kind(That's the segments). So in PM, there is not probability or factor, but statist is, PM search the closest match but Statist search the big probability(factor). So in this case, Cigaret's gun are pure PM. FloodMini's are pure statistical. Some combine way search the certain number of closest matchs and then segment it to count the factors was both PM and Statistical(maybe that was how Shadow gun does).
Well now, friends, very excited seen that you are focus into melee, and this is a cool page, Kawigi, great down. Maybe more melee discussing will be added on. The last version of BlestPain i tried to add the Lacrimas 1v1 movement strategy to melee, so BlestPain becamed a melee bot. But it did not good. I's hard to write a good melee movement. But when i saw PEZ and some other robocode friends are try to implement WaveSurfing in melee, i am waiting and see, I am cowered, when i was impelmenting Pear, i plan to implement WaveSurfing melee movement in it, but you know Pear's 1v1 was not enough good yet. Well however, maybe i will have a try.~:] -- iiley
Yeah, I think I knew that BlestPain was trying to do WaveSurfing in melee. It's not a bad thought, really, but it has two downfalls:
I hope the net effect of this page is that more discussion, development and general competition will happen in melee. -- Kawigi
Yup, i don't quite know who's aiming at me in the first place, so i can't think of every one are aiming me, i assume every robot target the closest enemy, then i just surf one bot's bullets. So there is not many dang bullets, but it is not very precision but most robots are targeting ther closest enemy in rumble. However, BlestPain are not real a sufer, it's Lacrimas's dodge movement, so it did not very good. If i want to improve it, i should base on Pear, but Pear's movement can hardly turn to melee, months ago, I'm think of just dodge enemy's bullet(The Highest of Factors) by Anti-Gravity, it must be easy to implemented than sufering(Many bullet may be easy to dodge than many Waves). -- iiley
Early in the development of Ugluk I noticed that he was doing well in melee. His movement was not complicated either.. it was basically going top speed with a slight weave and bouncing of walls at 45 degrees. While he didn't favor corners or avoid the center of the map, he lived quite a while because in order to remain a favorable target his enemies would have to chase him at top speed like a ram bot, which isn't a popular movement style. It also means he would present himself as a target option to other robots as he went on his way, but with infrequent full circle radar sweeps by the enemy Ugluk had a low chance of being chosen as the most favored target at any point. While the movement has been overhauled a few times, I try to give Ugluk an opportunity to shake pursuers in melee while not actively finishing off an opponent. --Martin Alan Pedersen
I was thinking of making a GrudgeBot, a bot that holds a grudge against the first bot it sees in a melee battle and proceeds every round there after to go after that same bot, ignoring all the others (cept for movement of course) till the bot it has a grudge against is gone. I was gonna do this for the sheer evil of it, but at the same time the bot wouldn't be much of a contender, but instead be a bot that drags down all the other bots. (Sorry i'm having one of those mornings where you just wanna make something truely evil) -- Chase-san
How do you make a bot that's shooting at you shoot at another bot (besides moving away from the shooting bot)? --Starrynte
A lot of bots just target the closest bot, so making another bot the closest would be one way. Some bots take energy into account, so shooting at another bot close to it might make it target that one. Really, though, there's only so much you can do... (You could also just try to kill that bot. =))-- Voidious
My latest melee movement is a pretty sound minimum risk implementation. One thing I am observing is that it is pretty weak in the very beginning. If you look at a melee round by how many opponents are left at the time, there is a large portion of it spent with 9 opponents. If your movement can't handle the opening of the round, you are going to get eliminated much more than your share. Right now in testing against the 9 best author's best bots, I am getting more than my share of Last Man Standing, but I am also getting killed first twice as much as the average. I may introduce a new opening movement and then switch after the first person dies. (I've broken it down even further in the past, but with duel style movements.) -- Martin
MeleePatternMatcher doesn't seem to work yet. Any ideas? (post on MeleePatternMatching page) --Starrynte
Right now, Smash is thrashing between enemies a little too much. Does anyone know how to fix? (code is posted at Starrynte/Smash) --Starrynte
There are two good ways to prevent this that I've seen. The first is not to switch targets unless your previous target dies or is at least 10% (for example) more desireable than the current target. In practice, this usually means until someone else is 10% closer to you than your previous target. The other way (which I believe Coriantumr does, but I can't remember for sure) is to realize that it only matters if you thrash too much if you do it right before you were going to fire - so only switch targets if your gun won't cool for another 4 or 5 turns. -- Kawigi
Ok...thnx Kawigi --Starrynte
Though I was not around for this, I have read about the timeframe that Cynical was released, which had a very hard to hit (at the time) movement style, and didn't bother to fire. He'd win battles through attrition, presumably prompting the introduction of points awarded for bullet damage to discourage the mockery. So the present assumption is that you need to actively attempt to damage your opponents to compete effectively. I am now wondering if that applies in Melee. In the early stages of the battle you definitely need to lay out as much damage as you can, because your opponents have less room to move and even misses are still likely to hit someone else. But later on, as the Last Man Standing bonus of 90 points is in sight, it may be time to be very conservative with your shots. Just a thought. -- Martin