Pour continuer la tendance des concours créés par les joueurs (et non par les employés de codingame), on retrouve cette fois ci csj , harshch000 & mcargille à la réalisation.
J’ai implémenté une simulation du jeu, en C++, qui m’a permis de reproduire le comportement du jeu. Avec un algorithme Monte Carlo et quelques heuristiques haut niveau, j’ai pu obtenir un bot qui tenait assez bien la route.
J’ai écrit un post mortem sur le forum de Codingame avec plus de détails sur l’implémentation (méthode d’évaluation, recherche des actions des adversaires etc). C’est en anglais.
Dernier contest de cette année 2017 sur le site Codingame (qui me plait toujours autant).
Cette fois ci, et contrairement aux précédents concours, c’est un concours réalisé par des joueurs (et non par les admins). On retrouve à la création les habituels premiers des concours, à savoir Agade, Magus, pb4 et reCurse (qui est un collègue d’Ubisoft!)
J’ai pu enfin, et pour la première fois, faire une « vraie » AI, à savoir utiliser des techniques plus avancées que des heuristiques simples.
Le jeu étant basé sur les collisions, il était très complexe d’arriver à faire une AI compétente avec du simple if/else.
J’ai implémenté un algorithme génétique en C++, après avoir réimplémenté la logique du jeu en C++. Ainsi, mon IA profitait des 50ms alloués par tour pour tenter une multitude de possibilité en simulant le jeu, et ce sur plusieurs tours. A la fin du temps imparti, la meilleure des solutions trouvées était choisie.
J’ai écrit un post mortem sur le forum de Codingame avec plus de détails sur l’implémentation (méthode d’évaluation, recherche des actions des adversaires etc). C’est en anglais.
J’ai fini 64ème, ce qui est très satisfaisant pour moi, sachant que c’était la première fois que je m’essayais à la simulation + GA, et tout cela en C++
Je n’ai pas réussi à rentrer dans le club des légendes cependant (il y avait 50 participants à réussir à passer devant le bot Gold de référence). Ca sera pour la prochaine fois!
J’ai commencé en C++, bien déterminé à mettre en place un treesearch optimisé (le précédent concours m’ayant pleinement convaincu)
Problème dès les premiers jours: le jeu est assez complexe (beaucoup de paramètres, beaucoup d’actions différentes). Je commence donc à faire de l’heuristique basique en C++.
Linq me manque tellement que je re-switch en c#.
Mon code final est bourré de if else plus où moins hacky (on appelle ca une IA full heuristic pour faire un peu plus pro), mais je parviens à rentrer dans le club très select des Legends, et je termine à la 61eme place.
J’ai pu terminer dans les 50 premiers pour cette première participation, mon AI n’était pas grandiose ni révolutionnaire, mais ça m’a permis de voir le niveau des concurrents.
Une super expérience donc, je compte bien participer aux prochains!
J’ai terminé à la 6ème position (70 participants) pour une durée d’1 mois et demi dessus (enfin, des soirs et weekends), assez intense (surtout avec le taff en parallèle) mais super sympa ! J’ai même pu être interviewé sur les stratégies mises en place (la classe! :D)
Voici un match (un des seuls que j’ai pu sauvé, où mon IA prends cher contre le 3ème de la compétition)
Quel était le but du concours?
Ce concours consistait à développer une Intelligence Artificielle (IA) pour le jeu « Capture the flag » L’implémentation du capture the flag était on ne peut plus simple : récupère le drapeau ennemi et ramène le à la zone de score pour marquer un point. Le bot qui a le plus de points à la fin gagne la partie ! Ce concours était organisé par AiGameDev.com et parrainé par « Guerilla games », développeurs de la série « Killzone » sur Playstation
A savoir:
– Le jeu est en temps réel. Certaines actions sont automatiques (comme tirer : il suffit d’avoir un ennemi dans son champs de vision et à porter de tir)
– Chaque ordre donné à un bot entraine un freeze d’une seconde (d’où une partie de la difficulté : il ne faut pas redonner des ordres sans cesse)
– Sur la carte, vous pouvez voir des petits blocs (blanc/gris). Les combattants ne peuvent pas passer à travers mais ils peuvent voir et tirer par-dessus. Les autres blocs sont trop grands pour voir quoique ce soit
Détails du développement (Fonctionnalités triées par ordre chronologique de dev)
A. Récupération du Drapeau & parcours pour le ramener
Ce sont les 2 premiers rôles que j’ai implémenté :
Atteindre le drapeau ennemi en utilisant les routes avec peu de risques.
Ramener le drapeau en utilisant une route avec peu de risques
Pour faire cela, j’ai utilisé un algorithme A* (astar). La pondération des cases a beaucoup évoluée durant le dev, et a fini par prendre en compte
– Les positions où l’ennemi défend
– Les positions où mes combattants sont morts.
– La proximité du spawn ennemi. (en lien avec la vitesse de respawn (différente selon les parties, et le nombre de combattants total) Lorsqu’un de mes combattants porte le drapeau, un autre va sur l’endroit de spawn du drapeau ennemi dans le but de maximiser les points marqués.
B. Défendre (camper) des endroits
Ensuite j’ai voulu avoir des protecteurs de drapeau.
Pour cela, j’ai implémenté un algorithme permettant de calculer la visibilité de chaque cellule sur la carte (pour que mes combattants puissent se cacher au maximum).
L’équipe d’admin AIGameDev nous ayant donné quelques indices très utiles pour réaliser ce type d’algo.
J’ai utilisé la méthode du “ray casting” pour obtenir ce que je voulais. Voilà un exemple de carte de visibilité calculé au début de chaque match (300ms~~ pour générer cela)
Map de visibilité
Au final j’ai utilisé cette fonctionnalité de recherche de points de campe assez souvent pour:
– Défendre la zone où mon drapeau apparait
– Défendre la zone de score de l’ennemi.
– Défendre mon drapeau s’il a été pris et relâché par un ennemi.
– Attaquer les points où mes ennemies pourraient se trouver pour protéger leur drapeau.
Cette fonctionnalité donne parfois de mauvaises positions (trop proche d’un bloc adjacent et empêchant mon combattant de voir réellement la zone couverte)
J’ai fait des modifications à la toute fin pour corriger ce bug mais je n’ai pas eu le temps de tester cela correctement (et j’ai bien l’impression que le bug subsiste)
J’aurai pu faire mieux aussi dans le sens où je ne prends pas en compte le chemin que les combattants ennemis prennent pour venir.
Donc il arrive (plutôt souvent) que mes défenseurs soient tués par derrière, sans qu’aucune intelligence ennemie ne soit nécessaire. Pour contrer cela, je surveille l’efficacité du point de campe (si 2 défenseurs meurent sans tuer personne, l’endroit sera recalculé)
C. Attaque des combattants ennemis les plus proches
J’avais donc mes combattants qui défendent, celui qui essai de récupérer le flag.
J’ai ensuite décidé d’envoyer tous mes autres combattants à des positions spécifiques (zone de spawn du drapeau ennemi, zone de score…) jusqu’à temps de voir des combattants ennemis.
Tout ennemi est traqué en suivant la consigne suivante : « Pas plus de 2 de mes combattants affectés par combattant ennemi»
D. Attaque de la base ennemie
Après un moment, j’ai vu que mon IA ne pouvait pas gagner contre une défense descente, donc j’ai implémenté 2 nouvelles fonctionnalités pour y parvenir :
Grouper plusieurs combattants proche du drapeau ennemi, et quand ils sont tous prêt, attaquer selon une route détournée.
Certains de mes combattants sont désignés pour tuer les campeurs. Ils attaquent leurs ennemis via l’algo AStar en prenant en considération la zone de vision et la portée des campeurs
E. Interception de l’ennemi porteur de drapeau
J’ai remarqué que nous avions, via l’API, la position de notre drapeau à tout moment (que nous voyons notre drapeau ou non) J’ai donc implémenté une fonctionnalité permettant à mes combattants d’intercepter l’ennemi porteur de drapeau.
Seuls mes combattants ayant un job « peu important » (à savoir attaque de zone où d’ennemi) sont concernés.
F. Etat “holding” d’un bot
A la fin, je me suis concentré sur une particularité de ce concours, l’état “holding” pour un combattant donné.
Cet état se produit lorsque plusieurs combattants se rencontrent alors qu’ils sont à une distance supérieur à leur portée de tir, ils se regardent sans bouger et nécessite un développement particulier.
Jusqu’aux derniers jours avant la fin du concours, j’ai eu des parties où ni moi ni l’adversaire ne savait gérer cette holding state, donnant de belles parties où tout s’arrête pendant quelques secondes jusqu’au déblocage par un évènement extérieur (un autre combattant qui passe par là). Parfois la partie freezait ainsi jusqu’à la fin.
Désormais, lorsqu’un de mes combattants est dans cet état, il obtient l’ordre d’attaquer l’ennemi qui le bloque, en prenant en compte la portée de tir de cet ennemi.
Le nombre de combattants alloué à chaque tâche est défini à l’initialisation, suivant le nombre de combattants total. J’aurai pu améliorer le niveau global de mon IA en jouant un peu plus sur ces chiffres.
G. Tests and optimisations
Dans le but de tester mes fonctionnalités, j’ai fait quelques fonctions de debug afin d’être sur que toutes les valeurs sont comme je les attends.
Evidemment un fichier de log (vu qu’il était quasiment impossible de debugger avec des breakpoints avec l’architecture du jeu) mais aussi des bitmaps des cartes (extrêmement utiles pour vérifier la carte de poids lié au pathfinding, aux positions de camp et aussi les zone de tir des ennemis suivant leurs états.
Comme pour chaque concours d’IA, je pense qu’il est extrêmement important d’avoir un plan de test. De cette manière il est facile de savoir si le niveau global de l’IA augmente avec les nouvelles fonctionnalités implémentées et s’il n’y a pas de régression.
Pour cela, j’ai créé une liste de .cmd qui lançait les parties avec des configurations spécifiques et écrivant les résultats des matches dans un fichier. A la fin (après import/groupement des données dans Excel) J’avais ce genre d’infos:
Très utile pour savoir sur quelles cartes mon IA est faible. (en l’occurence la map01 ou encore la map22)
H. Conclusion: Je pense que j’aurai pu faire mieux avec plus de temps (comme tous les participants en fait :D). Je suis entré dans la compétition à la fin de la phase 2.
Les participants et les admins ont été très sympa, j’ai eu beaucoup de plaisir à monter dans le classement jusqu’à affronter les meilleurs.
