CodeBuster - Feedback & Strategy

Contests
#23

Hi all, 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 :slight_smile: 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.

One small piece of feedback for the CG group: 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!

21 Likes
#24

Hmm… I think ghosts placed randomly but seems that they mirrored? This give big advantage for players who not fear to rely on this “feature”.

#25

I used (a little) the Magus site, but it didn’t give me enough informations

#26

Wow, the chain-zapping was damn smart. I never once considered I could stun an already stunned opponent. I’m pretty sure it gives a huge advantage in battles. Neat!

#27

Neither did I, and it sure did. It pays to study replays carefully!

1 Like
#28

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.

  1. 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.
  2. 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
  1. 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.

25 Likes
#29

What a nice post ! Thanks you very much.

CodeBuster will be available as a multi-puzzle soon. Your code might spoil a lot of people and some of them may just copy/paste your work to be ranked.

Feel free to share your code in your GitHub next to your Tropper one or waht so ever if you really want to, taking that into consideration :slight_smile:

Bonus: I know it’s a lot of work, but we prefer something like Magus did for Coders Strike Back (No Full Code):
http://files.magusgeek.com/csb/csb_en.html

#30

I’ve just devised the case when you still can’t detect who stunned you. Suppose there are two enemies who can do it. Simultaneously you move and some of them stuns you. You moved away from them and lost sight of them both. In this case you don’t know who stunned you.

#31

Yup, and there is an other case : one of them was busting a ghost, and you stunned him ; while busting he did not move, and you cannot know if he did not simultaneously stunned you :wink:

Those are the two “hard” cases I noticed ^^ (and exposed it the topic I opened on the subject https://www.codingame.com/forum/t/codebusters-missing-state/1724 )

#32

If buster was busting on previous move, there is id of busted ghost for him in input, so you know he wasn’t using stun.

#33

Really?!! I thought this id was here only when the state “BUSTING” was activated :’(

The rules were quite unclear on this point!

#34

If he was busting on previous move, his state is “BUSTING”.
And yeah, the rules are quite messed up here. These simultaneous moves are so deceiving…

#35

Even if you stunned him? I must confess I did not verify… So I guess my code was working after all (for all but the disappearing in the fog buster) ^^

#36

Oh, I just realized what exactly you have meant. It seems you are right, if you stun and he tries to bust, he won’t bust. Dunno what happens in this case about his state and ids though.

#37

Here is my strategy:

  • If stunned… well… cry ;
  • If I can release a ghost on the base, or make a safe move when I’m within 2400, do it, upmost priority ; if I’m stunned, my ghost will be automatically released in my base :slight_smile: (I saw some busters being near enough stunning instead ; bad idea !)
  • Stun every dangerous and / or busy busters I have in sight ; even if it’s already stunned, but will wake up next turn. Ignore him if he is idling and cannot stun you now or next turn ; ignore any opponent buster too near from his base (<2 400).
  • Fly if I see any dangerous opponent between 1760 and 2200, and call for others (and gods) help :stuck_out_tongue: If I see several of them, I fly the farthest point from their barycenter.
  • Bring back the ghost to the base if I carry one ; tried two solutions : direct bring back, and wall hugging ; first one worked better in legend, while wall hugging was better for gold.

The three next actions are chosen in a loop with number of moves to get a ghost from 1 to 64 :

  • Hunt a ghost, considering the number of movements to reach it and the number of bust actions to get it ;
  • Go helping a buster who called for help, considering the number of mouvements to reach him + the STUN on his pursuer ;
  • Intercept an opponent buster coming back to his base with a ghost, considering the number of mouvements to cut his trajectory + the STUN & the BUST to get his ghost.

If none of these actions were done, find one 1000x1000 square to explore, considering his last exploration date and the number of turns to cover it ; two modes : busters have to chose squares further than 3000 from each others during first 100 turns, and nearer than 2240 (1000 x √5) from each others during next 100’s .

Thats all ; I spent lots of time trying to find a nasty bug while stuck in this horrible gold league (800+ coders!!!) ; here are the things I would have liked to do:

  • Herding ;
  • An A* to find a safe return path, considering opponent’s busters as 1760 + 800 * (number of not seen turns) round obstacles, and if the base is not reacheable (campers for exemple), try to reach a corner instead.

:slight_smile:

3 Likes
#38

With second thought, I’m quite sure his state is “STUNNED” and not “BUSTING”, because I noticed sometimes I thought he stunned me when he did not in my debug messages. :slight_smile: Don’t know for the value though, but logically it’s the number of stunned turns and not the ID of the ghost he tried to bust (even if he removed one stamina from the ghost, or took it just before the stun) ^^

BTW, I hope this information will be added for the multi version with a few others it would have been logical to have (busted ghost in the bases for exemple) :slight_smile:

[Edit] Just thinking that if you saw the ghost he busted previous turn, and still see it, on some cases (but not always), you can have more hints of what happened ; but it becomes kinda complex :smiley:

1 Like
#39

thanks codinGame it was a great contest it was my first contest to catch up and go above 1000 rank (324th) :grin: :v:
the league system i liked and disliked it
i liked boss system beating a boss was a great fun and give me a push to continue trying ,i disliked not be capable to see the top ranked player strategy as they are hiding in the higher league :stuck_out_tongue_winking_eye: and after i go up i stick to the replays to figure out their strategy and oh no i need to reformat my code a gain

despite its the my 3rd contest I’m still having the same problem the ugly creepy bugs one of them make me stuck for a hole day to figure it out :cry: this because the game semantic was confusing and simultaneous actions was a pain :sob: i think in next contest i will try to implement a game simulator though it is time consuming i think it will save me time at end when AI become complex and code has become lengthy, trying to add new strategy at this point was difficult as my bots was synchronizing their actions all the time :sweat_smile: it will be nice if top ranked players share their opinions about if they used their own simulator was it beneficial what they gain what they loos and any advice on this to noobs also i think i need to read more about algorithms I’m late on this

at last thanks codinGame :+1:

#40

I won’t repeat what other already said, but here’s how I handled scouting unknown areas with a very simple approach: For the first 8 turns, everyone just moves straight away from the base and no one busts any ghosts. This pretty much scans my half of the map and through symmetry I know the positions of all ghosts on the map. I ignore ghosts with 3 stamina that are close to the enemy base, because I assume the enemy will have collected them before I have a chance to get there… If at some point in the game I run out of ghosts, I check the two non-base corners (hard coded point 2200 from the corner away) in case a ghost did move here. If I still don’t find a ghost I camp at the enemy base

Feedback:
This contest was very very fun to participate, thanks for organizing!
Some remarks/requests/comments:

  • As people already requested, for the next contests please make the rule description more detailed (movement order, stunned busters still move one turn,…).
  • Please decribe in the rules if the game map is constructed in a certain way. In this case I’m referring to the ghost symmetry and that ghosts always have 3/15/40 stamina. This was something what was apparently given in every map, but wasn’t described in the rules, so I was a little hesitant to use this info in my strategy, in case it changes.
  • For a timelimited contest I might have prefered a fixed number of busters. I think it’s a nice aspect to have 2-5 busters for a game, but since we only had 8 days, I completely ignored this circumstance and my strategy is exactly the same for all cases
  • Please never go away from 1vs1 contests. In 3-4 player games, you have to rely too much on other players not doing something what will make you both loose.
  • I missed the computer science aspect of this contest a litte… It was a very fun game, but successful bots were just if/else rule based.
#41

Thanks for all the great posts everyone. I don’t have many new ideas to contribute, but I wanted to share some small details that I implemented which seemed to help me towards the end of the competition. I ended up rank 15.

  1. When assigning stuns onto enemies I always assigned my carrying busters stuns first. If you have 1 carrier + 1 escort near an enemy buster, the enemy buster almost always will stun your carrier, so it is better to use your carrier’s stun than the escort’s stun. I think the worst case is if your carrier has a stun ready and you use your escort’s stun to stun the enemy. Then your carrier has a stun but is useless for 10 turns. So better to go 1-for-1 with the stuns.

  2. When I escorted my carriers I always positioned my escorts slightly outside the minimum bust range of my carrier. This way if my carrier gets stunned, I can immediately bust the ghost and continue towards my base.

  3. For exploration, ghost locations, and enemy locations, I created these “heatmaps”. I subdivided the map into a 5x6 grid and then created a 2-D array for each. And then I would update them based on certain rules. For example, in the enemy map, every turn I saw an enemy in a zone, I would increment the cell in that array by 1 and the cells of the zones within 4000 range (arbitrary) by 0.5. Then every turn I multiplied each cell’s value by 0.8. So this map gives me a sense of which zones most likely has enemies. The longer that I don’t see an enemy in a zone, the value is decayed by the factor of 0.8. If my home’s zone was one of the top 5 most dangerous zones, I would hide my carrying busters in a corner. (Though this strategy was not significant since the best bots did not base camp anyway).

1 Like
#42

First of all thanks for the excellent contest.
I was not able to get out of gold league and finished 174th.

I tried herding (with 2 or 1 buster) – it was not worth effort (at least against advanced players).
I tried camping - it is easily countered by most players.
I tried different strategiest against campers - didn’t want to do escort thing, hug the wall from 5000, 0 -> base was good enough for me for most cases.

Most effective thing that raised my ranks is interception code (so I can chase enemy busters with ghosts).
Logic is as simple as possible - assume he is moving straight line to base, calculate points 800 units one from other on this line, check if any of my busters can get in 1760 range of this point and have stun on cooldown - go for it.

What I find weird is ranking system: I adjusted code to beat boss 2/3 of times and have draws on almost all other matches - and ended well below 300th in gold leaderboard, so had to revert to code that beats other players, but not boss.

Also, one of the things that raised my ranks was simple logic - if I see enemy busting ghost and do not have enough busters in range to counterbust it – move in position so you can stun enemy and get his ghost right after he finishes busting.

Well, this was fun contest, even that I didn’t enjoy my final results, I could do better.