Ghost in the Cell - Feedback & Strategy

Contests
#21

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?

8 Likes
#22

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.
5 Likes
#23

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
  1. Send troops to nearby non-fully upgraded factories to facilitate faster upgrading
  2. Redistributes troops
- Pushes troops in factories further from the enemy to those closer
  1. 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 :stuck_out_tongue: 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 :smiley:

12 Likes
#24

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 !

4 Likes
#25

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

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 !

4 Likes
#26

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.

4 Likes
#27

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

4 Likes
#28

I don’t understand that part.

What was wrong with the provided inputs? :frowning:

1 Like
#29

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

2 Likes
#30
1 Like
#31

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

2 Likes
#32

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.

1 Like
#33

Hi ! Maybe I missed something in the inputs… Where was the information of where the bomb exploded ? If the bomb was rival, I didn’t know the destination or the remaining turns, so I had to detect it this way but I may have missed something. Anyway it was not hard to compute the expected cyborg count and compare it with the actual one, so I didn’t lose much time doing it.

1 Like
#34

The arg4 of every FACTORY gave you the remaining turn before producing again, so if arg4 > 0 means your factory was destroyed.

If your enemy bombed itself, you won’t find out with your technique right?

1 Like
#35

The step[quote="_CG_SaiksyApo, post:30, topic:2634, full:true"][quote]arg4: number of turns before the factory starts producing again (0 means that the factory produces normally)[/quote][/quote]

When did that get included in the problem statement?

1 Like
#36

Oh, I didn’t see that input for factories ! You are correct, with my technique I was only able to detect explosions in my own factories, but it ended up working well enough and I also was able to grasp some game mechanic concepts by developing it.

1 Like
#37

Since Wood 1, with the new “BOMB” command.

1 Like
#38

Looks like a lot of people missed it.

The differences between the problem statements should be more obvious.

At the moment you only get a small summary of the changes. To find the details you have to read the whole statement again, or skim through it and risk missing something.

3 Likes
#39

Reading through the posts here, it seems that my AI was somewhat more complicated than most. Not too surprising. My creations tend towards the complex. :unamused: It didn’t help me out all that much, though:

GOLD: 521 / 3508

EXPERIENCE
I loved this contest. It was easily one of my favorites. I love emergence in a system, and GitC exemplified that concept. I enjoyed watching games where troops were flying everywhere and trying to figure out the key points in the conflict that determined the outcome.

BOMB SIMULATION

  • I tracked all enemy bombs with a complete list of all my factories that existed at the time the bomb appeared, and the remaining distance to each of those factories

FACTORY SIMULATION

  • I simulated N turns in advance for each factory, where N = max( longest_dist, 10 )
  • For each factory, I created the following arrays:
  • deployment - contains the maximum number of troops that I can possibly have at that factory on that turn minus the maximum troops the enemy can possibly have
  • actual - contains just a flat prediction based on production and troops en-route.
  • actual_with_bomb - for factories that are deemed to be a potential target of a bomb currently in-play, this takes into account what would happen if the bomb were to hit that factory
  • I marked factories that were not yet owned by me, but had a positive actual value on a future turn, with the flag count_as_mine.

TESTS

  • I designed my AI to be easily testable. Each action generation method accepted state as input and produced a deterministic output.
  • I used the stdin reporting feature of CG Spunk to generate code that could be literally cut-and-pasted into a test case so that I could examine my AI’s behavior on a turn-by-turn basis in a repeatable off-line test.
  • By the end of the contest, I had a battery of 151 tests with names such as AvoidDoubleColonize, DontLeaveYourselfVulnerable, WhyNotColonize, etc.

ACTION GENERATION

  • Each XXX_actions() method returned an array of action strings for a given strategy, and were executed in the following order:
  • abandon_actions() - If a factory was considered to be a potential target of an in-play bomb on the next turn, then it would be completely abandoned. The fleeing troops would typically be sent to the closest friendly factory, but in some circumstances, they would instead attempt to take over an enemy factory.
  • rescue_actions() - A count_as_mine factory was considered to be “in danger” on a given future turn, t, if the number of actual_with_bomb cyborgs at t was negative. I then went through each of my factories, from closest to furthest, counting up the number of cyborgs that they could contribute to a rescue mission: min( deployment ). If I was able to muster enough troops that would all arrive before time t, then I would send the rescue mission.
  • increase_actions() - For each of my factories with production < 3 && cyborgs >= 10, I would recalculate deployment if I were to increase production at that factory. If the deployment array never went negative (not “in danger”), then I would perform an increase action for that factory.
  • colonize_actions() - This one was pretty complicated, and I never quite got it correct. My algorithm ended up a bit conservative, which I’m sure hurt my results. For each non-count_as_mine factory, I looped through all of my factories, from closest to farthest, and calculated the maximum troops it could safely send, based on deployment, and adding that MOVE action to a potential action list. I then calculated the enemy’s deployment at the destination when the troops would arrive. If the total of sent troops in the action list was greater than the enemy’s potential deployment, then I would perform all the actions in the list. Otherwise, I would continue to build the action list by moving to the next of my factories.
  • frontier_actions() - For each of my factories, I kept track of the closest friendly and closest enemy factory. The closest-friendly was a list, and was bi-directional, so that none of my factories could be orphaned. I looped through each list, and if a close friendly factory was closer to an enemy factory, then any extra ( based on min( deployment ) ) troops were forwarded on to the next factory in line, with the ultimate result of pushing all my troops as close to the opponent as possible.
  • bomb_actions() - My bomb logic was brutally simple. If I had a bomb available, and any non-count_as_mine factory had production == 3 && production_delay == 0, then send a bomb from the closest of my factories.

MISSED OPPORTUNITIES

  • My algorithm may have been too complex, and there were multiple difficult-to-find bugs in my implementation of the above logic.
  • I should have had my bomb_actions() done before anything else, and wanted to modify predictions at the opponent target factories according to bombs in-play. I did neither of these, and so my AI didn’t properly plan ahead for opponent weakness at bombed factories.
  • I wanted to make my bomb_actions() smarter, so that it would target a factory at the time that a large batch of enemy troops would arrive, possibly even targeting my own factory (and abandoning it) at the point an enemy was attempting a large takeover.
  • My algorithm was pretty conservative, erring on the side of “safe” moves. I wanted to make it more aggressive if it thought that it was “winning” based on total production and / or total cyborgs.
  • The colonize_actions() didn’t take into account that colonization time was pushed back with each new factory that contributed to the effort, and so factories that had already “logged” a contribution could possibly contribute more. This resulted in some missed opportunities.

EXAMPLE
Here’s a simple game example that shows my logic (and some bugs) at work:

https://www.codingame.com/replay/194800386

  • danBhentschel
6 Likes
#40

Nice comeback!

Good idea to show a replay to illustrate the strategy. Here’s how my crazy INC got me a game:

https://www.codingame.com/replay/194885896

(I still have some flaws in keeping my factories safe when I attack)

Damn I want to play again, I got some new ideas :smiley:

5 Likes