Codebusters game has come back on the AI page. The game is a bit different from the contest one since two rules will be added in silver and gold leagues, but it will still stay quite the same. We’re putting a highlight on the strategies from players which reached the top 10 of the contest leaderboard. For those who didn’t have the time to participate in the contest, this is the opportunity to learn more and dive in.
You can find a lot more strategies in this forum topic from which the following was taken.

Romka (5th, C++)

Eventually I ended up 5th despite being 1st first half of the contest. I think the reason is that I didn’t pay enough attention to the small details and didn’t believe in herding. I spent about 25 hours in total on coding and watching the replays, 10 hours of these 25 were spent during the Saturday, one day before the contest has ended.
 
Exploration
I coded my exploration algorithm in the first hour after the contest has started and didn’t change it during the whole contest. I consider a grid on the playing area with step = 100. I have a set of “unseen” nodes of this grid which I update every turn. When my buster wants to pick up new target to go to, he selects the closest node from this set, but adding to all distances random number from 0 to 3000. I could not decide what is better: to explore large area with all busters walking alone, or to explore small parts of the map with the group of busters in order to defend against opponent and to catch found ghosts faster, so this random change of the distance could lead to either of these scenarios.

Modes

I had two modes: “usual” and “careful”. If I see half or more of enemy busters near my base or if there is one ghost left for my victory, I get in mode “careful”. In this mode the whole team works as a support for the buster who is carrying the ghost. If my buster who is carrying a ghost finds himself significantly closer to base than its support guys, he waits for them.

Stealing ghosts

I didn’t try to steal ghost by sneaking at the opponent base, because I’ve found it boring. But I did try to intercept enemies going to their base assuming they will use a straight path, so I could not intercept busters of Khao (8th, Javascript) that moved along the walls.

Stunning

I didn’t come to the idea of chain zapping used by Hohol as I am not a Dota player. Still, if I need to choose between stunning enemy busters with stun cooldowns equal to 0 and 5 for example, I will choose the one with cooldown=5, as buster with zero cooldown will use his stun anyway.

Herding

I had absolutely no time to code during last Sunday. When I woke up in the morning, I saw matches vs Recar who proved that herding can be done efficiently. I tried to implement something similar, that I ended to code in my friend’s car and submitted when we arrived to our picnic location. After a few hours I decided to check how it’s doing and found some bugs that I fixed while my friends were playing Frisbee.

Some words about code organization

I had a base class for Entity and two derived classes for Ghost and Buster. All game information such as arrays of busters, ghosts, base locations was stored in a class Game. It could read information about a new turn and update corresponding fields. I also had one class GameAI which possessed tactical information such as a behavior mode, a list of moving targets, a list of enemy busters to intercept and so on. There was one main method named “makeDecisions” that subsequently called methods dedicated to one particular activity. Part of it was as follows:

 

setSupportWhenEnemyNearby();
setInterceptors();
setBusting();
setStunEnemyBustingGhost();
setExplorers();
for (int index : movingToBase)
    setHerding(game.myBusters[index]);
setFancyChat();
Each method considered only busters that weren’t used in the previous methods (with a few exceptions, like for herding). Last one was the most useful method, of course 🙂
I didn’t use any unit tests as I’m totally fine with controlling code of this small size (1.5k lines of code, including empty lines — about 50kb in total). I had a bunch of asserts here and there, though. Asserts are a great way to prevent using some methods in the way you didn’t suppose to use them earlier. So for those of you who think that unit tests take too much time to write I suggest you to try asserts. Nevertheless, I liked the way Hohol organized his testing, maybe I’ll try his recipe in the future.
I can answer any question that you may have about some details of my implementation.
I enjoyed this contest a lot because I like to write team-oriented AI very much. This kind of games always include at least two levels of AI: high-level AI to determine current mode and goals for each unit and low-level AI which makes unit to achieve its goal in some optimal way. I hope similar contests will be conducted in the future.

Hohol (2nd, Java)

This contest was similar to Russian AI Cup 201317 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.

 

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.
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 a new version and watch replays. 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 escorts already, i.e. when number of escorts >=  number of chasing enemies.
Escort is needed in the 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.
The idea of chain-stun was super obvious to me since I’m a Dota player. You’d better overlap your stuns a little, so enemy can’t instantly cast some of his spells between your stuns.

Enemy cooldowns

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.
But couldn’t these cooldowns just be available in the 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 a 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!
Thanks to CG team, it was very fun and high-quality contest.

csj (3rd, Scala)

I finished 3rd place and here is a breakdown of my strategy.

Scouting

At the start of the game (first 30 turns), scout aggressively — the targets are hardcoded. Do not engage any ground ghosts until you’ve reached your scouting assignment. After that, still within the first 30 turns, only engage a ghost that is downfield (i.e. further than our base than you are). Rationale: I’m likely to end up getting easy targets on my half of the map anyway, and early action on the opponent end of the field will cause ghosts to gravitate towards my base naturally. Map position is extremely important for times when the midgame/endgame turns into a race. I have found that I begin most games behind by 1-2 points, but that I make it back up over time as the map advantage is in my favour.

