Debriefing - The unofficial codingame contest (Platinum Rift 2)

[thibpat]

The Unofficial codingame contest is over! The goal was to get the best rank on Platinum Rift 2 during the 10 days of the contest. This thread is open for you to share your strategy, and/or feedback!

You can check the ranking there: https://thibpat.now.sh/contest/unofficial-codingame-contest

Edit: here is the blog post with the official winners: https://thibpat.now.sh/blog/the-unofficial-codingame-contest-is-over

[dadideo]

Thank for this great unofficial contest Thibpat! GG for every participant
I have not a lot of time to improve my AI, but as Thibaut said during live streams, basic AI is enough to reach Top1000. Some facts to figure out

• Total randomness, one pod only, rank 1016
• Total randomness, one pod moves per zone, rank 982
• Random, focus by unowned zone, one pod moves per zone, rank 904

That’s one small step for man, one giant leap for AI kind

[rmuskovets]

Just rushing the enemy is not so bad - got me to 476th place!

[dadideo]

rmuskovets It’s the famous (old but efficient) Zergling rush strategy
(from Blizzard #starcraft game, an example)

[jrke]

The contest ended with a smooth working thanks to @Thibpat who organised this contest before contest i was 488 and after contest i ended at 105 and my unofficial rank was 19.My strategy was not complicated :-
1-after getting initialising inputs (Links) i save distances from each cell to each cell from BFS.This was simple function to save all distances-
https://pastebin.com/k2k21yai
2-I was handling each pod seperately so that i managed team work till some limits and sending all pods to nearest cell which was not owned by me and in check if distance between your base and enemy base is < 10 or 9 then just attack.
NOTE-in this case don,t send your all pods to attack some for defence some for attack and some for owning.
3-But the problem that i faced was co-ordinating with all pods its the only thing that i wasn’t able to solve
This was my basic structure of code hope you understood

[k4ng0u]

Hi,

I’ll start with pros and cons on the contest format
Pros:
_Dedicated absolute/progression leaderboard that was motivating to compete with fellow contestants
_Nice 10 days format
_Discord discussions about strategies
_Recurrent thibpat’s streams
_Make people start the multi!
_Player progression graph (it seemed to only take ranks below 1000?)

Cons:
_Contest was run on a multi, meaning most of the match ups were done against non contestants
_Ranking isn’t accurate without final resubmission. (Basically if a bad matchup spam submits at the end of the contest, you can be pushed down, or the opposite with a good match up)

Regarding the multi itself, I kept a relatively simple strategy without any attack/defense logic that still enables my bot to rank between 40 and 80 (peaking at 42!) depending on who submits (thanks Nerchio for stopping after Thursday :D).

On Saturday afternoon, I didn’t really know how to start when I saw Thiesjoo’s message on discord “You can win a lot of games by rushing opponent base”, I decided to give it a try. After a little boilerplate work (store the node links, bfs for shortests distances and path, parse all zones where I have pods, a method to make pods move from a zone to another), my pods were going straight to opponent base and it sent me directly in top 300.
On Sunday afternoon, I noticed that a lot of people were doing this move and we ended with a draw. That’s why I came up with a small hack that would help me win in case of double rush. If I encounter 4 or more opp on the same cell on my way to his base, I would leave 4 pods behind to make the opponent lose one turn and let me be the clear winner. This worked quite well and sent me in top 250. Note, even on my final bot, I use this rush for maps where the opponent base is at a distance of 8 cells or less from mine.

But this logic was too limited and I had to work with pod repartition and expansion. In the end I had something working but still not that well. For each zone, I looked at the cells around. Then I sorted them according to number of neighbouring cells with pods (the less the the better), the cell value (the more the better) ,the number of unknown cells around (the more the better). And finally looped on it multiple times to split my bots. In the loop, I would only send pods if the zone is interesting ( based on cell value, cell owner, nb pods already affected to the zone and nb undiscovered neighbours). A cell owned by the opponent is systematically interesting, because it’s likely to guide my pod to the platinum the opp pod passed by. The remainining unused pods would be sent to the opponent base.

With this strategy my bot would do terribly on maps where there are multiple corridors to the opp base. In that scenario, in the middle/end game, my pods will generally all rush to the shortest path to the opponent base while the opponent will take all the platinum from the corridors and invade my territory without me knowing.

If I had more time, I would have tried to include some attack/defense on zones and maybe drive my pod depending on zones I want to target instead of choose the zone I want to discover depending on my pod position. Also I didn’t manage to make use of the number of platinum I have + the number of pods that spawns on my base/opp base to approximate my/opp platinum income and guess where the opponent has taken platinum from me.

Thanks @thibpat for this unofficial contest, it was awesome!

[WINWINWIN]

I managed a #47 on the Global leaderboard and a #12 on the contest leaderboard.

git-ani-p/codingame_pms/blob/master/Unofficial_pm.md

Here is my postmortem, for anyone who wants to read it.

I am also adding the other postmortems from my previous repo now.

EDIT: In the postmortem, I did not talk too much about how I implemented my ideas, so please send me a message if you want me to add a postmortem on implementation.

[Nerchio]

Hello everyone, for starters I will say that I ended up 2nd in the contest, 1st on the progression leaderboard and 7th on the overall multiplayer board in Platinum Rift 2.

Thank you Thibpat for this great competition and I think we can say it was a little bit of a success. I certainly enjoyed it a lot. As usual with multiplayer games on CG at first they seem very simple but quickly it turns out there is a lot of depth in them as it was the case with PR2. I think this one had a little bit steep learning curve since the game was based on hexagonal fields and you couldn’t do much without at least a full BFS in the first round.

I usually approach writing a multiplayer bot step by step which very often hurts me in the end because it becomes a mess of intertwined systems. I think if you want to try topping the board then you need some kind of plan from the beginning but it is hard to do without knowing how the game works and what exactly is the ‘meta’ at the top. So what was my step-by-step process this time?

1. To me the most obvious strategy you could take at the start was traversing the list of pods one by one and scoring their nearest neighbours splitting them when appropriate. You mark the hexes that each pods take so you try and avoid overlapping. I think this is the weakest part of my bot because very often a pod might take the most valuable hex near them(from multiple) which is also the only valuable spot near another pod so they overlap instead of splitting properly. Some people suggested Hungarian Algorithm for this but I am not an expert in this case, I think simple bruteforce for nearby hexes would work well but I didn’t implement it in the end. If I remember well this strategy lands around ~300 in the leaderboard around the same place where all the rushing bots with 2 lines of code end up
2. I added a defense mechanism which ended up very complex in the end because I wanted it to work in many different situations at many different distances from enemy base. Some bugs still exist in this system but it was able to win most close-quarters maps and defend against people rushing my base. I called it ‘circular defense’ as it expanded the ‘circle’ of hexes (you can see it as hexes at 1-2-3-4 distance from HQ) around my base checking how many turns left I have before the enemy can capture my HQ. It used a simulation of the future because in a very basic form it took account of the amount of time the enemy needed to reach my base and take it, so turns spent fighting would also be included. The basic idea was to try and intercept any units coming to my base if possible, in terms of defense it is better to be proactive than passive. Passive only works against simple bots. The higher in the leaderboard you climb, people rush your base less and less and instead capture any nearby valuable zones so waiting for them to come is a terrible idea.
   Having said that, my system didn’t deal with this perfectly either. At the end I still wasn’t quite satisfied with the result because in certain situations incoming enemy stack of units could kill your vision as they were coming to your base so I added a relatively simple system using ‘death detection’ which I will describe in point 3 that predicted an ‘invisible’ enemy units coming to my base.
3. Death detection (what for?) mechanism.
   I realised that in this game a system where your pods recheck hexes based on the “last seen X rounds ago” variable wouldn’t be very useful. You don’t really want your pods needlessly check the area where you didn’t lose any ground so I needed to come up with a different system which takes back the territory I lost.
   So at some point I discovered that in most situations when you lose the fight and you lose the vision usually what followed was you losing the territory as well. And even if you don’t lose the territory it is worth checking it again to see if it was captured. I compared the expected amount of my pods on hexes with the actual amount to discover hexes where ‘death’ occurred. I used this information then to leave a trail following the shortest path to my HQ that I calculated in round 1. It stopped on the first hex that was seen by me this round so in simple terms it could lead my pods to a hex where a death occurred. I feel like this system was one of the most important things that took me to the top. Not only it allowed my pods to reinforce ‘hot’ spots but also allowed them to go to important places on the map where my pods would stop enemy pods from taking territory or where I could take back a lot of ground.
4. The last system was trying to make my pods more efficient, I am still new to CodinGame so it was tough one to crack and I wasn’t sure how to attack this problem very well. I didn’t want multiple pods to enter small corridors that ended in a deadend and I also didn’t want multiple pods to enter “enclosed space” that could be taken by just 1 pod. It is much better to send your units to the frontline or other ‘hot’ spots instead of them following the trail of another pod. When a pod was making a move it used a simple calculation function(floodfill with custom heuristic) that was checking if the square leads to corridor or not. In this case I was checking that if a next square in the function had more than 2 “new” neighbours (not found before in a tunnel) then it was not a corridor. The idea behind it is that if it wasn’t a corridor you would quickly find a hex that has 3 “new” neighbours. This system might have some holes but it worked really well for me. I used a similar thing for enclosed spaces. If the area was a tunnel or an enclosed space then it was marked for a pod to take alone.
5. My next fix was a follow up to point 4 where I tried to split my pods as much as possible around the map so I added a small simulation where a pod making a move would make a “splash” to all the neighbours and marked that it can reach those squares in the future in X turns. This allowed me to prevent far away pods from picking hexes that, by the time they got there, would be already taken by other pods.
6. I realised that some maps were so broken that playing on them wasn’t really worth it on one side so I added a detection system that would recognize that map is not symmetric and my position sucks “send 10 to enemy base strategy and hope it works”. I could improve this one a lot more but I felt like it helped me climb more steadily through the ranks because in the middle of the leaderboard people don’t really have defense systems and you can very easily lose to them trying to win a lost game so it is better to take a draw(both capture each other bases) from a lost position and win the other side rather than go 1 win 1 loss. I only used this on distances higher than 2 because in very close quarters I felt like my bot can outplay them even if my position is worse.

I feel like my approaches were only one of the many approaches you could take to this game. For every system that I made I could come up with systems that approached the problem from a different perspective and this is why this game took me by surprise. It is a very deep game when you get into it and I am pretty sure other top submissions have completely different systems to mine. Compared to, for example, Ocean of Code where everybody had to code a tracking system for the enemy, this one has complete freedom with how you want to deal with it.

[zogstrip]

One is not enough for such an amazing post-mortem @Nerchio

[Hjax]

I came in 7th on the unofficial contest leaderboard, 3rd on the progression leaderboard, and 31st on the multi leaderboard (although a resubmission climbed to 20th this morning).

Overview

My bot was really simple, only about 200 lines of python, usually I start with python and switch to java midway through the contest, but I stuck with python this time because I felt that speed was not really a concern. It is basically just the Hungarian algorithm with a few tweaks.

Start Of Game

My bot calculates BFS distance between all hexes at the start of the game, and my algorithm sort of evolved throughout the contest.

Humble Beginnings

At first I wrote a simple spreader that just randomly moved pods to adjacent tiles. Just to make sure I understood the inputs. This version of my bot was about rank 900.

Simple Heuristic Based Strategy

Next I worked on biasing my simple spreader towards making better moves. I had it favor tiles that were unclaimed, enemy tiles, and tiles with platinum. If my pods were only surrounded by friendly tiles, they would walk straight towards the enemy spawn. I do rush on small maps, but I am not sure how much this helped my winrate. This version performed surprisingly well and peaked at about rank 130 after I added some rush defense.

Rush Defense

My rush defense was kind of hacked together and probably one of my bots biggest weakness. It just tries to keep more pods within range N of my spawn than my opponent has at range N+1, up to range 5. The problem with this approach is if I do not have vision of a rush in time, it is often too late to react and I lose anyway.

Final Bot

Eventually I decided to replace my heuristic based spreading strategy with a real algorithm, and I used the Hungarian (aka the Kuhn-Munkres Algorithm) for assignment. Fortunately for me, this was already implemented for me in scipy’s linear_sum_assignment function. I just generated a list of targets (any tile that I have seen but not visited, or any tile that is known to be owned by my opponent) and created a scoring matrix for every one of my pods. My scoring function was very simple, it was just distance - platinum / distance.

Omissions

I find it interesting how high my bot ranked on the global leaderboard (20th at the time of this posting) with the number of things I could have added but didnt. My bot does not abuse map symmetry to find platinum positions, nor does it use its platinum income to determine if its opponent has retaken parts of the map. In fact, my bot will assume territory it has taken will remain in its possession forever unless it accidentally learns otherwise (by a pod walking through and gaining vision)

Last Thoughts

This contest was pretty fun, and I don’t think I would have ever tried this multi if not for the unofficial contest, so thanks to @thibpat for hosting this!

[wala]

Thanks to @Thibpat for organizing this unofficial contest.
Improving my Platinium Rift 2 bot was on my todo list, but this motivated me to try a little harder than i would have done alone.

What allows me to move from top 10-20 to top 3 was trying to “break down” the fog of war.

Each turn :

• i update a boolean array to stock if opponent pods could be in the corresponding zone.
• i calculate the platinum i should have won and compare it to my real gain.
• i deduce which zones i could have lost.

It was basic but often there was only one possible combination, so i knew exactly which platinum zones were taken by the opponent.

Other features of my bot :

• Defense : retreat pods or make them stay close in case of danger (only for base and big platinum zones)
• Exploration : first opponent zones (possible infiltration) and unseen zones, then the possible lost zones (if there were any)…
• Spread : avoid too many pods in a limited area.
• Detection of symetric maps (with possiblity of rollback).

I hope you’ll organize this kind of contest again. It’s a lot more fun and motivating than working on a multi alone.

[alchemsti]

Hey all, thanks for a good time.

I didn’t get to spend as much time on it as I would have liked, and the time I invested didn’t pay off as much as I would have liked, but it was still fun. I went from no submission, to low 300s pretty quickly, to a slow improvement to low ~120.

I started with a generic strategy I’ve used to score in the middle of other, similar, contests – evaluate each zone with people, evaluate the neighbors, and split myself amongst them, based on score.

I assigned a score based on whether I owned it or not (or no one), platinum, and then also boosted further away from me, and closer to the enemy (the latter pretty small). I also added a small random factor later to help spread out exploration better. This worked pretty well, and got me in the low 300s.

Although I knew people were rushing, and I was losing to such rushes (sometimes foolishly, moving defenders off my base, so a solo enemy could claim it) I wanted to improve by moving my troops to the ‘frontier’. I considered the frontier a case where I could see it (or had seen it) and it wasn’t controlled by me. I then changed my assignment to send troops to the nearest frontier spot. This gave a pretty big boost. I actually did a bit of a hacky mix, so that if troops neighboured on the frontier, they sent troops to it, and then later looked moving those further away. I never did a decent job of ‘coverage’ (a troop has been sent and is sufficient, so don’t send more), which I think would have been key for a higher ranking.

I did do a nice technique, IMO, of figuring out where to move next based on where I wanted to go – given the distances of all-to-all, you only need check which neighbour is closest to the target.

I then spent some time on defence, but only in a half-assed way. Basically if more enemy were close to my base than me, move in the way, rather than further away. This got me into 100-200 region. There was definitely room to improve here – I think I only considered out to 3 hexes away, but it got complicated.

I think most important to me would have been the ‘coverage’ tactic – not exactly, but at least a better job of sending the right number of people to the target frontier. I also never did proper ‘defence’ of normal squares, e.g., if I and an enemy are dancing, sit on the hex with more platinum.

I didn’t do any advance zone loss detection, not did I analyze the map for chokepoints or such, but would have liked to, but I think they were less important. Tweaks to scoring zones would have been nice too, and a more generic defense/rush strategy. Oh well, can’t do it all.

Thanks for a good time!

[alchemsti]

This was about 550 lines of C++ code, FWIW

[Illedan]

Good job @thibpat for organizing and making the community focus on 1 game

I had a bot around 100 or so before the start and only had time + motivation the first weekend bringing me top 15.

My bot is quite simple:
Sort all zones in random order:

• Get the number of Pods and remove the amount needed for defence (only if I have enough)
• Send them to adjacent zones not owned and with platinum. If there is such a zone, mark the 2 closest neighbours as taken by this pod too.
• Put the rest of the pods in a FreePod list

Loop through the free pods:

• Take the next free
• Find the closest zone not targeted already. Only target zones with Platinum > 0 or with a chance for an enemy there. (I assume all zones have Plat at 1 at start, to enhance scouting.
• Look again at all remaining free pods. Pick the best pod for this target. Mark nearby cells as taken.

Enemy tracking:
BFS 1 depth every turn from the seen enemy pod zones. Only assume there is danger if enemy could have occupied a zone with known Platinum.

GG