Category: Artificial Intelligence

Il y a quelque temps s’achevait le concours: AI Sandbox: CTF(Capture The Flag)

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é :

1. Atteindre le drapeau ennemi en utilisant les routes avec peu de risques.
2. 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)

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 :

1. Grouper plusieurs combattants proche du drapeau ennemi, et quand ils sont tous prêt, attaquer selon une route détournée.
2. 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.

Annexes:

Une partie entre les deux premiers: