Mean Max (CC01) - Feedback & Strategies

Contests
#8

200th, :smiley:
I was near the 100th bar Sunday’s evening and some better IAs got the place.

As the very first contest I participated in on Codingame, I’m pretty happy it was such an interesting game where Genetic algorithms and heuristic based IAs can compete together until gold (if i remember well Mad Max is not a GA as well).

Strategy

Wreck selection
My IA was also totally deterministic and consumed something like 100microseconds to answer and with an heuristic based on 4 parameters : the number of turns needed to reach a wreck, the age of the last oil used on the wreck, how much wrecks are overlapping this one and how much water this wreck and the overlapping ones has.

Doof
My key idea was to attack the first opponent but I finally changed for the option “attack whoever you can but attack the first in you have the choice” option. It makes the doof have smoother changes of target when the opponents score changes suddenly.

Destroyers
It simply targets the tanker next to my reaper with a minimal amount of water.

Skills
Same as Ilovebugs, oil first but only if you didn’t target this wreck a turn before.
I used Nitro grenade in two ways: defensive way, targeting my own reaper if a threatscore was reached (based on distance to ennmy looters), offensive way, randomly harassing the opponent with some grenades just in front of its reaper.

Next improvements
I guess what my IA lacks was small fixes of direction when there is collision in the path to the choosen wreck. I’ll improve that in the multi !

Which language ?

At the very beginning I thought I would write the program in C++ to gain performance over simulations, but since my IA doesn’t need any real simulation there’s no need to select a language for its performance. I kept C++ but you can have the same results as mine in Lua, Python or Brainfuck (goodluck). My thoughts about this is that languages like C# with Linq or Java with streams are way easier to get the same results that I got in C++.

Anyway, thank you Agade, pb4, Magus and reCurse !

3 Likes
#9

I finished 7th but I am one of the creators. I will write something short as I’m sure the top players will write some nice postmortems.

Search Algo
It was pretty obvious to a lot of people that this game needs to be approached by some kind of search algorithm. For one thing the game has a lot of collisions going on that would be very hard to take into account in a heuristic bot. I had a buggy game engine ready before the contest (reimplementing helped us find referee bugs, I’m glad weren’t present in the final game). I took my time to fix the last major issue in my engine on Tuesday.

I searched with Simulated Annealing (SA). I never really used genetic algorithms (GA). I figure SA is inspired from Physics and GA is inspired from Biology, it is therefore obvious that SA is better. (@CG where is the Kappa emoji?)

Handling of skills

In my search I handled skills in the dumbest way I could think of: If SKILL is selected (10% chance) then the reaper tries to tar itself (to become really heavy+high speed and knock people away), the destroyer tries to throw a grenade on the Reaper, to push everyone away from it, and the Doof tries to throw oil on the nearest wreck (either the centre of the wreck or the closest point that allows to cover the entire wreck. I felt that partial oils that prevent looting for only 1 turn could be a massive waste of rage).

This is obviously not optimal but in many games it was enough to use up my rage. It occurs to me that I should probably have tried to grenade around the reaper to give it a speed boost.

Eval
I didn’t make much effort on my eval as I didn’t even make a local arena for the contest.

  • 1 point per unit of water

  • -0.1 points per unit of enemy water

  • 1e-3*MyRage

  • -1e-5*Dist(reaper,nearest_wreck) if there is a wreck

  • -1e-5*Dist(reaper,destroyer)

  • -2e-5*max(0,Dist(destroyer,nearest_tanker)-200-tanker_radius-destroyer_radius) (Get close but don’t encourage closer than 200)

  • 1e-3*Number_Of_Tankers (Don’t destroy tankers)

  • 1e-5*Doof_Speed

  • -1e-5*Dist(Doof,enemy_reaper)

Where enemy_reaper is the reaper of the enemy with the closest score to mine. I figure that annoying the player with the score closest to mine is most likely to affect the final outcome of the game. Extreme example: Why annoy the player who is 20 points ahead of me when I can try to keep the other player a few points below me?

I dissuade breaking tankers because I want my AI to destroy tankers as late as possible. Ideally my reaper will harvest the wreck on the same turn as the tanker is destroyed. Why destroy it early and give other players the opportunity to contest the wreck and/or oil it?

I evaluated as Eval(state after first move)+0.95*Eval(state after second move)+…

I think I have a big margin for improvement in my eval as I made very little effort to improve it.

