Hi, I finished 2nd, and I’d like to tell something about my strategy.
This contest was similar to Russian AI Cup 2013 contest, in which I was quite successful as well. They both featured turn-based games on rectangular field, squad of a few units under your control, fog of war and lots of fighting. So it was just my cup of tea.
I’ll focus on features I find interesting and which were not mentioned above.
Tests
The first feature is unit-testing. I’m quite proud of it. It allowed me to create some rather complex logic without fear to get lost in bugs.
Watch this: http://pastebin.com/6pJBV5fD
About a half of my strategy features are mentioned in these tests.
You can notice that all numbers used in tests are quite small, less than 100. How’s that possible if distances used in game are much greater? That’s because I use separate set of game parameters for unit-tests and for real runs.
public static GameParameters createTestGameParameters() {
GameParameters r = new GameParameters();
r.W = 51;
r.H = 51;
r.FOG_RANGE = 7;
r.MAX_BUST_RANGE = 6;
r.STUN_RANGE = 5;
r.RELEASE_RANGE = 4;
r.MIN_BUST_RANGE = 3;
r.MOVE_RANGE = 2;
r.GHOST_MOVE_RANGE = 1;
return r;
}
It allows me to use more convenient numbers in tests, easier calculations, and exact (without any scaling) schemes on checkered paper.
Some may say that writing such tests slows down development. For me, it’s the thing that speeds up development. When you implement a feature, you test it anyways. If you don’t have tests, you upload new version and watch replay. Writing test for a feature takes the same time as watching a replay (if you already have reasonably good testing framework). But test will stay with you, and will be run dozens of times later.
So, are unit-tests always such a great idea?
No.
Unit-tests make you sure that your code does what you want it to do. But it can’t check if what you want is the good thing. If you have some nice, but risky idea, only real matches can show if this idea is good. But if you are confident in your idea, you can start with unit-test for it right away.
So happened, that this specific contest was full of such obviously good heuristics.
The other case when unit-testing is not so good is when game rules are just too complex. If the world state contains many parameters, it’ll be hard to set them up for a test. If game events require some complex calculations (physics simulation, for example), it may be too hard to find the right answer for your test manually.
And again, this specific contest had small game state and simple rules. It was easy to set up tests and simulate game events manually.
Fighting
My bot relies heavily on fighting. Very much effort was invested to discover and implement useful fighting heuristics. So busters are quite confident in their fighting abilities and rush for a battle whenever possible.
All fights can be divided into 3 groups.
- Chasing enemy courier.
To prevent courier from running away on unpredictable trajectory, try to always keep him in sight.
If some of your allies is going to stun the courier, try to be in right bust range from courier, to be able to bust dropped ghost right away.
If you expect that courier is going to use stun, try to be in bust range again for the same reason.
Take into account the fact that if stunned courier drops the ghost inside his base, ghost is scored to that base.
If you stun the courier and lose vision over him, create imaginary ghost in his expected position.
- Escorting your courier.
Courier should avoid getting stunned, if his stun is on cooldown (yeah, sometimes my courier carries his ghost right to enemy base this way, even in final version).
If courier is going to use stun or get stunned, be in bust range from expected dropped ghost position.
Don’t escort when I think there’s enough escorters already, i.e. when number of escorters >= number of chasing enemies.
Escort is needed in following cases:
- when the enemy is in stun range from courier right now
- when there is enemy closer to your base than the courier
- when enemy can get in stun range to next courier position on way to base in one move
- Fighting for ghost with positive stamina.
If there is a fight for a ghost anywhere on the map, all my busters charge into the battle. I suppose that there is battle for ghost each time there is both my and enemy busters in it’s bust range. To avoid false positives, I ignore ghosts with 40 stamina. But ghosts with 39 stamina are already worth a fight!
If there is more enemies than allies near the ghost, don’t bust it. Just stun enemies, bait for their stuns, and wait for assistance.
And few more features not specific to any of fight type:
If your stun is on low cooldown, try to not get stunned. If you got stunned just before ending of your cooldown, it’s quite a pity.
Here’s the riddle. There are two enemies near you. One has stun ready, and one has stun on cooldown. Who you gonna stun? Codebusters! At first sight, you should stun the one with stun ready since he’s more dangerous. But that’s a terrible mistake! He will use his stun anyways, because moves are simultaneous. After few moves cooldown of the second one ends and some of your busters get stunned again. You’d better stun the guy with stun on cooldown right now.
Chain stun idea was described by csj above. I can only add that this idea was super obvious to me since I’m Dota player. You’d better overlap your stuns a little, so enemy can’t instantly cast some of his spells between your stuns.
Hmm… Did I mention that you have to know enemy cooldowns to do all of the above?
I detect which enemy stunned me and remember on what move it happened.
To do so, I check all possible things: whether enemy is stunned, carrying a ghost, moving, busting, his previously known cooldown…
I use previous game state to detect who could stun me, and current game state to cut off who could not stun me.
Still, there is ambiguity when there are two enemies who could stun you, and exactly one did it. Lol, I’ve just realized there is no ambiguity it all! You can always detect if enemy did not use stun. If he moved or busted, you know it. The case when he used release is just too rare. If he used move to same point just to trick you… well, that’s just too next level for me.
OK, it seems we can always know enemy’s cooldowns. But couldn’t these cooldowns just be available in API? Why should we use such sophisticated logic to have such basic thing? Is it fun at all? Well, it was fun for me for some weird reason, I admit it. But I don’t like when game rules are inconsistent with setting. A guy stuns you with proton beam. Which is sparkling and loud. You see it. Your teammates see it. And still, one tick later no one can remember what just happened. You only see that your guy is stunned. And you need to run whole investigation do detect what exactly happened. It feels wrong.
Though, if you were shot by invisible sniper somewhere in the forest instead, then lack of this information would be reasonable.
Some random features
When you have already collected half of ghosts, focus on the last one - it will secure you the victory. If you see few ghosts, bust only nearest to your base. If you carry ghost to base, everyone should escort the courier.
Use knowledge of total number of ghosts (ghostCnt in input) and map symmetry to detect that you have already seen all possible ghost types on the map. It helps to proceed to busting fat ghosts earlier without excessive exploring.
That’s all folks!
Should I publish my code? No one above have done it. I publish my code after all similar competitions, but maybe it’s too big deal in this site.
P.S. Thanks to CG team, it was very fun and high-quality contest.
(especially my exploration and fighting systems)
If I see several of them, I fly the farthest point from their barycenter.