Spring Challenge 2022 - Feedbacks & Strategies

#2 Legend

My bot starts with a simple if/else which assigns a role to each hero; the three main roles are gatherer, attacker, defender. Roughly until I reach 210 mana for the first time (or earlier, in some cases), all three heroes are gatherers camping at the 3 spider spawn locations around my base (with 1 of them occassionally switching to the defender role). After that, one hero permanently becomes a defender, and the other 2 become attackers, controlling spiders towards the opponent’s base, trying to use wind combos to damage it, and using control on enemy defenders. When ( if :slight_smile: ) I run out of mana, the attackers become gatherers for a while, then become attackers again.

All the roles work in a similar way - I consider several thousand possible points in the 800 range to move to, assign a value to each of them with an evaluation function and choose the best one; then there’s also a similar evaluation of spell usage (hundreds of angles for control/wind). If spellEval(spell) + moveEval(current position) - mana usage penalty > moveEval(best move), I use a spell. For example, the function that evaluates attacker’s moves rewards being in wind/sight range of spiders’ future positions, moving towards ~4500-6500 range of the enemy base, and setting up wind combos; it discourages attacking spiders and staying in defenders’ wind radius.

You might be wondering how to calculate whether a move “sets up a wind combo”, especially if it’s more than 1 turn deep; however, the idea is very simple: for t = 0,1,2… and for every spider I check whether it is possible to set up double/triple wind with my attackers (just a distance check between my heroes and the spider’s position after t turns) that yeets the spider close enough to the opponent’s base. When I find the earliest/closest/healthiest (weigh those however you want) spider, I remember the areas where I want my heroes after t turns, and the evaluation function rewards moves after which I can still get to those areas in t-1 turns.

That’s all; the rest of this PM will about the meta. There’s no advanced-ish geometry (yes, analytical geometry formulas for attacking 2 spiders at once are cute, but it doesn’t help at all when I’m attacking an enemy base with a train of 8 spiders against 2 defenders), no search (technically, I do simulate spiders’ movement up to depth 50, but I suppose that’s not what people imagined when I said in the chat that I do sim), just if/else and a couple of big cycles. This was supposed to be a relatively low-effort cheese bot that would require people to add some ifs to their code to beat it, but ultimately wouldn’t rank too high, so I didn’t go for anything too fancy. I submitted it in silver, got to rank 1 for a day, and I expected people to adapt quickly and make this strategy completely useless.

However, to my surprise, people had trouble with consistently defending against my strategy, even though it has one (at least to me) painfully obvious flaw: it requires me to move spiders to the enemy base along the edge of the map, where they are vulnerable to getting wind-ed out of the map. What’s even worse is that my opponents could track my mana to know when exactly to get the defender in position, because I need to stop farming mana (I don’t want to damage spiders I’m leading tot he opponent’s base) and I need to start using control. And yet, when the legend league opened, I was still consistently near the top of the leaderboard, often first, and I had not seen anyone defend like that once. Instead, I saw more and more people copying my strategy instead. And every one of them was easily counterable; e.g. early in the legend league, I tested this defense against kouin’s bot and most games went like this.

So I kept this defense hidden; in one of my legend submits I used it for about 50 games, and the day after I saw KawattaTaido push my spider train off the map, so maybe they had seen my games or someone finally realized that it’s possible. Still, it didn’t become widespread and I decided to see how far can I get with this joke of a strategy. I had a solution for bots that use 2 attackers; 3 attackers aren’t really that consistent to consider them a threat at the very top of the leaderboard; having no designated attackers might be theoretically optimal but it’s a very impractical way to play, because you need to be consistent against every cheese out there to climb the leaderboard, while I only had to come up with one. That meant I had to optimize against players who used only 1 attacker.

The problem appeared to be that 1 defender can’t defend against 1 attacker’s doublewind or control efficiently. Sure, I could keep shield on and wind away monsters, but then I would take longer to gather mana for the attack, and I would give my opponents more opportunities to damage my base in ways I couldn’t prevent just because of fog of war; another less obvious problem is that if I execute the 2 attacker push later, opponent’s defenders will be closer to their base because it’s simply no longer possible to kill spiders close to the spawns as their hp increases with time - and if my opponent’s defenders are already in place and shielded, ready to push both the spiders and my attackers back (not necessarily out of the map), there’s at most 30% chance for the attack to succeed. #1 managed to win about 75% of the games against me mostly because he pre-positioned his defenders (it’s not overfitting against me if it works…) even though his winds blew in a wrong direction.

The best way to defend against 1 attacker was to not let the spiders that target my base to get there - and use wind or control if I can’t do it only with attacks (each gatherer was placed at one of the 3 nearby spawns, as I wrote earlier, and took care of spiders that spawned there); I also used a simple prediction of the attacker’s movement to estimate which spiders will be seen by the opponent and I stopped only those spiders that the attacker will see or that will enter my base, and I didn’t care about losing hp due to my heroes getting controlled - better than delaying the attack by being overly cautious, and it costs quite a bit of mana that might be missing in defense later. I took damage quite often, but I rarely lost before I could launch my attack.

