Code Royale (CC03) - Feedback & Strategies

Hi,

17t Legend

I spent half of the contest hesitating between a pure simulation solution and a heuristic one (with a little simulation in micro-situations).
For both solutions, I needed the engine, so I started with this. Took me 2 days to write an bugged engine. After the initial draft, I spent a few days trying to figure out why the engine was slow and innacurate.
Pro-tip : re-read carrefuly the referee code when translating, and OVERTEST your engine in every possible corner case. Long story short, I lost shitloads of time with hidden bugs (the referee helped, as you can now run a local game with breakpoints in both your own code and the referee, and compare simulation steps on both sides to spot deltas).
Meanwhile, I was still hesitating between the two types of solutions and spent some time on both, in parallel; perfect time-wasting strategy.
The information given by the referee was once more incomplete, but it was pretty easy to guess enemy gold/income (assuming a queen standing still next to a mine is upgrading it).

Friday I finnally managed to fix most of my bugs and started focusing on a genetic algorithm, dismissing the heuristic version of my AI.

My evaluation function is rather classic :

  • Big bonus for health (overrides everything else)
  • Malus for destructed buildings (exemple : I build a mine over a tower)
  • Malus for each enemy knightā€™s health and squared distance to my queen
  • Gold income difference
  • Small malus for distance to the closest available site
  • Defense score (struggled with this one, and the result sucked) :
    defScore = (MIN(enKnights, 6) * (myTurretNumber * 4 + turrSize * 0.01));
  • enKnights = the number of enemy knights (those on the maps, those who are being produced, and 3 virtual knights for every 80 golds the enemy has)
  • myTurretNumber = sum(turrets) { 1.0 + (turret.distToMyCorner / 2800.0) } (I tried to favor turrets that are closer to the enemy corner, thus further away from my own corner)
  • turrSize = sum of turrets radiuses

    Itā€™s linear and it doesnā€™t have the notion of ā€œtoo much defenseā€. In lots of scenarios, my AI will build only towers. I tried to use log() and shit to make my AI stop doing that, without success.
    It also lacks a position component; for both the turretsā€™ positions on the map, and my queenā€™s position regarding the turrets. Often, my AI is making a pretty tower maze, then goes in the corner to make another one and gets stuck in there, trying to avoid incoming waves of knights, not taking advantage of the previously mentioned maze.
    I added a position score (mean of distances between my queen and my turrets), that didnā€™t work very well.

I also wanted to add something that says ā€œyou will lose some life, but in the long run thatā€™s okā€, but didnā€™t succeed.
Like in lots of other contests, my evaluation is poorly-balanced and lacks tons of stuff, but thatā€™s the best I could come up with in 10 days.

On the game itself, it is quite unbalanced but very interesting nonetheless; simple inputs/outputs, easy naive solutions but enough depth to really scratch your head. Congratz CC team.

Alos, kudos to CG for introducing swapped matches in the rerun.

Neumann

16 Likes

60th in legend.

Heuristic bot, not much to brag about, perhaps the strongest part is the gold control. It shoots only if the enemy is close or has bad tower protection, otherwise it saves gold. Once a threshold is reached it will try to build a second knight barrack and go all out.

I had prepared for the contest by practising Clash Royale . I like Clash Royale for the deck selection aspect, and how to counter cards. I missed this in this competition, since the archers and giants were useless.

Still it was an interesting contest with ample of room for different strategies. I had a good time, thanks a lot to the creators of the game!

6 Likes

10th
I decided early to build a hybrid algorithm:
For the macro game (where to build, what to build) I use heuristics. But for the micro game (how to escape from knights) I have a simulation of the game.

Path finding is done by checking for any other sites between me and my target (circle-line intersection with the queenā€™s radius added to the obstacle circle). I then combute the two tangents to the obstacle circle through my queenā€™s location and chose the one with the intersection point closer to my actual target and go there instead of to the target directly. When I know where I want to go, I run a bruteforce over different angles to take enemy towers and my own knights (they could block me) into account and get as close to the target as possible. This did not work well all the time, but did an OK job in general.

The heuristics part is quite boring: If the enemy is near, switch to escape mode (with sim), otherwise do actions based on the location of my towers, barracks mines as well as the opponent units.
If the enemy is attacking (but not in direct range), I try to go to each site to possibly build a tower there and check if I can do so before the enemy arrives and hits my queen (using the sim again). I then choose the site that is the closest to the opponent while still in a ā€œsafeā€ range.
Depending on whether I have more or less health than my opponent I either build towers and wait for the game to end or spam mines to attack and move the barracks closer to the opponent.

