Game of Drones AI battle: god's strategy (2nd place)

STAY CONNECTED, FOLLOW CODINGAME NOW

It is said that only Gods are fare-seeing so god2nd in Game of Drone's rankings, was right... His strategy proved to be rewarding as he reached the 2nd step of the podium after 10 days of challenge. Congrats to him and many thanks for his detailed review!
[see the French version here: http://ow.ly/v8vlS]
--

At first, I start by resolving the problem for a zone. For each of the players I sort their drones based on their distance in number of turns to this zone. Thus, for each player, I have a list of the number of turns before he is able to reach the zone with 1, 2, 3, 4… drones. I conclude the list with the number of turns before an enemy could reach the zone with 1, 2, 3, 4… drones, as well as my own distances. If the zone belongs to me, I add defense objectives to reach the zone at the same time as my enemies and with the right number of drones, if not with a drone more. For example, I make the objectives “to be able to have 1 drone in the zone within 2 turns”, “to be able to have 3 drones in the zone in 5 turns”. If the zone cannot be defended with 3 drones, for example, I will consider that it is no longer mine for the objectives with more than 3 drones. Likewise, if I know that I am going to take the zone with 2 drones in 3 turns, I will then consider defense objectives for more drones.


I attribute scores to the objectives based on minimum points they bring me, divided by the number of turns before having collected these points. Furthermore the defense objectives have a base score of 42, those of assured attack a score of 40, and those of uncertain attack a 10 (these objectives are added when an adverse action is necessary to take the zone but the adversary in question was not in the process of making this action the preceding turn). This score is defined by a somewhat crude manner and is not the most important parameter.

So far, everything flows naturally, I apply foolishly the rules of the game: take zones when I can, defend those which are mine, the score calculated in number of points won per turn. However, I remained very flexible in the definition of my objectives, which then allowed me to maximize the number of objectives attained. I contented myself with preserving my possibilities; I didn’t say “From now on I’m going to charge into this zone with 3 drones!” but instead “I want to be able to have 3 drones there in 5 turns”. Thus only the drones 5 or 6 turns from the zone will be constrained, and nothing keeps them from having other objectives simultaneously. Furthermore, since I plan the capture of zones, I can thus recapture very quickly a zone lost or defend in advance a zone not yet captured.

I thus begin by computing the objectives defined earlier, for each zone, and each number of drones possible between 1 and max-1 (not max because of a technical limitation in my calculation of the score, which was quite bad for the matches with 3 drones…). These objectives are of the form (N,Z,R)=”to be R turns from zone Z with N drones”. In practice the drones at R-2 turns or less are assured and thus are not taken into account.

I then looked to accomplish the objectives one by one, by order of score, while adding the corresponding constraint to all drones potentially useful for the present objective. A constraint being of the form “to be in a disc of radius R+1 around zone Z”, to merge several constraints requires a calculation of the intersection of several discs (one per constraint + the one with a radius of 100 around the drone). As I assigned the constraints to all drones available each time, I have the margin to go ahead with the next objectives. For example, if I have “1 drone at distance 0 zone 1 among drones 0, 1, 2,” then “2 drones at distance 0 zone 2 among drones 1, 2”, I begin by putting the first constraints  on drones 0, 1, 2, then I see that I can take drones 1 and 2 for the second objective since the first has a 2 drone margin. It is also necessary to be aware that certain objectives depend on others. For example, to go ahead with defense objective (N,Z,R1), I will first try to carry out defense objective (N-1,Z,R2) if present.

Finally, the last very important detail, what to do with the drones that have nothing to do? It’s the only point that so far has no answer in the rules of the game. At first, I sent these drones to the center of the map, but they usually did quite little there… Then I saw that a number of matches reached a point of stability where a player controlled 3 zones on the edge of the map. It is indeed a good defensive position and I thus placed my home-base at the barycenter of these 3 zones (to the right or to the left of the map while choosing the most isolated group of 3). This simple change resulted in an incredible augmentation of victories and as soon as I implemented it, I was making perhaps an 85% victory rate in a 4-peson match against the top 3! Unfortunately, towards the end of the competition, the difference in this parameter was less pronounced.

In matches of 3 players, I changed my home-base several times between the center of the map and the 3 zones on the edge. My last version online uses the center, and I would have perhaps held first place by maintaining the 3 zones on the edge. The choice was difficult and I would have submitted both versions to check if I had gotten up earlier (I have a +8 hour relation to France). The problem is the following: the edge is stronger in principle because it is more stable (less attackers, who come from one direction), but there remain only two other players and if one of them ends up at the 3 zones I chose, the third easily picks up the 3 zones on the other side and wins because he is attacked less then I am. This typically happened when a player was already on my 3 zones and persisted in remaining there. I didn’t linger too long over this as I was already ranked first and I was tired, but I think that the center is all the same a bad choice because I find myself between the 2 other players, and I should simply have better chosen my side, and perhaps have taken a barycenter with more weight on the 2 zones of the 3 the most at the edge to better repel the attacks towards the center, since 2 zones in 6 suffices if I capture the 3rd from time to time.

In matches of 2 players, I did very few tests and I suspect that I must have been not very good since my algorithm doesn’t attack zones already attacked by another player, which handicaps me in all my matches at first, and particularly in 1 v 1. Thus I couldn’t settle with taking 2 zones (too late) and falling into a stable position. I therefore made my home-base the barycenter of adverse zones in order to be very aggressive. Furthermore, this strategy is superior to the defensive because it’s impossible to hold more than one zone for certain if there are as many attackers as there are defenders. Thus if one defends his 2 zones and the other attacks, the attacker takes the zones before losing his own and wins. This becomes ridiculous if the defender does not counter-attack elsewhere.

But it was still insufficient because sometimes this led me to abandon a position already acquired, indeed even stable, to try to conquer my home-base. I thus updated the home-base at each turn so that it became the barycenter of my zones if I had 3 zones or more (this works for 2, 3, or 4 players).

And there you go –– to conclude: I had very good tactical efficiency, and a little strategy in the fine-tuning of the home-base. I had a few minor problems as in the start of the game or my inability to use all of my drones for the same objective (problematic in the matches of 3 drones especially). And the strategic side remains to be developed, I think, for all the candidates. For example, I didn’t consider the fact that taking such and such a zone assures that I will be able to then take the other behind it, or that to attack this or that zone is a good move because the potential defenders have other things to do, etc.

-----
Language and environment

As for nearly all of my programs, I chose C++ because it's a complete and efficient language that I quite master (maybe that's the most important point).
I use Debian with vim. Concerning the versioning, I just did a couple of manual backups.

A tip: in the middle of the challenge, I was quite fed up with copy/pasting to test my matches, so I found the xclip command, which allows to automate "copy" by adding to Makefile for instance. It was a real relief :-) 

----
Link to my code in C++

No comments

Post a Comment