Mean Max (CC01) - Feedback & Strategies

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

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

19 Likes

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

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

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

Post mortem from my 5th rank ! :slight_smile:

16 Likes

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

Iā€™m a bit disappointed by this first community challenge and my final ranking may be the worst since I play CG (639th / 2512)

I didnā€™t like :

  • The rules (especially in french at the beginning of the challenge).
  • The similarity with CoTC (that was a bad challenge too !)
  • The ā€œnearest wreckā€ strategy allowing to reach Silver with no effort
  • The useless speed parameter
  • The confusing viewer

Iā€™m also disapointed by my own failure :
I didnā€™t find a way to enhance my simple strategy. I tested many things, with very poor impact on the ranking. Observing replays during hours didnā€™t allow me to understand what was wrong :frowning:

That was not very fun this timeā€¦

What similarity ?

Collect something before someone else on a map.

pb4 said in this thread that he reused most of his code from cotcā€¦

41th - Java - TIMEOUT! - 30msā€¦

Thanks and congratulations to Magus, Agade, Pb4 and Recurse for the theme really interesting and also thanks for the referee which help us to manage collisions!

FEELINGS

This contest could be really fun if i didnā€™t waste more than a half of my time optimising memory consumption using Java Mission Control to profile it as i often get timeout with no error. I suspected the garbage collector doing major or full gc so i spent a lot of time caching objects avoiding deallocation, removing stream, foreach which create object like iterator that will be garbage later on. I also put some counters to securise my loop so iā€™m sure i do not have infinite loops, IN VAINā€¦

Sunday night i resign to set my timeout to 30 ms when in other contests i use 44ms. It takes me so much time doing that as i persevered too much that i couldnā€™t spend some times optimising the rest of my code like the collision engine. Too badā€¦

Strategy

Wood to Silver

Simple heuristic

  • Reaper move to the closest wreck
  • Destroyer move to the closest tanker

To compute target and power i just did a vectorial computing like this :

MoveAction createMoveActionStopOnTarget(Unit source, Point target) {
  Point newSpeed = new Point(next.x - source.x - vx, next.y - source.y - vy)
  return new MoveAction((int)(newSpeed .x + source.x), (int)(newSpeed .y + source.y), (int)Math.min(newSpeed.magnitude() / source.mass, MAX_THRUST));
} 

It works pretty well to stop the reaper inside a wreck if it has not too much speed.

Silver to gold

Add doof and skills

  • move doof to the playerā€™s reaper with a greater score than mine (not necessarily the best but the player i can more likely beat)
  • doof skill on wrecks where there will be 1 or more enemy reaper at the end of the turn excluding those with my reaper
  • destroyer skill on my reaper if i will be on a wreck in 0 or 1 turn and reaper in the range of the skill to move aside them
  • reaper wreck target take into account distance and water. I manage also to go to overlaping wrecks to earn more than one point in a turn
  • destroyer tanker target take into account distance and water

Gold to Legend
Hell on earth! Timeout power!!!
I use simulation engine from the referee coupled with my previous heuristics and an evaluation function to compute at depth 3.

First, I compute some possibles good moves at depth 1 for my reaper, doof and destroyer.

Then i test all moves combinaisons using the simulation engine at depth 3 using a dummy for the enemies and for my last 2 moves with a simple AI like :

  • reaper go to the closest wreck with the most water
  • destroyer go to the closest tanker with the most water
  • doof go to the playerā€™s reaper with the score higher than me or lesser if iā€™m ranked 1st

After that, during the remaining time i play random moves mixed with previous one and i evaluate them. I do not play random skill as it was not really efficient so i prefer compute skills using my heuristic.

Finally i take the best moves and play them.

The evaluation function is as the previous one described by Agade and other players. To reach the legend i had to avoid destroying tankers if my reaper is not close to it so i adjust the evaluation function to do that also as my heuristic to compute a move close to the next tanker position avoiding killing it.

What did not work
Timeout, timeout, timeoutā€¦
I think there is a problem with the garbage collector parameters used to launch java player perhaps since langage upgrade occured. I hope this problem will be corrected soon!

5 Likes

I had timeouts in java with 20ms limit too, so i switched to c++ at the end of contest, even though I donā€™t know it :stuck_out_tongue:

3 Likes

Finished #64, C++ - GA

