(Early warning that there are spoilers related to my solutions of the challenge itself. If you are interested to solve it, I recommend doing it on your own first.)
Aqua: "Our team name is Ponkotsu☆Stars!!!"
Towa: "..."
Suisei: "Hm?"
Aqua: "What? Why are you all silent every time I bring up that name"
Towa: "..."
Suisei: "Hm?"
Aqua: "What? Why are you all silent every time I bring up that name"
(TL: Ponkotsu means clumsy)
「Prologue」
It was a programming website. Nobody from the competitive programming communities I was in talked about this website, because this website is different from other online judge websites. I see the usual algorithm problems that appear in regular online judges like CodeForces and AtCoder, albeit the quality of the problems aren't impressive to a competitive programmer who trains IOI and ICPC problems daily. However, the bot programming section looks very interesting.
The bot programming system is fairly simple; given information of the current state of the game, output the queries you (as the player) should do to win. It is basically an interactive problem, but our code's score isn't objectively determined by a judge, but is decided by the code's ability to fight against other player's codes.
Before the challenge, I grinded CodinGame to get a good grasp of what to expect during the challenge. The Clash of Code section isn't a big of a deal since I'm used to speed-solve easy problems in CodeForces. The Optimization section is a bit hard for me as heuristics related to AI and ML aren't that famous in OI or ICPC. Same goes for the Bot Programming section, however I managed to get gold league in Mad Pod Racing and Spring Challenge 2021, both using only the competitive programming skillset I have from grinding Olympiad problems.
After 18 days, I got these cute certifications:
Here is a link to my full CodinGame profile. Nothing special to see.
Now I would like to tell a story about something that's somewhat cringe and unrelated to the challenge.
Around that time, I was also watching a V-Tuber Apex Legends tournament. My favorite team was specifically a team consisting of Suisei, Towa, and Aqua. It was a roller coaster of emotions watching them grow as a team. They named themselves StartEnd. closely related to how that was Suisei's and Aqua's first Apex tournament and probably the last too. For those who know and play Apex Legends (I don't), Suisei plays Valkyrie, Towa plays Gibraltar, and Aqua plays Wraith. As far as I know watching them play, Towa's role was as the tank and defender of the team, creating defensive domes, Suisei's role is some sort of fight or flight thing with Valkyrie's ability to fly, and Aqua... uh you can see for yourself how a mad dog she is. Her plays are so aggressive! As expected from the solo-rank Master.
No, you are not required to watch the whole thing.
Anyways, watching them was very fun and I enjoyed the arc. They even made an Asu no Yozora Shoukaihan song cover that I still listen to. I recommend listening to their original songs and covers. I usually listen to them when I code as well!
In what ways is this hold any importance to my experience in the Spring Challenge? A lot actually.
「Wood League」
I opened Spring Challenge 2022 an hour after start because I was too busy playing TETR.IO, a "modern yet familiar online stacker" game. The premise of the game is to "Protect your base from monster attacks and outlive your opponent". Lots of details are already given at the start of Wood League, which is a little bit overwhelming.We are to control three heroes and protect the base. Wood 1 only requires us to only use the command "MOVE", so the logical approach is to stay near the base and to move to the nearest monster attacking the base. It is ineffective to have all three heroes target the same monster if the monster is far away from the base, so I categorized the monsters to 3 danger levels representing how many heroes should attack the monster. core_toBronze.cpp is made in 30 minutes.
That strategy alone is enough to promote me to not only Wood 2, but to Bronze league! Hence, the name of the file is _toBronze and not _toWood2.
While my code was running in the arena, I thought of something weird: if this is just the whole game, wouldn't there be very frequent ties? That would be weird.
「Bronze League」
Now, there are three spells available: WIND, CONTROL, and SHIELD. The spells describe exactly what they do and details can be seen in the IDE of the challenge. The wood league also answered my previous question: the ties are determined by the amount of wild mana collected. This encourages the players to not camp in their bases and start touching grass. It is also noteworthy that the game is fully unlocked in this league, so no new features are added at the upper leagues. This gives a chance to fully explore possible strategies of solving the whole game.
I improved by previous code by placing the heroes circling around the base and attack nearby monsters outside the base border. When monsters are awfully close to the center of the base, I use the wind spell. barrier_bronze.cpp is made and this improvisation alone lead me to be 47th rank out of 1638 people 3 hours into the challenge. Since the silver league would open in about 3 days after the challenge started, I had nothing else to do and went to sleep.
In the morning, my rank obviously went up and I tried to find ways of improving my strategy. I realized that one could abuse the wind spell and camp at the center of the base, preventing monsters to pass through. So, I coded constructive_bronze.cpp which uses one hero as the airbender, protecting the base, and two other heroes roaming around the map farming for wild mana. This strategy is weak to other strategies that involve a hero controlling and shielding monsters to attack the base. However, such strategy is not popularized beyond top 100. At that moment, I realized that this challenge has a reliance to what the meta strategy is now in the arena. I immediately created lots and lots of possible strategies and think of which strategy to code. There was destructive_bronzeFAILED.cpp which, by its name, failed in the arena. There were other strategies that I scraped off. Finally, I found the strategy I want to dig in.
Looking back to StartEnd's Apex Legends journey, I realized that their team composition is exactly what I needed. An invincible defender that creates an impenetrable dome, an aggressive attacker that blows away the enemy's defense, and a midfielder that is flexible to both positions - fight away or fly away. Never would have thought watching an Apex Legends stream would be useful.
I named this strategy skyarrow. This was a part of the lyrics from the song "Asu no Yozora Shoukaihan", the song that was covered by StartEnd. Another reason why I chose the name "sky arrow" was because the formation of the defender, midfielder, and the forward form a straight arrow to the opponent base. This strategy is the main and most explored strategy I used throughout the challenge.
I created the first version of skyarrow which consists of a defender similar to the barrier strategy, a farmer similar to the barrier strategy as well, and a new attacker role that camps near the enemy base, controlling and shielding monsters to the opponent's base. The attacker controls the monster to different areas of the target base to prevent stacking and giving WIND spell advantage to the opponent. The code is messy and reached 206 lines of code, and this strategy got 69th rank 15 hours after the start of the challenge. Believe me, the code will get messier.
Having fixed roles are always a bad idea, so I divided the game into two phases: early game phase and midgame phase. The early game phase is where all three heroes farm for mana, and the midgame phase is where the main farmer falls back to defend with the defender and the attacker attacks with enough mana. Values of when the phase change is hardcoded to each hero. skyarrow_v2_bronze.cpp gets 18th rank 25 hours after the start of the challenge, which I am very proud of. This should be enough for Silver league. In the meantime, I kept on finding optimizations for my strategy.
「Silver League」
For some reason, skyarrow_v2_bronze.cpp reaches Silver league but as rank 300. I changed the file name to skyarrow_v2_toSilver.cpp and prepare code for skyarrow_v3_silver.cpp as I have to implement my optimizations as fast as possible. The optimizations I found in between the league promotion are all related to the attacker: control from more directions and using "SPELL CONTROL" on opponent defenders to obstruct them. I submitted the code and didn't find any improvements to my rank.
Version 3 didn't improve version 2 that much, so I put the code on hold and find more optimizations related to the defender. Watching my game replays I saw...
...the WIND spell stacks?????
This is new crucial information to me. While that has already been stated since the start of the challenge, I didn't realize until the start of silver league. I implemented a super aggressive blizzard_silverFAILED.cpp that requires three heroes to immediately wind spell on a monster, sending the monster flying 6600 units to the opponent base. It failed, so I went back to optimizing sky arrow. This brings to a question: what if there were two attackers and one defender instead of one attacker and two defenders. What if we can disregard the defender if we can KO the opponent as fast as possible?
skyarrow_v4_toGold.cpp is all about that. The farmer overlaps with the attacker during the midgame phase and abuses the wind stacking ability instead of the slow control x shield strategy. The final implementation only takes me from 500th to 400th rank. At least, I achieved Gold league.
「Gold League」
I managed to hold on Gold League at 400th, however my rank increased so fast it reached 600th rank. At this point, I would already be satisfied as I have never reached Legend league before. However, a motivation struck my head like an actual sky arrow.
My friend has reached the same rank as me, unacceptable.
Thus, I created my last attempt, trueStartEnd_gold.cpp. This is it, the final push.
I created a new file and rewrote skyarrow_v4_toGold.cpp as adding more improvisations in a messy 427 lines of repeated code would be hellish. I tidied up the code into a few functions representing attacking, farming, and defending.
I figured out that the attackers moving around isn't a stable strategy unless I use very very hard math. This is because the optimal attacking pattern using the WIND spell using two heroes are as follows:
1. Place the monster X units behind the hero. Here, X should be between 920 and 1100. The point where the monster will be, the point where the heroes are, and a point from the opponent's base are colinear.
2. Use one WIND spell to push the monster to 2200 - X units in front of the hero.
3. Use two WIND spells to push the monster 4400 units away, scoring to the opponent's base.
Sometimes this strategy won't give an instant kill, however the monster will end up being only 100 units away from the base.
For the defense, I push incoming monsters to the short side (vertical) of the map using the WIND spell. This is because the horizontal sides have more chances of monsters spawning to be used by the opponent to attack. I am not sure how effective this is, as the most optimal strategies would have dynamic attack positions, but for the current meta this defense mechanism is sufficient.
When tweaking the mana cap for defense spells, I noticed that using base health accurately represent the state of the game. Less opponent_base health means we are near to winning, hence we can strengthen the defense by lowering the mana cap to secure the win. Less our_base health means we are near to losing and we must lower the mana cap to strengthen the defense. Technically, we can apply weight priority favoring to either base, however I decided to just add both health points and multiply it by a constant to act as our mana cap.
And boom, trueStartEnd_gold.cpp reached top 100 in Gold league!
...legend league only took 15 people.
trueStartEnd_gold.cpp has an approximate of 20% win rate against the new gold boss. That doesn't look good. I became desperate.
Watching the replays of my code, I saw that most of the time I lost because mana was wasted on defense as the first hero and the final attacking blow wasn't enough as there wasn't enough mana to do two WIND spells for the second and third hero. trueStartEnd_S2_gold.cpp solved this problem by creating another separate function to precalculate the required amount of mana for the attack strategy to work in the next two turns. I used next two as the main attack strategy uses two turns: a soft wind and a large wind.
I also distinguished whether the current turn is an attacking turn by adding an additional one mana to the precalculation if it is indeed an attacking turn. With this, the defense can be filtered to not do any spells during the attacking turn, even though the current situation of the base is in heavy danger. High risk, high reward.
I also increased the number of controlled monsters allowed. It is more effective to blow more monsters and have higher scoring chance.
I submitted the code in the arena. Everything when fine for the initial 50% of the battles.
until..
Well, that was a bust.
I ended up getting 8th rank. Good, but not good enough.
Analyzing a few more replays lead me to a flaw in my strategy: when the two attacking heroes move to their designated positions while controlling monsters, some of the monsters reached their destination first before the heroes, hence they are wasted and can't be used to attack.
To ease implementation, I combined the attack simulation function and the actual attack query function. I also removed the control spell function from the defense, as it gives little impact on the game and wastes mana for the attack. I tweaked some of the constants and hardcoded values as well.
Small TL:
I present to you, the work of trueStartEnd_S3_toLegend.cpp
「Legend League」
At this point I am satisfied. I didn't continue to improve my code as I had other things to do. I had an optimization at hand, however I didn't implement and eventually that optimization was forgotten.
My final rank is 282th out of 7697 people globally and 1st in national ranking.
「Epilogue」
You can look into my codes in my GitHub coded in C++. However, I advise you to try implementing my or your own ideas yourself before looking into the code.
I would like to give thanks to JvThunder (second place national ranking orz) for introducing me to bot programming. It is definitely a fun experience. However, I named my final code "StartEnd" for a reason: this is the start yet this is the end. At the moment, I don't feel like joining any more contests like these, but only time will tell. Who knows in the future I would be interested again.
Small TL:
"Do you want to join another AI contest?"
"What does the name 'startend' fucking imply? I'm traumatized"
"What does the name 'startend' fucking imply? I'm traumatized"
(Disclaimer: I'm just traumatized of myself being bad at programming, not the actual competition. The competition was very enjoyable)
