Game of Drones: la stratégie de god (2e place)

STAY CONNECTED, FOLLOW CODINGAME NOW

Il est dit que seuls les Dieux sont clairvoyants mais god, 2e au classement de Game of Drones, avait vu juste... Sa stratégie s'avère payante puisqu'il arrive à la 2e marche du podium à l'issue des 10 jours de challenge. Bravo à lui et merci pour ce débrief détaillé !
--

"Au début, j'ai commencé par résoudre le problème pour une zone. Pour chacun des joueurs, je trie leurs drones en fonction de leur distance en nombre de tours à cette zone. Ainsi, pour chaque joueur, j'ai la liste du nombre de tours avant qu'il puisse arriver avec 1,2,3,4,... drones sur la zone.

 
J'en déduis la liste du nombre de tours avant qu'un ennemi puisse arriver avec 1,2,3,4,... drones sur la zone, ainsi que mes propres distances. Si la zone m'appartient, j'ajoute des objectifs de défense pour arriver en même temps que mes ennemis sur la zone avec le bon nombre de drones, sinon pour arriver avec un drone de plus. Par exemple, j'obtiens les objectifs "pouvoir avoir 1 drone sur la zone dans 2 tours", "pouvoir avoir 3 drones sur la zone dans 5 tours". Si la zone ne peut être défendue avec 3 drones par exemple, je considérerai qu'elle n'est plus à moi pour les objectifs avec plus de 3 drones. De même, si je sais que je vais prendre la zone avec 2 drones dans 3 tours, je considérerai ensuite des objectifs de défense pour plus de drones.

J'attribue des scores aux objectifs en fonction des points minimaux qu'ils me rapportent divisés par le nombre de tours avant d'avoir récolté ces points. De plus les objectifs de défense ont un score de base de 42, ceux d'attaque sûrs de 40, et ceux d'attaque incertains de 10 (ces objectifs sont ajoutés lorsqu'une action adverse est nécessaire pour prendre la zone mais que l'adversaire en question n'était pas en train de faire cette action au tour précédent). Ce score est défini de manière un peu grossière et n'est pas le paramètre le plus critique.

Jusque là, tout coule de source, j'applique bêtement les règles du jeu : prendre des zones quand je peux, défendre les miennes, le score est calculé en nombre de points gagnés par tour. Mais, je suis resté très souple sur la définition des objectifs, ce qui va me permettre ensuite de maximiser le nombre d'objectifs atteints. Je me contente de préserver mes possibilités, je ne dis pas "je vais foncer vers cette zone avec 3 drones dès maintenant !" mais bien "je veux pouvoir y avoir 3 drones dans 5 tours", donc seuls les drones à 5 ou 6 tours de la zone vont être contrains, et rien ne les empêche de valider d'autres objectifs en même temps. De plus, je prévois les prises de zones, je peux donc reprendre très vite une zone perdue ou défendre en avance une zone pas encore capturée.