I submitted my final version about 12 hours before the end of the contest (I didn’t want to risk because of recent ISP outages, so instead I just submitted early and watched some games to make sure my final version didn’t have some huge bugs) and I was first at the time; I was no longer hiding that I could defend against 2 attackers, some players saw the “counter strategy” and used it against me. The wind has turned against… the edge of the map. However, even if I had kept it hidden, I believe I wouldn’t have beaten bowwowforeach - he managed to refute my unsound attack even without it. Maybe some of the players came up with it on their own (I hope they did), and it didn’t help that much, because people couldn’t just dramatically rewrite their defense in the last few hours of the contest (and I also imagine they had better things to do than countering my bot last-minute).

What probably would have let me win the contest is abusing bugs, as seen in this replay; considering that the game was made, like, 4 years ago and it has been used before for private teambuildings/hackathons/whatevertheycallits, one would expect no gamebreaking bugs or wrong input, but… well, the game was nice, I liked that it tried to promote playing actively over turtling, and if it’s ever used again it will also be sufficiently tested.

52 Likes

Language: C++
League: Legend 282nd global (1st national)

I only created my CodinGame account a month ago because a friend from an informatics olympiad camp invited me to join this challenge. I don’t regret joining. This is a very new and unique experience compared to competitive programming I’m used to in Informatics Olympiads.

I’m very new to bot programming and my resources are limited. Hence, my final strategy is simple without any heuristics whatsoever other than hardcoded values.

Final Code Main Idea

I split the game into two phases: farming phase and attacking phase. My three heroes farm for mana for the first (approximately 50) turns, specifically after X mana has been collected. In my final code, X is 160. I’m not sure what a better number would be. The farming phase consists of two heroes roaming in the middle of the map and a hero making sure that the base is safe from attacks. The farming phase is simply “I see monster I catch”. I’m sure my solution is very suboptimal in this phase as other codes gather mana in a faster pace.

The next turns, the two roaming heroes come to a spot near the base, controlling up to 5 monsters with them. The monsters are controlled to a spot 1040 units to the back of the heroes. The spot where the monsters will be, the spot where the heroes will be, and the opponent base should be colinear. The controlled monsters should be guaranteed to reach their positions before the heroes to avoid mana wasting. After a monster has reached the designated spot, two turns are used: one soft wind spell and two hard wind spells, pushing the monster 6600 units away to the enemy base. Then, the heroes patiently wait until a monster outside the enemy’s base is in CONTROL radius, and the process repeats. The other one hero does a classic defending operation using WIND spells; probably similar to the codes in wood 1 league.

Clearly in my strategy, the attacking side is way more powerful than the defending side. Hence, I gave the offense a mana usage priority. I precalculated the amount of mana the offense will be using for the next 2 turns (in case of soft + hard attack) and prevent the defense to waste mana. I also added a mana cap to make sure that the defense does not use too much mana by using health as a parameter. The less health you have, the more dangerous it is, so the defense is allowed to use spells even if mana is low. The less health opponent’s health is, the better the state of the game is to our side, so the defense is allowed to use spells when mana is lower. I could give more priority to our health over opponent’s health considering how weak the defense is, but without such optimization my code reached legend league, so I didn’t bother

Here is my strategy in action

What to improve

There are a lot of things to improve that I didn’t implement either because I was buzy or because I was lazy:

  • Dynamic attack movement: Don’t just stay at one specific point.
  • Accurate value calculation: There are a lot of things I can say here:

    I only eyeballed the spell vectors. I only did things like “SPELL WIND opponent_base_x opponent_base_y”.
    I disregarded the vector movement of monsters and I just straight up do “MOVE monster_x monster_y” which I’m sure is far from effective

  • Defense: Yes. A bronze league strategy in legend league. Very funny.
  • Farming: As stated, my farming strategy didn’t yield mana as fast as others.
  • Monster tracking: After speedreading through some of the comments here, I just realised that monsters can be tracked due to the symmetrical nature of the game.

Final Words

It was a very fun experience. Before the challenge, I tried mad pod racing and spring challenge 2021 and reached only gold league. I was glad to made it to legend for the first time.

The game is very luck and meta based in my opinion. I don’t think there are perfect strategies that can counter every other strategy. When I submit my code in the arena, I try to reroll until the initial 10 battles have at most one loss. This is because the lower ranks have implemented counter strategies to the above ranks, which was a little bit annoying to deal with.

There are times (especially few hours before a new league was going to be opened) where the arena runs slow. That would be understandable, as I get how heavy the computation of the games are. I’m already used to long queues from other competitive programming sites haha.

I also wrote a blog that tells my whole experience joining this, including my flow of thinking starting from wood 2 to legend. That would be published probably few days after the challenge is imported to the problem list.

Thank you for the challenge!

6 Likes

That’s a very nice bug you got there :smiley: I checked for it so I’m not sure how I missed it, I thought wind didn’t affect mobs outside the map :frowning:
Well, now I know what I should try when the challenge opens as a bot battle.