Targets

Every turn, a collection of interesting targets is tabulated, consisting of:
  • Visible ghosts on the ground
  • Visible enemies carrying a ghost — only if any of our busters will be able to intercept him in time, considering their current stunned status and stun cooldown, otherwise ignore that enemy completely — no sense wasting valuable effort on him!
  • Last observed locations of ghosts (taking care to account for the fact that ghosts may float away)
  • Friendly busters carrying a ghost, if they are not safe (using the same calculation as above, in reverse — not perfect since we don’t know where all enemy busters are, but good enough)

Weapons

Initially I adopted a very liberal stance regarding weapons: if able to use them, use them. I found that I was losing a lot of shoot-outs with higher ranked AIs, and I decided to be more conservative regarding my use of zaps. Now, I never zap any opponent unless there’s a valuable target on the map somewhere: a <10 HP ghost (including one carried by an opponent or a vulnerable friend). In other words, if there are only big ghosts on the field, conserve those zaps; otherwise, weapons free. I’ve found that I come away victorious in a lot of zap battles simply because I was on stun cooldown less often when it mattered.

Buster behaviour

In general, busters act completely independently. For each buster, the set of available targets is filtered by viability (for example, if a buster can’t reach a ground ghost before it burns down and we’re the only ones burning it down, don’t bother). Then, whichever applies first:
  • If there’s an enemy to shoot (and we’re weapons free), shoot (only if he hasn’t already been shot this turn — this is the full extent of buster cooperation). Note: a buster will shoot even if currently carrying a ghost.
  • If carrying a ghost, dive-bomb for home in a straight line. I didn’t do any avoiding techniques because I had faith in my battling abilities 🙂 UNLESS it’s near the end of the game and we won’t make it back in time to have a material impact on the rest of the game anyway, in which case hide in a corner and avoid enemies
  • Pick a viable target based on the number of turns needed to burn it down completely: divide distance by speed (turns to get there) and then divide ghost health by number of busters adding myself if not already there (turns to burn the ghost down). Remember that this can include enemy-carried ghosts or friendly-carried ghosts. Select the one with the smallest number of turns and act accordingly (move towards, shoot, escort, etc.). Do not give additional preference for an enemy-carried ghost.
  • If no available targets, go into pre-assigned endgame roles, hardcoded on turn 1: camp enemy base or sweep far sides of the map (targets will likely emerge sooner or later)
By watching countless replays I made minor modifications throughout the contest. I made a few major modifications when I observed some brilliant behaviours from some top AIs.

Chain-zapping (Hohol)

Despite my best efforts, Hohol always seemed to get the best of me during gun battles, and I sought to figure out why. I watched replays frame by frame and observed that in some circumstances, Hohol would zap my buster one turn before I would zap his! I panicked and thought that I was not interpreting the input correctly and that I was misjudging the cooldowns or stun durations by one turn, but it was not so. So what happened? He was actually zapping my guys the turn before they came out of stunned state. This way they would not have a chance to fire upon enemies the turn they woke up. I immediately implemented this idea: when looking for enemies to stun, consider also those who are in Stunned status for 1 more turn.

Herding (Recar)

At 10AM on Sunday (4 hours before the contest ended), I noticed a new leader, Recar, and immediately started studying replays against him. While carrying a ghost (even sometimes when not carrying a ghost!) his guys would gently shepherd ground ghosts towards his base! This struck me as brilliant – while there would be a cost of doing this (ghosts float half as fast), the dividends would show: better map position for the mid/end game and fewer running costs later on (not to mention return safety). I set to work on this immediately and within a few attempts I got it working. This was submitted with around 2 hours remaining.

Scala

I learned Scala on the job and have been using it for about 8 months. This is my first contest attempt using Scala and I can confidently say it will not be my last. Scala is such an expressive language that makes it extremely easy to communicate intent — not once during this contest (at least that I noticed) did I discover a careless error in my code. Errors are extremely difficult to track down in a contest like this — without a debugger you’re reduced to writing a lot of console entries to diagnose the problems, and this takes up a lot of time — time that could be spent watching replays and studying top opponents. This time I was able to focus my attention where it mattered and it showed on the scoreboard.

A small piece of feedback

The zap cooldown of friendly and enemy busters was not available. This meant it had to be manually tracked for friendly busters — difficult for newcomers. It would have been very valuable to have this information for enemy busters as well: it could be used to prioritize enemy targets when considering whom to zap. Maybe some of the top AIs tracked this as well somehow? Otherwise an excellent contest, beautiful visuals, superb execution as always and a great pleasure to participate in!

Are you ready for Codebusters AI game now? Don’t hesitate to share with us your new strategies!