URL: https://linuxfr.org/news/geneticinvasion-des-algorithmes-evolutionnaires-pour-un-meilleur-jeu Title: GeneticInvasion : des algorithmes évolutionnaires pour un meilleur jeu Authors: MCMic Date: 2011年09月02日T22:12:04+02:00 License: CC By-SA Tags: algorithme_génétique, tower_defense, intelligence_artificielle, jeux_linux et algorithmique_génétique Score: 45 Je m’en vais vous annoncer ici la sortie de version bêta 0.4 du jeu GeneticInvasion, pour lequel j’ai activement participé au développement. L’idée me trottait dans la tête d’adapter la théorie de Darwin sur l’évolution pour créer un jeu où les ennemis s’adapteraient au comportement du joueur. Les jeux de type _tower defense_ me paraissaient tout adaptés à cela. Aussi je proposais le sujet en tant que projet de fin de semestre à mon école d’ingénieur. J’ai trouvé trois collègues partants pour l’aventure et un tuteur spécialisé dans les algorithmes génétiques. J’ai donc découvert que j’étais très loin d’être le premier à avoir l’idée d’informatiser la théorie de l’évolution, que c’était tout un domaine de recherche informatique et que cela s’appelait les algorithmes évolutionnaires. ---- [Vidéo du jeu](http://mcmic.haxx.es/index.php?page=geneticinvasion) [Site officiel](http://projects.haxx.es/p/genetic-invasion/) [Instructions de compilation](http://projects.haxx.es/p/genetic-invasion/page/Building-the-game/) [Evolving objects](http://eodev.sourceforge.net/) ---- **Comment cela fonctionne‐t‐il ?** L’objectif d’un algorithme évolutionnaire est de trouver une bonne solution à un problème en un temps raisonnable ; il ne trouve pas nécessairement la meilleure solution, et pas nécessairement la même à chaque exécution. Comme dit plus haut, le fonctionnement est basé sur la théorie de l’évolution : * on génère une population de solutions aléatoires ; * on évalue les solutions sur le problème, afin de voir si elles correspondent. En fonction du résultat, on leur donne une note (*« fitness »* dans le jargon) ; * on sélectionne, en fonction du *fitness*, un certain nombre d’individus pour la reproduction ; * on effectue alors les croisements et des mutations aléatoires ; * les solutions filles viennent remplacer leurs parents dans la population, et l’on peut de nouveau procéder à une évaluation ; * on s’arrête quand un critère de fin a été atteint, qui définit à quel point une solution doit être bonne pour que l’on arrête de chercher. Il existe de multiples algorithmes de sélection, de croisement (il ne se font pas tous à deux !) et de mutation. Nous avons donc utilisé une bibliothèque C++ libre gérant les algorithmes évolutionnaires — sérieuse et destinée à la recherche —, afin de développer un jeu de [_tower defense_](http://fr.wikipedia.org/wiki/Tower_defense) (elle s’appelle EO pour _Evolving Objects_). Le problème : - une évaluation = 1 round ; - nombre de solutions (ennemis) dans la population : 20 au maximum. Ce sont des conditions très inhabituelles pour un algorithme évolutionnaire, que l’on utilise habituellement sur une grande population en faisant des tas de générations par seconde. Après avoir infructueusement essayé de faire fonctionner l’algorithme dans ces conditions, nous avons dû renoncer et faire tourner l’algorithme en parallèle sur des rounds simulés : l’algorithme travaille donc maintenant sur une population de 500 ennemis, même si 20 seulement sont envoyés au joueur. Et pour chaque round réel nous en simulons deux (avant, on avait besoin d’en faire plus, mais suite à l’amélioration de notre choix de *fitness*, ça évolue suffisamment vite pour n’en faire que deux). Une fois le projet fini, le jeu n’était pas réellement intéressant à jouer, car nous avions été accaparés par la partie configuration de l’algorithme évolutionnaire et simulation des rounds. J’ai donc travaillé un peu cet été sur l’équilibrage du jeu, et j’ai enfin obtenu quelque chose qui est rigolo à jouer, d’où cette version 0.4. Il y a 3 cartes classées par difficulté, et un système de médailles bronze/argent/or attribuées selon le nombre de rounds tenus. Veuillez suivre les liens ci‐dessus pour voir une démo du jeu, télécharger les sources, se renseigner sur EO... Si quelqu’un prend le temps de faire une version compilée ou un paquet pour une quelconque distribution, je serai ravi d’héberger ça sur le site officiel. Veuillez pardonner toute erreur ou approximation commise au cours de cette dépêche, je suis encore loin d’être expert en algorithmes évolutionnaires, nous n’en avons vu que les grandes lignes.

AltStyle によって変換されたページ (->オリジナル) /