Tech Blog Menu

Coveo Blitz, où il faut développer à la vitesse de l'éclair

By Marie Beaulieu —

En janvier dernier avait lieu la 14ᵉ édition de Coveo Blitz, notre compétition annuelle de programmation pour étudiants. Ceux qui sont familiers avec l’évènement reconnaîtront la formule des dernières années : on y présente un jeu de notre cru, puis les participants disposent de 10 heures pour programmer un bot qui saura y jouer et triompher dans des matchs de 2 ou 4 équipes.

Cette année, notre défi revêt le thème de l’espace : chaque équipe est aux commandes de l’équipage d’un vaisseau qui doit affronter d’autres équipes afin d’être la dernière survivante. Nos concepteurs ont concocté un jeu qui était à mon sens l’un des plus sophistiqués, mais aussi l’un des plus complexes des dernières éditions : il y avait une grande variété d’actions possibles, et donc de stratégies à explorer, sans compter certains défis techniques au niveau de l’implémentation. J’aimerais dès lors explorer certaines des stratégies employées lors de la dernière compétition, mais plus important, comment en tant que joueur, on peut s’attaquer à ce genre de défi.

À noter que j’ai moi-même expérimenté le jeu dans un cadre assez différent que celui du jour de la compétition : afin de préparer le tournoi, nous sommes invités à jouer le rôle de bêta-testeur pour l’évènement et à concevoir un bot en solo histoire de non seulement trouver et réparer le plus de bogues possibles, mais aussi fournir un répertoire bien garni d’adversaires de pratique lors de la compétition. Je me suis par ailleurs entretenue avec Leebly, l’équipe étudiante qui a remporté la compétition, ainsi que SG1, une équipe vétérante qui participe à la phase de bêta-test chaque année.

L’inévitable lecture des règles du jeu

Sans surprise, avant de pouvoir parler de stratégie pour un jeu, il faut se familiariser avec les règles. C’est sans aucun doute la première chose que l’on devrait faire lorsque l’on aborde le défi. Je vous épargne toutefois la lecture des règles officielles, je vais ici tenter d’en résumer les grandes lignes.

Un match à quatre équipes

Chaque équipe commande un vaisseau spatial : le dernier vaisseau survivant est le vainqueur. Les vaisseaux ont bien sûr un nombre de points de vie, qui ne peuvent être régénérés d’aucune façon. Lorsque le vaisseau n’a plus de point de vie, il est éliminé.

Un vaisseau qui se repositionne pour viser un ennemi à sa gauche

À chaque tour de jeu, dit tick, les bots de chacune des équipes doivent soumettre la liste d’actions qu’ils veulent effectuer ; si le programme cesse de répondre, aucune action n’est exécutée. On ne peut pas contrôler le vaisseau à proprement parler, mais plutôt diriger chacun des quatre membres de son équipage de sorte qu’ils opèrent les différentes stations dispersées à travers celui-ci. Les actions que notre bot peut émettre consistent donc à ordonner à un membre d’équipage de se déplacer vers une position précise, ou alors, s’il se trouve sur une station, de l’opérer. Les amateurs de jeux vidéo ne manqueront pas d’y voir des ressemblances avec quelques-unes des inspirations de nos concepteurs, dont FTL: Faster Than Light, Lovers in a Dangerous Spacetime, Space Rogue et Tarsis.

Les matchs sont joués avec des vaisseaux distincts dont les stations et leur disposition varient grandement. Il y a cependant toujours les mêmes quatre types de stations à bord du vaisseau : stations d’armes, stations de contrôle, stations de bouclier et stations de radar.

Les stations d’armes se déclinent en cinq types de tourelles qui ont leurs propres spécificités. Certaines peuvent être orientées dans n’importe quelle direction, d’autres ont une orientation fixe par rapport au centre du vaisseau. Chaque type a également une vitesse et une force d’attaque distincte, en plus de bonus contre le bouclier ou contre la coque du vaisseau. Elles peuvent toutes être chargées afin de maximiser leur puissance d’attaque.

La position du vaisseau est fixe dans l’espace. Or, on peut le faire pivoter sur lui-même à partir d’une station de contrôle, dite helm. Cette station est d’autant plus importante, car c’est la seule façon de repositionner les tourelles fixes du vaisseau pour qu’elles aient les vaisseaux adverses dans leur ligne de mire.

