Third and last one of the Game of Drones winners, Gangrene, 3rd in rankings, explains his strategy and the steps of his reasoning.
[see the French version here: http://ow.ly/v8vRx]
The fact of having integrated IRC into the IDE allowed for a great deal of communication among the participants. One could thus hear quite a few strategic ideas, especially when it came to brute force or the analysis of enemy blows.
For my part, my reasoning was as follows:
As a result of this, my calculation was based entirely on distances.
Initially I made a table containing the number of turns necessary for each of my drones to reach each zone. To the side, in another table, I calculated, for each zone, the number of turns in which it could receive 1, 2, …, drones belonging to one same enemy (without worrying about which enemy it would be).
What followed is a calculation for which the difficulty was to address in parallel the number of turns needed for attack or defense. I calculated which zone I could capture the most quickly, or which zone would be taken the most quickly by an enemy if I didn’t defend it. Once my drones are assigned to attack, the target is considered as a zone belonging to me, and thus to be defended by my still distant drones.
In the same manner, a zone that I cannot defend beyond “t” turns becomes an enemy zone for my remaining drones.
As soon as I can no longer take or defend a zone, the remaining drones (“good for nothings”) are assigned according to an arbitrary decision. This was at the beginning to choose the barycenter of all the zones, so as to be quickly available. Later, I preferred to send them to an enemy zone to “nail down” opposing drones. In the end I returned to the barycenters for my final modifications, which I will explain later.
I quickly realized that the matches of 3-4 players were a challenge for the size of which my little drones were ill prepared. It is indeed easy to let oneself be taken in a sandwich and to die of suffocation between 2 or 3 teams. Thus I, exclusively for the matches of 3-4 players, set one of two zones on the extremities as a priority zone to be possessed at any price. My drones therefore headed towards this target as soon as it was lost and thus avoided a suffocating central position.
These decisions constituted my base strategy. Then, some details were taken into account to refine the calculations. I note three of them:
- The first concerns the calculations of distances. Many people are interested in this, and the CodinGame team explained to us that the coordinates of drones were stored internally in floating point numbers. Because of this, it is interesting for us to also store the data of our drones, and to recalculate their exact position depending on the point towards which we tell them to aim. When it comes to enemy drones, it is dangerous to try to guess their target. Therefore I didn’t use their coordinates of the preceding turn, but settled with new ones while adding 0.5 to the distances on the X and Y axes.
- The second detail is the position that a drone takes in the zone that it occupies. A zone has a radius of 100, which corresponds to 1 turn lost in order to leave if the drone is at the center or up to 2 turns if it is poorly placed. A drone that is in a zone will thus head for the point closest to my barycenter.
- Finally, sometimes a drone must defend a zone against an enemy drone one turn more distant that itself. This means that my drone must not distance itself from the zone in case the other will advance, but it can always move within the same radius. I thus send it upon the closest enemy zone, always remaining within the imposed radius.
This strategy gave me a good position, and I would have finished between 8th and 15th place with this alone. And then the last day, while observing my movements and those of the first in rank, I understood that my drones were too mobile. Two drones leaving to capture a distant zone weaken my defenses considerably, and this despite my priority zone.
I thus made a risky gamble, that of limiting completely my domain of action. Henceforth I still took a zone at an extremity (zone A), but also its two closest neighbors (zones B and C), and I removed all other zones from my list. My drones now knew nothing more about them and therefore concentrated on the 3 selected zones with redoubled efforts. It was also at this moment that I decided to reuse a barycenter for the “good for nothing” drones: My three zones becoming much more simple to defend, I assigned my unused drones to the position equidistant from zones B and C, zone A being in theory safely hidden behind.
This final modification gave me 3rd place, and was very much inspired by the AI of GoD, which limited itself to three or four neighboring zones. The imposition of which zones were involved allowed me, furthermore, to avoid the sandwich effect. In numerous cases my assailants were repelled towards the remaining zones where they shared the leftovers.
The major risk, of course, remained that someone else may follow the same strategy as I (which was, by the way, easy to grasp while watching my matches). I take the opportunity to give a wink to MasterBOX, the AI of whom made me very afraid while targeting the same zones as I only 6 hours to the end of the game. I suppose that he altered it in that time, because without that we would both of us have lost each match played together, which would have probably caused us to tumble down the ranks.