I even explicitly added checks to not wind mobs before they enter the map…

after I decided not to hide, I reported it and it was fixed… on Tuseday or Wednesday

7 Likes

Thanks for the challenge, it was pretty fun.

Although, in the end I had a very mitigated results (middle of the silver league), I’m pretty happy with the code I produced.

I didn’t see anybody tried to solve it how I did in the comments, so, I’ll describe my solution.

Overall objectives

My objectives were pretty simple, to find a scoring method to determine a few key aspect of the game state via:

  • a danger score
  • a scout score
  • an opportunity score

I managed to get a pretty good danger score, but not the other one. That means I was able to defend but nothing more.

Having the danger score at turn t, the turn resolution is simple: simulate every possible and sensible solution for the next turn, recalculate the danger score at turn t+1, and pick the best options.

This work pretty well for my 3 heroes in a defensive stance, being able to use the wind right when needed.

However, it’s pretty bad at winning the game, as, having not implemented a scouting score, my heroes stayed pretty much near my base and I usually loose to not having enough mana.

This also failed against more aggressive player, that disrupted my defensive formation.

And finally, this is quite a greedy solution and it fails to give answer in time some times. So implementing more score/decision in the process would have required a bit of optimization/refactoring.

3 Likes

**Legend #90 **

1) Data Structure:
I have an array of monsters for each player separately based on the threat_for variable. This helps me to focus on the threat monsters first and neutral monsters later.

2) Sorting
Sort all my monsters based on distance to my base
Sort all enemy monsters based on distance to his base
Sort all neutral monsters based on distance to my base
Sort all enemy heroes based on distance to his base

3) Art of Defence - 2 Defenders

Both my defenders guard two points GUARD1 and GUARD2

GUARD1 = Point(3600.0, 6500.0);
GUARD2 = Point(6800.0, 2000.0);

if (turn > 20) { #be slightly more defensive after 20 turns
	GUARD1 = Point(3600.0, 5500.0);
	GUARD2 = Point(5800.0, 1000.0);
}
  • Intercepting monsters - not chasing - This makes a huge difference at gold as this increases the win rate drastically especially against players with equal strategy.

  • Keep the guard - Always keep both defenders closer to either GUARD1 or GUARD2 (by 2200 distance) or closer to the base (9000 distance). Allocating 1 hero to each GUARD is not possible in the late game since monsters health is huge and they appear randomly and 1 defender cannot kill all the monsters coming towards a GUARD. They have to often go to the other hero’s GUARD either to kill the 1st closest monster to the base or the 2nd closest monster to the base and work as a team.

  • Focus on killing the first monster - Always let the closest defender (I call him the 1st defender) go after the first monster as it’s the most dangerous monster that could cost us a life. Use the next defender to either go after another monster or GUARD based on the danger level of this first monster.

  • CONTROL for defence - I’m kidding. I never use CONTROL for my defence. 1) It’s not an AOE spell, 2) It’s push distance is very less 3) It’s not effective in the immediate turn. The only time we would need a CONTROL is when the monster is going to damage our base and there is no way to kill the monster and the monster is out off range for using WIND. The chance for this was less than 1% and it never happened in any of my games even though I’ve this case programmed.

  • WIND only on the first monster - WIND is the only defense that’s actually required to defend our base and it’s always effective if we use it only on the first monster. If the monster is shielded there is no use in WINDING other monsters because we should use the time in killing the shielded monster than using WIND on another monster.

  • Always attacking - less walking - Our defenders should always be farming and walking less. Watching more replays and fixing team work among defenders helped me improve on this part. To avoid a hero going too far from his current position, I ignore defending with the 2nd defender when the 2nd defender is too far from the monster (say 3000 distance)

  • Knowing when to give up If I can neither intercept a monster nor use CONTROL spell on it’s time to give up on that monster. I assume it’s dead and ignore it.

  • Parallel farming There are cases when the two closest monsters are very close to each other (i.e. < 1600 distance) in this cases positioning both our defenders in between these monsters will do 2 damage per turn for each monster by each defender. i.e. 8 damage per turn which is nice.

4) Art of Attack - 1 Attacker

  • Double Wind I didn’t want to complicate my wind calculations by doing a cross pull to keep the monster in vision and do a second push. Instead I move my hero ahead 1279 distance ahead of the monster so that I can use the double wind effectively.

  • Tracking the monster that I wind
    As I’ve only one attacker and I only wind 1 enemy monster at a time, it’s easy for me to track it in the next turn even when it’s not in my vision.

  • Farm with attacker on low mana. NEVER help the enemy
    I never hesitate to farm with my attacker when I’m low on mana. But I made sure that he never ever helps in enemy defense i.e. to damage a monster who can be a potential threat to the enemy. (i.e shielded monsters, monsters with less than 2 health (Killing it reduces the number of threats for enemy).

  • Shileding This is the most OP skill in the game lasting for 12 turns with no counter except by killing it manually using defenders. I use it only when I know this shield lasts until the monster hits the enemy base and also only when 1 defender is not sufficient to defend this SHIELD before this monster kills opponent base making it a killing blow. Making both enemy defenders constantly busy keeps the opponent under pressure and gives them less vision in the map.

  • CONTROL Enemy defender cannot defend for a turn and he will be pushed away. Should I say more?.

5) Customized defense against 2 attackers
When I see two attackers closer to my base I name this opponent as a sneaker and store in a global variable. For this opponent I spam a lot of winds on the enemy attackers and even chase them when they come closer to my base. This did not work well against top level players like Blasterpoard whose attackers CONTROL me the moment they see my defenders. But it worked against most other players with two attackers as they often hesitate to use control or shield themselves as they are usually in less mana.

