# Spring Challenge 2023 - Feedbacks & Strategies

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

6 Likes

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.

## What my bot does

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 :

• Start from the resource cell (the “source”), and find the closest cell that is either one of my base, or a cell with a beacon from a previous pathing. That cell will be called the “target”.
``````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 :

• Do a random beacon mutation (add a beacon, remove a beacon, change a beacon power)
• Simulate for 6 turns, using the mutated beacons for 1st turn, then the static non-mutated beacons for the remaining turns
• Same eval
• Keep the best solution found

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…)

## What my bot cannot do

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

## Conclusion

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

15 Likes

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.

9 Likes

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:

• I chose random resource targets and construct best path from base to it, sorting by already placed beacons/ants/dist, for neighbours with dist<current_dist to target. This makes it deterministic, but dependent on order in which targets are added.
• I store paths to each target, so that when the resource dryed up the ants will distribute over the other targets. This helps a lot to not leave a few resources unfinished for a greater pile.
• Voronoi-based rewards for eating far targets, and overall simple eval i.e. crystals + ants*5 + win conditions. Sum with decay for each turn.
• Somewhat optimized and exact sim, it could be done better, but at least it is much faster than the referee suggest. The exact part was quite important for stability between turns.

A lot of things didn’t work due to bugs or not understanding of the game:

• Full depth search on turn one to find a better targets and optimal solution on isolated maps.
• Estimating the resources that i will gather in couple of turns, to improve win conditions.
• Different regimes of search based on map structure.
• Predicting the opponent behaviour with heuristics.

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.

10 Likes

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:

• Indirect control is an excellent idea as it could simplify the bot logic by taking apart the tactical step to implement a strategy. Consequently, a game with indirect control could be more open to heuristics, a desirable feature for a beginner-friendly contest.
• The tactical step is similar to a resource assignment problem: find the optimal way to assign resources to tasks according to an evaluation function. A greedy algorithm can only sometimes solve this. Usually, I would do a Monte Carlo algorithm to solve this kind of problem in a fixed time range or find a domain-specific exact algorithm.
• Using a non-optimal resources (here, ants) assignment is not straightforward. We have to scratch our heads to know why the ants are not moving according to the plan to implement the strategy we found. It’s hard to understand what’s wrong and what commands we should send.
• Moreover, we must change our strategies to incorporate the tactic implementation, which took off the fun in this contest for me. I could not care about finding the best strategy and waiting for the ants to move into place, but I failed to see how this would help me improve my developer skills. Another solution was to simulate the tactical step to find the best commands to execute my strategy, which was tedious, not fun and defeated the purpose of having indirect control.
• I can agree on having ants not moving optimally according to their order. But then, their algorithm should be simpler to be simulated or approximated by heuristics. Otherwise, bots not simulating the ant allocation method would be weaker than those doing it, again defeating the purpose I see in having indirect control in a beginner-friendly contest.

Input:

• The referee must send each information displayed in the viewer to bots. Scores are a good example.
• We could argue to send data that bots could compute from existing input, like total ant counts, ant increase, and score increase. Bots that do not rely on such info could ignore them, and simple bots could benefit from that data being directly available.

Viewer:

• If you are making a board game with cells randomly named, please display their name in the viewer in debug mode. Otherwise, you could rename the cells so their indices go up from left to right, from top to bottom.
• In fact, I suggest always displaying the cell names/indices in debug mode and having their indices go up from left to right, from top to bottom ^^. This quality-of-life improvement costs you nothing, and it truly helps to debug/analyze from our side.
2 Likes

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:

1. Which resources to target ?

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)

1. How should the tree be constructed?

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.
``````

# Strategy for the early game:

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).

# Challenges encountered:

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.

3 Likes

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 ?

• Kinda hard to go for this strategy with so few simulations, often doesn’t converge to anything decent on large maps.
• Failed to take opponent into account, (tried a 10 ms search for opponent to play against, to my surprise, it did not perform better, was always an improvement in previous contests). So my bot plays against a waiting opponent, not ideal in many cases.
• Simulated annealing performed worse than GA.
• Maybe I should have spent more time trying to improve simulation performance. I don’t use cache or dynamic programming, didn’t have any idea to speed up the sim.
• Depth 3 is pretty low, anything higher yielded worst results, probably because of low sim counts again …

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.

6 Likes

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!

6 Likes

Finished at #13 in Legend

Quite a simple bot actually. I used simulated annealing to find an optimal move.

• Move definition: Two sets of line and beacon commands
• Initialisation: A tree of lines connecting my bases and all resources
• Mutations: Switching lines on/off, changing the strength of a line, adding a beacon on a resource cell, adding a beacon on a random cell, removing a beacon, changing the strength of a beacon
• Simulation: As mentioned above I have two sets of commands. The first is used to simulate the first turn, and the second is used to simulate the next 3 turns. Opponent ants are assumed to be static. The sim is equivalent to the referee, but much faster.
• Evaluation: Simple weighted (discounted) sum of evaluation of the 4 simulated turns. Eval elements are: score, number of ants, win/lose, and number of egg cells where I have more ants than the opponent
• Performance: 6k SA iterations per turn on large maps, and 10k-15k on small maps.

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.

