I saw someone using herding, fairly effectively.
They would herd 40-stamina ghosts into their corner and bust them late in the game.
I’m very disappointed with my ranking. I thought I could reach the top 50 but I didn’t even reach the top 200 
I was super enthusiastic at first with this challenge. The fog of war is really an excellent idea for these AI games. 
The first 3 days of the challenge I coded with passion for around 20 hours total and reached the global top 10, even peaked top 3 when better players were resubmitting.
Then I continued to work on my code but it got more and more difficult to assess if I was improving or not with the time needed to get a ranking after a submit (around 30 min in gold league).
I spent another 10 or 15 hours from Wednesday to Sunday and in the end I had to dump all my changes because the global performance was worse thant the code from Wednesday. On Sunday I tried incremental, small changes which looked like bug fixes from the initial code but it always ended worse.
This was globally extremely frustrating to “lose” 15 hours for no positive result 
I’ve got no idea how to improve my strategy for the next contest … maybe a more TDD approach ? Or do all top players implement a full Judge engine to match their AIs against themselves outside of CG platform ?
I ended 73 in legend league with my initial algorithm. I don’t reuse any standard techniques I’ve read here like genetic algorithms or minimax nor predict opponent moves in advance.
Basically this is the idea by decreasing priorities :
- stun if enemy at range (always)
- release if carrying a ghost at home
- if carrying, come back home. If enemies are likely to intercept me, hug a friend instead. If being hugged, move just in front of carrier to pass the enemy campers.
- if an interception is possible, go for it
- if less than ~45% of map is discovered, go to a close corner or clear some fog. When a ghost is discovered, assume a symmetric one is also there
- grab the best ghost (scored by distance to base, to buster, and remaining stamina)
In the version submitted, most decisions are taken individually by each buster. In the intermediate work, I took collective decisions and considered at each step which busters were still available.
I also kept track of hidden ghosts and enemies with less importance if seen since a long time.
Some extra tuning was also helpful like avoid to double stun the same enemy, ancipating that a ghost will be dropped after a stun, positioning closer to my base when busting, only chasing guessed ghosts with one buster, avoiding being to close to borders when exploring … and many more that I had to drop.
Oh and I did this in Scala like always, grats to @csj for finishing #3. I think it’s the first time a Scala coder gets this high !
10 Likes
That was a really interesting challenge, with a pretty high level. Thanks Codingame for the experience 
I finished #93 but I don’t feel like I could have done much better (maybe top 50 but definitely not top 10), so I’m really eager to learn about the strategies of the winners.
My main issue for this contest has been the quality of my code. In Smash The Code, I’ve been really careful and it really helped me to experiment. For CodeBusters however, I didn’t plan on investing a lot of time so I went with some straightforward quick&dirty spaghetti code. Later, a friend convinced me to go back to the contest and invest more time, but because of my prime choices my code wasn’t as flexible as it should have been, and I was too lazy to rewrite it from scratch…
Anyway, for the global strategy, it’s pretty much a decision tree, with the following behaviors:
-
Stun has priority over everything else. If I can stun, I do it (I’ve tried more “intelligent” strategies, but they actually behaved worse). There’s a few checks in order to 1/ don’t have two busters stun the same opponent, and 2/ if I have multiple busters that can stun the same opponent, and one of my buster is carrying a ghost, then that buster will do the stun. The rationale is that the opponent will almost always target the buster with the ghost, so it’s better if that very same buster use his stun while he still can.
-
If my buster have a ghost, there’s a few behaviors:
- Most of the time, try to head to the home base to drop the ghost
- If I know there’s an opponent near my home (or if there was one last time I was at my home), wait for another buster for escort, then go home by following the map border (makes it easier to pass a wall of campers)
- The best path to home is computed to try to avoid opponents. Basically, if I know there’s an opponent nearby, I try all the angles from 0 to 360 (by increments of 5°), and I keep the trajectory that allows me to get closer to my home while staying out of reach of stun. There’s probably a more clever way to compute that path, but since I’m only using a fraction of the 100ms I decided to be lazy and go for the bruteforcing
-
If we’re near the end of the game, then I don’t try to get home and just hide in a corner of the map
-
If my buster don’t have a ghost, I rush to the position of the ghosts I know. Most of the time I ignore ghosts with 40 stamina (more on that later). I prioritize ghosts with lower health and closer to my buster (using a heuristic).
When finding a ghost, since the initial disposition is symmetric, I keep in mind that there may be another ghost at the other side of the map. I target in priority the ghosts whose position I know for sure, and if there’s none then I target the hypothetical ghosts. -
If I don’t have any real or hypothetical ghost in the queue, I switch to exploration. I divide the map in squares of 2000x2000 points, then each exploring buster goes to the closest unexplored and untargeted square. The very first move (at the start of the game) is hardcoded to ensure optimal spreading of the busters.
-
If at some point I notice an opponent carrying a ghost, I switch to the interception routine. Basically, I check how many turns it’ll get for the opponent to get back to his home, and I see if I have a buster that can get there in time. In which case, well, I do
-
When there’s 3 or more busters per team, I assign a “stalker”. Basically, when there is no ghost, instead of exploring he follows an opponent, hoping to steal their ghosts (and as a nice side-effect, it helps me discovering ghosts on my side of the map using symmetry)
-
When all the map is explored and there’s only ghosts with 40 stamina left, my team starts camping at the opponent home. If after 60 turns I haven’t seen any enemy buster carrying a ghost, then I conclude that the opponent must be camping too, and I start hunting the ghosts with 40 stamina (and hide in a corner of the map if I capture one, because my home is deemed unsafe at that point)
And that’s pretty much it, with a few optimizations here and there (for instance, if the opponent has more busters than me on a given ghost, I stop busting because I know I won’t be able to capture the ghost, and I wait for the stun to recharge with the hope that I’ll be able to get the advantage). Mainly, the poor quality of my code prevented me from building more advanced strategies, so I’ll be more careful about that point next time
9 Likes
CodeBusters was my first contest.
Having read threads and posts about strategies for the two previous contests, I was afraid that I would have to spend a lot of time searching/reading/implementing various “exotic” algorithms or even simulating the game engine locally. I was fortunately wrong; that was not the case, at least for my attempt to have a somewhat decent bot. So, it may took me more than “10 minutes”, but it was admittedly easy “to come up with a basic solution and start having fun”.
My simple strategy:
- If you don’t carry a ghost and have a visible nearby enemy who is not stunned/being stunned and your gun is charged (I didn’t like questionmarks under my head!), stun them (especially if they carry a ghost). If you have a visible not so nearby enemy who carries a ghost try to chase them, if you are closer than them to their base (I don’t think it ever happened/worked ).
- If you detect visible ghosts, try to bust the ghost with lower stamina (sometime I tried to combine it with distance, but finally didn’t use that).
- If you are trapping a ghost, keep trapping it.
- If you carry a ghost, return to base to release it. There was no special defensive strategy implemented, that means that my ghosts were easily stolen, especially when opponent busters were waiting at my base!
- If you don’t have visible ghosts, explore one of my (nine) predefined testpoints that is not being explored.
And that was all. It was really fun, it was a really great experience, I have already registered for HyperSonic and am waiting for CodeBusters to be released as a multiplayer game!
PS: When I was submitting a new version of my bot expecting that the changes would result in a slightly better behaviour/position, I would wait until stabilization just to find out that my bot was in a lower position; I could not really be sure if that was due to better players having entered the league or due to my changes not being actual enhancements. This is something I have to better understand in the next contest
Thank you again for this great contest!
I finished 13th and here is my strategy.
I select each buster’s move according to the following priority list:
- If in stun range with the cooldown available, stun, while making sure no other buster has planned a stun on that target.
- If carrying a ghost, go home in a straight line.
- If I know of an enemy carrying a ghost, intercept his straight line trajectory home if you can and if one of my busters will be able to intercept and stun before the enemy reaches home.
- Go bust a ghost according to the following eval: -endurance-dist/800-5e-3*distToCenter, the third term encourages getting the most often contested middle ghosts first
- Explore fog by going towards an unexplored point according to the following eval: distToOtherBusters+distToWalls-distanceToUnexploredPoint-1e-3*distToCenter. When looking at distance to walls and busters be careful to take min(dist,2200). A distance larger than the line of sight is not useful.
Exploration map is stored as a boolean array representing 50x50 squares in the map.
I store ghosts I have seen in the past and delete them from the array if I don’t see them at their last known position. For this to work well it was important to model ghost movements otherwise I would get their position wrong and wrongfully delete them from the array, potentially losing knowledge of a nice 3HP ghost. So at the end of every turn I simulate ghost movements.
I also store enemy busters carrying a ghost and model their movement as a straight line to their base. I delete enemy busters not carrying a ghost from my array if they are not in sight, I can’t model their behavior and having wrong buster positions causes wrong ghost movements.
At the beginning of a game I do not bust any ghosts until I have seen ghost 0, the one in the middle. This takes ~7 turns and has the effect of me contesting the middle ghosts and getting the ghosts close to my base later. It also allows me to see and store alot of ghosts so my busters can choose lower HP ghosts instead of going for the first 40HP ghost they see.
The day I implemented the interception of enemy busters carrying a ghost I went from ~120 to ~20. I have two remarks about this:
- Stealing a ghost not only give you a +1 score but it gives a -1 to the enemy. It is one of the best things you can do.
- Doing this counters campers as they will have to walk from your base to their base, which takes ~23 turns. In that time, revenge shall be sweet, and they will have wasted all their time camping at your base instead of getting ghosts.
I feel like the main weakness of my AI was that it had no smarts whatsoever in contesting ghosts, so against the other AIs at the top of legend it would often lose the busting duels. At the top some players would bait out early stuns and stun at the right time to get the ghost, this easily makes the difference between victory and defeat. As I said earlier stealing a ghost is twice as interesting as getting one.
Feedback
- The graphics were probably the best ever on CG.
- I kind of like the game but its complexity, for a programming game, causes a high barrier to entry where it takes maybe a few hours to get out of wood league. I think this is the cause of the “low” population on this contest, 2000 vs 2500 in the previous one.
- This complexity also has the effect of forcing people to rely heavily on heuristics. Now some people don’t like games like Smash The Code because they rely heavily on bruteforce search, describing them as “just bruteforce”. However, is it very much better to have an AI which is “just ifs”? This is a programming website after all, it is nicer to learn about Simulated Annealing than if statements.
Congrats on another nice contest and see you at the next one.
14 Likes
I hope this article that I discovered towards the end of the contest will help giving the general idea about resource allocation algorithms and simple strategy games. Too bad I didn’t have time to implement it
http://www.gamasutra.com/view/feature/1535/designing_ai_algorithms_for_.php?print=1
1 Like
I disliked:
- non-deterministic default AI: when I need to debug a bug that appears in a particular situation, the last thing I want is to discover “Replay in same conditions” will not actually reproduce it and end up hunting the last battles for a replay that shows the same issue and hope that the opponent isn’t random too. Please don’t do that again. Ever.
- weird input system - values with multiple semantics depending on other values… not hard to work around and you only need to do it once, but not nice
- reapparition of team id - honestly, that just adds some unnecessary boilerplate for the developer. Please bring back “you’re always team 0” as in BTTC.
- the game complexity probably made it harder to enter for beginners: in CSB or STC, you could easily get a working bot with just 5 lines of code. Here you must mix and coordinate three different commands and have some minimal working knowledge of arrays. Starting curve is probably a bit steep for the less experienced coders
- the game complexity and variety of strategies seemed to induce weird artefacts in ranking: you can get good results against the boss and yet not come near it for a long time because your strategy is ineffective against a group of players in the middle of the board
- typically, number of battles in Wood 1 was too low at start of contest and it was extremely confusing and frustrating: my code and algo were on the right track but somehow wouldn’t even get near the boss with only 40 battles. That really suggested something was fundamentally wrong in the approach, rather than just needing to wait for more matches. I nearly gave up right at this point…
- likewise, ~20th in gold on Sat evening slowly gravitated to legend on Sun noon, just because other players pushing me up.
- spent several hours in top 5 of gold and not one single match against Boss, out of ~200 after initial ranking??? How is that even possible?
I liked:
- very fun to play and code
- graphics and theme very nicely rendered - the theme felt much less artificial than for, say, BTTC or STC
- the game complexity, opening to a larger array of strategies and more game-logic-oriented than optimization-oriented development, giving their chance to the less performant languages and a different class of coders. I don’t mind either but I think it would be nice to alternate between both types.
- gold boss was a real challenge
- no more multi-hour wait for promotions, at last!
- as always, even more enjoyable than the previous one. do keep it up!
14 Likes
Every boss had a fixed random seed.
I don’t mind the boss being random - it’s the boss, it’s not supposed to be easy.
The default, non-boss AI, on the other hand, should be usable as a predictable punching bag so I can reliably test my code against it, which is not possible if it’s random.
4 Likes
I agree with that. It wouldn’t have helped me much in this one (since my AI had a fair bit of randomness) but it’s still a good idea for the future.
Hi everybody,
Very good challenge as always.
This Codebuster game is great with infinite possibilities and finding new ideas to progress was very fun. I made a big error thinking I could wait to pass Legend before improving my code, because the better thing would have been to improve my code first (especially my exploration and fighting systems)
But adding new small ideas one by one was very fun too, even if I could"nt pas the Big Bosspectre ! I’ll find the time when on multiplayer…
Thanks again to Codingame for this great challenge !
1 Like
I did the same mistake 
Hi everybody,
First of all, I want to thank CodinGame for this wonderful challenge.
I haven’t spent that many hours thiniking and coding in years, I enjoyed the challenge.
Even if I could not make it to legend, I’m quite satisfied ,for now, of my result.
My lack of debug capacity kinda have me struggling with minor bugs, instead of working on strategy.
I discarded strategies that might have been good because a minor bug prevent them from working.
So my final strategy was pretty simple.
A- Any Ennemy aroung Carrying:
1-stun them if in range
2-intercept them if closer to their base
3-evaluate the path if they don’t go toward the base
B-Go to the cheapest Ghosts first guess peer ghosts
if battle tied for a ghost call for reinforcement
C- Stun shooting ennemy
D- stun ennemy for fun
E- if nothing else explore.
I always kept record of the position when last seen of both ghost and ennemy (adjusting them as much as i could), clearing the info if not there when if visibility range
So again, I wish to thank you, that made this fun possible.
I’m an, old style, old programmer that wish to learn new techniques like genetic Algo, or Neural network, but time is lacking on that aspect.
I’ll be ready for the next contest.
Thanks
1 Like
Extreme frustration on this contest but that was fun !
I finish in the middle of the Gold League with a very simple code (about 600 lines of PHP)
My strategy in short :
RELEASE if I can
STUN if I can
Hard coded first moves to spread busters on the map and collecting positions / using symmetry
MOVE to the base when I’m carrying a ghost. Stopping if an enemy buster on the range
BUST ghost if possible, priority to lower stamina
After turn 150, move up to 3 busters in front of enemy base
Explore map tile by tile of 1000 pixels, or where a ghost has been seen recently
When one of my buster is fighting, he aks helps to other
I disliked :
- Slow ranking calculation. Please buy some additional servers
- Unable to play with Firefox. Crashing, bugging, slow… Google Chrome is evil. Don’t force me to use it !
- No way to analyze datas of last matches played, unless doing this manually (if everybody must click on each replay to see what happened, what about the global server load ?) . It would be very interesting to know how many games I loose or win in a particular configuration (with 2 busters only, with few ghosts, when I’m player 2…), or the number of rounds of each battle. What about a CSV file containing all this useful stuff ?
I liked :
- theme
- no brute force strategy
- addictive league system
Thanks a lot to the CG team and to all players that I love to hate for a week.
4 Likes
- No way to analyze datas of last matches played, unless doing this manually (if everybody must click on each replay to see what happened, what about the global server load ?) . It would be very interesting to know how many games I loose or win in a particular configuration (with 2 busters only, with few ghosts, when I’m player 2…), or the number of rounds of each battle. What about a CSV file containing all this useful stuff ?
Good idea!
For a beginning to this you can use CGStats (cgstats.magusgeek.com - thanks @Magus)
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 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
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”.
I used (a little) the Magus site, but it didn’t give me enough informations
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!