The topic where you can tell how you liked the challenge and how you solved it.
As the challenge game will be released soon as a classic game on the platform, please don’t share your code publicly.
Global leaderboard: Coding Games and Programming Challenges to Code Better
Hi, my bot ranked #7 in Legend.
I wasn’t convinced in the beggining of the contest, but it ended up being quite a nice game overall.
First, I coded the engine to simulate the ants moves exactly like the referee does.
Then I plugged some sort of search on top of that :
List all potential targets (i.e. cells with resources on them) and compute a weight for each one (basically 1/distance_to_base).
For 60ms do :
Pick between 1 and min(ants/5, 6) targets, with weighted random based on weights set before
Sort the targets by distance to my base, closest first
For each target, place beacons that leads to it. That is done with a greedy heuristic :
current = source
while (current != target) {
var beacon_strength = current == source && current.my_ants == 0 ? 2 * 10 : 10
beacons[current] = MAX(beacons[current], beacon_strength)
best_score = -inf
best_nei = -1
foreach(neigbhor of current) {
if (distances[nei][target] != distances[current][target] - 1) continue
var score = nei.resources * 10 + nei.my_ants
if (score > best_score) {
best_score = score
best_nei = nei
}
}
current = best_nei
}
The beacon_strength computing is designed to act like a “magnet”; put more beacon strength at the “end” of the path if there isn’t a complete chain to the resources, so the ants move a bit faster towards the target.
Simulate that plan for 6 turns, with static enemy. Each time a targetted resource is mined-out, recompute the whole beacons, discarding that target
Eval each simulated turn with : solution_score += (0.8^turn) * (0.2 * (crystal[me] - crystals[him]) + (eggs[me] - eggs[him]))
Keep the best solution found
For 35ms do :
The first part is basic hill-climbing, the second part is done with a SA that I failed to implement correctly (I forgot to include the temperature in my acceptance formula, so it’s a SA with a constant temperature of 1. When I tried to fix that, it performed worse, ofc…)
The bot fails to account the enemy as it should.
Disputed objectives are key; if you can farm a bit more than the enemy on resources that are in the middle of the map in early-game, you often wins, and I failed to implement something that does that.
Because my eval is quite poor, and my search depth “only” 6, my bot would focus on close objectives and ignore more interesting ones that are out of reach in 6 turns. Which leads to suboptimal farming, and to the problem I mentionned right before.
I also tried to replace my greedy beacon heuristic with something better: computing all possible paths of same (shortest) length from the source to the target, and keep the one with the highest : resources + my_ants - his_ants score. On the paper it’s way better, in the arena it’s worse :shrug: .
I heavily relied on psyleague (GitHub - FakePsyho/psyleague: Simple cmd-line league system for bot contests.) during the whole contest (thanks @Psyho), and not once have I found a local improvment that didn’t translate to gains in the arena. Great tool (and RIP CGBenchmark).
Thanks CG for the contest and see you on the next one 
BlitzProg, 97th - 2nd gold
It almost happened
Silver League
I first got to Silver League using a procedural approach: Start collecting some eggs then spread everywhere within my “territory” (voronoi Diagram) using a smarter “LINE” command.
That “smart LINE” will not directly drop beacons between the source and destination, it will instead find the nearest beacon that is already connected to the source, and link that to the destination. Less beacon => more ant on beacons.
“Smart LINE” is pretty easy to setup if you can BFS, just search from your destination and LINE with whichever of your own beacon you find first!
Higher up in Silver League
I then started writing some mutation genetics to improve the procedural commands, using ressource/base pair as genes. When taking a sample, all the genes are read in order, and the corresponding "smart LINE"s are applied accordingly.
Fitness calculation is made using a simulation of the next turn. For the population, I use a mix of un-mutated commands of this turn, with the mutated commands from previous turns + commands made from random set of moves.
This means recoding some of the referee to precisely predict ant movement. Then before outputing, you feed your solution to your own AI and let it see for itself if it’s gonna work out and search for improvement
The mutation is very useful to optimize the point collection and attack/dodge the opponent. Therefore the resulting AI is much more aggressive and steps in the enemy territory whenever it seems advantageous to do so. But it does so at the expense of forgetting completely about eggs. Yet the game, you actually benefit from investing and holding off from scoring early!
Gold League
Getting the AI to stop obsessing for early points and invest on eggs was tricky but absolutely necessary to get past the Silver boss, but I was short on time. so I ended up hardcoding a rule where score is meaningless before turn 8. This small modification beat the Silver boss, and almost beat the Gold boss with it.
Something fun happened where my AI elo was consistantly worthy of legend until right after its match quota was done, then it constantly teased me with a mere 0.01 elo difference with the boss, never actually letting me past. This was a very entertaining conclusion to the challenge, even if a bit frustrating!
There is probably still massive room for improvement for my AI, as I stopped making any progress as soon as Silver boss was beaten. For example the turn 8 was completely choosen arbitrarily, and I barely ever changed the different factors of my fitness function.
Thanks you for the contest!
Edit:
Legend League
After the contest, I implemented a common strategy suggested in this thread, that is: fight for the center. During the contest, I was giving the same amount of evaluation points for any beacon placed on top of crystals. Now, targets in or near the voronoi border are heavily prioritized. This passed the gold boss with about 1.4 points in difference and I ranked up to 70th legend overall.
Top 18 legend
I did what I think many people end up doing, namely put some beacons with equal weigths in paths to some targets, sim N turns, eval. After that search optimal first turn beacons distribution with basically the same engine and eval. I use MC and HC for this parts correspondingly. It was also really important to gather eggs in begining and contest the crystalls that are voronoi-neutral (equidistant from players bases) as soon as possible.
Some implementation details:
A lot of things didn’t work due to bugs or not understanding of the game:
I overall quite liked the game, and I’m probably in the minority here to say I liked the indirect control aspect of the game, even though it was somewhat poorly implemented in the referee. Sim based aproach quickly gave quite good results, inspite of a lot of bugs that I fixed to the very end of contest, and being in the upper part of ladder gave a lot of motivation to keep going. Thx a lot to organizers, and to the community, it feels good to be back and fully availible for the whole contest.
Thank you CodinGame for making this bot programming contest. I’m glad you are still making one of these.
Unfortunately, I gave up quite early as new priorities popped into my schedule, and I was not motivated enough to pursue the contest. Thus, my opinion might reflect something other than that of the majority, and you may have to ignore the following. After reading the postmortems of other players, I’ll give this game another chance when you release it as a multiplayer game.
Game:
Input:
Viewer:
Rank: #177 global (#82 Gold)
As always, I’ve tried to keep it simple to facilitate the implementation of new ideas.
There are essentially two questions that need to be answered:
Each resource is assigned to its closest base.
For eggs, I’m targeting half of the eggs that are closest to my basis.
For crystals, I sort them by distance and select enough to have victory (i.e., selected crystals plus my score exceed half of the total crystals)
The problem at hand is not the minimum spanning tree problem, as not all nodes need to be visited.
Instead, it is the Steiner tree problem, which is known to be NP-complete.
To tackle this, I adopt a greedy approach to build the tree:
Choose the nearest node to the tree.
Perform a breadth-first search (BFS) to add the path to the tree.
During the first four turns, I focus solely on targeting the two closest eggs per base.
After that, I expand my scope to include all resources (eggs and crystals).
I struggled to optimize the movement of ants (i.e tuning the strengths of the beacons).
Each attempt I made resulted in poorer result compared to my current implementation.
This was likely a key factor preventing me from reaching the legend league.
Hello, my bot ended up #12 Legend
My bot is a depth 3 full simulation GA for 95ms.
I only managed to get ~2k sim per turn on large maps, so the bot often plays far from optimally there.
To aim to eggs then crystals I compute a score based on remaining eggs and crystals on the map and my ants count. At some threshold, I switch focus, the idea is simple, your initial focus is to harvest eggs to be able to harvest crystal faster but you don’t always need to get all the eggs.
Eval: quite simple, ants counts, crystals score, reduce distance from what we’re after at the moment, some bonus to form good attack chains.
This simple bot doesn’t have the insight to leave the crystals close to its base(s) and go fighting to the middle ones. I tried to implement this behavior (witch was needed to climb the leader board) in the eval but failed.
So I trick him.
I compute the remaining crystals needed to win : (opp_score-my_score+remaining_crystal)/2
If I have enough of crystals closer (or equal) to my bases than opponent to win, I do nothing and let the bot do its things.
If not, I mask the crystals cells that I feel are pretty much secured, putting their resources to 0. The search then go to more contested ones, ignoring those closer to my base.
What didn’t work ?
To wrap things up
Thanks to codingame for hosting programming bot contests, I love those 10 days twice a year.
Thanks to @Psyho for psyleague, just like Neumann, I used it extensively to test any ideas, refactoring…
More often than not, what you think maybe an improvement is not, testing locally before sending your bot in the arena is a must if you want to climb the leader board.
Legend 20th
Similar approach to @Neumann / @wlesavo.
First, I converted the referee from Java to C++ until I was able to simulate the same games in the IDE and locally.
Then, I used a messy MC / hillclimb hybrid, to place beacons and simulate for 5 turns while opponent waits.
The evaluation was the difference of score + weight * ants, where weight was scaled proportional to remaining food.
My number of simulations was kind of small, mostly due to the pathfinding required to compute actual moves (probably room for improvements here).
Also tried to GA (combining multiple beacons placement) and a small NN (for evaluation) without success.
Thanks CodinGame for this great event again!
Finished at #13 in Legend
Quite a simple bot actually. I used simulated annealing to find an optimal move.
Was a fun contest, thanks for organising!
PS: the reason why the 1+3 turns works well, I think, is that if a resource has only a little bit left, keeping your ants hanging around there for 4 turns is bad, so they prefer to go elsewhere leaving some resource unharvested. By allowing one turn of harvesting and then going away, they will prefer harvesting. Of course, if the resource is not depleted yet they will again choose to harvest for 1 turn in the next turn. This allows the ants to clear every resource.
#87 Legend
Python 3 heuristic script with a bunch of ifs.
This competition obviously favored a strategy which simulated multiple turns and picked the best path, but I did not do that, because I battle in the shade.
I created a graph mapping how to get from each cell to any other cell in the grid using Djikstra, but slightly modified: my provisional path between A and B would be the shortest one and in event of a tiebreaker, the one with the most resources on it. I evaluated the value of aiming for any cell containing resources by the following factors:
Is the resource crystals or eggs
The number of resources in the cell
The distance between that cell and my closest base
If I had more ants than enemy could possibly obtain
Ratio of crystals left to capture to how many ants i have
If crystal was either very close to my base and far from enemy, or vice versa.
If the cell was equidistant between my base and enemy base
I then picked any moves that were within a certain factor by my scoring metric of the maximal scoring move.
I then went through each of the potential moves adding them to my desired move list but modifying them if other paths I had already chosen allowed me to form a shorter path to the desired destination.
If I ran out of ants to populate cells, I stopped adding paths.
I then did a pruning logic where having established which paths I wanted to take, I try removing each of them to see if i still had complete paths connecting all start and end points. If I could remove cells I did.
Thanks to codingame and fellow competitors.
Legend 23rd
Thanks Codingame for this contest ! Kudos for reactiveness, even during weekends (thanks for that too !), on bug fixes, referee improvement, and other glitches.
My bot is simulation based, since the end of silver league.
In its latest form, it is composed of two GA searches. My “search space” is computed like this:
A candidate of the population is a combination of objective variants.
The first search uses a rather simple eval (crystals, ants) with a depth 6 to 8 (changing the depth had a low impact on outcome, except on biggest map, to break the horizon effect), and a subset of variants (only full beacon path variants, either going to closest base, or to closest harvesting chain). The purpose of this search is to find the “master plan”, the objectives to target in priority.
The found best plan is then duplicated in all candidates and used in a second search, with a lot more beacon layout variants, and the ability to mutate strength per variant. This search is depth 1, with a more complex eval (to compensate the lack of depth insight). Here the purpose is to fine tune next turn beacons placement to maximize effectiveness.
#49 Legend
My bot was a simple heuristic one with the most complex part being optimizing the beacon placement.
Determine target cells based on map type (surplus, famine) and various factors such as ratio of distances to my/opponent closest base, % of eggs gathered, % of crystals gathered. Generally the goal is to go for eggs first, then contested crystals, then safe crystals. I tried to use sim/eval to determine the target cells, but didn’t manage to make it work better than the heuristics in the limited time I had.
Build an optimal path connecting the selected target cells. My approach was to use a greedy nearest neighbor algo, where new paths are added based on shortest distance between any cell already in the tree and any not yet included target cell. I stopped adding new paths if my ants would be spread too thin. This algo does not guarantee to find the shortest possible path between target cells, but it seemed to work well enough in practice.
Optimize beacon placement by reimplementing the ant allocator from the referee and using hill climbing to find a set of beacons that produce the desired ant movements. My implementation was buggy though.
I really liked this challenge except for the need to trick the suboptimally implemented ant allocator into making the desired ant moves. Thanks to CodinGame for organizing.
52nd position Legends
Initial AI: Pathfinding
My initial AI utilizes a BFS-based pathfinding algorithm to locate the best available resources on the map.
I started by path closest to the bases,
I continued to search for resources closest to the previously discovered paths, and so on.
I stopped this search when I ran out of ants to fill the paths.
I used one marker by cell (cannot find better …))
Inclusion of KPIs :
I defined several important KPIs:
-Path density factor: number of ants per marker.
-Path density factor with enemy presence: number of ants per marker when the enemy is present. This allows me to react more or less to the enemy’s presence. The path with the enemy is more costly, so it is naturally ignored if I don’t have enough ants.
-Exclusive egg collection time: I collect eggs until a certain limit of available power on the map, which is effective in resource-rich maps.
-Exclusive power time collection: I collect power since a certain limit of available power on the map
Writing the Game Simulation C :
I started the complete re-coding of the game to achieve a perfect and relatively fast simulation.
This step takes me a lot of time, particularly to accurately reproduce ant movements based on markers and perform score calculations.
It also allowed me to gain a better overall understanding of the game.
Local Testing:
To verify the proper functioning of the simulation in all situations, I wrote tests and ran the game locally , playing against myself to check conformity to CG original code in java.
These tests validated the accuracy of the simulation and helped address any potential issues.
Performance of My Game Simulation:
My algorithm is capable of executing around 60 full game simulations (60 x 100 cycles) on the most complex maps, with two AIs.
On simpler maps it can handle even more simulations.
My Final Algorithm:
I run multiple complete matches of my AI against my AI.
I test a combination of KPIs for the first AI with my current state.
The second AI has fixed KPIs and works based on the last known opponent state of ants position/scores.
After the simulated battles, I select actions corresponding to the KPIs that generated the highest score.
Conclusion:
Full game coding for efficient simulation, rigorous local testing, simulated battles using two IA (variable and fixed KPIs), KPI-based pathfinding.
Thanks CG 
Great post and great solution. I just wonder how did you come up with the scoring function?
As with many other contests I started with heuristics to have a better understanding of the game. But this time I was not able to field anything special for quite a few days, the games seemed hectic. So inspite of my initial uncertainty in the complexity and assumed slowness of the allocation code I decided to add simulation. I had immediately jumped to top3 and remained in top10 till the end. I was surprised that first version of search worked so well, but later I realized that it was not really possible to seriously improve it. Most improvements came from new/improved heuristics, but even there only 1 out of 10 ideas worked, the game is just complex. Local testing was a must, but not enough, as variance is huge. Congratz to winners, and thanks for great challenge!
As many others I have combined target choice through heuristics and search with actual simulation for a few turns.
Heuristics worth mentioning:
Search features:
59 Legend
Wood 2 to Wood 1 => Used LINE command to all crystals from my base with 1 strength
Wood 1 to Bronze => Tried prioritising cells with most crystals didn’t get good results. Then I noticed what the boss was printing… He was simply LINE command with 1 strength to all the crystals except in the first 5 turns where boss was using LINE commands to all the eggs… So I just mimic him and got promoted.
Bronze to Silver => I assign each resource to the base I own that’s closest to this resource and solve the problem for each base. I chose half of the resource cells for this base (closest from my base). I find a Minimum Spanning Tree with these cells and do a BEACON command with 1 strength to this tree.
Silver to Gold => Lot of bugfixes by finetuning against replays that I lose by huge margin. Improved the MST slightly by prioritising to remove the farther nodes without any resources first so that I end up with a good tree with good no. of resources. I included a new constant called eggTurns that’s proportional to the number of initial crystals in map… Until eggTurns I prefer eggs over crystals. I still give 1 strength to all my BEACON targets.
Gold to Legend Strength allocation by mutating the strengths of my beacons starting from the solution with average ants as the strength at each beacon target. I had to copy the ant allocation part from the referee to compute the ants in next turn for my strength allocation. This is how I scored a game state.
long getScore() {
long bad = 0;
for (int i = 0; i < inPath.size(); i++) {
long diff = cells[inPath[i]].my_ants_next - avg_per_cell;
bad += diff * diff;
}
return -bad;
}
Legend bottom to mid legend: I changed the scoring function to this
long getScore() {
long bad = 0;
int minAnts = INF;
for (int i = 0; i < inPath.size(); i++) {
long diff = cells[inPath[i]].my_ants_next - avg_per_cell;
bad += diff * diff;
minAnts = min(minAnts, cells[inPath[i]].my_ants_next);
}
//minimum in this inPath should be least..
bad -= 1000 - minAnts;
return -bad;
}
Overall I’ve enjoyed this contest. Guess I’ve become Dr. Pym from AntMan now as I can control multiple ants at the same time 
Thanks to the problem setters, testers and system admins who gave a smooth contest.
Hello CodinGamers, @logiqub here, finished 60th legend, using Python only.
In this contest, I was top 100 from start to end, hovering near 50, but around
15 in the first days. Unluckily, I never tried to read the referee code,
because I kept coming up with ideas, watching the games, coding, evaluating and
deciding whether to keep new features or not. The last two days, after legend
opened, I was stuck against the wall of players who knew how to adjust weights
to raise their population quickly. Couldn’t stay in the top 50 because of that.
What must be understood about this game is that it snowballs extremely fast.
Missing one ant in the first 5 turns can mean defeat with little hope of
recovery. Because I am still bad at coding, I used obsveration and tricks to
keep up with everyone else. And I am glad that the game’s design allowed for
intuitive types like myself, to get that far with heuristics alone.
Here is how this game works (I think):
For this to work you need to triage resource nodes by type and sort them by
distance to your bases.
And to get the distances, you can compute everything at the start, since you
have 1000 milliseconds of initialization for the first turn. There has to be a
smarter way of doing this, but I just wrote a flood fill algorithm and repeated
it on every square, putting the results in a map.
To build chains, I put beaons starting from the resource node trying to join
with another beacon already set or a base. This way, I guarantee minimal
routes, but I also take into account the existence of other resources on the
way back. That way, I maximize income. And finally after every beacon is set,
I remove the redundant ones (remove and check if everything is still connected)
to maximize the strength of chains. And by the way, unless it is the first
chain (some maps have the closest egg 5 cells away), all chains must have
strength >= 2, unless there is good reason to do otherwise (like contesting the
center when there is a single crystal).
That is it. What should be done to improve this strategy is to include chain
strength calculation to seek and cross opponent chains that are weaker than
yours. Should be possible, even if you have a lower ant count, and you could
paralyze the opponent by gonig through their base, checkmating them.
There are also times where one or two crystals are on the map, but those
situations occur only in 1-3% of games. I spent hours optimizing for that case
but ended up removing that code, because this percentage is too low.
And this is the crucial ingredient that makes everything work. Fine tuning
parameters and features. I keep versioned source files, which I set to readonly
with a version number. It’s far easier than dealing with git or mercurial.
I wrote my own tester in the previous contest where I finished 176th. And
pretty much used the same code without modifications. The only new thing I did
was using the game log to filter which phases where activated (thanks to the
message you can write). That is how I knew maps with one or two crystals
represent only 1 to 3% of games, and I should never have spent time optimizing
for it.
Accuracy begins with samples of 150 games, and are usually good enough above
500. Because my code runs in less than a millisecond, I could run a thousand
games in about 3 minutes, using 3 cores. After each run, against all previous
versions, if the improvement is above 5%, I can consider keeping the change.
(Google translation below)
259ème global, 164ème/400 en gold, heuristiques.
D’abord merci à l’équipe CG pour ce challenge très intéressant. La difficulté à simuler a permis de laisser plus de chance aux personnes utilisant la logique et les heuristiques. L’épreuve s’est très bien déroulée techniquement, les délais des arènes étaient très corrects.
Pour commencer j’ai décidé de passer bronze rapidement pour éviter les embouteillages, j’ai donc soumis en 10 minutes un code qui sortait des LINE entre ma base et chaque ressource présente. Passé bronze en une demi-heure (2ème/200 après 35 minutes, puis-je avoir l’achievement correspondant ? )
Je passe les détails sur l’évolution de mon code, j’ai juste appliqué plus que d’habitude le principe du « keep it simple ». Voici le fonctionnement de mon code actuel, très facile à comprendre et à coder :
attribution à chaque case d’un score dépendant de la ressource présente sur cette case et celle de ses voisins directs (0 si rien, valeur plus élevée pour des œufs que pour des cristaux).
Calcul des distances et des chemins entre chaque case intéressante (base ou ressource) et la totalité des autres cases, avec un algo flood fill mais basé sur un dijkstra (grâce au score précédemment calculé) plutôt qu’un BFS. Cela pour accepter un léger détour si ça permet d’avoir plus de ressources.
Pour chaque ressources, repérer la base qui en est la plus proche.
Tri des ressources en fonction de leur distance avec la base qui en est la plus proche, avec un biais pour favoriser les œufs par rapport aux cristaux.
Et enfin calcul des BEACON à placer, pour cela une boucle sur chaque ressource (dans l’ordre précédemment trié) et tant que j’ai assez de fourmi (au moins 2 par cases) :
cherche quelle case contenant un BEACON (ou une base) est la plus proche de cette ressource
récupère le chemin entre cette case et cette ressource, place un BEACON sur chaque case du chemin.
Petite anecdote, j’ai appris que les LINE fonctionnaient mieux quand le 1er index est celui de la destination. J’ai simulé ça avec mes BEACON en les triant juste avant l’output, du plus éloigné de ma base au plus proche. Le résultat s’est effectivement fait sentir, sûrement pas autant qu’une simulation, mais faute de lire le code source du jeu ce critère s’est avéré avoir le bon rapport efficacité / simplicité.
259th overall, 164th/400 in gold, heuristics.
First thank you to the CG team for this very interesting challenge. The difficulty in simulating has given more chance to people using logic and heuristics. The event went very well technically, the time spent in arenas were very correct.
To start, I decided to go bronze quickly to avoid traffic jams, so in 10 minutes I submitted a code that printed LINEs between my base and each resource. Passed bronze in half an hour (2nd/200 after 35 minutes, can I have the corresponding achievement? )
I skip the details on the evolution of my code, I just applied more than usual the principle of “keep it simple”. Here is how my current code works, very easy to understand and to code:
attribution to each cell of a score depending on the resource present on this cell and that of its direct neighbors (0 if nothing, higher value for eggs than for crystals).
Calculation of distances and paths between each interesting cell (base or resource) and all the other cells, with a flood fill algo but based on a dijkstra (thanks to the previously calculated score) rather than a BFS. This to accept a slight detour if it allows to have more resources.
For each resource, locate the base that is closest to it.
Sorting of resources according to their distance from the nearest base, with a bias to favor eggs over crystals.
And finally calculation of the BEACON to place, for that a loop on each resource (in the order previously sorted) and as long as I have enough ants (at least 2 per cell):
finds which cell containing a BEACON (or a base) is closest to this resource
get the path between this cell and this resource, place a BEACON on each cell of the path.
Little anecdote, I learned that the LINE works better when the 1st index is that of the destination. I simulated this with my BEACONs by sorting them just before the output, from the farthest from my base to the closest. The result was indeed felt, certainly not as much as a simulation, but for lack of reading the source code of the game this criterion turned out to have the right efficiency/simplicity ratio.
My bot consists of three parts:
Initially, I check whether I can win solely by harvesting crystals near my side.
If I can, I utilizes chokudai search (a time-managed beam search) with simple actions (such as setting beacons to maintain current positions or setting beacons on the minimum spanning tree of resources) to determine which resources it should go for.
If I cannot, I greedily selects all the higher-tier resources.
Tier 1: All eggs. Crystals near my base but also close to the enemy’s attack chain. Crystals at the same distance from each base, taking a few turns to obtain.
Tier 2: Crystals near my base or close to my attack chain.
Tier 3: Others.
I construct a minimum spanning forest by considering my bases and target resources as vertices. When choosing the path between vertices, I apply dynamic programming (DP) to score each cell based on the distance from my ants and the number of resources/ants on the cell.
I set the same number of beacons as ants and evaluate the board by simulating the states after the HC process (30,000-140,000 simulations per turn).
Congratulations to @MSz and Domiko for the 1st and 2nd places with your impressive bots. My bot is nowhere near that level, and I’m eager to read your PMs.
I would like to express my gratitude to CodinGame for organizing this challenge, and for successfully completing it.
37th in Legend
My architecture is similar to @Neumann & other’s: A simulator, a ‘strategy’ optimiser which schedules which resources to begin targetting when by hill climbing, and a ‘tactics’ optimiser which mutates beacons for the next turn only.
I don’t use any scoring function for partial games, instead always sim to the end and prefer: victories, then earlier victories (or later losses), bigger victories (smaller losses) on the same turn, and only in case of same-turn crystal ties do I care about ants. I could see many had heuristics to favour early egg gathering but also that the best way to do that was very map specific and that the game should be simple enough (at resource targetting level) that some kind of optimal balance should be derivable from end game state without adding arbitrary conditionals.
The result was mixed: My bot tends to beat similar ranked players while gathering less eggs. Sometimes it will make really insightful plays and appear to trade early resources for positional advantage. But it’s undeniable that having more ants makes for robustness in the face of opponent uncertainty because you’re more likely to show up at contested resources with stronger attack, and on most maps the top bots are gathering both more eggs and more crystals than mine.
This full game sim choice also made it important to model the opponent. I run an opponent plan through the same strategy optimiser as my own each turn. Occasionally this works beautifully (eg. my bot predicting it will lose by 7 crystals in 15 turns and then doing exactly that, or spotting opportunities to steal unguarded resources in opponent’s territory, or hanging out near key resource piles but only moving on them when the opponent begins to), other times the opponent prediction and their actual play diverge too much that my bot gets very erratic or even delusional (eg. believing games which actually end at turn 40-50 can be won by attacking opponent’s expected weak lines and extending the game until turn 100).
The problems are: My plan and predicted opponent’s plan end up co-evolving in a sort of cooperative way which doesn’t reflect genuine gameplay. And I don’t have any really profound way of re-syncing the opponent’s plan to their actual play. In the last hours of the contest I finally got around to optimising my ant allocator sim (with it’s horrible n^2 log n sort, for n of the order of beaconed cells you have). After a 20 fold improvement in num sims/time I was confident my strategies would be even better and they seemed that way, but unfortunately the opponent over-fitting got much worse so I was left trying to tame that in the final 3 minutes of the contest. Overall I was a little disappointed in my final rank and eagerly wait the forever-arena to open and try to find some missing potential.
My tactics optimiser was very simple: Move a beaconed cell (or a half, quarter, eighth of the beacons) to another random cell and keep the change if it improves the attack power (as a proxy for gather power) on the next turn on any resource that has less or equal opponent ants on it the current turn. I’d wanted to make it a bit more focused at improving partially-built paths (something like @cegprakash’s method sounds good), and perhaps look 2-3 turns ahead but this was already powerful so I didn’t expend much work on it.
Feedback wise: I concur with others that indirect ant movement was a great choice over simple MOVE commands some requested. However I also agree the ant allocator logic was a bit more arbitrary than ideal, because of the ordering by cell indices. It might have been more intuitive and lead to more creative beaconing solutions if the ordering was by beacon strength or some other priority we could control. But there was plenty of depth to the game elsewhere and the default movement logic wasn’t that bad most of the time even without mindless mutation mashing.
This was my first CG contest I dedicated proper time to and really enjoyed it! - thanks to everyone involved in running it, and everyone else who competed (especially those taking time to share write-ups) 