Pour ce qui est de la défense, le vaisseau a un bouclier qui se régénère automatiquement chaque tour. Cependant, une fois le bouclier épuisé, il cessera de se régénérer, et c’est la vie du vaisseau qui est désormais en jeu. Les stations de bouclier permettent de réparer le bouclier ou d’accélérer sa vitesse de régénération lorsqu’il est en fonction.

À noter que les attaques des autres joueurs ne sont pas les seules menaces : le combat se déroule au milieu d’un champ d’astéroïdes où sont projetés les débris des autres vaisseaux et du vôtre. Alors que les spectateurs peuvent faire état de tous les projectiles dangereux en un coup d’œil, notre bot, lui, n’a qu’une perception incomplète de son environnement. C’est là qu’entre en jeu le dernier type de station disponible : les stations de radar permettent de gagner de l’information détaillée sur les adversaires et d’augmenter la distance de détection des débris sur le champ de bataille.

Premières itérations… Et premiers bogues

Lorsqu’on pense stratégie dans ce type de jeu, la balance entre l’attaque et la défense entre rapidement en ligne de compte. SG1, par exemple, m’ont dit avoir de manière générale avoir favorisé une stratégie plus défensive, soit de manier le bouclier, de détruire les astéroïdes et autres débris, etc. Ils m’ont d’ailleurs rappelé le principe de l’ours :

Pas besoin de courir plus vite que l’ours pour s’enfuir. Il suffit de courir plus vite que l’autre à côté de toi.

Ainsi, leur stratégie va de manière générale consister à favoriser leur survie, et à ensuite catalyser la défaite d’une autre équipe, en priorisant celle qui s’en approche le plus déjà. Personnellement, je suis moins sage et plus sauvage à ma façon : j’ai bêtement commencé avec l’attaque directe par simplicité et un peu par plaisir. En ce sens, puisqu’il faut bien commencer quelque part, je décide d’envoyer tous les membres d’équipage vers les tourelles d’attaque et de tenter d’attaquer immédiatement, sans me soucier de leur orientation ou d’autres critères de performance.

En compétition, Leebly, une équipe de trois personnes, a pu paralléliser leur travail sur l’attaque et la défense. D’ailleurs, leur première itération en termes d’attaque était très similaire à la mienne, ou du moins tout aussi rudimentaire. Fait plus cocasse, avec notre technique naïve, Leebly et moi avons introduit le même bogue, à savoir que nous avions négligé d’envoyer les membres d’équipage à des tourelles distinctes. Coincidence ? Peut-être pas tant que ça. Permettez-moi une nouvelle tournure d’un adage célèbre :

Une personne qui n’a jamais créé de bogues n’a jamais tenté de programmer.

Vous allez faire des erreurs, c’est inévitable. Heureusement, lorsque l’ensemble des changements introduits est petit, comme c’était le cas pour notre stratégie d’attaque élémentaire, c’est souvent plus facile à détecter et à réparer.

Un autre exemple particulièrement coûteux est apparu pendant que j’ai implémenté la priorisation des tourelles d’attaque : suite à ce changement, il arrivait fréquemment qu’une paire de mes membres d’équipage demeurait en perpétuel mouvement, prisonniers de quelque chose qui s’apparentait à la très embarrassante danse du « toi d’abord - non toi vas-y », et qui n’était certainement pas acceptable dans mon plan de domination intergalactique. Le problème devenait très apparent lorsque je visionnais des matchs. Si je ne m’en étais pas rendue compte rapidement, j’aurais eu bien du mal à identifier la source de mon problème.

Peu importe votre stratégie, une implémentation fautive ne la mettra probablement pas en valeur. On ne peut pas complètement éviter les bogues. La clé est plutôt de s’outiller pour détecter et comprendre les problèmes rapidement. À défaut de tests automatisés, le mode local de Blitz est très pratique justement pour expérimenter et valider nos itérations, sans avoir à se commettre. Il nous permet de lancer des parties de notre poste et de les visionner. Et si vous oubliez de vous valider en mode local, il y a toujours les matchs contre les autres équipes.

Quand « regarder le match » est une vraie question de priorité