Je commence donc par calculer les objectifs définis plus tôt, pour chaque zone, et chaque nombre de drones possible entre 1 et max-1 (pas max à cause d'une limitation technique dans mon calcul du score, ce qui étais assez mauvais pour les matchs à 3 drones...). Ces objectifs sont de la forme (N,Z,R)="être à R tours de la zone Z avec N drones". En pratique les drones à R-2 tours ou moins sont acquis et ne sont donc pas pris en compte.

Je cherche ensuite à accomplir les objectifs un à un, par ordre de score, en ajoutant la contrainte correspondante à tous les drones potentiellement utiles pour l'objectif en cours. Une contrainte étant de la forme "être dans un disque de rayon R+1 autour de la zone Z", fusionner plusieurs contraintes requiert le calcul de l'intersection de plusieurs disques (un par contrainte plus celui de rayon 100 autour du drone). Comme j'assigne les contraintes à tous les drones disponibles à chaque fois, j'ai de la marge pour valider les objectifs suivants. Par exemple, si j'ai "1 drone à distance 0 zone 1 parmis les drones 0, 1, 2" puis "2 drones à distance 0 zone 2 parmis les drones 1, 2", je commence par mettre la première contrainte sur les drones 0, 1, 2 puis je vois que je peux prendre les drones 1 et 2 pour le deuxième objectif car le premier a 2 drones de marge. Il faut aussi faire attention que certains objectifs dépendent d'autres. Par exemple, pour valider un objectif de défense (N,Z,R1), je vais d'abord essayer de valider l'objectif de défense (N-1,Z,R2) si présent.

Enfin, dernier détail très important : que faire des drones qui n'ont rien à faire ? C'est le seul point jusqu'ici qui n'a pas de réponse dans les règles du jeu. Au début, j'envoyais ces drones au centre de la carte, mais ils n'y faisaient souvent pas grand chose... Ensuite, j'ai vu que de nombreux matches arrivaient à un état stable où un joueurs contrôlait 3 zones sur le bord de la carte. C'est en effet un bonne position défensive et j'ai donc mis mon point de chute au barycentre de ces 3 zones (à droite ou à gauche de la carte en choisissant le groupe de 3 le plus isolé). Ce simple changement avait provoqué une augmentation de victoires incroyable et au moment où je l'ai implémenté, je faisais peut-être autour de 85% de victoires en match de 4 joueurs contre le top 3 ! Malheureusement, vers la fin du concours, la différence sur ce paramètre était moins marquée.

En matchs à 3 joueurs, j'ai plusieurs fois changé mon point de chute entre le centre de la carte et les 3 zones au bord. Ma dernière version en ligne utilise le centre, et j'aurais peut-être gardé ma première place en gardant les 3 zones au bord. Le choix est difficile et j'aurais soumis les 2 versions pour voir si je m'étais levé plus tôt (j'ai +8h par rapport à la France). Le problème est le suivant : le bord est plus fort en principe car plus stable (moins d'attaquant, qui vienne que d'une direction), mais il ne reste que 2 autres joueurs et si l'un d'eux se retrouve sur les 3 zones que j'ai choisies, le troisième récupère facilement les 3 zones sur l'autre bord et gagne car il est moins attaqué que moi. Ça arrive typiquement lorsqu'un joueur était déjà sur mes 3 zones et s'obstine à y rester. Je me suis pas trop attardé sur ça car j'étais déjà premier et que j'étais fatigué, mais je pense que le centre est tout de même mauvais car je me retrouve entre les 2 autres joueurs, et que j'aurai simplement dû mieux choisir mon bord, et peut-être prendre un barycentre avec plus de poids sur les 2 zones les plus au bord des 3 pour mieux pousser les attaquant vers le centre, car 2 zones sur 6 suffisent si je récupère la 3eme de temps en temps.

En matchs à 2 joueurs, j'ai fait très peu de tests et je me doute que je devais pas être très bon car mon algo n'attaque pas les zones déjà attaquées par un autre joueur, ce qui me handicape dans tous mes matchs au début, et tout particulièrement en 1v1. Je ne pouvais donc me contenter de prendre 2 zones (trop tard) et de tomber dans une position stable. J'ai donc mis ma position de chute au barycentre des zones adverses pour être très agressif. De plus, cette stratégie est supérieure à la défensive car c'est impossible de tenir plus d'une zone de manière sûre si il y a autant d'attaquant que de défenseurs. Donc si un défend ses 2 zones et l'autre attaque, l'attaque prend des zones avant de perdre les siennes et gagne. Ça devient ridicule si le défenseur ne contre-attaque pas d'ailleurs.

Mais c'était toujours insuffisant car parfois, ça m'amenait à abandonner une position déjà acquise, voire même stable, pour essayer de conquérir mon point de chute. J'ai donc rajouté une mise à jour du point de chute à chaque tour pour qu'il devienne le barycentre de mes zones si j'ai 3 zones ou plus (ça marche pour 2, 3, ou 4 joueurs).

Voilà pour conclure, j'avais une très bonne efficacité tactique, et un brin de stratégie dans le réglage du point de chute. J'avais quelques problèmes mineurs comme le début de partie ou mon incapacité d'utiliser tous mes drones pour un même objectif (problématique dans les matchs à 3 drones surtout). Et le côté stratégique reste à développer je pense pour tous les candidats. Par exemple, je ne considère pas le fait que prendre telle zone m'assure de pouvoir prendre ensuite telle autre qui est derrière, ou que attaquer telle zone est fort car les défenseur potentiels ont autre chose à faire, etc".

-----
Langage et environnement

Comme pour presque tout mes programmes, j'ai choisi le C++ car c'est un langage complet et efficace que je maîtrise (c'est sans doute le point le plus important).
Je code sous Debian avec vim. En ce qui concerne le versionement, je me suis contenté de quelques backups manuels.

Petite astuce : Au milieu du concours, j'en ai eu vraiment assez des copier/coller pour tester mes matchs, et j'ai trouvé la commande xclip qui permet d'automatiser le "copier" en l'ajoutant au Makefile par exemple. Ce fût un vrai bonheur :-)

----
Lien vers mon code en C++

god

1 commentaire :

  1. Merci pour cet article, ca permet de mieux se rendre compte ce qu'il y a derrière un score et un comportement des drones. Bravo !

    RépondreSupprimer