Ugluk by Martin Alan Pedersen
Subsections: [/Code Samples]? - /Workshop? - /History? - Chat Logs 1?, 2?
Ugluk is the name of an orc in The Lord of the Rings. He leads Saruman's Uruk-Hai to snatch the halflings and return them to Saruman unspoiled. In the movie he's the one with the bow shooting Boromir and fighting Aragorn, though he dies near Fangorn Forest in the book. I started using the name while playing World of Warcraft, and it seemed a suitable persona for a melee tank. Ugluk is the sum of my Robocode experience. I have no plans to develop any other competitive bots. All of his code is my own, though I certainly read the wiki and discuss concepts freely.
Movement Challenge (wave surfing)
Head to Head (Targeting vs Movement)
Ugluk has a set of proven guns for projection or statistical targeting. Performance statistics are segmented in the same way as bearing offsets, and gun selection is based on the best performing gun under the present situation. Firepower is determined prior to determining targeting, and a virtual wave is fired each round with a firing angle associated with each gun. Segmentation reduces the effectiveness of stop-n-go movement styles.
Ugluk has a selection of movement styles to choose from. The best performing movements are selected through atrittion. Most movements augment their style with repulsive fields for walls and robots. Some do not, including my latest movement style which determines possible destinations in a hexagonal grid and iteratively projects both it's movement and the anticipated trajectories of enemy bullets. I have four tangental 'wave surfing' styles, none of which work especially well. I do not have any techniques implemented for adjusting wave surfing according to actual bullet hits. In melee I try to strike a balance between 'securing a corner and squatting' and 'moving around to avoid being targeted for long'.
Ugluk's scanning has undergone some small revisions, mostly matters of style, but also avoiding some potential skips. The beam is really really narrow and hopefully that will scare my opponents into believing that I know what I'm doing. If the radar does lose its target (most likely due to an opponent's running into something) it will start sweeping again after a few ticks.
There are a few aspects to Ugluk's energy conservation, but the most important is that he won't take a shot in a duel if taking the shot gives the energy advantage to his opponent.
Debugging, Statistics, and Persistence
Debugging is broken down into 'lines', 'debug', and 'exception'. Lines are sent to the console print stream. The rest is written to file due to volume.
Archnemeses / White Whales
My white whale is Freya, but she's somewhere on the horizon now, and I am not actively chasing her. In general Ugluk wants to conquor opponents who will fight back when defeated (i.e. are under active development) so he's targeting the offerings of Loki and GrubbmGrb primarily, and aspires to oust Corbos and wcsv in time. Eventually it would be nice to take out Mue, ABC, and PEZ as well, but I'll talk that talk when Ugluk can back it up.
While I take pride in Ugluk's code being of my own design, some implementations are very close to the illustrations or suggestions of others.
Comments, questions, feedback:
Subsection: [/Chat Log 1]? - [/Chat Log 2]?
After achieving my goals for v1.0, I am now forcing myself to get back on the melee horse. I modified my Grid movement (really it isn't a grid any longer, but several rings of potential positions) to be a minimum risk system. It is good for getting out of the middle and keeping distance from other bots, but one drawback I am observing is that I will often get on a wall between two other bots and start moving back and forth along the wall. I soak up a lot of damage from that. I tried making a few tweaks to my melee radar but now I am back to the original. I've toyed with targeting a bit and guess-factor style targeting just really doesn't do well. I think there are three major factors. The lesser is that your radar has to spin more to collect updates of everyone in the battle, and it will cause you to miss wave collision data. Next is that as the battle field becomes less cluttered your opponent's movement styles change. But the biggest problem is that you've got to learn how 9 opponents move, and there's simply not enough time to learn it. I've had the most success with dead-on targeting. No learning involved. As a test bed I am using bots from the 9 top authors. I can usually place in the top 3. That hasn't translated to dominant ratings in the rumble though. I've got a few more tricks to try though, and I imagine more will come to me. -- Martin
I had the same problem, oscillating along the wall and getting targeted by the two bots in the closest corners. When I introduced perpendicularity proportional to danger (distance and targeting me) in Griezel, I jumped from rank 30 to rank 10. Performing good against topbots is important, but performing good against a bunch of mediocre and 'not-so-good' bots is as important, maybe even more important. Pitch in Gruwel against 9 top-20 bots and it will end dead-last. Pitch in Gruwel against 9 (very)low-ranked bots (see SampleBotMeleeChallenge) and it will slaughter them faster than nearly everyone. Meleebattles will almost always consist of one or two topbots, some mediocre ones and a few bad bots, so being good against everybody does pay off. -- GrubbmGait
I know I have a tendancy to repeat what the person before me said, but well I like to outline things, your bot has to beat most of the bots below it, and all the bots below it to gain the 1st rank position, or atleast more then the current 1st placer does. So your bot might beat all the top bots all the time, but if it beats the top 10 bots and nothing else, then it only beats 10 bots out of over 200 bots. Beating the top bots means nothing in a division based ranking system. --Chase-san
Well, I think it is about time to develop a qualitative measurement of bearing offset profiles. I don't want to go into detail about the targeting system I've been developing, but I've decided that I need to dynamically choose segmentations, since tests in the Rumble have shown that different segmentations can have significant impact on individual opponents. Rather than choosing the best overall combination, it would be nifty to pick them on the fly. Certainly not a new concept, but one I think I can attain, for better or worse. -- Martin
Not an easy task, but if you manage it, awesome (has anyone ever managed that?) --Chase-san
Toad has working DynamicSegmentation? and does fairly well, though it's kinda slow. Albert says Virus has some type of DynamicSegmentation?, too. Definitely a tough task to get it working well at a reasonable speed, best of luck! -- Voidious
Toad kicks royal butt in PL still. Maybe this is why, its tuned for every opponent to 'win'. --Chase-san
With traditional segmentation, various conditions are recorded when a shot is aimed, a wave is created, and as the wave crashes over the opponent more data is recorded to note what shot(s) would have hit the opponent. When a similar condition is encountered, the targeting can make an educated guess as to where the opponent is likely to be, and fire in that direction.
The main issues with this approach are what data to record, and what granularity to use. The more data used and more finely grained slicing of the data, the more precise the measurement of likeness of condition, but with that you are less likely to find a matching condition, so the slower the gun is to learn and adapt.
As far as I know all bots to date treat all combinations of data as unique conditions, and have storage bins specific to that combination, though there are also techniques of bin smoothing to blur the hard edges provided by segmentation.
My latest approach is to treat data categories independently from one another. I record wave hits for the categories seperately, and when my gun requests a angle to shoot at (with a collection of targeting condition data), I grab the hit count bins from each data category and then layer them together as a composite, and find the best angle (i.e. most commonly hit angle).
In the debug screenshot above, you can see six bins lining the bottom. Above is a composite of some of those bins. If I don't think that a data category (e.g. distance to wall) profile has much to offer, I don't include it for that shot.
A traditional segmentation array would not see the similarity between, for example, a bot circling you counterclockwise near a wall vs. far from a wall, because the wall distance would make it fall into an entirely different bin. With my approach, the counterclockwise circling is read from by both conditions, and recorded to twice. This means that each data category is learning more quickly.
The hope is that giving each category an equal say in the final composite will still result in a reasonable prediction of future position.
Well, any single buffer (multi-dimensional array) treats each combination as a unique situation, but many bots use multiple buffers and layer them like you do here. Usually, each buffer still has multiple segments, but I do have a couple with zero or one segment in parts of Dookious. I think this is a good idea (and like what PEZ was doing in CrowdTargeting), but I think you have so much data at hand with every-tick wave collection in a gun that it seems like you could afford more than one attribute in each buffer. -- Voidious
There is a frustrating issue with bullet collisions. When a bullet collides with a tank, it shifts position. When watching battles, you can see it yourself. The explosion on the tank occurs near the point of impact, but not where the bullet seems to have struck the tank's exterior, or even along the segment. The bullet's location in the related events received match up with the explosion's center (seen as yellow rings above), but they are not along the bullet path (seen as gray lines above). I was trying to match up the position, heading, and velocity of the bullet with a known enemy firing position, but it wasn't matching up. Eventually I took another route to reach the same end, but it irks me that the event was useless. -- Martin
First thing I would check is that your gun is actually firing where you think it is - are the bullets following your painted lines? -- Skilgannon
* It's true that robocode does this. But knowing the bullet power and approximate impact location gives you enough information to eliminate all but the correct Wave / EnemyWave --Simonton
*Correct. I actually use the bullet's getHeadingRadians method and apply that to all known inbound waves' firing positions to see which wave intersects my bot's position at the time of impact (after bullet movement, before tank movement). I could use the velocity of the bullet for an extra check, but I don't really need to. At this point the only bullets I can't match up to are the ones fired when the opponent hits a wall in the same turn, throwing off the energy drop. -- Martin
* Thanks for bringing this up =). I would have assumed that this would be correct. This could be what's throwing off my otherwise pixel-perfect wavesurfing. I think I'll file a bug report =) -- Skilgannon
** Well, if your bot would be hit at the yellow circle but not along the line segment, do you get hit? I think not (and don't see any examples above), but I can't say for certain. If it's just the reported spot that's off, it shouldn't affect your surfing much at all - for most bots, the two spots would resolve to the same GF bin anyway. -- Voidious
*** Every pixel counts =). I found that out with DrussGT. 6 pixels off in my precise prediction was more than 40 points in the Rumble. And I've got 151 bins, so at a distance of 400 that's 2.11 pixels per bin (0.8*400/151). So a few pixels off will definitely change things. -- Skilgannon
**** Something seemed wrong with that calculation. It's 4.22 pixels per bin, because the MEA is in each direction. =) -- Skilgannon
Thank you for the report at SourceForge. So, if I fix this issue with Robocode, would this break anything with existing robots? --Fnl
*Well, there is this to consider: If a bullet segment clips a corner off of a tank, or if the bullet segment starts within the tank and exists (because the tank moved into the bullet during the tank movement phase of the previous round, after bullet collisions are detected), the bullet's ending location will be outside of the tank's body. If that location is used for the explosion, it will look odd. Now that I am thinking about it, I've noticed that a bullet's lifespan lasts a few ticks after the collision, and its position follows the tank's, and I conclude that the reason for this is that the bullet's position is used throughout the course of the explosion graphics. Basically in order to correct the problem you would have to mark the bullet's initial point of impact on the robot, wether that is on the exterior (bullet begins outside and enters the hitbox) or interior (bullet begins inside and passes through hitbox). Because the hitbox doesn't rotate or even match the tank's graphics, it will still appear to be an interior hit. Its probably not really worth it to change this, but it should be documented on the Wiki and in the API that a bullet's position after colliding with a tank will not be exact. -- Martin
* I would think it'd be fairly easy to use a different coordinate for the graphic than the one that gets reported via the RobotHitEvent?, wouldn't it? But I do not know if changing what's reported via the event would affect some existing bot. -- Simonton
* No, unfortunately it is not that easy as the Bullet class gets it's data dynamically from an internal BulletPeer? class. But the problem is that the bullet is not a snapshot when it collides, i.e. a deep copy. I have changed this with a special test version of [Robocode 1.4.5 here]. Please try out this version to see if this fixes the problem at report back. :-) --Fnl
*I'll look at it in the morning. I'm trying to get Tomcat, MySQL?, and an old Java web app installed and running. I enjoy programming, but I sure hate setting up the environment. -- Martin
* Is it possible to work around this (for accurately detecting enemy bullets) by projecting from the fireposition with the bullet's heading? The heading of the bullet isn't changed on impact, is it? -- Skilgannon
* If you now the coordinate, heading, and velocity of the bullet, then I should be quite easy to figure out. When the bullet hits the tank, the only things that are changed for the explosion part is the x og y coordinates and the state of the bullet = "bullet_hit_robot", which means that the bullet is no longer active on the battle field. ;-) --Fnl
* Ok, thanks. It should be as simple as Point2D.Double realLocation = project(wave.fireLocation,bulletHeading,wave.distanceTraveled); -- Skilgannon
* Yes, exactly. ;-) --Fnl
* Skilgannon: I take my words back! I found out that a deep copy would not do, as the Bullet would become a new object, which you cannot compare to your own bullets you fired, e.g. when you hit another robot for example. Thus, I have changed it, so the rendering x og y coordinates for the explosion part is independt from where the bullet did hit a robot or other bullet. I have now made a new version, which I have tested, and it seems to work now. But I should still like you to try it out. A new test/debug version can be found [Robocode 1.4.5 (02) here]. I tested it by putting all bullets received in bullet event as onHitByBullet?() in a list, and then I paint all the bullets in this list using onPaint().
Ugluk is presently undergoing a code transplant. I started a new project, rewrote the physics engine building blocks, and am slowly refurbishing the old Ugluk guts as they are moved to the new body. It is a fairly intimate refresher course in the bot. I'm also culling obsolete functionality (dependencies of features long abandoned) and changing some of the flow. I'm sure Ugluk will need some physical therapy following the procedure, but he should be a lot healthier at the end. -- Martin
Cool! Welcome back. -- Voidious