6) Protection against enemy CONTROL (Rare scenario)
When enemy attackers control my hero it’s often pretty scary and most likely lead to monsters damaging the base so I self shield my defenders when I have a large quantity of mana and monsters are threatening my base and the enemy has a good opportunity to CONTROL me.

To sum it up I had 193 if statements in my code and it was fun filled contest. Only feedback to CG is to increase the speed of servers as the submits are often too slow during contests. I say this besides CG being the best platform available for us to learn and test our AI.

11 Likes

Congratulations, especially using scala!
I may already asked you that but how do you avoid JVM warmup?
I tried scala in contests but it ended up in timeout, because either warmup or me using wrong time measuring functions. I switched to go or c++ for simulations.

Top 29 legend.

Really glad to make a good result for the first challenge I play seriously. First I would like to thanks the community (especially the french one) which was really kind to discuss with.

During this challenge, I explored different strategies. First, I quickly understand that farming was key in this challenge. In the early game, I position my heroes on farming points (top and bottom) and I try to select a point damaging multiple spiders. I did not decide to use maths to find the best farming point, I simply tried hundreds points and select the one which is closer from the farming point and hits the biggest number of spiders. To test that bot, I implemented a naive triple wind attack. This strategy was just enough to climb legend.

I then tried to switch the attack with a “blasterpoard” strategy. My lack of organization and practice made it really hard to implement. I finally made something playing good enough (double wind for kill, pass to double wind, control enemies in defense…) to beat blasterpoard bot quite often in practice because my farm was a little better and I managed in most cases to attack faster. But I was only losing against lots of legend bottom players for different reasons.

I didnt have enough time to improve my bot on multiple aspects. My bot has a really bad defence, I did not work a lot on that point. But more importantly, if I don’t win after the attack, the game is lost because my attackers dont go back to farmer mod… I will try to do something better when the multi will be out.

See you in the next challenge !

8 Likes

Legend, 55th

Thank you CG for this contest!

I did not want to write a heuristic bot, so I tried to sim it despite the action space / hidden information.
Started with a MC like wlesavo, then switched to GA to try to better combine strategies for heroes.

Instead of actions, I tried to accomplish simple objectives (KILL a random mob, move to a random mob and WIND/CONTROL it, etc).
My evaluation was a combination of mob threats to bases, attackers/defenders distance to base, etc.

See you soon in the multi !

19 Likes

It was my most stressful contest so far.
I went full simulation, with a beam search for each hero, because ending up lost amongst ifs during code a la mode wasn’t fun.
As the days went by, i was more and more worried i’d made the wrong choice. Looking at the heuristic bots doing so well, with so many strategies, and mine not making the cut at the silver and gold opening and time-outing at depth 1.
But last Friday, with a more aggressive strategy (following the most dangerous mob in the opponent base) and avoiding pushing mobs when there’s almost no chance to score, i suddenly reached legend and the top 50. Then there was 2-3 days to work on strategy/evaluation and looking at the top bots.
It wasn’t enough (the last Sunday, with the slow submits, is useless).
I’m glad i ended up 21 but surely a bit disappointed considering the work and stress involved. I will keep trying it as a multi but without the contest hype…

I started with the referee code, “cleaned” and optimized it by removing all streams, collections, object creations…
I used two defenders (ids 1 and 2) and one attacker.
My beam search has a width of 50 and a max depth of 4. For the first iteration, it tries every 20° angle for 400 and 800 length. 30° and 800 after. Plus the spells for only one direction or one target. Plus some special moves : move toward player or opponent base, move just behind the closest mob to opponent base to be able to push it without hitting it… Some moves ae only for attack or defense or the first iteration.

I would have like to try :

  • different beam search width and depth.
  • different angle and length.
  • using the beam search to find the opponent first move.
  • having 2 attackers and 1 defender.
  • taking the mob’s speed into account when calculating the number of round between it and a hero (can he even reach it?).
  • avoiding sending 2 heroes on the same mob.
  • defeating top players strategies (against double or triple wind my bot will almost always loose).
  • using the shield efficiently.

So a lot of ideas compared to the last contest where i was easily done 2 days before it ended.

Anyway it was a fun contest. Congrats to @bowwowforeach for becoming a new legend. Thanks Codingame. Those AI challenges are the best. But once a year, really, with all the great multis from the community ?
PS: i miss the contest and boss funny names.

