Ghost in the Cell - Feedback & Strategy

[martin]

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.

[eulerscheZahl]

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.

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

[yckmciaiy]

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.

[Kera]

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.

[dolmen1234]

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

[_Royale]

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!

[_Random_J3ff3z]

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

[Aveuh]

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.

[TwoSteps]

First time I reach Legend on CodinGame, and first time I get that high in the rankings: 57th! I’m super happy and proud. 660 lines of Java for around 15-20 hours of coding.

Moves
My strategy from the start was to compute future turns and send troops only if I could really take the factory (or defend it). So I’d send only one more troop than needed. Because sending troops to die is just a waste of troops: not in the sense of them dying (they still kill troops), but in the sense of having available troops to do something else more interesting. Looking at replays where I finally lost battles although I had enough troops, I realized I needed to be more aggressive. On Sunday, I finally decided to send a maximum of troops without putting at risk my sender factory.

Increase
After discussing with Maxime, I realized that INC was really really important. If my factory was far enough to an opponent, I would INC (yes I would INC at T1). I also added a small thing to be more effective at INC in my backline: sending troops between my factories so I could INC some turns earlier. First, I decided to INC before deciding my moves. That was wrong and a bit too reckless, so I changed that and evaluated INC along with the MOVEs.

Bombs
Probably the worst part of my algo. I only evacuate when I’m sure (so the farthest of my factories). Works well if bombs are sent on turn 1. I was already aggressive with my INC, so I also have to send bombs early (to limit opponent prod). But I believe it would have been interesting to keep them a bit longer, to allow aggressive moves on important factories (sending the bombs from close factories)

Decision
I stayed with one output until Gold I think. I’d store the best move. My eval was taking into account prod and distance. The goal was that it represents how many troops it will add me in next 5 turns. Approximately. Double it if I take a factory from the enemy. To add multi outputs, I just loop on that until, my best move is a bad move (below a certain threshold). Was relatively simple but worked quite well.

Shortcuts
As @TylerDurden1, I compute at turn 1 intermediate factories B so that AB+BC < AC. Really useful to gain ahead in prod before your opponent. As I aggressively INC, that was nice. However it did bring a lot of issues in my evaluation of move as I didn’t dare to use it when the intermediate was an enemy or neutral with zero troops.

What I could have improved

• Bombs detection: I’m not sure how, but probably you could detect where the opponent would launch bombs instead of evacuating every factory (which I decided not to do).

• Better use intermediates to attack. Especially with this factory 0 at the center of the map. Lost a lot of matches because I wouldn’t take it.

• Take into account close enemy factories that could counter-attack my moves (I don’t always go to the closest enemy).

How to improve the game

• Maybe introduce a bit more uncertainty with another rule. Bombs are great for that.

• Add maps with no center factory. Was there?

[ThibaultJ]

Hi!

Just discovered this site and this is my first contest. Had a lot of fun. Thanks everyone.

Ended 60th legend. My strategy:

Every turn, I would compute the most profitable single action, and repeat until I reach out of available cyborgs (or time, damn you badly optimized pathfinding algorithm).

Basically, I would compute two things:

1. If I do this action, how much productions points will I get?

   • conquest of a factory -> production of the factory
   • increase of a factory -> 1
   • etc.

2. how much cyborgs will it cost (weighted by a time factor)?

Divide the first by the second, and give the action a score. Select the action with the best score. Execute action, evaluate the new game state. Repeat.

Also, favor conquest of factories closer to my factories than the enemy’s.

I would also compute a timeline to know exactly how many cyborgs (friends or foes) would arrive in any factory at any time, so I know how many cyborgs are available.

To execute actions, I always route cyborgs to the closest factory, so I can be as reactive as possible.

Send the two bombs as soon as possible in the beginning of the game to the enemy’s most productive factories, so I can gain an edge.

As the contest ended, I noticed that I got good results by removing the increase actions, since the blietzgrieg strategy was often working good. I added a quick heuristic to only allow increases if I was holding the factory 0 in the center.

What could have been done better:

• better defense strategy
• no bomb avoidance strategy
• spend more time creating a good game simulation with a reliable API that I can query easily.
• I did not realize for days that all factories were connected. Should’ve spent more time studying the referee’s code.

[Kodle]

First CodinGame contest for me, finished #13 in Legend, pretty happy with my result. Coming in, was really scared by all the talk of GAs/FSM/MCs, none of which I’ve done before…Still, this particular game lends itself well to simple heuristic methods.

