Game of Drones : la stratégie de Gangrene (3e place)

STAY CONNECTED, FOLLOW CODINGAME NOW

Troisième volet du Top 3 de Game of Drones, Gangrene, 3e au classement, nous détaille sa stratégie et les étapes de son raisonnement. Merci pour ce débrief !

"Le fait d'avoir intégré irc à l'ide a permis une grande communication parmi les participants.
On a ainsi pu entendre pas mal d'idées de stratégies, notamment sur du brute force ou de l'analyse des coups ennemis.

Pour ma part, mon raisonnement a été le suivant :


Ces deux stratégies avaient leur place dans le tron battle car chaque joueur n'avait que 4 possibilités d'actions maximum.
En revanche, pour les drones, le nombre de choix était très élevé et difficile à déterminer.
Le drone ennemi se dirige le plus souvent vers une zone, mais parfois vers une destination calculée (souvent le barycentre d'un ensemble de zones).
De plus, un drone peut très facilement changer de direction d'un tour sur l'autre.

De ce fait, mon calcul s'est basé entièrement sur les distances.

Dans un premier temps je me suis fait un tableau contenant le nombre de tours nécessaires pour chacun de mes drones pour rejoindre chaque zone.
A côté, dans un autre tableau, je calcule, pour chaque zone, en combien de tours elle peut recevoir 1, 2, ..., d drones appartenant à un même ennemi (sans se soucier de quel ennemi il s'agit).

S'ensuit un calcul dont la complexité est de traiter en parallèle les tours nécessaires pour l'attaque ou la défense.
Je calcule quelle zone je peux prendre le plus rapidement, ou quelle zone sera prise le plus rapidement par un ennemi si je ne la défends pas.
Une fois mes drones affectés à l'attaque, la cible est considérée comme une zone m'appartenant, et donc à défendre pour les drones plus éloignés.
De la même façon, une zone que je ne peux pas défendre au-delà de "t" tours devient une zone ennemie pour mes drones restants.

Dès que je ne peux plus prendre ou défendre de zone, les drones restants ("bons à rien") sont affectés selon une décision arbitraire.
Celle-ci a été au début de choisir le barycentre de toutes les zones, afin d'être rapidement disponible.
Par la suite, j'ai préféré les envoyer sur une zone ennemie pour 'clouer' des drones adverses.
Au final je suis revenu sur les barycentres pour mes dernières modifications, que j'expliquerai plus loin.

Je me suis rapidement rendu compte que les matchs à 3 ou 4 joueurs étaient un défi de taille auquel mes petits drones étaient mal préparés.
Il est en effet aisé de se faire prendre en sandwich et de mourir étouffé entre 2 ou 3 équipes.
J'ai donc, uniquement pour les matchs à 3 ou 4 joueurs, défini une des deux zones des extrémités comme zone prioritaire, à posséder à tout prix.
Mes drones se dirigeaient donc sur cette cible dès qu'elle était perdue, et évitaient donc une position centrale étouffante.

Ces décisions constituent la stratégie de base.

Ensuite, quelques détails étaient à prendre en compte pour affiner les calculs. J'en note trois :

- Le premier concerne les calculs de distances. Beaucoup s'y sont intéressés, et l'équipe de CodinGame nous a expliqué que les coordonnées des drones étaient stockées en nombre flottants en interne.
De ce fait, il est intéressant de stocker nous aussi les données de nos drones, et de recalculer leur position exacte en fonction du point qu'on leur demande de viser.
Pour les drones ennemis, il est dangereux d'essayer de deviner leur cible. Je n'utilise donc pas leurs coordonnées du tour précédent, mais me contente des nouvelles en ajoutant 0.5 aux distances sur les axes x et y.

- Le second détail est la position qu'un drone prend dans la zone qu'il occupe. Une zone a un rayon de 100, ce qui correspond à 1 tour perdu pour sortir si le drone est au centre ou jusqu'à 2 tours s'il est mal placé.
un drone qui est dans une zone se dirigera donc vers son point le plus proche de mon barycentre

- Enfin, parfois un drone doit défendre une zone d'un drone ennemi distant d'un seul tour de plus que lui.
Cela signifie que mon drone ne doit pas s'éloigner de la zone au cas où l'autre avancerait, mais il peut toujours se déplacer dans le même rayon.

Je l'envoie donc sur la zone ennemie la plus proche, tout en restant dans le rayon imposé.

Cette stratégie m'a offert un bon positionnement, et j'aurais terminé entre la 8e et la 15e place avec uniquement cela.
Et puis le dernier jour, en observant mes déplacements et ceux des premiers du classement, j'ai compris que mes drones étaient trop mobiles.
Deux drones qui partent prendre une zone éloignée affaiblissent ma défense considérablement, et ce malgré ma zone prioritaire.

J'ai donc fait un pari risqué, celui de limiter complètement mon champ d'action.
Désormais je prenais toujours une zone à une extrémité (zone A), mais également ses deux plus proches voisines (zones B et C), et je supprimais toutes les autres zones de ma liste.
Mes drones ne savaient plus rien d'elles et se concentraient du coup sur les 3 zones sélectionnées avec une énergie redoublée.
C'est aussi à ce moment que j'ai décidé de ré-utiliser un barycentre pour les drones "bons à rien" :
Mes trois zones devenant beaucoup plus simples à défendre, j'affectai mes drones inutilisés à la position équidistante des zones B et C, la zone A étant en théorie bien cachée en arrière.

Cette ultime modification m'a offert la 3e place, et m'a été fortement inspirée par l'IA de god, qui se limitait à trois ou quatre zones voisines.
Le fait d'imposer de quelles zones il s'agissait m'a permis, en plus, d'éviter l'effet sandwich.
Dans de nombreux cas, les assaillants ont été repoussés vers les zones restantes où ils se sont partagé les restes.

Le risque majeur bien entendu restait que quelqu'un d'autre suive la même stratégie que moi (qui était d'ailleurs facile à comprendre en regardant mes matchs).
J'en profite d'ailleurs pour faire un clin d'oeil à MasterBOX, dont l'IA m'a fait très peur en ciblant les mêmes zones que moi à seulement 6 heures de la fin de l'épreuve.

Je suppose qu'il l'a remodifiée entre temps, car sans ça nous aurions tous deux perdu chaque match joué ensemble, ce qui nous aurait probablement fait chuter du classement."

Gangrene

3 commentaires :

  1. Merci Gangrene, de nous dévoiler si impudiquement ta belle stratégie. Il y a beaucoup à en apprendre. Je pense qu'au delà du talent de traduire en langage (C++, PHP, Python ou autre...), il fallait une stratégie de béton, qui comme tu nous l'a montré, a tiré sa quintessence de l'observation. Peut-être nous croiserons nous à Paris... Bon code à toi.
    McKelian

    RépondreSupprimer
  2. Bien joué Gangrène !
    En fait j'avais cette stratégie dès le dimanche soir, et mon envoi du mardi n'a été qu'un retour arrière sur des réglages moins bons (changement potentiel de zone en cours de match si ces dernières étaient trop attaqué, comme c'était le cas lors de nos matches ou avec God justement).
    Ma position défensive devait néanmoins être moins bonne, je me plaçait entre 2 zones et non 3, et je tentais également d'attaquer 1 ou 2 autres zones suivant le nb de drones.
    A par ça nous étions sur une stratégie très proche, d'où la proximité à un moment (mais je pense que ma volonté d'attaquer d'autres zones m'a peut être perdu ?)

    J'avais la volonté d'implémenter également une stratégie de "ruche" ou tous les drones attaquaient d'abord la zone prioritaire pour ensuite attaquer par moité les 2 autres, pour enfin se positionner en défense si possible, je suis convaincu que ça aurait été payant, mais pas assez de temps !

    En tout cas ce fut un beau match !

    RépondreSupprimer
  3. Merci pour vos commentaires.

    McKelian, désolé mais je n'ai pas pu me rendre à Paris, ça aurait été avec plaisir.

    MasterBox bien joué également. En fait la zone prioritaire a aussi un autre gros inconvénient, c'est que si tu la défends totalement, tu te retrouves facilement à avorter des attaques et à finir enfermé dans ta zone.

    En tout cas ça aura été une épreuve intense et épuisante. Les places se sont jouées à peu de choses. J'ai hâte de vous affronter de nouveau.

    RépondreSupprimer