18 Likes

31 Legend
A positively unexpected ranking (as last year I reached 1700). So I hope this PM will motivate some other beginers to keep on participating to CG Challenges !
Wrong approach : GA with too few generations
I tried to simulate next turns with random moves, and optimize the solutions with a GA. With less than 10 generation at its peak, heroes had a sense of priorities for mobs entering the base range, mixed with a shaking randomness. I re-engineered the data structures with the hope of a beefed up simulaitons. Leading to a 30ish generations per turn. Thus, I didn’t bother adding spells to this soup. And in the end, I was not really sure that a simulation approach could have an easy sucess due to fog.
Better approach : Simple Heuristic based on the best ranked submissions, improved untill the last day
I resigned this first approach on Wednesday and went for a only heuristic approach, highly inspired by the Arnaud. net 's strategy that was leading the challenge at this time. 2 defenders, 1 attacking hero.
Bronze - to mid Gold, with MOVE and WIND. Adding CONTROL to the attacking hero pushed to top Gold, and some sneaky SHIELD for mobs near the base pushed me in mid Legend during Thursday night. Given those first results, I kept this strong base and spent the last days on correcting the unexpected behaviours or striving for a more efficient use of mana. Here are some key features :
1 Attacker :
⦁ After WINDing a mob out of your sight, keep track of it in the game loop for next turns. It will be surely a priority for you (to wind or shield), or it will tell you to control other heroes going to this hidden mob.
⦁ If enough mana and nothing more interesting, put a SHIELD on. Some defenders can be unfriendly.
2 Defenders (with the remaining mana) :
⦁ Send the nearest hero to the mob, it is not always the first in your output sequence. Don’t send everyone farming one bot, if one heroe is enough, otherwise you will reduce the time you are earning mana (by increase transportation time between mobs), and reduce map visibility. Given the mob aimed, is there more mob that can be attacked at the same time (use of barycentre).
⦁ When two oppenents have been seen near my base, wind them away (there are surely preparing a double or triple bam)
Conclusion :
⦁ Throwing away a bad approach can be hard if you have been putting efforts into this direction. Don’t get too emotional about your lines of codes. You are keeping the new knowledge you have earned on the problem.
⦁ Throwing away a bad approach is also an opportunity to rebuild a cleaner code and data structures ! That will be much more easy to improve your code once the new solution will be working. I would love to win more clean code skills untill next challenge.

Thanks to CG team for hosting such diverse games over the year, and to players for their feedbacks, it is always a pleasure to discover the diversity of your solutions ! I hope that with more practice on CG, during the next challenges I will be able to focus more on finding creative strategy (or maybe implement a descent python simulation based bot :grin:).

12 Likes

For this challenge, I had no issue with JVM.
Otherwise, you should warm-up the JVM (e.g. by doing precomputation) before reading the first input and you should limit as much as possible memory allocations to avoid GC pause.

4 Likes

Hi, I started this challenge with a basic idea: two defenders and one attacker, which become a rusher in my last version of my code.

All my change for my AI was to make my attacker more aggressive and faster because 90% of my lost was a draw because I did not succeed to farm wild mana well. Each time I saw a replay with a draw, I understand that the farming is not for me. It is why in every change of my AI, I chose to get my attacker more aggressive than ever before to goal/win faster.

My first strategy farming before attack (=> send/control monster to opponent base) was not enough against the boss 5 (gold => legend) that why I decided to rewrite all my code to overcome boss 5 and try to become a legend.