My simulation only uses depth 3 (when the enemy isnā€™t too close) or depth 2 (when the enemy is near and I will take damage for sure), because I donā€™t get many iterations and miss a lot of better options with higher depths (my sim is almost 1:1 the referee without optimizations - I supposed that adjusting the heuristics gives higher benefit than performance tuning).
It allows me to run away from the opponent and use collisions to my advantage not to take too much damage.
The simulation completely ignores Giants and Archers (not a big deal, as almost noone uses them) and also doesnā€™t spawn any creeps (resulting in smaller errors, as the spawn does a collision check as well - moving the creeps that already are on the map).

I really liked the game. It allowed for both heuristics as well as simulations to compete for the tshirt ranks. The graphics were well designed and simple (cool artwork for the towers; no real knights might not look that nice, but itā€™s easier to debug this way - and I watch the replays to analyze the bots, not to admire the graphics :wink: ), I only missed a way to print debug text. I was quite happy, that the giants/archers didnā€™t work well (it would add more complexity and coding large heuristics is no fun for me).
On the downsides I see the assymetric collision + spawn giving the first player an advantage (there were two matches with swapped positions in the recalc, so Iā€™m fine with it) as well as the Kotlin referee.
Latter is just a personal preference, as Iā€™m used to C#/Java code. I was able to understand what the Kotlin code did, it just took me longer than usual.

20 Likes

Excellent contest! First time legend for me (45th), and second in python after a tough battle against Spacerouquin (Congrats, man! Well done!).

I totally agree with you all for the game graphics, which were excellent. And also the gameplay which allowed for both heuristics and simulation - much more like simple calculations in my case as I will explain.

Concerning heuristics, nothing much to say except that I beat my ifs blocks record: 17! I am sure some did much better with lessā€¦ What made me gain some places however was my escape function, used when the queen is attacked. I did just like for mean max as it worked quite well : a wind rose of the future positions my queen can go : 16 points at 60 pixels distance away. And then, for each of these positions, ascribed a score according to the distance to the point I want to go to, the enemies around, the obstacles in between, distance away from my gold mines to avoid to break themā€¦etc. Then I returned the best of these positions Quite easy to code and much valuable to escape enemies knightsā€¦

To conclude, thank you very much for the contest, CG and the creators, much fun once again!

7 Likes

Thanks to the creators for a very fun contest. Very happy to have won a proper contest, especially after coming so close during Mean Max.

My postmortem for this contest

29 Likes

Hey (Wow, posting just after the winner :heart_eyes:)
25th Legend

Iā€™ve started full heuristics.
I thought I wouldnā€™t have enough time with my current personal schedule to go deep in this contest. (aka sim)
Looks like CG contests are actually hard not to focus on while started oO

Went gold with some basic strategy:

  • If there are units close, go to the opposite direction of the closest one. (which is definitely not working well: Lot of time I was just blocked by a site behind me, or by the borders of the map)
  • If Iā€™m at a site, choose what to build. (bunch of if else)
  • Otherwise try to find a close site with no structure or a tower to grow.
  • Doing knights as soon as I can (if I have 2 rax, wait to train in both at the same time)

