Game of Drones AI battle: Loujo’s strategy (1st place)

A Game of Drones Thrones

*Thanks to Manwe for this involuntary pun

The playing out of the competition was comparable to a television series, with its share of unexpected developments. For an entire week, I was first in rank with a comfortable lead. On the English chat, a participant compared me to Sauron: when Sauron grows up, it can’t stop.

Last Sunday, 48 hours before the end of the competition, I had such a lead on the 2nd and 3rd spots that I watched videos on the uses of drones and talked on the online chat rather than keeping at improving my AI.

Then, bang! Monday morning, the player “god”had come from the orient (he will understand) to bring down Sauron: I had slipped back down to 2nd place, he was very strong, and I had much less time to code. There were even some who told me that they were thoroughly bewildered!

Thus I got back to work. Last night at the end of the competition we were neck and neck; after having spent the afternoon in front of me and the night on a hair’s thread, my AI climbed back at the end to finish in the first place.

Languages and Tools

Python

Compared to Tron, in this game there were fewer calculations to be done by the program: in principle no in-depth calculations or excessive research. I, therefore, chose to leave C++ aside and to program in Python. If I needed computing power, I could come back to it eventually but I didn’t have to do it. I wanted less to hold on to my code already existing at a point in the game in case of a change, to not hesitate to rewrite entire portions and more to consider the game and its logic rather than the code itself.

To sum it up, for this game: less programming, more logic, and more geometry. Incidentally, each move was found by my AI in 1 to 3 ms on the game’s server.

I didn’t even use the classes with Python, only the functions: no variables of the type drone.pos.x, for example. Everything was thus arranged in tables, tables of tables of tables, etc… with great sweeps of

[f(n) for _ in xrange(N)]

It’s compact, quick to write, orgasmic, dirty. I nonetheless documented each function of my code and passed the data in parameters to avoid global variables, quite scarce.

Environment

As usual, I code on Linux on a bépo keyboard with Gvim. I use Subversion as the versioning system while identifying the revisions that were good in the arena, which also allowed me to write this article. When said and done, it does you good. In 10 days of competition, there’s no time to program a game environment to test different versions at home, and then, the very concept of the game nullifies any interest in setting against each other two nearly identical AI’s (the score remains 0-0 at the end).

Situation of the Game in SVG

On the other hand, to improve the debugging and the development, I coded a function in my AI that writes an SVG image when it is being tested. The situations of the game are written in text input files, and instead of analyzing loads of numbers in loads of tables to see if the program reacted well, I look at a pretty image. I even have a script that re-launches the bot on all the test files to check a new version.

Here is what that gives us:

This SVG was made with Gimp and converted to PNG for the needs of the blog

The filled circles are the zones of the color of the player who has them, the points with the circles around them the drones and their active radius, the red lines the movements determined by my AI.

Chronological Commentary on the Algorithm

The game began Friday the 14th of March and finished the 25th of March.

My first version was such that each drone goes towards the closest zone. I entered this code in the arena the first Saturday, and then I slogged away until Monday. This movement towards the closest zone remained for the first round of the game.

For the real algorithm, from the start, the goal was to find the best target zones and to send the drones there.

For each zone, one writes in a table all the future turns of the game where there would need to be drones either to take the zone or to protect it, while considering that all drones in the game can come there. One unites all these objectives from all the zones in a single table, which results in this. Attack = take control, defend = protect it

• zone 1 in 2 turns, 1 drone from [0,3] can attack
• zone 1 in 4 turns, 3 drones from [0,1,3,4] can defend
• zone 2 in 3 turns, 2 drones from [2,3] can defend etc.

Then one sorts this table; the sorting criteria were henceforth a major point of fine-tuning for my AI. Initially, they are:

• One puts first the objectives closest in number of turns
• In the case of equality, one puts first those for which fewer drones are needed.

Then one takes the objectives in order. For each objective, one retains the drones that are no longer busy with another preceding objective, or for whom the objective is already that zone, or certainly if their preceding objective is sufficiently close to the new zone to do both (distance between the 2 zones <= delta of the allotted time of the 2 objectives)

If they are numerous enough to realize the objective, one sets the just a sufficient number of drones, otherwise, one releases them and abandons the objective. Finally, one takes each drone and directs it towards its 1st objective. If there is not one, they go towards the barycenter of the zones.