Intro
First of, thanks a lot to the 4 creators and to CodinGames for hosting such fun and interesting contests (as always)

Iā€™m used to do spaghetti ifs in C# with my best friend Linq, but wanted to try what pros do : c++ and simulation.
This contest was perfect for this: I donā€™t think I would have had fun with C# heuristics, compared to something like GitC, where heuristics were way easier, because no collisions and much more ā€œunitsā€

I had 0 previous knowledge with Sim/GA (Iā€™ve never played CSB for example) so it was quite long and hard for me to setup a working simulation + GA in C++ within 10 days (got a job, not living alone, barely havenā€™t done any C++ in years)
So when it started working, I had a blast (not directly commanding through ifs, and seeing units doing smart moves is awesome). For this, Iā€™d like to thank ZarthaxX for his help with GA, and others on the chat.

Strategy
My strategy was quite simple, my eval function using common parameters already mentionned several times before, so iā€™ll do that quick:

  • Depth 3
  • Additionnal weight for each depth (same ratio between depths)
  • A function determining who is the opponent I target (#2 if Iā€™m #1 or #3, #1 if Iā€™m #2), used in Evaluation Score and below.
  • Ga ran for 2/4 ms on opponents to avoid using dummy moves (the 4 seconds being the opponent I target, and done with moves found for the second less important opponent)

Iā€™ve disabled TAR spell since my reaper was randomly putting that on the ground. Maybe it was useful (I like to tell myself this xD), but I couldnā€™t tell by watching replays,
and it was eating a lot of rage I prefered to spend on avoiding enemies to collect water. Sometimes it would use grenades as well, didnā€™t have the time to really validate it was useful (letā€™s say it was)

The main issue I faced was to have my sim + GA working less than 24h before the end of the contest, so no time to setup a proper environnement to tweak parameters and adjust them correctly. (+ no experience with that)
Plus, during the last 24h, A LOT of players did A LOT of submits, which slowed manual submits/tests even more.

What I think of the design (for Magus who asked)

  • First, I found it quite ā€œmessyā€, especially when I had a look at games in bronze with full rules. I found it quite hard to explain to random people (like my girlfriend), compared to something like CotC.
    But after a while I got used to it.

  • I think it was not so easy for a noob (I find not so easy to just address the destination issue, using velocity and stuff).
    My brother who is not really good at coding liked it thoughā€¦ until he quit because he couldnā€™t improve his AI, quite early. His ranking is around #1050

  • The 1v1v1 format is ā€¦ special, makes it even harder to tweak parameters and make sure your AI improves. But hey, itā€™s the same for everyone, itā€™s quite fun to watch and it adds an extra layer of strategy. So Iā€™d say itā€™s a +

  • The design looks like CSB: collisions, angles, speed, small number of vehiculesā€¦ (at least in my eyes, but once again, I havenā€™t really done anything on the CSB contest, so I might have missed huge difference).
    IMO it makes people who worked a lot on CSB (and AFAIK, itā€™s the ā€œmainā€ multi played outside contests periods) quite good right away (but hey, the worked for it right? :p)
    I say Iā€™d prefer contests where itā€™s less obvious to know how to handle things (like C4L, GitC, where you canā€™t just plug a global GA)

Conclusion
Anyway, Iā€™m really glad I tried hard on this one, learning way more than on any previous contest Iā€™ve partipated in (even those where my final ranking was higher)

Congratz to everyone who learned something during this contest!

I really hope those contests will still occur on a regular basis.

Oh, and last thing: thank you reCurse for letting me the #1 Canada spot. :smiley: (DN38416 / Chalzy were close !)

7 Likes

One of the best contests in CodinGame Thanks for organizing :slight_smile: We want more contests from you guys.

I used C++. I used a random search with an evaluation function (I donā€™t think mutation or crossover would give better results :P). I spent more time on fixing my bugs and optimizing runtime and memory than actually improving my evaluation function. So Iā€™ve learnt a lot of things especially on memory management, pointers, upcasting, downcasting, factory design, state design pattern.

The first thing I noticed in this contest was I didnā€™t have to track anything globally because I get every required information in every turn. The referee code was shared in the wood 3 league which was very useful for me because that helped me build a nice data structure that I would require in higher leagues.

Enemy score and mana information also gives freedom to play it safe or aggressive or hold the rage for late game and try various such strategies.

The hardest part for me in this contest was to predict opponentsā€™ doof and destroyer movements.

Below is the class structure I used for the contest.

3 Likes

Silver - 450/2512

Best contest ever in my opinion, got to learn so much from it.

Wood to Bronze:

  • Used a dumb code that, had a major bug but it helped me get to to top of bronze pretty quick.

Bronze to Silver:

  • Same code, found that bug from the initial code, was using Unit_ID instead of Player ID FacePalm.
  • After getting to Silver worked on the distanceRatio between enemy Reaper and my Reaper.
  • Destroyer would target tankers only after they have filled up (worked 90% of times) otherwise it says in Water Town.
  • Doof targets closest enemy reaper (well after reading others reactions and strategies, it was not the smartest move, i could have used Enemy_score to evaluate which enemy reaper to target.
  • Finally, my Reaper only targets pools of water that have more than 1 water.

This helped me get to top of Silver but ran out of time to improve my code further. Waiting for the Multiplayer to open soon.

Lastly, A BIG THANK YOU TO THE CREATORSā€¦ Awesome Job Guys!! Even though i was among those who thought you could have waited till the Multiplayer opened to submit your codes, but at the end of the day none of you put in that extra effort to claim those top 3 spots. Respect!

3 Likes

Thanks for the contest guys, it was even better than most contests created by CG team.
Some comments:

  • Thanks for providing all game state in the inputs.
  • Iā€™d say the amount of units was too big. With all 9 units and bunch of tankers and skill effects on a map it was hard to be a spectator. I was able to understand what was going on only by going frame by frame
  • Instant change of direction made vehicle movements not smooth, it was not as pleasant to watch as CSB.
  • I was around 60 at the end but was not able to use Reaper skill the way I could profit from it. I guess a lot of people did not use it.
    Overall: Good job guys! Thanks a lot.
    If case if you need any suggestions for the next contest: Iā€™d like to see something more smooth and aesthetically pleasing :slight_smile:
1 Like

Hello all,
I didnā€™t find any topics on the forum so I will post it there as Razielwar pointed it out.

I also have a lot of timeout and as he said it is probably due to the upgrade of java.
I was looking previous multi games and saw that I was having plenty of matches lost by timeout: FB and CSB.
I have seen that BeardedWhale (using Java too) was also having the issue on FB, which truly make me think that it was due to the Java upgrade.

Is this issue known? We can no longer use the System.currentTimeMillis()?

2 Likes

This thread is discussing specifically how to measure time in Java:

For MM, I had to use a 15 ms margin, which is enormous when we have only 50 ms. @nmahoude as well I believe.
And itā€™s not as if Java was already well under C/C++ performancesā€¦

2 Likes

Yeah good point, no additional burden (coding/execution time) to try to estimate opponentā€™s scores / mana.
Only missing thing you have to track globally was the round number, I guess itā€™s OK :slight_smile:

1 Like

Thanks for the contest, it was truly interesting!

My current solution is only an heuristic (posted on tuesday), and thatā€™s what was incredible on this contest, with a good heuristic you can have a truly good solution.

  • Donā€™t focus tanker with 1water and far from the center (3500)
  • Find the best nearest wreck (dist - nbWater*500) where I am the nearest from (donā€™t go if my opp will take it first)
  • Destroyer goes to the nearest tanker of the targeted wreck
  • If no wreck, reaper goes to the same tanker as destroyer
  • If no tanker, reaper and destroyer go to the center by default
  • Doof focus the opp reaper with the nearest score and launch oil when itā€™s possible and when opp reaper is on water :wink:

I was trying to perform an AG but I didnā€™t had the time to finish the code engine :cry:.

1v1v1 was interesting as we must choose if itā€™s better to secure a second place or trying to have the first one.
50ms is interesting to have competition between AG and heuristic (and also matches and submit more fastā€¦)
Rules were hard to understand (even more true with french rules at the beginning). It became clearer after rules updates.
Referee is truly a must! As it allow to reply to some question easily by looking it at =).
Circle arena was easier to perform computation, it was a good idea.
Maybe the contest was a little too hard for the beginners in a contest.

A big thanks to CG and our 4 incredible CGamers who created this :wink:

See you for the next challenge :wink:

3 Likes