L’espace est un milieu hostile, et je ne l’ai que trop bien réalisé à Blitz : alors que je visionnais des matchs contre les autres équipes, je me suis rendue compte qu’il m’arrivait d’être éliminée simplement parce qu’un gros astéroïde venait de me frapper et d’enlever la quasi-totalité de mon bouclier d’un coup. J’avais déjà une stratégie élémentaire d’attaque et de défense contre les autres joueurs, mais si moindrement la partie s’allongeait, je n’arrivais pas à survivre la rafale incessante d’astéroïdes alors que les autres si, ce qui n’était pas le cas en début de journée. J’ai opté pour une solution simple : un membre d’équipage dédié à la destruction des gros et moyens débris via une tourelle pivotable, et donc capable de viser rapidement n’importe quelle cible. J’ai raffiné la méthode avec le temps : entre autres, j’ai exclu les astéroïdes dont la trajectoire n’allait pas intersecter mon bouclier et j’ai utilisé le radar pour anticiper leur venue plus tôt.

Évidemment, regarder les parties est aussi un bon moment pour espionner la compétition. Pendant longtemps, j’ai favorisé les tourelles pivotables, car elles étaient plus simples à opérer et ne nécessitaient pas une rotation du vaisseau. Néanmoins, après quelques améliorations faites à ma défense, je me rends compte encore une fois que je plafonne dans le classement. Comme la plupart des vaisseaux ont moins de quatre tourelles pivotables accessibles, il arrive de plus en plus fréquemment qu’un des membres de mon équipage se tourne les pouces. Je m’attelle donc à utiliser les tourelles d’attaque fixes : mais laquelle choisir ? Pour ce faire, je me suis basée sur mes observations des matchs joués : certains de mes adversaires avaient déjà implémenté l’utilisation de ces tourelles. J’ai remarqué que les stations de tir à haute fréquence avaient tendance à bien complémenter la défense en général, car la cadence ultrarapide de projectiles agissait comme un écran sur le champ de bataille. J’ai ajouté ce qu’il fallait pour opérer les tourelles fixes qui étaient en direction de l’ennemi, en les priorisant selon leur type, avec celles qui me semblaient les plus rapides et versatiles d’abord. Rapidement ensuite viendra la réorientation du vaisseau afin d’orienter une tourelle de mon type préféré dans la bonne direction. J’avais de vagues idées pour mieux prioriser le type de tourelles à utiliser en fonction de leur bonus d’attaque par exemple, mais je n’ai jamais eu le temps de m’y pencher sérieusement.

Une autre idée que j’ai implémentée est de charger au maximum avant de tirer. Or, c’était difficile d’évaluer à quel point c’était avantageux ou pas dans certaines situations. J’ai donc fait une petite expérience : en local, j’ai opposé le bot avec seulement ce changement contre le bot de ma version précédente. Il s’est avéré que la nouvelle version gagnait constamment contre la précédente. J’ai dès lors adopté le changement et pu constater que je continuais de monter dans le classement. À partir de ce moment, j’ai souvent opposé mon propre bot à sa version antérieure pour valider mes itérations.

Il y a plusieurs possibilités à Blitz, et c’est parfois difficile de bien balancer et d’implémenter certaines stratégies. Lorsque j’ai parlé à SG1 de l’idée de charger les tourelles, ils m’ont mentionné avoir complètement écarté cette idée, car lorsqu’ils l’ont essayée, ils ont observé qu’ils étaient moins performants. Comme quoi, il y a plusieurs subtilités qui font qu’un élément de stratégie peut bien marcher pour une équipe et pas une autre : de là l’importance de s’autoévaluer constamment, puis de faire des choix et de savoir prioriser en conséquence.

Un Blitz d’itérations

Dans l’effervescence de la compétition, il est tentant de se plonger dans le code sans interruption, d’ajouter le plus de sophistication possible et de maximiser notre temps d’implémentation. Or, notre temps est fini, et notre créativité potentiellement infinie : on ne peut pas raisonnablement penser qu’on aura le temps d’implémenter toutes nos idées, alors il faut choisir.

De trouver le plus de valeur ajoutée pour le moins d’effort possible, c’est le secret.

Nicolas Legros, Équipe Leebly

Les membres de l’équipe Leebly ont beaucoup renchéri sur la valeur de travailler en courtes itérations : c’est une leçon qu’ils ont apprise de leur expérience passée avec Blitz. Lors des éditions précédentes, ils auraient probablement commencé par essayer d’implémenter une stratégie d’attaque où l’on envoie les membres sur la « meilleure » tourelle d’attaque pour attaquer les ennemis. Cette année, ils ont commencé par implémenter une stratégie bien plus rudimentaire, soit d’envoyer les membres sur n’importe quelle tour libre disponible, et ils ont peu à peu raffiné leur implémentation, réparé leurs bogues et expérimenté en regardant des parties contre les autres équipes. Ce n’est que plus tard dans la journée, alors qu’ils étaient déjà en bonne position dans le classement, qu’ils se sont attaqués à la question du choix de tourelle optimale. Or, leurs essais n’ont pas donné de meilleurs résultats que leur stratégie plus naïve sans priorisation et ils ont donc laissé tomber cette avenue. Ainsi, lors de la finale, c’est leur stratégie plus simple qui leur a permis de gagner. Les plus petites itérations leur a permis d’en arriver à une solution fonctionnelle, de gagner de l’information sur leur performance, et même d’incidemment trouver une meilleure solution à moins effort.