I entered this version in the arena Sunday evening 03/16; it was 250 lines. I don’t remember how I ranked; I think it was among the first 30.

First Killer Optimizations

On this foundation, Monday morning 03/17, I coded 3 optimizations:

• For each objective, one first sorts the possible drones before choosing them in order. One puts first those that already have another closer, compatible objective, in order to leave the others free. Otherwise one takes first the drones farthest from the zone (knowing that they are close enough for the time allotted for the objective). In the end, this criterion will change and be passed on to the nearest drone.
• To decide upon the movement for each drone, one looks to see if one can do better than to direct it towards the 1st objective, for the moment in a crude fashion. One defines the concept of comfortable distance to an objective: if whatever it does, the drone remains ok for this objective for the next turn. For example, a drone at 2 turns distance from the zone in which it must be in 4 turns. If this is the case, the drone doesn’t consider this objective and looks towards the next ones. It will optimize its position in terms of different objectives, all while remaining on course for the first ones (and the first in priority)
• Thus, certain drones are rather quiet and move only towards the barycenter. I, therefore, chose for each drone a supplementary objective, unrealizable as is, towards a neutral or adverse zone. This makes the game much more aggressive and opens possibilities for real future objectives.

This version of Monday, entered into the arena, quickly reaches 8th place then climbs little by little to 1st in a few hours. It remains 1st in the arena until its update 3 days later, and the legend of the domination of Sauron begins.

Precision and Geometry

The following days, I entered nothing into the arena and started with precision work on the distances (I’ll talk about them later) and the movements of drones that have several objectives. It’s thus the moment to do a little geometry and to give myself a tool for debugging and analysis. First of all, paper and pencil:

Despite the editing in GIMP, one sees that the face of the sheet is a score.

I then tried to use gnuplot for the automatic diagrams, but it was hell. So I decided that my AI would write an SVG image for the test situations, to draw the situation, and its choices for movement. After having looked through several python libraries for the SVG, I concluded that it would be simpler to write the image directly in XML.

A testing situation with the case of 2 objectives for a drone

As one can see in the beautiful diagrams, I was looking for the best movement for a drone in the case of 2 objectives (both of them real, or real/secondary). The goal of the drone is to be close enough to the 1st objective to remain within the objective (in 1 turn on the last diagram) while drawing as near as possible to the 2nd. I thus considered 4 points in the plan that I put into the competition:

• A movement of a drone towards an ideal point, which is the intersection of the circle of the 1st zone with as a radius the maximum distance beyond which it must not pull away, and the straight line that ties the 2 zones; in other words the point in zone 1 ok for the 1st objective, and as close as possible to the 2nd zone.
• The 2 intersections of circles formed by the possible movements of the drone and the limit of the zone that remains ok for the 1st objective.
• A simple movement towards the 2nd zone.

From the 4 points, one retains those that are still ok for the 1st objective even after rounded to whole number positions. Of these one takes the one closest to the 2nd zone.

I also improved the sorting of objectives by privileging the attacks over the defense, and by having come first the attacks that concern fewer drones. I tried to give an advantage of 1 turn to drones that want to attack those adversaries that don’t move in the same direction, considering that when it comes to a group of immobile drones those that take the initiative of advancing in a direction in front of the others take a one turn lead, but I abandoned it (it was a regression). Finally I corrected many bugs, especially those tied to distances. I submitted again a version in the arena Thursday morning 03/20. At that moment I was still 1st but the gap had diminished, and several had perceived that they easily beat me at 1 v 1, notably MasterBox with whom I talked on the chat.

The first entering of the arena Thursday morning was a failure because I remained 10th. I again corrected several bugs and entered a version in the arena towards noon, which quickly climbed to 1st.

This version, with these innovations and its 535 lines, was much more mature than the one preceding. The management of whole numbers was acceptable even if it was not exact. The precision of movements for the drones limited the tremblings of the preceding drones, caught by something feverish, like myself who was sick that week. It was hugely successful, and until Sunday night I sometimes had a lead of up to 5 points on the runners-up.

Following Improvements

I continued to improve my AI, without pushing it to the arena.

• With more than 2 objectives, a drone can take into account n objectives if the first n-1’s are comfortable; then it advances as much as it can towards the nth to still remain within the others.