Dummy
I had only: Reaper goes to nearest wreck (-its speed according to the popular CSB formula). Destroyer and Doof wait. For me this dummy is a very safe assumption.

I might have some room for improvement in this aspect but I suspected and found that making assumptions about enemy movement can easily be worse than assuming a WAIT.

Optimisation of Search

I found that the quality of the search affected the strength of the AI significantly. Performance is therefore probably very important but I focused only on the search itself. I wrote some code to take 20 states from real games and locally Search those states over and over to look at the average score. Using this metric I optimised my SA’s parameters. I used an exponential cooling schedule:

current_temp=Max_Temperature*exp(-Temperature_Exp_Decay*fraction_time_spent)
Max_Temperature=100
Temperature_Exp_Decay=10
fraction_time_spent=time_spent/time_limit

Every 100 iterations I reset the current solution to the best one ever seen. I also found that searching with moves described as (target,acc) was better than (angle,acc). I suspected this because if you have a sequence of N (angle,acc), when you change the first angle you end up at a very different location, so “small mutations” aren’t so small anymore which goes against the principle of SA to search in the neighbourhood of a solution.

I searched 4 turns ahead, this is probably a very important parameter but I didn’t test any other values.

Conclusion

In the end me and pb4 decided to stop improving our AIs to ensure we didn’t finish in the top3. We wanted to avoid devaluing finishing on the podium. “I am first but there are two people in front of me”.

23 Likes
#10

BlitzProg, 51th

Aww. what a ride. Worked day and night for this. Prepared myself, took days off, went all out and did everything I could. I’ve learnt a lot, this was great, though a bit frustrating. The bosses were so strong.

Wood 3 -> Wood 1
Go to the last entity of the list.

Wood 1 -> Bottom Bronze
Switch from PHP, Proper C++ algorithm. Dumb dummy consisting of targeting neighboring wrecks and targets. Doof was given arbitrary coordinates.

Bottom Bronze -> Top Bronze
Thought a bit more about the AI, made it so it would make smarter choices. Think of selecting wrecks more carefully, targeting tanks with more waters and sometimes try to use grenade to move opponents away from wrecks.

Top Bronze -> Middle Silver
Simulator done, basic Monte Carlo that just evals over his score minus leading opponent’s score.

  • Simulator translated from github referee and adapted to my game structure.
  • My simulator is very accurate. I tested it using 3x IDE code, all going to 0 0 300, and try to predict which position they will be on their next turn. 6000 6000 300 to test the borders.

Middle Silver -> Bottom Silver
My 2nd Genetical Algorithm ever : done, same eval as above. I’ve coded it so it would evolve against a dummy AI because i thought it was the most important at that point! I didn’t stay disappointed for long, though.

Bottom Silver -> Top end Silver (2nd)
The curse of the 2nd position starts!
GA shows how good it is. Merely factoring distance to closest wreck and closest destroyer made it jump over the entire league, stopping just behind the boss.

Top end Silver -> top Gold
My doof wasn’t factored in the eval, so with my genetic evolution it was roaming aimlessly.
Tweaked eval so it would get a slight penalty the further away he is from opponent reaper. Useless doof immediately became very annoying for the opponent. I rank somewhere in the 60th gold.

Top Gold -> Top end Gold (2nd)
The curses of the 2nd position continues.
Superb results with doof additions. more results from finally simulating skills, something my AI was completely oblivous about until then. - also adding ability to cover wreckages with oil.

2nd Gold -> 2nd Gold
Things I tried:

  • Adding ability to throw grenades
  • Fixing slight simulation glitches (oil radius of effect also depends on your radius)
  • Better eval changing weighting of distances penalties
  • Adding more stuff to eval (reaper => distance to oppoent doof)
  • Finding magic numbers (weightings, parameters)
  • Evolving my opponent for 20% of the time (dummies could beat silver Boss after that)
  • Adding rage generation and weighting it
  • Timing my submits, trying to count on others to push me up in front of Boss, etc.

None of that made any noticeable difference, though it did help me reaching that annoying 2nd gold place much faster and much more reliably. Smallest gap with boss was 0.2 point.

2nd Gold -> 3nd Gold

  • frustration nap to accidentally kill the remaining time! Good job to the new 2nd , you get to share the frustration with me :smiley:
6 Likes
#11

14th

Performance