5 Likes

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

1. Is the resource crystals or eggs

2. The number of resources in the cell

3. The distance between that cell and my closest base

4. If I had more ants than enemy could possibly obtain

5. Ratio of crystals left to capture to how many ants i have

6. If crystal was either very close to my base and far from enemy, or vice versa.

7. 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.

2 Likes

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:

• list the objectives to target
• for each of these objectives, generate multiple “variants” (multiple beacons layouts, with various weight)

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.

## Notes for future me

• the choice to do a depth 1 search in the second search was bad: it made my bot a little bit schyzophrenic, trying to go in a direction in the end of first search, and then go in another direction in the second one. I think I shoul’ve kept the same search depth in the second search (like having first turn beacon layouts, and then repeating a simpler layout)
• the choice of GA as search algorithm sounded nice in order to combine objective plans (candidate crossovers ar done at the plan level). But it also suffered from an horizon effect when there were too many objectives, with the first search sometimes missing the most promising objective combinations (especially on big maps). I think I should’ve done something simpler here
• Too much time dedicated to toy playing with magic numbers in evals and technical aspects, instead of taking the time to better think at the game itself (I’ve missed some pretty obvious things that I think costed me a lot)
3 Likes

#49 Legend

My bot was a simple heuristic one with the most complex part being optimizing the beacon placement.

1. 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.

2. 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.

3. 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.

3 Likes

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

5 Likes

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:

• simplified prediction of the remaining number of turns till the game is decided on score
• two modes: “need” egg collection and cr-collection mode (partly based on previous point)
• “keep” the trace to existing targets and choose some new targets
• target choice depends on lots of factors, mode, distance to current paths, distance to enemy, total resource, impossible tp reach, etc.

Search features:

• SA-like search
• number of turns depends on length of new paths (1-4)
• single beacon setup for multiple turns (no succeess with having more)
• only minimal opponent predict (just a light adjust when it seems to have a clear target, everything else failed)
• eval takes into enemy ant/score and also bonus for ant/score gained from “contested” crystal/eggs
4 Likes

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() {
for (int i = 0; i < inPath.size(); i++) {
long diff = cells[inPath[i]].my_ants_next - avg_per_cell;
}
}
``````

Legend bottom to mid legend: I changed the scoring function to this

``````long getScore() {
int minAnts = INF;
for (int i = 0; i < inPath.size(); i++) {
long diff = cells[inPath[i]].my_ants_next - avg_per_cell;
minAnts = min(minAnts, cells[inPath[i]].my_ants_next);
}
//minimum in this inPath should be least..
}

``````

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.

6 Likes

Hello CodinGamers, @logiqub here, finished 60th legend, using Python only.

# Intro

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.

# Snowballing

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.

# Overall strategy

Here is how this game works (I think):

• PHASE 0: Collect eggs only, about 50%. PHASE 1: Rush the center for
• contested crystals, but keep collecting eggs. PHASE 2: Once there are no
• more contested crystals, fall back and take
all resources closer to your bases.
• PHASE 3: There should not be a phase 3, but as a safety measure, collect
anything that is still on the map.

For this to work you need to triage resource nodes by type and sort them by

• Near resources (eggs and crystals): distance to your base <= 1.5 times
distance to the opponent base. If you target every resource, you will
overextend, form weak chains, have low income and get blocked. Plus, it is
not necessary to win (read below).
• Constested resources (eggs and crystals): difference of the distance of that
cell to your base and the opponent base <= 1. The key is that to win the game
you only need half the crystals or more. Therefore, rushing the center is
paramount to rob the opponent of any hope of victory (Sun Tzu). If you take
more than half the center crystals, even if you have less ants, it will be
impossible for the opponent to win because, as you fall back, your chains get
stronger and theirs get weaker.

# Pathing

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).

# Going on the offense ?!

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.

# Benchmarking

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.

3 Likes

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.

1 Like

## Overall Strategy

My bot consists of three parts:

1. Determine target resources to harvest based on rules.
2. Create target path shapes that will be formed by ants and include the resources.
3. HillClimb (HC) beacon positions to achieve the target path. Repeating the process of simulating one turn and evaluating the results using the target path.

## Target resources

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.

## Target path shape

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.

## HC beacon position

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).

### ・Neighboring states:

1. Decrease the number of beacons at a random position by 1 and increase another position by 1.
2. Erase all beacons at a random position and increase another position.
The positions to increase are chosen either from the cells on the path (50%) or completely random cells (50%).

### ・Evaluation:

1. Win or lose.
2. The number of ants on the target path.
3. The amount of acquired resources on the target path.
4. Proximity to the target path.

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.

6 Likes

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)

3 Likes