CodeBuster - Feedback & Strategy

Contests
#1

The topic where you can tell how you liked the challenge, & how you solved it. (Do not post full code here.)

You can share your solution via github/pastebin, but every link will be removed when the competition will be available for multi.

Here is the link for the next one : https://www.codingame.com/contests/hypersonic

2 Likes
CodeBusters (aka Soul Snatchers) - Puzzle Discussion
#2

Thanks CG for this challenge, I really liked the concept (both thematicaally and mecanically).

The fog of war and the exploring was a nice part of the contest, even though “fighting” and stealing might have been the most important in the high level.

My strategy was very simple, for too much to achieve a high ranking:

  • My guys moved randomly if no Ghost were seen, if they were there they would target one. Tazzing passing by opposing busters.
    I improved it by using the symetry to “guess” the position of paired ghosts. But I didn’t have any “team synergy” (each Buster used the same AI without carring about what the other members of the team did). I think this would have been a key for my AI to move a bit higher in the ranking.

I think I have read some strategies about using a queue of actions (And I read about that also in previous post-mortem), I’d be interested in reading a bit about how people are handling those “order queue” in this type of challenges (how to had priority orders and when to “clear” it or this kind of thiings). So if anyone wants to share some tips about that, please contact me.

Thanks again CG!!

1 Like
#3

Good one. I hope I will reach legend league in the next contest :smiley:

I would like to suggest a first leaderboard after 2 or 4 hours of competition because for some players, 8 days is too long. (One t shirt for the first player?)

Codinghub was a very good idea. (Thanks Murex team)

3 Likes
#4

Thanks CG for the game, I believe the guys must have spent great effort tweaking the game rules and parameters for maximum fun. :slight_smile:

Because of the fog or war, the traditional AI techniques (those taught at university) seem not a good fit. This throws me off balance and I am not happy with my performance.

Later I realised that the fighting / camping / stealing / symmetry was key, though I had too little time and idea to implement these.

#5

Thanks CG team, for me it was very nice contest.

This time I do not fight for every “ms”, just implement pure human logic, I even haven’t play sandbox for brute force best solution.

I split turn for several modules: stun, bust, attack, explore and so on. Modules have priorities, each module can take as many free busters as it needed. As a result when there is a lot of enemies - explore strategy very often haven’t free busters.

I explore areas just by checkpoints. Take nearest unexplored checkpoint and go to it. Next buster take another one. Checkpoints generated in way, that make ghosts during explore move to my base.

Stun logic also simple, if there is enemy - stun it, if nearby ghost that we can bust - stun only if my busters can take ghost within 10 turns.

Bust also not so hard, just bust until there will be not enough one buster that can take ghost within 4 turn. If enemies nearby - take all possible busters nearby.

Than of course base protection strategy, hide strategy at end of game and so on.

Main idea I just check reply and see, what is going wrong and implement this case, just with “enemies.CanStun(myBuster).LastVisible(0)” and so on.

Thanks again for contest, it was a lot of fun!

1 Like
#6

Ah, forgot to say, Recar, amazing job! :slight_smile:

Actually I was surprised that nobody try implement “herd strategy”, I haven’t time for this, but sometimes I saw random cases that was work like “herd” strategy, and it was looks very promise.

#7

I saw someone using herding, fairly effectively.

They would herd 40-stamina ghosts into their corner and bust them late in the game.

#8

I’m very disappointed with my ranking. I thought I could reach the top 50 but I didn’t even reach the top 200 :disappointed_relieved:

#9

I was super enthusiastic at first with this challenge. The fog of war is really an excellent idea for these AI games. :smiley:

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 :frowning:

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 !

11 Likes
#10

That was a really interesting challenge, with a pretty high level. Thanks Codingame for the experience :slight_smile:

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 :stuck_out_tongue:

  • 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 :slight_smile:

  • 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 :slight_smile:

9 Likes
#11

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 :stuck_out_tongue: ).
  • 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 :slight_smile:

Thank you again for this great contest!

#12

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.

15 Likes
#13

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 :slight_smile:

http://www.gamasutra.com/view/feature/1535/designing_ai_algorithms_for_.php?print=1

1 Like
#14

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!
15 Likes
#15

Every boss had a fixed random seed.

#16

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.

5 Likes
#17

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.

#18

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 :slight_smile: (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 ! :slight_smile:

1 Like
#19

I did the same mistake :rage:

#20

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