I copied the referee to simulate the game. In hindsight that may wasn’t the best idea, as my simcount is quite low compared to others (about 3500 single steps in the best cases, also because I used C#).
For speedup I did two things: cache collisions and assign objects to fields on the a grid for faster prechecking.
For caching I just compute all possible collisions at the begin of the turn and later only update the objects involved in one collision.
For the grid collision I split the total board in regions of size 1500x1500 (so I get 8x8 regions on the map, ignoring the edge, where only tankers can be - this makes me blind for collisions in that area, but they aren’t that important). The size is because that fits in a 64 bit integer.
I then create a surrounding rectangle for each object at the beginning of the turn as follows:

// xMin, xMax, yMin, yMax are in range 0..7 for grid coordinates
// don't forget that the objects are moving when computing the limits
ulong xMask = (1UL << (xMax + 1)) - 1;
xMask ^= (1UL << xMin) - 1;
Grid = 0;
for (int y = yMin; y <= yMax; y++)
	Grid |= xMask << (8 * y);

Later for ever collision check I can do:

if ((unit1.Grid & unit2.Grid) == 0) continue; // no collision

That checks, if the objects can even be in the same region with a single bitoperator and a comparison. For most cases that is false and I can just skip the more expensive check.

Generating moves

In most cases it makes sense, that the reaper goes to a wreck or the destroyer to a tanker. So I don’t genereate most of my moves in a fully random manner, but select a target depending on the distance and type of the target (the reaper might go to a tanker as well - I can destroy that and make it a wreck before the reaper arrives, but wrecks are more likely to be a good target).
I realized, that the speed is equal to the max speed in many cases, so I choose that more often.
Grenades and tar are placed randomly, as it is hard to see what will happen. But for oil I use a heuristic to selects a good target, as my bot often partially covered a wreck, allowing the opponent reaper to just move a bit to the oncovered part or even split oil accross the map without any opponent or wreck in sight, wasting my rage.

Mutating plans

I did not write a genetic algorithm. Instead I randomly choose one looter, assign some semi-random moves (depth 4) and keep it, if it’s better. In the case, that I wanted to spend more rage on my new plan, than the plans for the other looters allowed, I just set their actions to WAITs.

Enemy prediction

I basicly used the same code to predict the enemy, that I then use for myself, but with some restrictions. The enemy assumes, that I wait myself, doesn’t try to block me and can’t use skills (these predictions were to unreliable). The enemies don’t know about each other’s plans. I use 20% of my time for each enemy and the remaining 60% for myself.

Scoring

The most important factor is water of course. So I massively reward the gain of it.
Then comes the distance of my reaper to wrecks. Here I use the amount of water, squared distance, distance to other wrecks nearby and whether I’m closer to the wreck than the opponent reapers (euclidian distance, the attempt of a more precise estimation including the speed made it worse). The first round is more important than later ones, as the enemy prediction become increasingly unreliable.
I do the same scoring for my opponent too and subtract it with a certain factor. The opponent closer to me in score is more important (so I’ll try to at least save the second place, when one player has much more water than I have, while the other is slightly behind).
I did a little offline training to check, how important different things like closeness to a wreck and having much rage are. I think it gave me 1 or 2 points on the scoreboard, but at some point stopped helping - other arena bots are to different from mine and getting better against myself isn’t the same as getting better against other bots.

About the game

It was a fun game, but sometimes hard to see what’s going on. The complexity didn’t allow heuristics at the top. The referee was very helpful. Much respect for getting such a complex game almost bugfree from the beginning on (only a misplaced exit condition on crashing players).
Thanks for reaching silver in the stream and not struggling to even reach Bronze.
I don’t see a problem with the contest creators participating. They did a great job creating a new contest for us - for free. The least we can do to honor that is letting them participate for fun and not complain about that.

20 Likes
#12

43rd legend, C #

I started writing the referee’s class pattern during Wood 3, and I tested it in bronze league. The C # Linq tool is a good way to quickly test many filtering and sorting possibilities.

In Silver League, I used a brute force and a simulation on each wreck making them a target for my reaper, to see which one will maximize my score after 6 laps.

In the gold league, I added to the combinations of bruteforce, an angle parameter for the reaper, a parameter for tankers with a particular sort to all parameters.

The biggest and the greatest moment of the contest for me is when my bot has been selected to be the MadMax, the Ultimate Gold Boss, and it makes me very, very proud and happy.

Many thanks to Agade, Magus, Pb4 and Recurse and all CG staff for their work and for providing us with this unique and unforgettable moment of fun, of coding and gaming experience.

Big Up

10 Likes
#13

First of all, I want to thank Magus, Agade, pb4 and reCurse for the time they put to build an engaging contest, thank you guys !

I ended up #46th.

This was the first time I used a search algo with simulation in a contest, with all my previous attempts relying on heuristics/if spaghetti. I used a GA algorithm.

The only thing I want to add to the discussion is the relevance of the search algorithm. I spent most of the contest twiking the evaluation function score parameters, writing more and more complex and creative ways to score the board. All of this with almost no changes (and very often with very bad results) in my AI performance.

So, what did make a difference?

I was getting really frustrated by not getting past wood 1 after a lot of work in the eval function, and then I changed my GA depth from 6 to 3. Magically skipped 2 leages to reach silver. I couldn’t belive it.

Then changing the pool size from 50 to 6 gave me another boost, and finally on saturday I made another change that allowed me to reach Legend: improve performance by ignoring every collision that don’t involve my own looters.

I still couldn’t believe the difference between the top players score and my own (it will end up being like 11+, which is a lot) so I was eager to read their postmortem. After reading Agade’s (which is always very interesting, thanks @Agade) I think I can conclude that the evaluation function is absolutely secondary (in fact I tried Agade’s eval in my GA, and my version beated it 88% of the times), with the search function optimization being what makes all the difference. It doesn’t matter if you have an optimum that is very high if you can’t ever get close to it, right?

That is really the most important thing I learned in this contest that I will try to put in practice in the next ones.

Thanks again to the creators and the CG team for the amazing experience and learning opportunity !

6 Likes
#14

19 Legend , Java

Based on experience of CSB and PCR and the referee, the physics engine was pretty simple to write (all my tests were green on the 1st saturday night).
Then I used jvisualvm to grind the perf ladder (keeping my tests green obviously, they were a life saver a bunch of times)
Nothing fancy here except the early exit by doing projection of entities (not as smart as EulerscheZahl):

    double posx1Min = Math.min(position.x-radius, remainingTime*(position.x+speed.vx)-radius);
    double posx2Max = Math.max(u.position.x+u.radius, remainingTime*(u.position.x+u.speed.vx)+u.radius);
    if (posx1Min > posx2Max) return Collision.NO_COLLISION;

    double posx1Max = Math.max(position.x+radius, remainingTime*(position.x+speed.vx)+radius);
    double posx2Min = Math.min(u.position.x-u.radius, remainingTime*(u.position.x+u.speed.vx)-u.radius);
    if (posx2Min > posx1Max) return Collision.NO_COLLISION;

    double posy1Min = Math.min(position.y-radius, remainingTime*(position.y+speed.vy)-radius);
    double posy2Max = Math.max(u.position.y+u.radius, remainingTime*(u.position.y+u.speed.vy)+u.radius);
    if (posy1Min > posy2Max) return Collision.NO_COLLISION;

    double posy1Max = Math.max(position.y+radius, remainingTime*(position.y+speed.vy)+radius);
    double posy2Min = Math.min(u.position.y-u.radius, remainingTime*(u.position.y+u.speed.vy)-u.radius);
    if (posy2Min > posy1Max) return Collision.NO_COLLISION;

gave me ~2000*3 simulations in 30s
**Note : I think there was something amiss with timeout, it’s the 1st time I have to set the timeout limit so low 30s instead of 44 in the other contests **

Then came the fitness function and it was a nightmare :angry:
There is so many things happening that i could not (and I still can’t) really understood what was good and not (except some basic facts like score)
I reimplemented the eval class many times and, at the end, came with something pretty simple stupid but seemed ok.

I want to congratulate the fab4 and CG for the contest, it was really good.
I look forward to be a member of a team to create a new one with this quality.

4 Likes
#15

First of all whoever came up with the game idea, good job, well done. It’s probably the most entertaining game here at the moment.
Can’t wait to see it released, maybe i will finally have some time for it.

The skills could have used a bit more tweaking maybe, but aside from that little tidbit, it doesn’t matter. It’s a great game to have on this website.

Too bad not all 7000 registered users joined the contest. We didn’t even have half of them enter. :confused:
The submission lag was annoying though and i can’t image what it would have looked like with those 7000 all participating.

My Contest experience:

Wrote a bot that could get #65 gold and then i messed everything up with greedy submits trying to get more. Ended up #256 overall. I don’t care about this rank though, for me it was either legend or nothing.

Had a busy work week so my strategy was improvise on the go.
Wood 3 i used a powerful algorithm that got me to Wood 2:
in the starting code i printed out for the reaper:

print “x y 300”

and it got me #2 in Wood 2 until i finally had time to try something out few days later.

I went for very basic heuristics, add a few lines to the starting code, that’s it really. Got 300 silver with Python3.
Switched over to Java to use the stream bot, improved it a little bit and got gold, which i kept improving to a bot that can get top 100 gold easy. That’s about it, i just i wish had better luck on the last submit, or maybe should have been less greedy. Oh well whatever.

2 Likes
#16

Finished 196th in Gold
This was my first contest. I am new to CodingGame.
Thank you for this wonderful contest, it was a very good learning experience for me.

I tried simple if/else logic as well as genetic algorithms (my very first attempt).
I failed miserably on GA version, it would not even beat my out if/else – I would be very thankful to anyone who did GA - if they can share their fitness function or would want to review mine, which is pretty much the referee code.:slight_smile:

For if/else logic -
reaper would look for the wreck where it has best chance i.e. the one nearest to me and farther than opponent reapers & doofs. if enemy is low on rage, I did not care about doofs. Also, if an opponent is leading and in range, my reaper will use skill on them.
destroyer would look for nearest tanker within watertown radius if there are no wrecks. Else fights the best opponent’s reaper
doof would chase the best opponent and use skill if there is a wreck near any of the opponent

Thank you!

1 Like
#17

Hi everybody,

Thanks to Magus, PB4, Agade and Recurse for that great great contest. A lot of fun and hard work have been there during all these days.

Starting day
Oh, I was very sick. I got a fever of about 40°C. I read the subject, then couldn’t think much about it because of a very strong headach. Too bad, because the real pleasure in those CG contests, is to think about problems and solutions. So I stayed to bed and thought about how not to think about the contest :frowning:

Wood3 to Wood1
Saturday, the fever was always there (about 39°C), but I could code and I wanted to. A very light code (300 LOC) :slight_smile:

  • Read the input and decide what to do without stocking any information
  • Destructor will follow the strongest opponent (which has a better score than the other opponent)
  • Doof will do the same : follow the strongest opponent
  • But if at least a tanker exists, so Destructor will go to the nearest tanker
  • The reaper will follow the Destructor
  • But if a wreck exists, the reaper will go to the nearest wreck

Wood1 to Bronze (44th / 383)
No change needed : The same wood code entered to Bronze on saturday PM 7:00 (Saturday Night Fever !!)

Bronze (23th / 767)
To stay in top of the ranking before the Silver league opens, I added some features. My fever was lower (38°) and I could even write a better version code, properly reading all informations :

  • read and stock all data informations
  • if at least a wreck exists, the Doof will go to the middle point just between the strongest opponent and his nearest wreck to intercept it
  • Shield feature : if my reaper detects a collision on a wreck on the next turn, it casts a skill just behind, at a distance of 1390 from its next position, to give +10 mass, and kick opponent unit or a friend unit
  • Oil : If a winning opponent is on a wreck, and my reaper is not, and I could cast an oil skill, I do so (I had a bug here because I forgot to test the <= 2000 distance).
  • Grenade : if an opponent goes to a wreck, and my reaper doesn’t, and I could cast a grenade, I do so (here the distance was good)

Silver league opens (38th / 545)
As my bot was in the top of Bronze league, passing to Silver league was immediate on monday evening. On tuesday, there was the CodingHub in Lyon. There I met Saelyos (yes he is real), and now I can confirm that the best french coder on that challenge (#4) lives in Lyon :D.

End of Silver league (34th / 759)
Nearly the same code stayed on top 40 till the Gold league opens on wednesday evening.

Gold league (12th / 250) on Legend opening
To maintain my top ranking in Gold league, I had to add some new improvements :

  • Adding evaluation for my Destroyer to choose the best tanker to kill
  • Adding evaluation for my Reaper to choose the best wreck to collect
  • All evaluations are based on water points, distance, and proximity of enemy units
  • For my reaper, add the same evaluation for tanker than for wrecks. So my reaper would sometimes chase a tanker. Here the evaluation includes my Destroyer proximity
  • To improve all my moves, I added a post treatment to avoid collisions. Once I knew each destination point for my Destroyer and for my Reaper, I parsed all angles and thrust to determine the best way to follow without collisions

Top Gold Till the end of the contest (final rank 6th Gold / global 55th)
I couldn’t pass in Legend Guild because I didn’t have a simulation working. On the last day (sunday), I tried to code the complete referee (in C), but collisions functions didn’t work at all. From the beginning of the contest, I chose not to invest my time on developping the simulator, because I knew it would be a lot of time for me. So I prefered to use my time to perfect my heuristics, try other criterias (often not very good), and play with my magic numbers. My last feature was to kick opponents from a wreck with my Destroyer or my Reaper :

  • When my Destroyer or my reaper is on a wreck, and I detect a collision on the next turn with an opponent reaper, so instead of parsing my way to move my unit, I choose to move to this opponent unit.
  • Cast oil every time I can spoil the enemy collect of water, not only if the enemy has a best score than me.

Again, this contest was a very good one. I had a lot of fun and having my heuristics very stable from the beginning made my progression not too hard. I don’t regret not to have code the simulation, because it would have been a lot of pain without any garantee of success. I’ll code it when multi player game opens.

Thanks to all you people, to CG, and to the developpement team :smiley:

8 Likes
#18

Hi!
A great time consuming and challenging contest :slight_smile:
I think the creators should participate.

Post mortem: (Feel free to mention errors)

8th and C#.
First non C++!

Note: Pretty nice to test small pieces of code on the tech.io/snippet runner :slight_smile: Faster than creating a new console app just to try stuff…

15 Likes
#19

On my AI :

Not a lot to say about my AI. I basically reused most of my code from the COTC contest. (see post-mortem here)

For those who might be interested in the different codes that I posted during the contest:

  • pb4_TestCode01
    (first 24 hours of the contest)
    was a fully heuristic bot written for early tests of the game design

  • pb4_TestCode02
    (next 48 hours of the contest)
    was a basic GA bot, written for more advanced tests of the game design
    I spent a very low amount of time on this AI during design: the motivation to improve simply isn’t there when the test-leaderboard contains only 6 contestants…

  • pb4
    (from tuesday morning to the end of the contest)
    was my main code, written during the contest

On the design

I am curious to have feedback on the following:

  • Given a 1v1v1 game, we totally excluded 1v1 variants. Thoughts ?

  • Heuristics-friendliness of the game ? I’m waiting for more post-mortems, but I hoped that most search-based strategies (randomized or not) would benefit from heuristics-based guidance

7 Likes
#20

217th (hence Gold), F#.

Many, many thanks for this lovely contest. The atmosphere and the art work contributed a lot of fun. The heavy rate of collisions gave creativity a chance over stochastic algorithms. The subtle effects of the skills and their paper-scissor-stone structure generated a bunch of possible strategies.

I had only about 20 hours available for this contest, and I wanted to test F# on it. I started learning this language in June, and I must thank Codingame for this. My personal objectives were Gold (got it!), number 1 in F# (I did 2nd) and good laughs (got it, beyond expectations).

The few hours I had and the chaotic rhythm of collisions incited me NOT to compute them. I chose a structured, progressive approach:

  • Make an educated guess to predict what each adverse unit would do. I finally had no use for it.
  • Find the best strategy for my reaper, given all other units: rush to overlapping wrecks, or to a single wreck with some interest (water gain / (water gain + turns to reach it), or head to the tanker of most interest for my destroyer (so that I can get the water as soon as it is destroyed).
  • Then,knowing what my enemies and my reaper are about to do, select the best strategy for my destroyer: push enemies away from the reaper or head to the most interesting tanker (same formula as for reaper, using turns to hit and destroy, and then for the reaper to reach it).
  • Then, last piece: the doof: oil a wreck to let my reaper reach it while some opponents are on it, or increase rage.

This approach reduces the search space a lot. It also makes it easy to add new strategies. It could have been improved with some prediction of the collisions. No time for it.

The only area where I can see an option for improvement is in the delay for ranking. It was very hard to know if a strategy was good or not, because one had to wait for hours before any significant result.

Again, many, many thanks for this really entertaining contest!

3 Likes
#21

1v1v1 was essential to generate chaos, which in turns favors heuristics.
Heuristics-friendliness is essential for fun and for creativity. Developing new search algorithms takes years, even for IBM. In just 10 days, we can only implement existing ones.
So thank you for your choices!

2 Likes
#22

My postmortem is here: https://github.com/robostac/cg-meanmax-postmortem/blob/master/readme.md

19 Likes
#23

109th - Gold - Java

Thanks & congrats to the 4 autors, amazing game with a fun theme :slight_smile:

  • Nice to finally have a referee involving physics !
  • Getting to Silver was surprisingly easy, just send the repear to nearest wreck (with classic speed correction), leaving destroyer/doof in WAIT mode
  • From there, I worked on a MC bot. My simulation was probably functionally correct, so despite poor performance (between 6k and 8k in total, so 1000/1500 with depth 4), poor evaluation function (only score and min distance myReaper/wrecks, so no objective for destroyer/doof), no usage of Tars/Grenade, and always at max speed, it was enough to reach Gold and be around top 100 :open_mouth:
  • It shows that the game was rather hard, because looking at my own replays was almost embarrassing
  • Speaking of replays, it’d be nice to have a ~0.25 option, as 0.5 was still too fast when so many things are happening at the same time (and 0.1 is really too slow). The game’s complexity made it hard to analyze replays efficiently.
  • 1v1v1: I guess I prefer 1v1 as it feels less random, but at least the 1v1v1 was perfectly implemented with the right map
  • it’s obviously fine to let the autors play

Again thanks to the 4 autors, and still to CG for the platform !

4 Likes
#24

I think it was great because of the uniqueness. It’s good to have one game dedicated exclusively to 3-player mode.

I honestly believe Wonder Woman was far more heuristic friendly, because it was easier to predict positions and manage movement. The skills should have been slightly different, as they are they seem to make the game quite random.

Still the best game on CG.

2 Likes
#25

Uni here! Silver (~516th)

First contest, can’t really say I had high expectations of performing well, considering I’m not familiar with the contest system. I watched a few previous contest replays in advance for fun, fully aware that I’m probably not as competent as other experienced contestants to write a bot like what they had in the limited time. With that in mind, even though I’m still aiming for as high as possible (why not?), I wasn’t trying too hard and used an exotic language that not many other users are using for a language ranking badge. (It worked out, I was 2nd out of 2 users.) Also, I didn’t have any contest badges prior to this point, which is why I even signed up. Though, I did get a lot of fun for my free ticket.

I had made it a commitment before the contest started that I would do it in Bash for honors. I would actually have solid chances if I practiced beforehand, as while I knew the commands I’ve had to look them up (-lt, if syntax, decimal places in bc output) way too many times. If I wanted a chance to climb to silver in under three days I would have to switch out of bash. Maybe next time.

Day 0

I had a clear battle plan: I knew it would never get easier than wood, so treat it like a Clash, get to bronze, and sleep (contest starts at 1 AM my time. I was up late and would like to sleep ASAP)

Wood 3: Find closest pond, move to it. This was simple, but it took 7 minutes while I expected it to be done < 5, and it took some precious time.
Wood 2: Find closest pond, move to it. While waiting for the ranking to settle, I found out you can attach messages to your cars, so I made them say something for fun.
Wood 1: Find closest pond, move to it. If no pond, move to the water truck that our destroyer is aiming. Rage truck just runs towards whoever that was player 1. I’d had thought about using skills, and had implemented a very simple system that tried to throw a grenade to player 2 every few rounds, but it was performing poorly and I didn’t want to work on it further. Submitted rudimentary bot and went to sleep.

Day 1

I didn’t think the bot that I worked on for a grand total of 10 minutes (~20 if you include the time in / moving out of bash) and was 10 ranks below the bot at 10% battles done would actually carry me to bronze. This is good news because being on the top current league I can actually take time off and worry about a few other things before 11/21/17 (Silver league opens). Also it means I have two days to learn some algorithms for this, I was more of a “build stuff” coder, not really an “account for environment and perform well” coder. By that I mean I stared at the game with three main ideas in mind and didn’t know how to implement any. Since my bot building knowledge was at theoretical minimum, I had to ditch general tactics and focus on heuristics I concluded from analyzing replays. These elements are:

  1. Reward: Find “hot spots” of wrecks. If there are big wrecks connecting, it is good loot. By that I mean the reward of a wreck spot is proportional to how many other wrecks are in reach, and also that reaching a farther/bigger wreck may be a better option than competing for a closer, but remote / small wreck.
    Also: Merge adjacent wrecks (to modified x,y) with a bonus to encourage the bot to harvest from multiple ponds at once.
  2. Cost: If a wreck has many obstructing units like opponent looters, they may be competing for the water or just getting in the way to make navigation hard. Also, there are way too many cases where a reaper runs between water trucks and promptly gets stuck, losing valuable time. This means if there’s a distant wreck in plain sight it would be better to aim for that than rush towards a hard-to-reach wreck.
  3. Skills: Eventually I’ll need to replace the behaviour of my doof, while having him run to an opponent is funny, I probably wasn’t getting as much rage as I could. I felt this doesn’t matter early on anyway so my Bronze bot just throws a grenade properly and accounts for the range instead of stopping to try an impossible action.

Even though I didn’t think I could had, I tried implementing a basic simulation. I failed horribly. Ended up spending the rest of the evening sitting around watching cartoons.

Day 2

I woke up with an epiphany that I could target whoever that currently had the most score to delay him, rather than choosing whoever that happened to be an arbitrarily set player. I refactored out some of my mess of code that was a result from randomly throwing in a variable just because I needed it. This meant looking up the syntax of structs and pointers (it’s been years since I’ve used C properly) and trying to initialize things properly. This was not successful, and my printerr statements are telling me that I’m reading in 6250566 as almost all integers into field locations. Hurriedly deleted all the struct stuff and just made a table of int declarations.

After finally formalizing the data storage (with an array), I’m quickly struck by another problem: My bot was hilariously incompetent when submitted, and would often fail games where it had an advantage. As it turns out, it stops moving, so it probably crashed. However, loading the same parameters into the IDE to test couldn’t reproduce the crash, and often times even have my bot emerge as the winner.

After spending most of my day debugging, at 3:36 am I’ve discovered the problem: In the ide code running procedure, out-of-bounds coordinates as output is allowed, while the same thing for the real game is rejected as an invalid move. I had ran out of will to fix this and promptly shut down my computer, leaving the task for tomorrow.

Day 3

More debugging. I fixed a lot of bugs, it took the entire day. Going through them would be hard, plus you can write this section for me and still probably be on point.

Day 4

I thought I’d implement something, and I did. Top 250 is probably good enough for silver, I thought. While users in chat are frantically building their own simulations, I looked up a few algorithms.

Day 5

My bot comfortably sits on the near bottom (~2/3) of silver league. When it opened I was promoted and the bot ranked somewhere in the middle out of sheer randomness, but future submits proved it’s actually trash. In fact, it was a simple “score ponds based on water and distance and a few other factors”. I implemented tar -> bot got worse -> deleted it and implemented oil -> bot got worse -> deleted it and implemented depth-1 search for pond clusters -> bot got worse -> …

Day 6

I think I speak for most people on that pressure doesn’t help when you’re already struggling. With the pressure of Gold league opening soon I was getting worried that I couldn’t even make it to the upper half of the leaderboards if I wanted to make it to gold, which started to get to me. Instead of trying to redo what I failed to do, I took the day studying the rules of the game (and reading the arbiter code) and looking for inspiration. Unfortunately I didn’t get that inspiration I wanted.

Day 7
I attempted to code a genetic algorithm. I’ve seen a video on it before but I’ve never coded one myself. Even harder that I’m not using a familiar language.

Day 8
I am not a good programmer.

Day 9
Near the end of day 9 with ~23 hours left, I gave up trying to make a GA.

Day 10
I (properly) redid using the oil and grenade spells, and look for pond intersections properly. This helped me reach the high quartile of silver, which is totally where I’m fine with being. In the end, I had a few for-loops and not much more. If anything, it’s a really pragmatic bot.

Now

I made a few observations. Unfortunately I did not have them in time to use them as grounds for decisions to make during the contest:

  • 10 days is quite a lot of time to go on, if you figure out what you have to do early.
  • Near the early hours of a league, there are more bots that are performing poorly to boost your ranking, where as if you join late it is harder to get wins / ranking points.
  • Due to the nature of games between suboptimal players being mostly determined by a random number generator, having more games played seems to directly correlate to how high your ranking gets. If you submit your bot early, in addition to the primary batch of games used to determine your initial ranking, you will also be played against other new submitters, which push you further up. Conversely. submitting late puts you against huge odds which you have to fight against.
  • There doesn’t appear to be replacement for the rating points that are lifted as a result of already promoted players. This makes it a disadvantage to players trying to catch up. In fact, it might even be feasible to make a simple bot early on than craft a below average but sophisticated bot if it takes a lot of time.
  • I don’t know if it belongs here, but I showed three of my friends (who don’t use CG a lot) Mean Max and none of them even made it to bronze.

Good games to everyone that played!

5 Likes
#26

Post mortem from my 5th rank ! :slight_smile:

16 Likes
#28

15th - C++
My solution to the Mean Max contest : https://github.com/Garvys/MeanMax-CodinGame-Contest/blob/master/README.md
Basically a lot of fun and many things learned! Thanks a lot to everyone involved in making this possible from creators, to participants!
See you for the next one where I shall take my revenge! :wink:

12 Likes