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