Code Royale (CC03) - Feedback & Strategies

T-Dup · May 1, 2018, 2:38am

Hey CowZow,
I’m going to reply with my small knowledge:

(1) You can either go totally random or specify different determined values. Going with determined values (like for me it was trying between 16 differents angles with max distance) will make “sure” you try all the basic directions for a low cost.
It’s dictated by the performance of my “engine” in my case. If it was way better (like if I could make 100 times more sims) I could try 32 different angles, or maybe trying half max distance, so it’s becoming more accurate. I hope I answer the question.

(2) I’m using some basic helpers:

A custom made bundler called in the post build in my favorite IDE (Visual Studio) will build the “final” code, allowing me to use includes in my c++ files. It allows me to reuse some code between contests.
I’m using CG-Sync synchronized with this post built file, so I just need to build in my IDE to have it ready in the CG website.
I’m using base64 encoding to store the inputs, and I display it in the debug view each turn, so I’m able to debug what’s going on. (when there a not too much hidden variables, like aggro in the BotG contest :’( )

… and that’s about it so far. But I’m always trying to improve this, since it makes you go way further in contest to be well equiped.

Note that all of this has been discussed over this forum already (those 3 things I’m using for example)
If you look at some winner’s Post mortem, you might find interesting things. (like in this one)

You can also look at this specific area in the forum.

Good luck and have fun building tools. They are too often underestimated.

Magus · May 1, 2018, 8:33am

In a game like Code Royale you can’t search “everywhere”. So you have to make a choice.
My code only search for 36 angles (0°, 10°, 20°, 30° …) and always with a speed of 60.

I code in a single file. Using visual studio when i’m at home, and sublime text 3 when i’m elsewhere.

MSmits · May 1, 2018, 9:49am

This was my first contest and I placed 5th overall, 1st in C# and 1st of my country. Very proud of this achievement. I don’t remember exactly what happened in each league, but I will describe my strengths, weaknesses and my pitfalls.

Pathing

My biggest strength I think was coming up with good pathing. I thought about A*, DFS, BFS and all that, but in the end I came up with some simple processes to determine the path. The first is about obstacle avoidance. For this, look at the picture below. When discussing this on the forum I realized there were two kinds of players. Players who just rammed into obstacles, letting collisions slide around them and those that completely avoided obstacles by sliding past them (yellow in my example). The best way, in fact, is to use the collision engine and aim into the obstacle. The green circle in my picture is the speed radius (60) for the queen. Here slightly exaggerated in size. You can go anywhere within it. You want to get as close to the target as possible, so you will land on the circumference of the circle. The collision will then push you outward (black line). The trick is to find the spot where you get pushed out to the most favorable location. For this, you draw the tangent to the green circle, from the center of the obstacle. The spot where the green circle is hit, is the best movement target. You will always come out a little better than just by using straight avoidance (yellow). This does not matter when it doesn’t save you a move, but sometimes it does and that means you get a whole free turn! The math for this is not hard. If people want me to do a more extensive explanation with math formulas and such, I would need to make an actual post mortem. If you really want me to, let me know and I will.

My next big pathing thing was the way I go from to one site and then to the next site. The red and green paths give you two extremes of this. You want to reach the first site in a position that is favorable for your next path, to the next site. However, you do not want this to cost you an extra move. So the best path is the one where you get to the first site, as close to the next target as possible, without it costing you an extra move.

What I did was take the extremes and then interpolate between them like a binary search (very fast), to find this position.

Also, at the beginning of every turn, I calculated the best path to any single target on the map that was reachable without entering enemy tower range. That meant I had a pathlength to factor into my building choices.

Very few players got these things right and that made it my biggest strength. Every extra turn you save helps you get more buildings up.

Simulation

I used simulation to avoid enemy knights. What I did was pick the 8 closest sites that were viable to build on. I would simulate 12 turns ahead and see on which site I could get the most builds done without getting hit by knights (assuming that I would stop leveling the building if I had to go hide). That gave me good avoidance. My scoring algorithm for what were valuable build targets contained the path length. I also used simulation for a single turn ahead. I checked to see if my path was blocked by any other unit and then tried a bunch of paths (between 100 and 700 depending on available sim time) to see which got me closest to where I wanted to go in the first place. This was really necessary, because sometimes your own units block you and when you get surrounded by enemy knights, you can also get stuck.

Towers

Another thing that got me busy was deciding which sites were valuable to build towers on. You want to get as much territory in range of your towers as possible. However, if that territory is outside the map it is useless. Below my way to determine an “area factor” to decide which towers are valuable. If they are near to the corner of the map, the area of the circle that falls within the map is smaller, making those towers less valuable. Of course I also factored in the pathlength to the tower, when determining whether to build there or not.

Pitfalls

At some point I “wasted” 3 days trying to get a monte carlo simulation going, similar to what you would do in ultimate tic tac toe. It just doesn’t seem viable, especially with C#. There are way too many variables and some of them give short term benefit and others long term benefit. You can’t simulate 200 turns ahead and you have no idea what the enemy queen will do. This just won’t work. Better is to have a lot of heuristics to try and figure out what is best. I also spent time with archers and giants that I could not get to work (noone got archers to work).

Weakness

I’m not that good with heuristics and structuring them. I had no good ideas about getting an overall strategy to work, so in the end I was inspired by that awesome gold boss (made by Spacerouquin). Gold boss had a really strong opening move that I copied. It involved making a few mines, putting a barracks in a good spot and then rushing to the other corner. After that turtle up with towers until the enemy runs out of gold.

This worked really well (though not against the top 3). Because the goldboss did not have some of my other perks (pathing and such), my bot did what gold boss did, only better. That got me into the legend league on friday, with two more days left to iron out some of the vulnerabilities and bugs.

One of the last things I added was a way to keep track of enemy gold. I also counted his knight waves to see how soon the next wave would come and if it was more than 15 turns or so, I would go into a mine and barracks building frenzy, which usually overwhelmed the enemy if there was enough time left. This worked well with the tower-turtle type of player.

Thats it, I may have left out some details, but this post is already big enough. Many thanks to the creators of the game and congratulations to everyone who did well.

Shingy · May 1, 2018, 10:55am

9th Legend.

First of all, thanks to the creators csj, harshch000 and Netbattler11 for the great contest. I had a blast and really enjoyed it.

This is a first for me in a few aspects:

First time touching 1st place, at least until the next day (waves fist at Azkellas).
First time being near the top for most of the contest.
First time I finished in the top 50.
First time I felt like a legitimate threat to most of the legend league.
First time using Kotlin in a contest, mostly because I’m a JetBrains fan and my Rider evaluation expired…
First time I felt the need to counter specific players.

Before going into too much detail, I just want to thank Bob for his “Legend of the Lazy” article. After following the guide for the Fantastic Bits multiplayer game, I really started to understand how important it is to do fewer things really well before adding new features and how a few lines of code can go a long way. My final version was purely based on heuristics and had 864 lines, with lots of if statements and System.err.println calls.

1st place on day 1

The code I used to reach 1st place on the first day was actually quite simple. It roughly went like this:

Build 2 or 3 mines, 3 towers with >400 range, and then 2 barracks.
- Weighted based on average distance to my other sites, max mine rate, and distance to the map’s centre, depending on what I was building.
If all towers have sufficient range and my income is low, build more mines.
- If no sites are safe to build mines on and I have at least 5 towers with sufficient range, consider replacing my furthest tower from the centre with a mine.
Else, make my weakest tower stronger until range >= max(400, min(distToCentre, maxRange)).
If I touch a site, I have everything I need, and I don’t gain value from building a mine there, build a tower.
Only train knights if I have enough (or will have enough) gold for 2 concurrent waves of knights.

And that’s about it! If I left that code as it was, I think it would have easily reached Gold league, or at least high Silver. At this point, players did not handle 2 concurrent waves very well. I knew I had to continuously improve my bot if I wanted to stay near the top though, as I knew the real contest was waiting on the top contenders to finish writing their C++ game engines.

Most of my remaining time was spent on bug fixes, tuning, and small features which I felt were strict improvements, but I’ll discuss what I felt was the most impactful change.

Path finding and Defense

When there is another site in between my queen and the target, I saw that my queen would just faceplant into the blocking site, wasting precious turns doing basically nothing. As Nagatwin was climbing the leaderboard earlier in the week, I noticed he was taking advantage of this by doing something really clever - when enemy knights are attacking, hide behind towers so that the knights get blocked while the towers kill them. My defense at the time was simply to run to the corner, which was only effective some of the time and occasionally lost me some games. When I saw Nagatwin’s approach to defense, I knew that this was the big feature I had to blatantly copy (lol).

After changing my queen’s movement to move along the blocking site’s tangent, my results didn’t really improve that much. It wasn’t too surprising when I thought about it, as my basic strategy never really took advantage of it. After implementing better defense though, using the average position of enemy knights close to my queen to hide behind towers, I was back in the top 3 again, for a while anyway.

Staying in the top 10

When RoboStac and Agade entered 1st and 2nd respectively, I just couldn’t beat them. I think my win rate vs Agade was 0-10 in one of my submits. I actually won a few of my games against RoboStac at the time, so I spent a lot of time focused on trying not to go 0-10 vs Agade and looking for counters to the contestants who I was consistently losing against, namely RiSuS and Xyde. Some of my changes for the rest of contest were:

Changing general build order to 2 mines -> 1 barracks -> 3 towers before doing anything else, unless under attack.
- I found only having one set of barracks to be more consistent overall. The continuous pressure felt important near the top 10.
Completely swarm the enemy when they have no income for a number of turns, by only building mines wherever possible. This worked really well vs RiSuS and Xyde when I wrote it, and occasionally against Agade. It feels like I got countered though as I started to see enemy mines stay in the game for longer. Perhaps I submitted this version too early!
Aim to always move at the queens max speed, leaning toward the next probable target to try save an extra turn.
Try not to walk into enemy tower range. This was mainly for Agade’s strategy of covering the map with towers. Didn’t always work though…
Try to go for “safe” sites, which are out of enemy tower range and are generally closer to friendly sites than enemy sites.
Replace mines with towers when under attack - I scrapped this idea as it seemed to make me lose more often than not.
Sit in the corner when I have nothing safe to do - worked surprisingly well against Agade for a while, until he figured me out and built towers which covered the corners.
Only build one mine in the early game if the enemy built barracks on the first turn - seemed to help my win rate vs one of RiSuS’s later submits.
If only one knight is close, is far enough from the queen, and will die from my towers in range, pretend it doesn’t exist. This was the closest I got to simulating anything, and saved me two turns in most cases.

Overall I’m really happy with my result. My original goal was top 50 since I finished BotG 56th, that is until I saw one of my submissions on the first night reach 3rd place. It was really worrying when I started my Monday in 4th place and I was seeing my position slowly drop whilst I was at work… Seeing people with good win rates against me repeatedly resubmit their code was also concerning (waves fist at Azkellas again). However, I’m honestly impressed with everyone’s massive climb on the last day. Congrats to RoboStac and Agade for being so dominant for most of the contest, and Xyze for the huge comeback later on to claim second place!

ThomasNicoullaud · May 1, 2018, 11:17am

Hi All !
15th Legend. No Simulation, No global heuristic evaluation, just a lot of conditions

My game engine :

1- Calculate some variables :

Mine’s gold left for prevent a rebuild on an empty site.
Accumulated gold of my opponent (but i didn’t use it finally).

2- Manage queen security :

Calculate an estimation of a “danger score”. I simply used enemy’s knights distance from me and count of them (no collision, no simulation of their move).
I added the sheduled knights in barracks in anticipation.
I used some coefficients and parabolic functions for calculate this score.
If this score is greater than a constant value (4 in my last version), i’m in a danger situation.
If i’m in danger situation and enemy’s units are far (more greater than 400px from me) , go to the safety tower and upgrade it.
The safety tower is the closest tower of the towers’s ranges intersection (with a maximum of towers).
If i’m in danger situation and enemy’s units are close (more lower than 400px from me) , build another tower on the first empty site behind me, if there is.

3- Manage mines :

I must always have minimum 2 mines, except if my life is two times more greater than enemy queen’s life (in this case no mine is needed).
I must have 2 mines by each barracks (I didn’t use the mine’s rate, just number of them).

4- Manage building :

I have an unique build order for the early game : Barracks, Tower, Tower, Tower.
If build order is completed, my build depend my healthy situation. For the next closest empty site :
if is in the back side, build mine.
else if my life is greater than his life, build tower.
else if i need giant (depend number of enemy’s towers), build giant barraks (limit 2).
else if my life is lower than is life, build knight barracks (limit 2).
else build tower.

5- Process action :
Take the first action of possibilities and play it.
If there is an collision with a site and the targeted move, calculate the deviation (for some trigonometry rules, tangents, …) and go to the new position.

6- Manage gold :

If number of turn is lower than 200, build a maximum of units that i can do it for prevent enemy expansion.
If enemy’s queen is next to the map center (distance lower than 400), build a maximum of units that i can do it.
Estimate the number of unit waves for touch the queen (depend number of the enemy’s towers which protect the queen).
Estimate if i need some giants for support my knights (depend number of the enemy’s towers).
If i have enought gold for build needed units, build a maximum of units that i can do it.
If number of turn is greater than 350, build a maximum of units that i can do it.

It’s all

It was a funny contest !

Thomas

qbit86 · May 1, 2018, 11:48am

Is there some tool which lets you write code in multiple files but then compile it all into one file for submission?

It’s just a couple of lines in MSBuild-file (aka *.csproj) which merge files in .NET Core project into single amalgam during build.

RockyMullet · May 1, 2018, 2:18pm

Lol, I was thinking the same thing: “no reCurse ? Yay number 1 in canada !” but then you passed me
I guess number 2 is ok…

gg

polettix · May 1, 2018, 7:10pm

Thanks. I don’t know what the application is but I’ll understand it in some future contest I guess.

xinux · May 1, 2018, 9:24pm

This is the first time i participated and I had lots of fun. I tried my best to reach top 20 but the competition toughened up a lot the last days. I’m happy with my placement (44th legend), and 1st in sweden.

I have no idea how to even begin doing simulations, that will be for a future compo. I simply made “actions” and weighted them based on parameters that made sense. I spent a ton of time just tuning the weights. In the end my code turned to spaghetti, but I learned a lot of python in the process.
Big thanks to the devs!

CowZow · May 1, 2018, 10:45pm

The trick is to find the spot where you get pushed out to the most favorable location. For this, you draw the tangent to the green circle, from the center of the obstacle. The spot where the green circle is hit, is the best movement target.

Wow I am very impressed by your maths. How hard did you find implementing the math in code? For me, I can calculate derivatives and tangent lines by hand, but I found it quite hard to implement math ideas in code because one must take into consideration so many edge cases, like avoid divide by zero or avoid taking sqrt(-X). And also when you have to take a derivative of a function that is completely general, the algebra gets quite messy! Do you have any tips for this?

Azkellas · May 3, 2018, 6:12pm

Hi all,

6th Legend and 1st with no simulation at all.

At the beginning, I thought simulations wouldn’t perfom well in this game, so I decided to go with Python, which I find easier to read and to use for heuristics.

How I managed my time: I mostly coded the first Saturday to get #3, and 30 minutes the next morning to secure #1 with a 4-point lead. I then refactored my code to make it more flexible and I used it to try new strats (giant rush, double giants late game, archer-based defense, etc.) on Monday and Tuesday. None of them made it in the end. Seeing how good RoboStac was with his sim, I decided to code my engine in Python on Wednesday, but it was horribly slow. I profiled it, made my own local referee to test it, search for some hacks to make it faster, but I couldn’t make it usable. God I missed some -O2 / inline pragmas. I started translating my code to C++, but that wasn’t fun at all and I was not here to do that, so I gave up and decided to do it without sim at all, even if that meant losing some ranks. When Legend opened, I barely made it with the exact same AI I had on Monday but had one of the worst AI there. It was time to react. I was wondering why so many people copied some top AIs ideas (like Nagatwin’s anti-collision system or Xyze’s defense), but no-one cared copying my swarm strat. I benchmarked it, and realized it was awful. Removing it made me caught up with the top10 again. I then used cgstats to look at my worst match-up and fix them. At the end of the day, I could just go to any defeat I had in my last battles, jump to frame 60, and say “Yup, I’ve already lost this one.” After a really lazy Saturday spent testing some magic numbers, I used the final rush of Sunday to reimplement my build opening (that made me go back in the top5), then study match-ups against the top3, without being able to find a way to beat them. Eventually, I ended #6.

About movement in this game, eulerscheZahl already explained how to find the best path and MSmits how to visit intermediary sites. Personally I copy-pasted a function I made in the BotG contest that was slightly sub-optimal (losing 1 or 2 turns per really annoying site on my way), but earned an hour, used to implement something that may have been more useful. Roughly, I computed the two intersections between the circle representing the movements possibilities of my queen and the circle representing where she could be around a site without colliding with it, going straight forward if I wasn’t colliding this turn.

Final AI:

My queen has three states:

“I’m a new queen but I see big: Let’s create a empire”
“Ok I’m safe, let’s expand”
“Oh God, I’m under attack, what do I do?”

Each state has its own ramifications that I will skim through.

The “I’m a new queen but I see big: Let’s create a empire” state

A good starter is really important because in most games, the only damages dealt are in the first two waves sent. After 30 turns, you can almost always know who will win this game. A bad start and you would either have taken way more damage than your opponent (which is instant defeat against defensive sim like Xyze or Agade), lost ground or been cornered.

My build opening is the following: mine, mine, barracks, tower, tower (after benchmarking different combinations, that’s the one that worked best for me).
Then:

I want my two mines to be where I will not go anymore, ideally in the top band if I’m red, bottom band if I’m blue
I want my barracks to be near the opponent side. It has to have easy access to the other side: no site to collide against when units spawn.
My towers have to be near each other so I can defend easily in the beginning. Furthermore, I need to first build the furthest one, to hide in my side when the first enemy waves spawn.
If I can, I want a third site to be near my towers to build a tower on it and be safe.

Example:

So in this example, I took more damage than my opponent, but my placement already ensures my win. My mines are safe for the rest of the game, I will never go there again and no enemy can come here. My barracks can easily attack the enemy side, top and bottom. Finally I have a third tower easily accessible. On the contrary, see how the blue player is hiding near their mines and how their only tower is not covering their queen. They will eventually lose a mine to protect themselves. 10 turns later, I will have more income, more towers, more health, and a better placed barrack to attack them.

Another example:

The “Ok I’m safe, let’s expand” state

This state occurs when I believe no one can hurt me (I will define how I computed this in the next state).
If this is the case, then I need to develop my “empire”. This is done with a serie of priority:

If I have a low income (4 or less if I’m ahead to defend, 7 or less if I’m behind to attack), then I try to find a site where I can build a mine safely, even if it is my own tower. To know if a mine is a good idea, I have a rough estimation that computes the number of towers protecting it from any enemy barracks (protecting = on the path). I’d usually ask for 3/4 towers if the enemy has one barracks, 6 if s/he has severals, and 2/0 if I’m confident I am playing against a camper that will not attack me.
If there are sites where my queen would be useful, I go there. Are considered as such neutral sites (where my queen can build something new), enemy barracks / mines (that she can destroy and build upon) and tower with low health (to repair)
Else, I don’t need anything, I go and hide near my furthest tower from enemy barracks. (very rare case)

For each site I check, I make sure that if I went there, both my next position and my last position would be safe, safe meaning “I won’t get hit by a tower there”. If I am behind, I consider my knights are covering me, so I can expand, but if I’m ahead, I often disable this because against Agade who had tons of towers I often had the case where my knights died and left my queen alone in dangerous zones, taking free damage.

The site I find is my goal. The goal is where my queen should go, and why, may it take 10 turns to do so. However, there were often multiple towers on the way, that cost nothing to improve on the way. My queen could then stop and repair it, before going to her goal (or change her mind and go elsewhere). I relied a lot on the dense map to modify sites on the way and had no actual pathfinding algorithm to do so.

The “Oh God, I’m under attack, what do I do?” state

Last, but probably most important. Since I had no simulations at all and since most games ended at the 401st turn, I had to be extra cautious to not take any undesired damage.

At the beginning of each turn, I computed the number of knights really closed to my queen, those near and those far away.
Then basically:

I_m_under_attack = numb_knights_close > 0 or numb_knights_near > 2 or numb_knights_far > 4

With 200 / 500 / 1200 as ranges to computes the numbers. The idea here is to detect really close knights to not get immediately hit, not so far single wave and far double or more waves.
This boolean also takes into account my number of towers to protect myself. I’m not that in danger if three knights are coming but I’m already hiding between six towers. Also, if I was ahead in life, I’d sometimes start the “ultrasafe” mode (or camping mode) where I’d double those range values to be extra extra safe.

Then if I think I am in danger, I have several reactions depending on what is the danger:

If I am under an enemy tower, I just run in the opposite direction
If the danger is not immediate (numb_knights_close == 0), I first try to run to a site I can improve. For this, I compute the angle danger-queen-site and consider it possible if it is greater than a certain value (for example 120° or 80° if the enemy are still far away). I’ll then validate this candidate by making sure it’s not in the middle of nowhere, but comfortably between several towers I own.
If I haven’t found anything before, I run to the most protected tower (often the furthest tower, that has the most towers in the way of the enemy to protect it).
If I’m already there, I hug around the tower, using it as an obstacle for the knights (with their pathfinding, it really bought time) and then just running around it to limit the number of knights able to hit me.Jeu de survie

Once again, on my way to my goal, I might touch some site that I could improve before resuming my journey. I had no problem destroying a mine to build a tower instead to protect me.

A good example to show it: https://www.codingame.com/replay/307872437

You can see how I used towers to make the knights collide then after some time go in a ultrasafe mode.

When to train

Until Friday evening, I had a swarm strategy where I’d save up during turns 100 to 150 before lauching a huge wave in the last 50 turns. It lead to beautiful replays with 50, 100 zerglings massing and overwhelming the enemy side and sometimes even the CG engine itself. However after some benchmarking, I realised I had a 20% better winrate without it (going to 60% to 71% on 200 games against top15). I was surprised because I saw many blatant wins thanks to this technique. In fact, by saving money for 50 turns, I drastically reduced pression and territory control. Watching some replays against Agade who had a territorially agressiv AI really made it clear.

The metagame is not to kill your opponent, but to deal more damage in early game, then defend. To defend you need to have territory and to constrain the enemy to theirs. And to do it, you need to attack as much as you can. For this reason, I’d attack any time I had enough money to train in all my barracks. I’d build a second barracks (or a third) only if I had a great income, like 6 for the second and 10 for the third. Being honest, that was only the case if I had already won.

I really liked this contest. It had a nice balance between simulation and heuristics and a clear viewer. Thanks CG and the team behind it (csj, harshch000, Netbattler11). The stream about the evolution of the game between the first alpha and the final release was also very interesting, thanks again csj.

For the multiplayer, I’d like the max_mine_rate in the viewer as well. AIdevOOPS made a pull request to fix the asymetry which was blatant against top sim. I think the collisions of the queen should be calculated after the knights’s, making everyone “blue side”. (A queen taking 1 damage per turn while being circled by 7 knights doesn’t seem fair to me).

Lastly, gratz RoboStac for winning this contest. Your AI really was amazing, it is more than deserved.

GoofyGas · May 4, 2018, 11:55am

I’m still somewhat new to this site. How can I see the results for the contest or where I am on the leaderboard? After the contest ended, all links to it seem to have disappeared. Sorry that this is probably such a simple question but I’ve looked and googled and can’t seem to find the answer.

eulerscheZahl · May 4, 2018, 2:02pm

To get your final submission, go to Compete/contests and click “view report”.
You can find the leaderboard either by Compete/Leaderboard or by clicking the rank at your profile. That shows your ranking directly and it also contains a link to the leaderboard.

Kodle · May 5, 2018, 3:36pm

Hello CG!

#55 Legend What a fun contest!

Congratulations to the CC team for this wonderful game, good balance between Heuristics/Sim (Macro/Micro respectively). Simple rules to jump into, somewhat like a Tower Defense game with RTS elements. Pretty pleasant graphics too (peaceful, not too distracting, does the job of visualization well)!

Like many, my bot was a mix of heuristics/simulation, and in my case more of simulation-informed heuristics than a search-based bot.

Macro

Main aspect of Macro strategy was what structure should each site have? In order to make these decisions, my bot took into consideration what the structure types on adjacent sites are and how far away the sites are from enemy tower/barracks. Since we don’t have a clear adjacency list, we precompute it at the start of each game.

Delaunay Triangulation

What this algo does is avoid having points within the circumcircle of each triangle. Usually applied to automatically generate a mesh from a set of points (3D-modelling), but useful here to give us a set of adjacency lists.

Implementation and usage in python is super convinient with scipy

import numpy as np
from scipy.spatial import Delaunay
points = np.array(samples)  #[[100, 200], ...] List of site co-ordinates
tri = Delaunay(points)
print(tri.simplices)        #[[0, 1, 2], ...] Gives the vertices of each triangle

With this information, my bot tries to construct a barrier of towers and place mines behind towers away from the enemy. (Blue->Tower, Green->Mines, Black->Barracks)

To select the initial barracks position I set a limit on how far I should propagate outwards from my initial site (based on starting health, lower->closer) and from these sites, simulate a single knight pathing towards enemy queen and pick the one with the shortest distance.

Micro

With the simplier collision algorithm the referee uses in this contest, I had hopes python would be able to simulate fast enough to be useful. Still, I needed to do some optimisations before it was anywhere near usable.

Some numbers in python (simulating movement of 2 groups of 4 knights heading towards respective queens averaged across 40 turns right after spawning):

[146ms] Straight-up implementation of referee collision (removing site-site checking).
- Python is slooow…
- Class access is pretty costly in python (using the ‘.’)
[13.7ms] Pre-loading of class data into arrays, operating on the local array and updating at the end of the simulation.
- Accessing data from local arrays is *10 faster!
[2.58ms] Sectoring optimisation
- Many objects are simply too far away to be even considered for collision, by precomputing a grid of possible locations where collisions may take place, we reduce the time used for collision checking further.

Sectoring Optimisation

We split up the map into grids (in this case a 24x12 grid) and precompute an occupancy lookup table (ids of objects that occupy the grid). To account for border cases (not yet into the next grid so I do not ‘see’ the object there), each object will test for collision with other objects within a 3x3 grid. This hugely reduces the collision search-space when there’re numerous objects in play but in separate regions.

Sites can be precomputed once but units move so their ‘affected grids’ will have to be computed each turn then used for the turn’s collision checking.

Now with under 3ms per turn collision simulation with 10 moving objects, it starts to be useful for my queen to assess when it will come under attack by enemy knights.

Alas I only managed to finish the simulation engine on the second last day of the contest and didn’t manage to implement much micro dodging/evaluation of moves after simulating the results. My bot’s dodging was its greatest weakness. All I did was simulate if my queen will get attacked prior to completing her goal and choose another goal/run away (and the running away was really just running directly away haha).

Python Graphics Library

My main gripe with CodinGame bot programming contests is how hard it is to debug visually. By simply drawing some lines and labels overlayed onto the game (could be a debug toggle option), it will tell you much about how your bot is making its decisions and where your bugs may be. So for Mad Max I used the default python turtle library to debug my simulation. This time, I used the same base code to write the sim. It’s a short 300 lines in python (including my own implementation of Point and Vector classes for linear algebra - useful for physics) that I’d like to share with you guys, if you need a quick way of making visualisations for your bot, feel free to use it

Till next time Code Of Kutulu!

Agade · May 13, 2018, 3:08pm

I finished 3rd and here is my postmortem.

I am somewhat mitigated about the game, like Magus I thought it looked very promising, but in the end it was actually very simulation-heavy, in some ways even more than Fantastic Bits since the winner Robostac had to reproduce even rounding errors. I thought there would be interesting RTS-like strategy in the choice of buildings but in the end I wonder how important this is, since I had 40% winrate against Robostac with half the search depth, an approximate simulation and pretty much only built towers. Perhaps the multi will shed some answers.

qbit86 · May 15, 2018, 7:33am

When will Code Royale be available in multiplayer/bot-programming?

qbit86 · May 21, 2018, 3:32pm

@csj @harshch000 @Netbattler11 Any ETA on publishing Code Royale to multiplayer/?

TwoSteps · May 22, 2018, 9:59am

Code Royale will be released tomorrow (Wednesday)

Nagatwin · June 1, 2018, 2:06pm

Hi all !
I had a lot of stuff to do so it took me time to publish any PM
I finished 33th during this contest, and was in the top 10 about 8 days of it.
This was my first contest and my first thing on this site apart easy puzzles.
I had a lot of fun doing it! Thanks to its creators.

I had 4 AIs on this contest (and after as I post it after the puzzle release):

-A basic AI in C#
-A simulation in Java
-An heuristic in Java (the one that made it to 33th)
-A simulation in Rust

Let’s talk about
The different IAs I came up with.

C# :
First of all I made the C# one. Started with C# because it was my main language
Pretty sure I didn’t event submitted it

I quickly moved to Java because I wanted to learn more about this language (I am studying this one.)

Java :
After some basic coding I ended up in top 10 on the 2nd day (or so). I had a pretty basic strategy :
Find an empty site
Build on it on it; in order
2 mines
1 barracks
Towers

Then train as much as possible

The simulation :
Seing Shingy in Kotlin made me think about makyng a simulation.
I ended with a working engine for knights; queen; towers; barracks; income and mines pretty quickly. It was running pretty fast (for Java) so I was able to make from 600 to 200 simulations with a map crowded by knights.

With a basic eval function and an unoptimized BFS, it was able to make some moves but not that much, mainly because I actually discontinued it.

However I thought that doing an AI with heuristics would let me handle more things than the simulation.

The heuristic :
This one is the one I worked the most on.

The strategy was hard coded (if-else):

Escape tower range
If there was not enough towers, build one (2 per barracks)
If an opponent’s knight is 1 turn closer than my Queen from the closest tower, start fleeing (explained below)
If i’m in contact with a tower or a mine, upgrade it. (Mine to max income rate, tower to 600 hp)
Build 2 mines
Build 1 barracks
Build 3 towers
Build 1 barracks
Build an equal amount of towers and mines.

That’s it for the strategy.
I had an alternative strategy for the ones that camped after 1 single wave (Xyze, RockyMullet, …) but ended removing that flag as it made me loose more battles.

Escaping units:
This was made after I saw how R4N4R4MA escaped units and turned around sites.
I ended up with the exact same calculation as MSmits for the best way to move around a site, i’ll let you check it’s explanation on it’s PM.
To escape knights, I :
-Calculate a barycenter of the opponent’s knights weighted with the opposite of the distance to my queen (the farthest knight had less influence)
-Find the safest tower and move to it (the one in the maximum number of ranges of other towers)
-Move at the opposite direction from that barycenter of the Tower
-If the Move is less that 15 unit long, upgrade the Tower instead

Bulding repartition
I selected different sites for each building:
-Mines near spawn location
-Towers at the opposite Y
-Barracks anywhere

This was influenced by the distance to the site each time, this led to formulas like :
double cost = 5 * site.distanceTo(startPos) + s.distanceTo(game.queen); (for mines for instance)

Also I checked that sites where I wanted to build mines were not on opponent’s creeps’ path to one of my tower.
This was meant to prevent opponent’s units from destroying my mines.

Pre-calculation:
I also made some code to optimize the start, basically:

Do a DFS to find 5 sites with the least moves between (also had MSmith calculation for that). Bonus for mines and tower placement.
Go to these sites an do a classic opening (2 mines, 1 barracks, 3 towers)

Somehow this made worse than running straight to sites so I threw it away.

This is the code that made it for the contest.

Rust simulation :
After all that, I wanted to try to code in some new language. A lot advised my to try Rust as it is fast and secure.
So I made a simulation, that has probably a gold-like level.
It is still bugged but is doing fine tricks, I will probably try to improve it.

Anyway this was a fun contest ! Grats on Robostacks that made it 1st with 0% wins on my AI on it’s first submit (probably a bug that made him time-out he quickly fixed). and every other participant !
And see you next contest

Jahz · June 1, 2018, 3:13pm

4 AIs (including 2 simu) in 3 different languages in one week ?
Were you in vacation or something ?