Legend / Simulation
Then I noticed the top bots were siming, making some really cool moves :slight_smile:
So I jumped in. I have some bugs in my sim I didnā€™t have the time to fix (or maybe I had and I should have, but thought "letā€™s focus on macro strategy instead), which made the very end of the contest problematic for me (had to do some approximations)
I saw in several games opponents using the tactic of going to the center to build one rax, I used it to have a simple strategy to test my sim/avoidance.

This strategy + the sim made me go into legend right away.
After that, I just made my code more complex to handle some differents cases (Iā€™m not sure if those modifications were all the time for the best though, but I might pop giants sometimes ā€¦ definitely worth it!)

My simulation is using MC/depth 6, Iā€™m doing it only for creeps not too far from my queen, with fitness using :

  • My queen health
  • total enemy creep hp (so they go under my towersā€¦ right?)
  • my mines destroyed during the process
  • Is my queen in range of my towers.

When I look at my final submission, I feel there are (at least) 2 huge issues Iā€™ve left:

  • I hesitate a lot when units are close. Where I could just DO stuff, like growing tower with safety. This is because I go into the PANIC ESCAPE MODE where I just try moves and not build anything.
  • I donā€™t make enough mines when Iā€™m ahead, which leads me to lose some games Iā€™ve started well.

I feel with a perfect sim, I could have done way better (since I currently donā€™t fully rely on it because of bugs). But itā€™s hard during a 10 days contest. I might come back for the multi :slight_smile:

The contest:

Positive:

  • I really liked this contest : a perfect mix between sim and heuristics (and being able to reach top 15 legend without sim is a good thing IMO)
  • Iā€™ve had 2 friends trying it (first CG contest for both of them), and they had fun. (They both ended up in the silver division)
  • Not too many inputs, I really like this. No aggro to keep track of or other weird stuff.
  • Perfect balance in game complexity for my taste.
  • Clear visuals
  • Kotlin referee. I actually think itā€™s fun to discover new language this way :thinking:

Negative:

  • Archers behavior seemed the most complex, but they werenā€™t useful
  • Being 25th doesnā€™t deserve a t-shirt

Thanks to the creators of this really fun game, CG obviously and reCurse for not participating and letting me the #1 canada spot for the second time :smiley:

ps (unrelated to the contest) : Being a C# programmer training my C++ here, Iā€™m still sad not having Linq to quickly write and test heuristics. Iā€™m wondering how I could quickly write readable code like in c++:
var jungleMobs = Units.Values.Where(p => p.UnitType == eUnitType.Jungle && p.DistanceFrom(Enemy.Tower) >Enemy.Tower.Range +50).OrderBy(p => p.DistanceFrom(Me.Tower)).Take(2)
If someone has advice for me, go ahead thanks! :wink:

10 Likes

4th Legend.

First of all thanks to the creators, it was a really fun contest with a lot of possible strategies and a good balance between sim and heuristic approaches.

Start heuristically
I started the contest with heuristics on first Friday since when I first saw the rules I thought ā€œtowers, creepsā€¦ this should be similar to BOTGā€. I reached Bronze with a simple heuristics bot that built 2 mines, then a barrack and then towers. When the mines depleted it built new ones. I couldnā€™t code the first weekend, and when I took it back on Monday I knew heursitics evasion would never be as good as with sims, so I started working on the engine. I donā€™t agree with others that found it hard to code, I found it relatively simple to build a ā€œgood enoughā€ engine in a few hours that could evade knights farily well. At this point my code was heuristics for build, move and produce, and when being attacked I used a random search of depth 4 to evade.

Switch to sim
Then I figured that since I had an almost fully working engine I should try to make all decisions by simulations, including creep production. I switched my code to a GA of depth 10 with a decaying factor of 0.95 and fixed the details that were making my simulation fail (thanks a lot to RoboStac and Illedan for their help understanding some details that I had missed from the Referee and from Kotlin!).

Depth
Regarding the depth, Iā€™m not entirely sure why but I was able to find good solutions despite achieving only like 250 sims per turn on depth 10 (because of the expensive engine and my code is not the most efficient). I even had good results with depth 14. I think itā€™s because I didnā€™t use much rival information in my eval, so the impact of the rival decisions usually takes several turns to affect my queen (knights attacking for instance), so the solution of the previous turn shifted is a very good starting point.

Eval
I always find it difficult to write good eval functions. I find it hard to compare the value of for instance losing 1 unit of health vs building a mine or increasing a towerā€™s hit points. In the end my eval takes into account all the following:

  1. My queen health (a lot of value) and the rival queen health (very little value).
  2. A score for each tower, mine or barrack. I used a logarithmic function to model the value of increasing the tower hp. The first 200 points are worth much more than the last 200 to complete the 800. Mines are worth more if they are close to the edges of the field, towers are worth more if they are more thowards the center, and barracks are worth more if they are closer to the enemyā€™s side.
  3. Distance to closest empty site.
  4. Health of rival creeps.
  5. On sunday I added a bonus for having a Giant barrack and for producing Giants if Iā€™m in the situation of having much more extraction rate than my rival.

Missing information
Since symmetric sites are consecutive in ids, i set the maxExtractionRate of the sites symmetric to my known sites. Hence I could estimate preety accurately the total extraction rate of the rival queen and also her gold.

Enemy prediction
For rival prediction, I only used the following:

  1. She doesnā€™t move
  2. She improves towers and mines if she is touching them
  3. She produces knights every time she can.

Good Saturday, Bad Sunday
On Saturday night I sent a version of the code without expecting much, and it ended up in 2nd place, right in between Agade and RoboStac !
After that I spent most of my Sunday trying to simulate the rival queen with my GA for the first milliseconds of the turn, but I failed misserably while my ranking dropped slowly to towards the 10th place. Iā€™m still not sure what went wrong, but my bot couldnā€™t stop making stupid decisions and I couldnā€™t find the bugs that caused that behavior. Pursuing that instead of improving my eval was the worst decision I made on the contest. On Sunday afternoon I decidedo to drop rival simulation, go back to my Saturday version and try to improve that. Until that moment I didnā€™t have any Giant barracks in my moves, and my mining vs towering decisions were very conservative (max 2 mines unless iā€™m in a preety comfortable position). On Sunday night I made a change to be much more mining aggressive, and I tried that code against Agade, Xyze and Risus and to my surprise, this aggressive behavior paid off and I was beating them more often than not ! I submitted this expecting the same results as Saturday night, butā€¦ The excesive aggressiveness paid off against some, but it took excesive risks and got destroyed in a lot of matches, even to players in the lower end of legend.

Letā€™s balance it out
Finally I made some more adjustments to make the AI more balanced between the mining/towering dicotomy, and with that change I ended up 3rd/4th in the ranking on Sunday night (Agade/Azkellas were computing atm) and finally after the rerun ended up in a comfortable 4th place (same as in BOTG). I really wanted to end up in a podium position, but hey ! Maybe the next contestā€¦

Thanks again to the creators, congratulations to the top 3 and specially to RoboStac that wrote an amazing AI that dominated the competition almost from start to finish. Great work !

12 Likes

Iā€™ve managed to make it to Rank 30 in Gold besides spending very less time coding.

Wood to Bronze :
I spent my first 6 hours in wood3 writing my classes. After that it was easy to get to bronze in just 1 hour. I initially didnā€™t even needed mines because we have gold per minute without mines.

Bronze to Silver:
I wrote a basic sim hoping to implement random search because random search helps avoiding creeps to escape optimally. In a game turn all we can do is 1) Move to a random point or 2) Build at the site Iā€™m located at. Try 40000 random choices at a depth of 5 and choose the one which gives the best score. I score my number of barracks, towers and my distance to my next target and distance away from closest enemy creep.

