Game of Drones : la stratégie de Loujo (1ère place)

STAY CONNECTED, FOLLOW CODINGAME NOW

Game of Drones a été une belle aventure... Riche en rebondissements, en coude à coude, en bonne surprises et aussi parfois en déceptions. Mais quelle aventure !
Loujo, qui termine brillamment premier au classement en ayant trusté le haut du podium pendant plusieurs jours avec panache, revient sur sa stratégie dans un très bel article qu'il publie sur son blog.

[...]

Explication chronologique de l'algorithme
Le jeu a débuté vendredi 14 mars et a fini mardi 25 mars.

Ma première version a été que chaque drone va vers la zone la plus proche. J'ai mis ce code dans l'arène le premier samedi, et j'ai bossé à la suite jusqu'au lundi. Ce mouvement vers lazone la plus proche est restée depuis pour le premier tour de jeu.

Pour le vrai algo, dès le départ, le but a été de trouver les meilleurs zones cibles et d'y répartir les drones. Voici comment je procède :
Pour chaque zone, on inscrit dans un tableau tous les tours de jeu futurs où il y aurait besoin de mettre des drones soit pour prendre la zone, soit pour la garder, en considérant que tous les drones du jeu peuvent y venir. On réunit tous ces objectifs de toutes les zones dans un seul tableau ; ca donne ça. Attaque = prendre le contrôle, défense = le garder
- zone 1 dans 2 tours 1 drone parmi [0,3] peut attaquer
- zone 1 dans 4 tours 3 drones parmi [0,1,3,4] peuvent défendre
- zone 2 dans 3 tours 2 drones parmi [2,3] peuvent défendre
etc..

Ensuite on trie ce tableau ; les critères de ce tri ont été un gros point de réglage de mon AI par la suite. Dans un premier temps, ils sont :
· On met devant les objectifs les plus proches en nomble de tours
· En cas d'égalité, on met devant ceux pour lesquels il y a besoin du moins de drones.

Puis on prend les objectifs dans l'ordre. Pour chaque objectif on retient les drones qui ne sont pas encore occupés par un autre objectif précédent, ou dont l'objectif est déjà cette zone, ou bien si leur précédent objectif est suffisamment proche de la nouvelle zone pour pouvoir faire les 2 (distance entre les 2 zones <= delta des délais des 2 objectifs)
S'ils sont assez nombreux pour réaliser l'objectif, on fixe le nombre juste suffisant de drones, sinon on les libère et on abandonne cet objectif.
Enfin on prend chaque drone et on le dirige vers son 1er objectif. S'il n'en a pas, ils va vers le barycentre des zones.

J'ai mis cette version dans l'arène dimanche 16/03 au soir, elle faisait 250 lignes. Je ne me souviens plus combien j'étais classé, dans les 30 premiers je crois. 


Premières optimisations de killer:

Lire la suite sur le blog de Loujo >>

3 commentaires :