My way from bottom gold to the legend league (rank #30)

I began a brainstorming on my notebook, and I keep in my mind a thing that I saw, we can double wind a monster with only one hero (cyan border in the circle of my schema).

This two schemas show monster direction after spawning and the range of the different spell/view/attack.

After my brainstorming, I get a new strategy:

  • 2 defenders and 1 rusher, he will play soccer with double tap.
  • Defenders:
    • Write a “brain” for my base which will decide the action for my two defenders. This brain will consume the lowest mana as possible and kill the spider as soon as possible. It will not do waste action and mana (I will let a spider go to my base if I can’t kill/wind/control with any of my heroes).
    • I also write a custom event for my code: CATCH, this one will directly go to the catch position. I calculate the exact position of where will be the spider and the time necessary to get it. (Multiply the number of turn by the hypotenuse (x: hero speed ; y: target speed) to get the time/distance increased in the way).
    • With circle and vector collision, I increase the threatFor (at 6000px).
    • If my defender do nothing, they will farm and go in the jungle.
  • Rusher (Attacker):
    • Goal as soon as possible and commute between two points in the opponent base to increase chance to see spider (=> but this was easily counter by opps).
    • Try to double wind with the border of the spell range 2580 and the distance winded 2200, we have a range of action of 360px.
    Normalize (reduce to 1) vector to multiply with the distance that you want to do

    Vector math — Godot Engine (stable) documentation in English

    const magnitude = hypothenus(opp, ball.pos)
    const oppGoal = relative_xy(MAP_WIDTH - 200, MAP_HEIGHT- 200)
    const vect = xy(
        (oppGoal.x - ball.pos.x) / magnitude,
        (oppGoal.y - ball.pos.y) / magnitude
    )
    

When I click on the button to try my code in my first try/fight to the boss 5, I did not expect to go to the top of the legend with this new strategy.

I tried to improve my script, but that was not efficient. If I change, I need to rewrite some part, like a better defense against blast and keep in mind low mana consumption, seedfinder to farm and control spiders with my defender before rush. I am curious to try my code with seedfinder, I started a mirror spawn function, but I didn’t use the result in my code because there is too rare case to be implemented, but will be helpful for triplewind.

(I am French, I hope to write this message in a good English)

NB: You can use cosinus to commute between two points without a loop:
number_points = dist / 800
frame = number_points * (cos(current_turn / PI * 10 / number_points ) / 2 + .5)
way = dist / number_points * frame
14 Likes

I was hyped for this competition and it delivered, thanks CG!

Bottom of legend.

I started with sims and a GA but couldn’t get proper evaluation functions, I couldn’t get out of the bottom of the gold league. During one submit I was pitted against a triple-wind canon bot and I thought “why not”. Turns out it became rather infamous and that actually added some fun for me to make it work.
Getting into the legend league took some fine tuning (faster & more mana friendly attacks, better crowd control prior to reaching the attack position).

Please CG, bring back proper pop-culture based boss names! Boss 1, 2, 3, 4, 5 was rather dull compared to what you usually come up with :slight_smile:

10 Likes

Rank: Legend, 171st in World, 30th in Japan
Language: C++

I write my solution because (despite of my rank) I thought that some part of my approach is somewhat unique.

1. Overall Strategy

I implemented a “mana collection” → “3 attacker” strategy, which is one of a common approach (similar to tkodai’s one). The outline is as follows.

  • First ~40 turns: While collecting 150-180 manas, the heros (practically) only concentrate on collecting manas as soon as possible.
  • Next ~10 turns: Move 3 heros to coordinate (W-7700, H-1300), along with controlling some nearby spiders to this coordinate.
  • Next ~10 turns: Throw 3 spiders by WINDx3 or WINDx1 → WINDx3.

2. Algorithm to Collect Manas

The unique part of my solution is when collecting manas.

One difficulty of this problem is the “fog of war”. If all information (including the angles of generating spiders) were given, we can collect manas efficiently by, some ways like following:

  • Decide the destination (target spider) of heros, with a greedy algorithm, so that the mana-collecting efficiency is maximized
  • Run a beam-search, and maximize the number of manas collected in next certain number of turns

However, this game is not easy like this, because the only the very part of the information is given.

So, I came up with a Monte-Carlo-like algorithm, that generate “random” samples of tracks of each spiders (including the time of spiders’ death), to be consistent to all past informations.

You may wonder how it is possible, because it is difficult to predict the opponents’ future actions. It is especially true for two bases (radius <= 5000). However, for outside the bases, we can “approximate” the probabilistic process of spiders, like roughly following:

  • When monster reaches opponents’ base, it will die with 60% probability, and controlled to my base with 40%.
  • Otherwise, it will die with 5% probability, it will be controlled to my base with 2%, and nothing happens for 93%.

(The estimation is very rough, I should have done more statistical way for this.)

When we’ve successfully taken random samples, we can estimate things like “the expected profit when a hero comes to (x, y)”. My program chose the directions of each heros greedily so that the expected “profit” is maximized. (Note: I wanted to do beam search, but the 50ms time limit didn’t allow this.)

Here, there are so many numbers of tracks of spiders, it takes time to find a consistent track, and the number of target coordinates (x, y) to search is quite big. However, with some improvements on time compexity, it was possible to execute in time with 100 samples, and could brute force for all (x, y) = (100m, 100n) (m, n are integers).

When I apply this algorithm purely to mana collection, It gathered about 170 manas in 40 turns, and 500 manas in 100 turns.

(I think this kind of Monte-Carlo-like estimation algorithm, can use all information given before, so it may be sometimes useful for “partial information” games. Though I think there are so many improvements for this scheme…)

Thanks CodinGame for hosting this event! For me, it was the first time to compete in this website, but it was very fun.

10 Likes

156th Legend

Implemented two common attackers and one defender.
I didn’t do a deep search, so the efficient positioning simulation did a full search with several angles and velocities.

3 Likes

Finished 11th (somehow reached 1st before final recalculation :upside_down_face:)

Till top-100 gold I used heuristics only full defense bot, it was unable to reach gold boss, despite beating him constantly in IDE.

Defense heuristics:

  • Heroes are allowed to hunt spiders only in range max(base_nearest_enemy_distance, 8500), or else go to their default points
  • sort all spiders by their “threat level” (time_to_reach_my_base - (hp + 1) / 2). Time calculated through movement simulation
  • greedily assign nearest hero to the most dangerous spider (calculate the point where spider can be reached in t turns and find the hero with minimum t)
  • if spider cannot be killed in time, try to push him instead of attack
  • if meet point inside base attraction range, push spider outside to gather wild mana
  • if there’s an enemy in sight try to control it to map center
  • also check if spider cannot be killed with one hero and assign two in that case

In legend these heuristics changed slightly:

  • allow enemy hero control only if 3 enemy heroes are near my base (trying to prevent triple wind push)
  • do not push spiders outside for wild mana, cause it doesn’t matter anymore

Also, I use “mana gain maximization” concept: given constraints (point, range, and time in which we should be at least on a given range from that point) try to slightly change trajectory trying to maximize spider hits. Here I use simplified simulation without health consideration, which allows using bruteforce with 12 movement points on depth 3 without noticeable time impact.

The main advantage which gets me to top legend is attacking using search algo. I use bruteforce for 4 depth, with a fixed set of movements:

  • wait
  • move to 8 directions with maximum speed
  • use wind on the spider nearest to the enemy base
  • use control on an enemy, closest to his base
    Also tried to use a shield on monsters, but discarded it due to periodical timeouts.

As an evaluation function at first, I tried to account enemy hp and mana, but this doesn’t work at all, cause of the small search depth.
So I end up with scoring function below (here lerp(v, from, to) means clamping value in range [from, to] and lineary interpolate into range [0, 1]):

  • (1.0 - lerp(enemy.hp, 0, 3)) * 3000
  • extra 10000 bonus, if enemy reaches 0 hp
  • lerp(my_mana, 0, 100) * 50.0
  • very small bonus for moving in point on enemy attraction range,
    motivating move when nothing more to do
  • bonus for winding spider into enemy base
    10 + lerp((my_mana - enemy_mana) / 10, 0, 5) * 100
    means the more our mana advantage, the more aggressive we are trying to push spiders
  • for each spider in enemy attraction base,
    calculate spare_time = time_to_reach_base - (hp + 1) / 2, and give bonus proportionally 1.0 - lerp(spare_time, -1, 4)
    • if spider in our wind cast range and not shielded increase bonus by 1.5
      (solely this condition pushed me into top legend, I guess it motivates a hero to be in a nice push position after the search ends)
    • give a bonus when nearest to the base spider is out of enemy view range (motivate to control enemy out)
    • give a small bonus if the spider is in our view range (motivate to follow and make sure it reaches base)

Given the very small search depth, I spent many hours tuning the scoring function, trying to hint good future positions for search.
Using lerp function, allow me to easily set desired behavior such as “try to push spider, but if low on mana, try to farm instead”.
For enemy prediction, I use a simple approach: go to the nearest spider and use wind, if a spider is too close to the base. It helps with using control on an enemy, in other cases, I didn’t notice any effect compared to “wait” actions.

Also, I use tracking (move spiders in fog) and symmetry (if a spider is seen the first time, create his sibling in a symmetrical position). Tracking can be done quite easily: just check position and remove those who should be visible but not given in turn input

Big thanks to Codingame for that contest, it’s nice to again compete and chat with all of you :slight_smile:
Also, this game has a really simple simulation and allows different approaches to strategy, which is very friendly to beginners.
Pretty satisfied with my rank, despite falling so fast during recalculation. Touching first place was the first such experience for me, I definitely do my best to stay there longer next time.

25 Likes

Rank: 349th Legend, 2nd in Spain
Language: Java

Hello, my bot is so simple that I feel ashamed after reading your strategies.

Essentially my bot is a huge collection of “if - else if - else”. I used a two defender - one attacker strategy with a lot of trial and error and tweaks after watching my games. The key to my rise to legend was when i started to send my attacker to a spawn point to recollect mana and after 100 mana start to attack.

The attacker bot is pretty simple, wind spiders into enemy base and some control on enemy heroes. If there are spiders near the enemy base he chases them to use more winds. I have a list with the most dangerous spiders for my enemy and the attacker bot chases that spider. I failed trying to implement a patrol system, i did it and it seemed to work well but the rank was 200 positions worse I don’t know why…

The defensive strategy consists of the two bots chasing the two most dangerous spiders, each chasing the one closest to him and using wind if the spider is too close to my base.

All this in just under 300 lines of code… I had a great time but after reading you it’s clear that I didn’t stand a chance, in fact I don’t even know how I got into legend. Can you recommend me some resources to improve for the next events?

Thanks!

5 Likes

Rank 35 Legend, Python 3. Heuristic script of ifs.

Many thanks to CodinGame for making this possible, and my competitors for such a fun competition.

People whose bots I watched and gained insights from (I watched a lot of games between lots of bots but these 3 in particular I benefitted from observing at key stages of the competition):

Main ideas:

  • 1 attacker, 2 defenders.

  • Start attacking as soon as possible (important for vs 2 and 3 man rushers using the wind stack mechanic)

  • Don’t chase lost cause bugs which you can’t stop from running home in your base

  • Don’t shield your heroes or enemy heroes (shielding yourself is a net loss because you spend mana where they never bother wasting mana on spells when your shield is up, and even then they can wait for their chance in the 1 turn your shield is down and you cannot replace it). Credit to @Husenap for his cool strat where he shielded enemy defenders so his attacker could windspam spiders past them.

  • I had a default formation where the 2 defenders prioritize spiders within my base, and wind them when they’re close to my base (which becomes more generous with winds the more enemy attackers there are), and outside of the high priority base spiders, they also had a permitted wander radius looking for spiders to farm/defend against within radii of hotspot points.

  • The attacker had a patrol path much like @Arnaud.Net . One specific detail about my patrolling was that I kept it on a fixed period of 8 turns rather than ‘when you get to your destination, switch destinations’ - instead, the destination switched every 8 turns.

  • I had a special formation if there were 3 attackers where I would send the two defenders off to 1) the ‘problem’ corner of the map, and 2) to follow around the enemy trio

  • @blasterpoard seems to think he was the only one to pioneer the idea of sweeping spiders off the map at the edge, but I had that in my script for the last 3 days or so. It is helpful, but evidently either I could have implemented it better or other things were also important that I failed to do well. In short, if your defender heroes are near the board edge, instead of winding spiders towards the enemy base, wind them off the map. Also, if you are about to wind spiders defensively, if you can avoid winding them straight into an enemy hero by winding them horizontally or vertically instead, do so.

  • Attacker controls spiders into enemy base sometimes, he also controls enemy heroes who are defending well. He winds spiders into the base sometimes, and he winds them home when in the base. If he has just winded or done something important which means a spider might be ‘runnning it home’ within the enemy base, but i cannot cast a spell on it, I either chase the spider closest to the enemy base, or I run towards the enemy base.

  • I very rarely used shield, I only really used it with my attacker on spiders running it home in enemy base if it guaranteed they’d score.

  • Attacker would also leave his patrol point sometimes to get the nearest spider in some situations.

  • Devil being in the details: farming positioning, attacker positioning:

Defender farming:
Rather than just making a beeline for a specific spider of choice, if I could find a trio of spiders with a hotspot to stand in which lets me hit all three and one of the trio is the spider of choice, I do that. And if there is a spider next to my spider of interest and they are within 1600 of each other, I stand in the midpoint of them.

Attacker not killing spiders running home:
Make sure to offset my position next to spiders I am trying to get into the enemy base: if i am further away from the enemy base than the spider, stand a fixed distance behind it, if i am already between enemy spider and the base, stay ahead of it a fixed distance out of melee range.

  • My defenders would wind defensively on spiders within trouble distances

  • My attacker would not only wind spiders in various ways but also sometimes wind defending heroes away into the middle of the map.

  • My attacker would also specifically wind spiders in the direction which takes them directly towards the enemy base, not just “SPELL WIND {0} {1}”.format(enemy_base_x,enemy_base_y).

Thats it. About 635 lines of crude code, which could have been written better, but was ever evolving and had various bits repeated in slightly augmented forms in order to preserve a sense of priority.

Other minor points: tracked my own mana throughout so that i would never try to cast something if i couldnt cast it, never tried to control something if it had a shield up.

This could easily be improved upon, there are tons of things I didn’t do that other people did.

Thanks to @jar for as always being a great rubber duck/sounding board, he also made legend with a completely defensive bot, no attackers.