• I again corrected several bugs

• I improved the function that assigns secondary objectives while implementing a Voronoi (like in Tron) for the drones of all the players by relation to the zones and while taking as a supplementary objective that which has the fewest drones from one adversary and which is closest to the drone.

• I instated the possibility of limiting the number of drones per objective, so as to avoid struggling for a zone full of drones while a 3rd thief stuffs himself elsewhere. I looked quite a bit at this parameter during the latest entries into the arena.

• I worked again on the distances following a message on the forum, which was useless because I had misunderstood at the time.

The Fall and the Climb

Getting up Monday morning, Sauron sees that God removed him from his podium. He thus needed to react, and not let the ring be destroyed. I started the final work on the distances for which I had finally understood the issue, and implemented 2 improvements:

• To calculate the expected duration of domination of a zone for each objective, and take it into account in the criterion of sorting these objectives. I tried several things, but the final version is to sort with t = expected-distance (both in number of turns) and to put the largest as 1st, obviously.

• I realized a mode of defense for when I’m winning, to avoid playing the fool. A function calculates the number of final points held by each player if the zones remain theirs until the end. If I have most points, I put myself in defense mode. In defense mode, the defense objectives come before those of attack in the sorting function, and the number of drones per objective is not limited.

After having tested several small adjustments, I pushed the final version around 10:20 on Tuesday. It was 784 lines. My AI climbed directly to 2nd place, remaining 1 point beneath god. In the afternoon, the points fluctuated, the challengers drew closer to the 2 first ranked without worrying us. Sometimes I fell behind god who entered a last version in the afternoon. In the evening, the final entries into the arena from the strong players resulted in me quietly taking 1st place.

After the finish, I talked a little with god. He had made an algorithm very similar but still more precise than mine in several respects. On the other hand, he had not implemented my last two improvements, which I think allowed me to cope until the end. I congratulate him on his work, and I hope that he will write an article.

The Problems of Whole Number Positions

I had to spend at least half of the coding time with the problems linked to the whole numbers of positions of drones, and with the resulting bugs. Indeed, the game server provided with each turn the coordinates of drones in whole numbers. For a long time I believed that these whole numbers represented the position actually held by each drone. I’m just going to detail the solution used in the final version. But I had formerly coded something that paved the way very well for the version of Thursday 03/20, though it was based on false hypotheses.

It took some time before I understood the message on the forum on this subject. I summarize the problem in two words: the server resends each turn the coordinates of drones in integers, but works with real floating point numbers that it keeps from one session to the next.

For example, a drone on 0x0 that moves towards 1000×1000 will have as its real position at the next turn 70.71067×70.71067, but the server will say that it is at 71×71.

If one bases oneself on these whole numbers, the ensuing problems may arise (and do arise):

• The AI thinks that a drone can reach a zone when in fact it will take a turn extra.
• The opposite is also true, the AI can think that a drone is n turns from a zone when it is at n-1 turns.

Here is my final version on the question of positions and distances:

• It calculates the positions of all my drones in real numbers from one session to the next without taking into consideration what the server provides, with the same algorithm as the server.
• For adverse drones, the whole coordinates provided at each turn are used, but 2 verifications are made at the moment of calculation of the distances of the drones from the zones in number of turns:

1. If the drone appears to advance 2 turns at a time towards a zone, it is actually advancing only one
2. If the drone appears not to advance towards the zone in number of turns, but its position corresponds to that which it would have if it had advanced towards this zone, it is the case that it is a turn short of the zone.

Possible Improvements

I see two big possibilities:

• Instead of sorting objectives by criteria, I could have made a real algorithm that truly optimized the number of zones or objectives attained.

• My AI is very poor strategically. I thought to include more global geographic considerations, but I didn’t know how to articulate it with the rest. With more time, one would surely have been brought to optimize the occupied space, to gather together the zones controlled, to lean up against an edge, etc…

Conclusion

• It’s been cool–– thanks to the teams at CodinGame and Parrot
• I won a drone and an awesome headset

• Bravo and thanks to the contestants, especially MasterBox with whom I talked, and of course god.
• We’ll see each other on April 5th for who knows what, but at least to drink a beer I imagine
• The link to the code is below, with all the usage disclaimers.

Links:
Final rankings
My code in Python