That helped me get to Silver.

Silver to Gold:
I realized that for making the eval work for the whole problem i need to implement the sim correctly and the weight distribution is very complicated to code because there are just too many factors only if else can resolve. Also as I could only spend very less time for the contest, I switched back to if else. (Feel free to tell me Iā€™m lazy to write a proper sim and eval)
I did aggressive placement of barracks with a full defensive (not as good as simā€™s defense. But my attack is much stronger)

Climbing to high gold

Copying the boss strategy didnā€™t help me go above top 100 because there were too many anti boss strategy at the bottom. I build my mines at my spawn corner, then build a aggressive baracks then build my towers in the other edge of my spawn corner (so my mines wonā€™t be destroyed). This helped me stay defensive as well as not hindering my attack. This strategy miserably failed against gold boss because gold boss builds barracks very close to my tower area and I had very less options to hide. But this was sufficient for me to be there at the top gold.

This was the first contest where I wrote code with few bugs (and none of them were crashing my bot with segmentation faults or run time error) and was able to fix bugs quickly. (May be Iā€™ve improved? :stuck_out_tongue: or is it just the problem is too easy to write code for?)

My repeated feedback that I give after every contest : Open this for Multiplayer immediately just like any other coding challenge websites (like Topcoder or Codechef or Codeforces or what not). Peopleā€™s interest will get reduced 2 weeks from now when you open it up on multiplayer.

3 Likes

Hey T-Dup,

For this contest I coded a LINQ-like queries in C++:

	const Unit closestEnemy = game.Units().All().Enemy().Creeps().ByDistTo(myQueen).First();

The trick here is that the filters methods in your query class should return reference to *this, that allows chaining them:

class UnitsQuery
{
public:
	UnitsQuery(const std::vector<Unit> &units);

	UnitsQuery &That(Filter &&filter)
	{
		filters_.push_back(std::move(filter));
		return *this;  // <-- this allows chaining
	}

	UnitsQuery &Sites()
	{
		return That(IsSite);
	}

	std::vector<Unit> AsVec();

	Unit First();

	...

Itā€™s not as pretty as LINQ, and you have to code quite some code manually, but in the end it does its job quite well.

And to save a bit of performance, you could operate not on a Unit directly, but on a reference or a pointer to it.

2 Likes

Being a C# programmer training my C++ here, Iā€™m still sad not having Linqā€¦
If someone has advice for me

Request Boost to be added to environment. It has range adapters that allow syntax like items | filtered(predicate) | transformed(mapping).

Thanks everyone for posting your strategies; it is very interesting to read.

I have 2 questions for you guys:

  1. For those using simulation-based strategies, how did you guys come up with the set of moves that your queen could make each turn? Like the queen can travel anywhere within 600 radius; how do you determine which were the ā€œinterestingā€ moves you would choose between each turn?

  2. What is your dev workflow like? I spent my time writing all my code in a single file but this became painful. Is there some tool which lets you write code in multiple files but then compile it all into one file for submission?

Many thanks.

1 Like

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.

4 Likes

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.

1 Like

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.

27 Likes

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

13 Likes

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

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

It was a funny contest !

Thomas

8 Likes

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.

Lol, I was thinking the same thing: ā€œno reCurse ? Yay number 1 in canada !ā€ but then you passed me :frowning:
I guess number 2 is okā€¦ :unamused:

gg :smiley:

1 Like

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

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!

3 Likes