I spent a lot of time on this contest because of my obsessive nature and it coincided with a holiday, but I fell ill in the last 2 days which basically had me bed ridden, but also it was difficult to do much rigorous testing because the calc time was pretty slow, so if you made a change and wanted to tested you had to basically go afk for an hour, but whilst I complain, I still appreciate everything CodinGame do, and even if this issue is not fixed, I have no doubt I will be back.

10 Likes

With my bot I decided to go with a two attackers one defender strat, because (at the time) nobody else seemed to be doing that.
My bot was sorely in need of a rewrite by the end, however I ran short of time so I continued with the original.

Some of the features I implemented were:

Defence:
-Spider n-move prediction and interception.
-Spider health-per-tick before reaching base post-interception.
-Maximal-clique based enemy group targeting.

Both:
-Implementation of my own ‘threat_for’, as the provided one was bugged (might have been fixed?)

Attack:
-Dynamic selection of raid members based on task value.
-Control and shielding of enemy heroes before a spike into goal.
-Enemy defense estimation for how my attackers should act, e.g. self shielding, acceptable spike distance, etc.
-Patrols to get clear of enemy heroes for a clean spike.

Farm:
This build was hyper-aggresive and it was always a delicate balance between executing a raid quick enough, and bringing enough mana to finish the enemy off, as my defence could not last into the mid-late game.
Due to this, farming was of utmost importance.
Initilially I would send all my units to the borders to intercept incoming spiders, which as well as generating mana, would keep the spiders away from any start of game enemy attackers lurking near my base.
The spider clique-finder helped with this as well, as a minimum of heroes could be pulled to defend while the others were utilised for farming.

Final word:
I enjoyed this challenge very much and it was interesting to see a large variety of builds.
This was actually my first challenge and I only started a few days in, so next time I’ll see if I can be in early.
Good game everybody, and happy coding!

4 Likes