Lors de la finale, Leebly, malgré une tourelle qui tire dans le vide, gruge petit à petit les points de vie de son adversaire, Les_Avaturiers, et sortira vainqueur de cette manche

Selon mon expérience, plus les itérations sont simples et courtes, plus les bogues sont faciles à trouver, et plus on peut avoir une rétroaction rapide. Un autre exemple de simplicité mentionné par Leebly est leur choix de stratégie défensive de dernier recours. Ils m’ont expliqué que lorsque leur niveau de vie était très bas, ils envoyaient tous les membres d’équipage manier une station de bouclier, leur raisonnement étant qu’en étant en situation critique, les débris de l’espace auraient raison d’eux, mais peut-être aussi de leurs adversaires. Le seuil utilisé pour déterminer le déclencheur de cette solution d’urgence lui a toutefois été déterminé avec beaucoup d’essais-erreurs, c’est-à-dire en changeant la valeur, en regardant quelques matchs, et en réajustant au besoin. Bref, il n’y a pas de trop petites ou trop simples itérations à Blitz!

Même si les stratégies de SG1 et de moi-même différaient en plusieurs points, nous avons, nous aussi, procédé par itération plus ou moins importante. Lors des phases de bêta-test, je soumettais fréquemment mes changements au serveur afin de me mesurer aux autres équipes, dont SG1 en particulier, qui menait le classement constamment. Ils m’ont dit qu’ils en faisaient de même pour valider et développer leurs stratégies. Ce sont dans les deux cas les nombreuses et répétées confrontations entre nous qui nous ont mutuellement aidées à avancer efficacement. En réalité, je ne pense pas pouvoir prétendre avoir résolu la clé d’une grande stratégie pour cette édition de Blitz : j’ai l’impression que c’est plutôt l’attention à de nombreux petits éléments au fil du temps qui a été fructueuse.

La stratégie finale

Lorsque j’ai commencé cet article, j’avais pour sujet « les stratégies de Coveo Blitz 2024 ». Je pourrais donc conclure en vous parlant des diverses actions que j’ai choisi de prioriser et d’implémenter, soit des scans de radar périodiques, une utilisation du bouclier en cas de dommage critique, une tourelle dédiée à éliminer les plus gros débris et une offensive constante. Or, je crois qu’il serait un peu caduc de s’en tenir à la stratégie que j’ai employée. En effet, tout cela vaut bien pour le jeu de cette année, mais qu’en est-il pour les prochaines éditions ? Je préfère de loin la réponse spontanée qu’a fournie Leebly lorsqu’on leur a demandé, suite à leur victoire, qu’elle a été leur stratégie. Sans hésiter, ils ont répondu : « On a été itératifs. »

Ainsi, pour mieux résumer la stratégie que j’essaie de mettre en œuvre chaque année, ce serait probablement de suivre ces principes :

  • Prendre le temps de comprendre le problème qui nous est présenté
  • Implémenter de petits incréments simples
  • Tester les changements, comprendre et analyser les bogues
  • Aller chercher le plus de rétroaction possible, le plus souvent possible afin de décider de la prochaine étape

C’est là la simple description d’une méthode itérative : car oui, ici, ça vaut autant pour Blitz que pour n’importe quelle tâche qu’on rencontre en développement logiciel. Parce que oui, cela vaut pour tout : devant toute situation, vous êtes doté d’une créativité infinie, mais votre temps est limité, sachez en faire bon usage !

Merci à Sébastien Caron, à Nicolas Legros et à Sébastien Legros de l’équipe Leebly de s’être entretenus avec moi. Merci également à Andy Emond et à Jesse Emond de m’avoir parlé de leurs stratégies et d’avoir révisé cet article. Enfin, merci à Frédéric Boutin et à Kevin Sampson d’avoir révisé cet article.

Written by Marie Beaulieu
Développeuse Logiciel