# Ghost in the Cell - Feedback & Strategy

The challenge is now over and, as the best of you keep making matches to reach their final ranking, you can now tell us how how you liked the challenge, & how you solved it. (Do not post full code here.)

Don’t forget to register to the next contest here: https://www.codingame.com/contests

I did lots of small optimizations… heuristics and dumb code and it got me to the Legend finally (final place is #19).
How I did it:
0. Bomb sending. I choose most fat enemy factory and target there a bomb and 1 unit. So right after the bomb on next turn my unit would conquer the zone.

1. defending, calc free units and help needed
1.1 I was sending units to help defend only from factories which are no more than 3 turns away, it helps against cases when you try to send a unit over whole map.
1.2 Instead of predicting how much units I need on every turn - I did it other way: I wrote a function which calculates max bandwidth for incoming troops (e.g. max cyborgs coming at the same turn to the base). Then I feeded coming enemy cyborgs and coming my cyborgs (but not all, I limited them only to troops which are about to come in 5 turns or less). The difference was the help needed.
1.3 For my zones with no incoming enemy troops I predicted that they could be attacked if there are enemy zones in direct vision (i.e. shortest path is not going through my zones) with cyborgs around (nor more than 3 turns away) and they have more cyborgs than our zone. So I requested for such zones help too.
2. bomb - choose best target to attack and also protect from enemy bombs (detect them and move out when they about to hit me). Detecting - I was calculating my most fat zone on every turn and when I saw a bomb - I predicted that it was targeted to my most fat zone on previous turn.
3. If all bombs are done or my_cyborgs-enemy_cyborgs>=20 (across all zones) and I have enough cyborgs on a zone - I do INC.
4. If I can’t INC - I attack with all zone units. If I can INC and my production<3 - then I dont attack and collect units for upgrade.
3 Likes

BlitzProg, ~300th

Really liked it. Simple and interesting to code, and the best way to play isn’t as obvious as it seems.

• Wood league was about targetting the nearby factories and spread quickly. That did the job for me.

• Got past bronze using a pathfinder to reach my goals more efficiently and allow most armies to change their mind halfway. The behavior also got armies to “defend” factories in the way, which was very helpful. hardcoded bomb so one get sent turn 1 to the opposite starting factory.

• Got past silver with some strategical optimisation. Only INC when a factory is secure (not in front of the ennemy), secured factories that produce 3 have no reason to have any army inside, send them out. I also bomb other 3-producing factories. Don’t attack with more units than what is needed to defend yourself.

• That is all. I have wasted the rest of my time trying genetics to get beyond that, it was a huge failure, Not effective at all and random time outs, so the IA that made it past silver is all I’ve got. I’m very bad loser, so I’m going to bed and sulk a lot.

Congratz to the winners! I hope I can do better next time, I really need some decent preparation if I want to stand better chances going into legend league.

4 Likes

Excellent contest!
I followed the same steps as dyatlov. Pure defense+bombs got me in the top 200 mid-challenge. Didn’t have enough time after that and did basic attacking which got me nearer the top of gold.
Messy code didn’t help me improve things near the end…

Nothing automatic, no minmax/genetic algo etc., everything was deterministic with simple if/else stuff.

2 Likes

Yo!
Top gold while calculating.

Used a Genetic Algorithm where the solution was every factory I own in depth and every other factory as size. Moving units to a location further than 7 is too risky, so I prohibited my GA to send units further. I did try multiple moves ahead, but found it worse than only trying the current round.

One round:

• Simulated the enemy against myself which did nothing.(10 ms)
• Simulated myself against this enemy. (30 ms)
• Sent bombs on the first round against the expected factories taken by my enemy.

After sending troops I simulated the game 7 rounds ahead (without sending more units). Bombs were also simulated. Though I removed 100 cyborgs from a bombed factory to scare my eval.

Eval:
5MyProd + Cyborgs(in factories) - 5HisProd - HisCyborgs(in factories)
Didn’t consider moving cyborgs, because they would be moving more than 7.

Enemy bombs:
I found the 2 most likely targets for each bomb, then added them with correct timer and target instead of the actual “-1” bombs.

Move:
When my GA was done I used a shortest path matrix found with Floyd-Warshall (implemented the last hour). To send the units. I didn’t care if the shortest path was owned by an enemy or was neutral. (Did not use shortest path while simulating, but set the Length of the path to the shortest path.)

Very good on small maps where it predicted how to own the enemy in the first rounds. Though it had problems vs bots which focused only on upgrading. Since it wouldn’t find the optimal upgrade path.

I created a GA framework(C#) for CSB which I used in this challenge:

In this game I used a population of 10 with 1 Elitechild (which is the best from the previous round)
1 Mutation of the elite child
5 Crossovers (swapping parts of 1 solution with another)
2 Random mutations
1 Completely new and random

A published source code is really helpful when simulating.
Also, fun and interesting game!

6 Likes

I ended up 22nd in legend. My bot tried to prioritize the following:

• Every node would calculate it’s spare amount. I did this by simulating 20 turns into the future and finding the minimum number of my cyborgs at that factory. I also assumed any enemies that were closer or the same distance as each factories closet friend would attack with their full amount. No factory would ever send cyborgs out if it would reduce the spare below 0 (except for bomb evacuations)
• Try to move cyborgs from the closest factories to any that had spare < 0 in order to defend them.
• Try to take any neutral production factories that are closer to me than enemy, with the closest first.
• Calculate the factory that is furthest from the enemy that isn’t fully upgraded and send up to 10 cyborgs from the closest factory with spares. If there is a 0 production neutral factory that is further from the enemy, send to this instead.
• For every factory with more than 10 spares, upgrade if possible.
• For every factory with spares left, if there is a friendly factory that is closer to the enemy, send them all there
• For every factory with spares left, send them to the closest enemy
• For every factory that might be hit by a bomb this turn, send all cyborgs to the closest factory that won’t be hit by a bomb on the turn they arrive. Every time an enemy bomb launched I’d calculate two targets - the closest 3 production factory to the source and the most valuable factory (which was production * 3 + current) and say the bomb was heading for both of these.

For bombs I’d bomb any factory that the enemy had that was the highest production on the map with a timer to ensure the same factory didn’t get bombed twice too quickly. Any factory with more than 30 cyborgs (after first turn) would also get bombed, but I don’t think this can trigger anymore as it would always have used the bombs by the time this happened.

I did something different on turn 1 where I did a search of all possible combinations of factories I could take that are closer to me than the enemy to work out the best combination. If the starting enemy factory had the highest production level on the map I’d also launch a bomb straight at it. I wanted to improve this to do a multiple turn search but didn’t have time (I saw a map where I started with 28 cyborgs and there was a 13 and 15 factory so I couldn’t take both with orders from the first turn).

At every point any routes were calculated to find the shortest route with the most possible nodes in it (as it’s always better to have cyborgs on a factory instead of in transport).

8 Likes

447 - gold

This game was really fun and seems easy at first but finally really hard!

I used a pseudo-random strategy with an evaluation and it was easy to go to gold. After that…

Strategy

• simulate 10ms random enemy move and take the best
• simulate the remaining time player move and take the best

Eval

• play 1 turn and evaluate the following 15 turns increasing factory when possible to favor the IA let some troops to do this action later
• eval on cyborgs, bombs remaining (malus on using to avoid wasting them), production, small malus on troops moving, factory position (far from enemy and close from my other factories is better)

Adjust the evaluation was really painful and the AI did rarely what i was expected. No increasing factory one time when another just doing that and no moving…

I didn’t have time to predict enemy bombs targets.

Congratulation for the legend players and the winners!

It’s my worst ranking on contests but it was really funny and i look forward to do better when it will be available in multi.

3 Likes

My 13th and favorite conquest ! Simple rules but hard to master, like my favorite games (Go, Chess, Hearthstone …)
And no time wasted trying to implement elastic collistions like in Quidditch or Pod races …

I was about 70th legend (#2 in Scala) this afternoon with 15-20h of programing this week.

I didn’t use any genetic algorithm, minimax or other clever stuff, just some basic logic. By priority desc :

• keep defenders to avoid losing a factory in the next 5 turns if possible (I added this on Saturday to reach legend league)
• up to 8 “conquer plans” : a set of moves which would reach to capturing a factory if no extra moves are played by opponent. These were scored with an heuristic : benefit/cost (benefit = cyborgs gained in 20 turns, cost = cyborgs lost against neutral and cyborgs time “used” in travel). So I highly priotize capturing enemy over neutrals
• send a bomb if an enemy factory has 2 or 3 production and is not already bombed in the 5 turns to avoid overlap
• avoid enemy bombs : move cyborgs to closest factory
• leave cyborgs in factories which can be upgraded
• upgrade factories if they cannot be captured soon and are not under possible bombing
• move remaining troops to the center (factory 0)

I tried on the last 24h to predict opponent moves and react but this gave me much worse result.

This accounts for about 700 lines of Scala, purely functional style.

I also have 400 lines of tests : to implement the game engine and basic features I now use a Test Driven Development approach which saves me lots of headaches since debugging a simple test case is much easier than a full feature in a match.

Oh and I also implemented very early looking for “stops” in a trip : safe factories which do not make the trip longer, this allows my AI to “change its mind” if the situation has changed instead of having cyborgs busy for too long.

8 Likes

Hello Thx for this contest, i think it was the more interesting i have done ^^ : few easy rules, “easy to understand, hard to master”… More possibility for pure algorythm ^^

My “Strat”: I just done an array of Factory/Time… full it with Moving entity, and then, Tryed to make it better for me at Round 20…

To choose Action:

• I First check for defend… (to beat other on def, you just need same number of bots…)
• After, i check every attack i can do… (but need +1 Troop) => easier to defend than attack, for same result (for same production)
• Then, the move part=> Evacuate Factory with bomb incoming Next trun… Troop can’t be loose this way… better to save same, lose the factory, but better to just send same to nearest NMY if they don’t have safe spot… will kill Troopers at least…
=>INC if my Prod isn’t upper than the opponent… (INC Is Good, but need 10 Troupes, so if you win a factory by fight, you win “free” troop income…that’s wy it’s after…)
=>Then, I move every troops resting to the fight…

No “Pathfinding” just checking All AC where AB+AC <= AC during First Turn… make a list of them…
when i want to move, from A to C, i Check If There is one or more B, i take the shortest AB (and clean when i go on)…

if there is an a “Shorter” ABCD than AD, I will find C when looking shortest way to D…

When you put All Moving troops in an array of turn on factory, you just have to check states of Factory at the turn=Distance +1… if it’s the turn where a bomb can land… don’t go… Make easier all decision… (checking if B is fre… for exemple…)

And if you seen troops incoming at the good distance to bomb them… easy kill… (don’t append often, but when it’s the case… )

No Adv prediction, he will react to my actions anyway… but i check for my Attack if he has enough troup to defend around… if yes, i don’t attack… if no, i Send them to fight… take his production, even 1 tour, can change the match…

Simple heuristique, hope to finish in Top50, but not sure… pushed a last version with a trick on map where there is no prod>1… in this case, i don’t send bomb if i don’t take 5 troop on Factory… can make some lucky strike… or loose because my ADV as at least 5 more trooper to kill me…

Thx Again, was realy fun to do that and happy to not have to wait to long before the next one ;p

(Sry for my english btw ^^just passed few debug-coding hours, i’m tired to read myself ;p)

3 Likes

Bottom legend.
My bot is petty much the same as other heuristic bots described above.
Only thing I did differently is I separated Orders from executions:
2 step process:

1. Get the list of all possible orders: attack, backup, upgrade, upgrade_assist
2. Rank all the orders and try to execute most high ranked one
2 Likes

I took a relaxed approach to this one. Nothing earth-shaking and no heavy-duty thinking involved; I simulated the whole board for 10 turns and used that as the basis for my movement decisions. I didn’t do enemy prediction since unless the enemy was 1 move away you already knew what would happen in the next turn. The decisionmaking was just boring if-then stuff… first reinforce, then find a bomb target, then send an invasion force after a bomb if it’s close, etc. Each step involved trying every possibility and then picking the best of them based on heuristics for each one. I had it all done by the time Gold opened and I didn’t improve it much afterwards (though that wasn’t for lack of trying).

• 1v1
• 50ms time limit made for fast evaluations, even if it limited some algorithms
• Simple to grasp

What I didn’t like

• At the high levels, the mechanics of the game didn’t allow for comebacks… if you fell behind, you stayed behind.
• (obviously) whatever the heck happened to the servers at the end

Finished 51st in Gold, #274 overall.

Special thanks go to @EulerscheZahl for being so open about his methodology and helping lots of people (including me) make their bots better.

7 Likes

Hi everybody,

Again, this challenge was very nice. Here are my strategies :

• Wood 3 boss : Select the factory with the most cyborg. Send random number of cyborg to the nearest factory.
• Wood 2 boss : Wood 3 code passed it
• Wood 1 boss : Wood 3 code passed it
• Bronze : My Wood 3 code was top 20 in bronze on my first submit, 1h30 after the challenge start.
• Bronze Boss : Including all new rules passed it :
• Multiple action : evaluate all couple moves (source, destination), sort them, play them in order
• Bomb : launch bomb on the best evaluated destination
• Silver Boss : My bronze code was top 10 at first in silver league, but there was time to wait before Gold league opens. So when the Silver Boss appeared, I had lost some places. After some submit, I decided to add a defense code line, just one hour before going to the CodinHub in Lyon. When I arrived, I was in Gold league.
• Gold Boss : Here, my code didn’t do more than attack (best couple), throw bombs, and do some defense action. Although I was in the top 20 to 40 for 1 day, I didn’t pass directly to Legend, and the hard work began :
• Optimize the bomb target
• Send more cyborgs to factories to upgrade when possible (very bad rules too)
• emulate other side playing for 1 turn with my engine, so I would know the actions list of the opponent.
• Optimize criterias to evaluate all I need to evaluate
• Avoid opponent bomb attack
• Send cyborgs to reinforce my attacker factories
• Replace all my targets (except bomb) by the precalculated array : shortCut[source][destination]; This trick made me pass to Legend league (all other complicated stuff was finally useless I think)
• Legend : In legend we were only 50 the first day. Then it began to be very hard to stay in 20/60, 40/100, 80/250, 120/300. I didn’t add much features, principally adjusting my numerous parameters…
• When evacuate factory on supposed enemy bomb ?
• When send cyborg to defend / attack / upgrade other factories ?

My real problem here was I didn’t create a fine data structure to describe each turn states, so my model was too simple. In gold league, I tried to refactor all my code, but I gave up because I knew I would not have the time. I think a simulator would have help me too, but with all my heuristics and parameters, it would have been very difficult to translate all the logic.

On sunday, I didn’t have much time, and my ranking was decreasing 150, 180, 200, 280…so I resubmit and resubmit my saturday code but Legend was a great jam. Looking at several matches, I understood that the legend strategy was to build strong factories before your opponent does. My code was not able to do that, because all my logic was on attack. So I decided to deactivate all my defense features, keeping only attack, and some upgrade or defend opportunities. The idea was that if my attack was the fastest possible, and the map not too big, may be the upgrade tactic of the opponent would not have time to work.

Final rank 105th.

Very nice challenge. Thank you to CodinGame and all competitors

9 Likes

For this contest, like many others, I began with an algorithm using heuristics. Lots of ugly if then else, loops over my factories and opponent factories, etc.
I planed to do an other algorithm with some kind of simulation later.
But my first algorithm worked not so bad. When I realized after a couple of days that the direct path between factories is not always the shortest, I recycled my Dijkstra function from TAN network puzzle to find the shortest paths. When 2 paths have the same length, I choose the one with more steps, because it allows to re-route the troops if needed.
With this improvement, I somehow managed to climb to the top 5 in the middle of the week. So I stuck to this algorithm I kept tweaking it for the rest of the week.

For each factory, I keep a list of incoming troops. It allows me to compute how many cyborgs I have to keep there to protect it and how many are available for increasing or to move.

My final algorithm looks like this:

1. Bombs : As soon the opponent has factories with a 2 or 3 cyborg production, I send a bomb to the closest ones, while avoiding to send 2 bombs to the same factory within 5 rounds. I also added at the last minute a detection of incoming bombs. It’s pretty basic and it works only for a bomb sent in the 1st round, assuming it will target my 1st factory. It allows me to get out just before the explosion.
2. Increase : If a factory has at least 10 available troops, upgrade it. Also, always choose one factory to be the next to be increased. It’s typically the furthest one from the opponent. Then, from the close enough factories around, send all available troops to it. I realized that increases are very important to win in this contest.
3. Moves : for each of my factories with available troops, I find the destination with the best “score”. A score is better when the destination is closer, when it has less cyborgs in it and when its production is higher. I send to this factory (in fact, to the 1st factory in the path to reach it) the minimum number of cyborg to save it (if it’s mine and it’s in danger) or to capture it. If I still have available troops to send, I do the same thing with the second best destination and so on.

That’s pretty much it, and it gave me the 18th place!

It’s not a perfect algorithm. I noticed that it quite often looses against bots with lower ranking, but it also sometimes wins against the top 10 bots, so I suppose it’s why it made its way to the top 20.

10 Likes

6th in Legend
My code isn’t that complicated and lacks of some features as prediction of hostile bombs and a danger level (how many troops can attack me in turn X, if my enemy will send them now?) to be able to defend against a big number of attacking troops. I tried the latter one, but it made my bot too shy.

Needed troops
You know, how many troops will reach a factory at what moment. So you can simply define an array and add (or subtract for your own troops) the incoming troops with their arrival time as index. After parsing the input, calculate the owner for each turn and add the produced troops.
Nice gotcha: when an enemy is about to conquer a neutral factory and you can still make it in time, set needed to 1 (or whatever is needed to keep the factory neutral). You will send 1 troop and the enemy will kill the neutral troops for you, so you can take the factory in the next turn.
Here is a replay showing what I am talking about: https://www.codingame.com/replay/196806568
In turn 7 I send one troop to factory 5 to keep it neutral and take it in the turn after that.

Target selection
I looped over all my factories and selected targets for them independently.
For each source I calculated my prefered targets (production/(distance^2*needed[distance])) and attacked until I had no more troops left, subtract the troops from needed ones.
This greedy approach makes mistakes (e.g. sending from 0 to 2 and then from 1 to 2, because factory 1 is closer to the target, making to troops from 0 to 2 unnecessary). So I loop over my plans to find these late arrivals, remove them and repeat the process.

Path finding
An important part is not to attack directly, if your target is far away. This would allow your opponent to prepare for the attack, make you inflexible for changing your mind and sometimes even costs you a turn, as the direct path is not always the shortest.
For doing so I implemented Floyd-Warshall to find the paths at the beginning of the match, maximizing the number of hops, if there are two paths with the same length. I ignore, that there might be hostile factories on the path.

I treated upgrades as neutral factories with 10 troops needed and production 1, that I have to conquer. This way it is easy to combine upgrades, instead of having two factories collecting troops independently. As I don’t know if it is save to upgrade (I don’t compute the possible number of attackers in the next round), I only upgrade, if the next hostile factory is at least 3 turns away. My bot doesn’t upgrade, when bombs are coming (though I am still not sure if this is a good idea).

Bombs
I try to throw bombs early to slow down the enemy on the first rounds. Targets are selected by production, then by time, the bomb needs to arrive, including factories, that the enemy will conquer in the next turns, taking currently moving troops into account. If I can throw a bomb now or make it arrive at the same target in the same round (because I will for sure conquer a factory closer to the target soon), I wait with it. This way I might be able to find a better target. If not, I didn’t lose anything.

This contest made a lot of fun. Upgrading and bombs made it complex enough to be interesting.

17 Likes

Well, final result #283, about ~100 in gold league.
My first contest and I really liked it, but I thought i could do better xD.

Pretty lame tactics: sort all factories on in danger or not, counting the current armies, defenders and production, sending bombs to enemy’s bases with production=3 or if enemy sends an army to capture neutral factory with same production.
My cyborgs didnt go too far to capture the base - max was 5 turns away, the only exception was if i had more or equal production than my enemy and 5% more total points, magic numbers that dont work all the time, yeah. They were not also trying to overkill defenders on the prioritized factory so most of time enemy could defend the base,
Priority was 1st to defend bases, then capture nearest neutral factories with most production, then go for nearest enemy, upgrading factories and relocating units to be closer to enemy. For anti-bombing I just evacuated all factories, the bomb could explode on, guess this one was a great failure, including that I didnt set production = 0 for those turns,
I enjoyed the game, waiting for the next contest.

But actually I thought this game could become more complex and exciting if there was a rule in silver or gold to be able to change cyborgs` targets on their way.

1 Like

My strategy
・I deal with only factories that is closer to me than opponent and id=0 factory.
・I tried hard to increase total productivity earlier than opponent.
・I aimed for a total number of point victory at 401 turn rather than aim for enemy extinction.
・Prediction of Bomb collision
・Calculation of shortest path

Priority order of military operations

1. Fleeing from bombs : If there is a possibility that a bomb will come to the factory that is now, evacuate to the nearest factory.
2. Defending : I simulated one by one turn to calculate the number of aid required.
3. Increase : I simulated one by one turn to calculate the number of aid required.
4. The remaining troops : move to id=0 factory.

I was suffering from a trade-off between defense against opponent’s attack and productivity increase. After all, I decided to rely on luck.

Thank you.

14 Likes

Ended 51th in legend.
I was ~10th on sunday morning, so I’m wondering if I screwed up somewhere or if a lot of people pushed improved versions during the last day.

I used a genetic algorithm (1 gen = 1 action). First simulating my opponent’s moves and using them to simulate mine. Exploring too deep in the future didn’t work well, I guess it is hard to make good predictions, so I explored only the 3/5 next turns.
I tried to put a lot of strategy in my evaluation function (increase vs conquer, control of the center, …). Worked quite well although it didn’t trigger “extra clever moves” like it did in Fantastic bits (like using the bludgers to score goals).

7 Likes

14th - Legend

My first algorithm was a Monte Carlo:

• generate a random number of random commands for my factories at the first turn
• simulate for 30 turns
• evaluate the difference of units on factories after each simulation with a decay factor

Then I switched to a genetic algorithm:

• same random move generator using the genes as the random number generator
• uniform crossover
• no mutations, instead I injected some new random genes
• this performed a lot better than the MC, since it reused intelligent moves found before

Optimizations/tuning:

• a local referee allowed me to run a lot of local simulations, I usually did 1000 matches between my best AI and my new one, with a short 1 ms timeout to quickly tune the parameters/strategies
• instead of storing the troops, I just stored the difference between his troops and mine at each factory for each step
• opponent new moves were too costly to simulate, so I just assumed he would move from any factory to any factory with a decay factor over distance
• use the Floyd–Warshall algorithm to move units using the shorter path (I ignored the owner of the destination)
• my factories that were safe (not under attack by the opponent) were excluded from my evaluation, to avoid keeping unused units on them

This was a great contest again, thank you CodinGame!

9 Likes

Gold League - 671/3508

First, I want to thank all the staff of CodinGame for this contest.
Indeed, trying to solve this contest give me a lot of fun.
I hope that the next contest will be as fun as this one.

So, my solution was very simple :

First, I create an array which contains all the distances between the factory’s
Then, I create all the entities, and place them into arraylist
After that, I scored all the factory for the every factory. I mean, For each factory, I was computing a different score to all factory. This score depends of the distance between them, the production and the population of the second factory.
Just after that, my code decides where to go. For that, it browses the arraylist, and for each of my arraylist, it chooses the minimalScore, and launch the troops there.
If my factory contains more than 10 soldiers, and have a production under 2. I increase the factory.
At the end, I was launching the bomb at turn 0 and 5, where the enemy’s maximum troop where from the closest factory I have.

That’s all.

Sorry for my english
And a large thanks to the CG Team

4 Likes

Hey !

Nothing much to say here. Ended 128 legend, so my code is basically a heuristic like the ones explained above (only not as good :D).

I wanted to thank the CG team. I think I never had such a blast in a contest, and was really involved (more than 5 hours a day on this contest !).

I really enjoyed really seeing some meta game changes during the contest, especially the fantastic take over by Kera on thursday that got me into rewriting my whole code to build a more defensive tactic !

Great game, the rules were simple enough to be quickly grasped but complex enough to make some pretty awesome fights. As MrAnderson, I regret only that no comeback could be possible at high level, and that basically everything was decided in the first 15 turns. On the other hand I think the 50ms were for the greater good : I really enjoyed seeing different languages in the top and knowing that cleverness kind of defeated the brutal approach of search-based algorithms (but don’t get me wrong : I’m not saying these algorithms are not clever, just that they provide a firepower hard to beat in a complex game).

Oh yeah and : please can you continue giving us the referee ? That was awesome and really helpful to understand the mechanics of the game.

6 Likes