###Strategy Outline:

1. Simulate 20 rounds into the future based on input
2. Simulate enemy actions*
3. Update simulation post-enemy actions
4. Scores enemy targets (using future states) and bombs high-scoring factories
5. Update simulation post-bombing
6. Execute actions (in order):
7. Reinforce factories
8. Upgrade (if safe to do so -> based on next 10 turn simulation minus the 10 troops required for an upgrade)
9. Attack nearby factories

- Prioritizes those we can immediately capture

4. Send troops to nearby non-fully upgraded factories to facilitate faster upgrading
5. Redistributes troops

- Pushes troops in factories further from the enemy to those closer

6. With what remaining troops left in factories, indiscriminately whack the nearest enemy factory…

###Nuances

• Target Scoring Some variation on (1/distance)*production-troops.
• Floyd-Warshall Adjusted F-W to ignore links greater than 7 dist (making decisions that far into the game didn’t really pan out that well). Also, prioritized path with more factories when dist is the same (so troops will hop rather than directly path towards target).
• Enemy Simulation Only simulated steps less than 5 turns into the future. Also, tuned enemy to be more aggressive (*1.53) hence, making my bot more defensive.
• Offensive Factor Added a multiplicative factor (1.17) for attacking factories, counters enemy reinforcement and prevents uselessly sending troops against the enemy without achieving much.
• Magic Numbers I guess even without implementing a GA, I was a human-GA All these magical numbers were the result of many submissions with but a tweak for a single variable haha…

###Analysis:
*The one step that I think Machine Learning techniques could lend itself to best is in predicting enemy actions. Once we know what the enemy will do, the optimal move is a mathematical outcome. So some prediction-feedback cycle would work well with a good initial seed, slowly tuning itself based on how the opponent chooses differently to attack.
As I didn’t manage to come up with a model to learn the enemy’s movements in time, how well the enemy’s actions concurred with my bot’s (static) predictions played a huge part in its success (or failure).
Floyd-Warshall pushed me from ~#100 to top 15. The flexibility in troop hopping multiple factories allows you to change your movement based on changing enemy actions. This avoids the issue of over-committing troops where it could have been otherwise better used.
Troops are an investment, you could attrite the enemy, upgrade your factories or attempt to capture enemy/neutral factories. This game was all about managing such an investment well with bombs thrown in to shake things up (since bombs couldn’t be predicted with too much accuracy).
One thing I left out was predicting enemy bombs and evacuating my factories. Oh and sending troops to factory 0 seems to be a simple but effective strategy employed by many top bots >.<

Well, that was a really fun week and I can’t wait till the next competition! Thanks CodinGame for such great fun

[ilovebugs]

I ended 835.

For fantastic bit I used all kinds of heuristics. I decided simulating collision was too complex and I would not have the time to make a working bot. This time rules were simple, so I decided to try a simulation with random search. Also, it was hard for me to see which strategy was the best, so I hoped the computer would find it for me. I made something really simple:

• at the start of the run consider that each of my factory will wait.
• for each factory: 1) choose a random action 2) simulate 25 turns, considering that nothing will be done and evaluate the score. 3) better score: keep the action else restore the previous one
• I used a simple heuristic to launch bombs, similar to what was previously said.

This took me to the upper of the silver league. I did not have a lot of time to improve beyond this: e.g. did not use the shortest path which seems to be a major flaw: my bot tried sometimes to conquer far away factories. I’ll use this version as a base for a GA algorithm if the contest reopens as multiplayer game.

What did not work:

• I tried to simulate the opponent with a dummy bot or by making my bot playing against itself => no real difference or worse.

I must say that I preferred fantastic bits. It was much more exiting for me. Seeing the sorcerers playing and casting spells was really pleasing. There was much less epic moments for this one. But, I agree that seeing python in the top of the ranking is nice, this means that the challenge is more balanced w.r.t. languages.

Looking forward the next contest !

[IloIlo_JRFerguson]

Hello all ! This was my first contest in CodingGame and I want to really congratulate the staff for the excelent experience, and of course all the participants and specially the winners, it was a really fun coding week. My final result was 29th overall, and #1 from spanish speaking countries

Reading this discussion is also very enriching, so thank everyone for taking the time to share your strategies ! Mine was not so different from some of the previously discussed, this was some of it:

INC strategy
I believe this was the key in Legend. I got to Legend with an almost pure deffend/attack strategy and almost entirely neglecting INC, only increasing when the game was preety much decided on my side. I had to change this quickly to be able to compete with the top players. I still think my INC logic is not aggressive enough. For instance, I only INC when there is no more neutral productive factories to capture, and never when a rival bomb is in the field.

Bomb Strategy
I used early bombing to high productive nodes, when the decrease in production is more harmful. In the first turn, I bombed neutral nodes only if I was preety certain that the node was going to be captured before the bomb reached the target.

Opponent move predictions
I think this was also key to success and I should have put more time on it. I only used predictions of close attacking factories to calculate deffenses needed or spare troops. If a factory has an adjacent rival, then assume it will attack with all its cyborgs and calculate the deffenses needed and troops to spare accordingly. I didn’t do this to predict defensive behaviors or opponent INC, to then be able to attack or INC myself. I also didn’t predict several turns ahead like others successfuly did.

Bomb target prediction
I assume bombs are headed towards high production/closest to rival factories, and clear the cyborgs of the target on explosion turn. I’ve tried more risky logic, for instance assuming all high productive factories are potential bomb targets, but that didn’t go well and I switched back.

Bomb explosion detection
I calculated the expected cyborg count for each one of my factories at the begining of the turn, and matched this with the actual cyborg count. If it didn’t match then that ment an explosion happened, and so the factory is marked as not productive for the next 5 turns.

Action priority decisions
I iterated through my factories, deciding for each one individually. I used the following logic: 1) keep all the cyborgs needed to deffend this factory 2) with the remaining cyborgs, deffend close factories in need 3) with the remaining cyborgs, attack close rival factories 4) with the remaining cyborgs, send troops to factories marked to INC, and 5) with the remaining cyborgs, attack and deffend farther away factories.
This is another area where I think I have much to improve. I didn’t take into consideration if I was certain to lose a factory, or if I was certain to take one, or if I had no chance of taking one. That way I could have done a much better resource allocation. I was experimenting with this when I run out of time and didn’t want to risk another submit because of the long battle computation times on sunday.

Again, thanks to all for the amazing experience, I look forward to the next contest !

[Marchete]

I did badly on this challenge, went for the attacking strat and was a complete failure against INC strategies. This and a lot of bugs I never fixed.
But I write to thanks Codingame for releasing the referee code. It was incredibly helpful for creating the simulation part.
I hope this becomes the norm from now on. It was much easier to get the idea that from expert rules.

[dolmen1234]

We saw you make an impressive move up to th 1st place on midweek, congratulations.

[_CG_SaiksyApo]

Bomb explosion detectionI calculated the expected cyborg count for each one of my factories at the begining of the turn, and matched this with the actual cyborg count. If it didn’t match then that ment an explosion happened, and so the factory is marked as not productive for the next 5 turns.

I don’t understand that part.

What was wrong with the provided inputs?

[Illedan]

I used 3 days before I saw that particular change inn inputs. It should’ve been anounsed in the statement…

[_CG_SaiksyApo]

If entityType equals FACTORY then the arguments are:
arg1: player that owns the factory: 1 for you, -1 for your opponent and 0 if neutral
arg2: number of cyborgs in the factory
arg3: factory production (between 0 and 3)
arg4: number of turns before the factory starts producing again (0 means that the factory produces normally)

[dolmen1234]

Me too, I thought this input was not available at the beginning of the contest ?

[Gulzt]

I had a great time, it was the first competition I tried, and was happy to find myself in the gold league. I would be happy to try and improve my code when it’s released as a multiplayer mode.

My strategy:
I did a risk analysis to decide on the best possible move. I would divide my army into attackers and defenders. If enemy troops and my troops would be heading for the same target, I would cancel out there effect, freeing up attackers. If my army would not be big enough to deal with an attack I would ask other factories to send me help. In case I couldn’t hold up, I would spend my last defenders to attack the weakest enemy factory within close proximity.

I started doing really well when I started predicting enemy bombs, based on the source and timing. I would flee my units in the last second.

I was most proud of countering the strategy that was done a lot in the top, where people would send a bomb and send a big chunk of there army right behind it. I would time sending a bomb from a nearby factory, and blow up my own factory the moment that big chunk arrives.

Using the bombs correctly was key in beating the gold boss. I didn’t have the time to work out the fine details to beat him consistently. As I ended up somewhere position 500+ I imagine a lot of people were in that position.