Développer une IA astucieuse dans un jeu tactique basé sur l'heuristique et les mutations

Dans les jeux tactiques, l'IA est très importante. Si l'IA est considérée comme un «idiot artificiel», le jeu peut être sauvegardé par un multijoueur, une intrigue, une atmosphère et des graphismes incroyables (c'est inexact). La solution est évidente: faire une bonne IA, quel pourrait être le problème?


Dans les détails. Voici mes étapes pour construire une IA forte avec du caractère. Pas super fort [ 1 ], mais capable de travailler rapidement localement dans un navigateur gourmand de n'importe quel PC moyen-faible. J'ai appliqué l'approche de systèmes experts en utilisant un ensemble d'heuristiques et de mutations. 15 étapes de transformation progressive de l'IA sont décrites, chacune des étapes peut être ressentie.

Brève description

Dans un jeu par navigateur expérimental, l'IA est basée sur la génération de nombreux états possibles - les résultats du mouvement actuel. (En raison des spécificités et de la commodité du jeu, ces états résultants dans l'article sont appelés des scénarios de virage ou des stratégies d'IA, selon le contexte) . Ensuite, les scénarios du cours sont mutés. Selon les scénarios obtenus, les estimations du «succès» sont calculées. Le plus réussi et exécuté par un joueur d'ordinateur.

Par exemple, trois stratégies sont générées:

1. Courant frénétiquement vers l'avant et attaquant tous ceux qui lèvent le bras. Points de l'état final: 37000 points.
2. Attaquez les archers à une distance sûre, tandis que les autres se cachent dans les coins. 45000 points.
3. Tous battent en retraite, se regroupent et se cachent des ennemis. Si vous pouvez blesser un ennemi à une distance sûre, alors attaquez. 18000 points.
4. Dans ce cas, la 2ème stratégie sera sélectionnée.

Eh bien, tout semble être standard. Pas vraiment.

Toute la pulpe est de savoir comment les scripts sont générés et comment le coefficient de valeur du script est calculé. Imposer dans l'un d'eux et le résultat vous attristera.

Règles du jeu

Le joueur et l'IA ont initialement 6 unités identiques dans les coins. Chaque équipe se relaie à tour de rôle par toutes les unités à la fois. Options pour la progression de chaque unité:

• sauter un mouvement;
• se déplacer et sauter;
• déplacer et attaquer ( vous pouvez et parfois vous devez attaquer le vôtre ).

Le terrain de jeu et la composition de l'équipe sont générés de manière procédurale ( c'est-à-dire au hasard, mais avec des contrôles de perméabilité et de «tact» acceptable ). Types d'unités:

1. Fighter F, unité de mêlée avec la plus grande capacité de survie, dégâts et mobilité. Une sorte de char + dégâts.
2. Archer A, les dégâts les plus faibles, mais l'attaque est à une distance de 1-7 en ligne droite.
3. Le Sorcier W meurt d'un coup de combattant, mais l'attaque est à une distance de 1-5 en ligne droite à travers toutes les unités.

Le terrain de jeu est toujours de taille 10 * 10.

Champs possibles sur la carte:

• Terre - n'impose aucune restriction.
• Mur - à travers lui, vous ne pouvez ni tirer ni passer.
• Eau - il est impossible de le traverser, mais un archer peut tirer dessus (un magicien ardent ne peut pas ).

Le jeu est complètement déterminé, c'est-à-dire qu'il n'y a aucun élément de chance en lui (100% de chances de toucher, pas de dégâts critiques, etc.). C'est aussi un jeu avec des informations complètes, c'est-à-dire que les rivaux savent tout sur l'état des troupes des uns et des autres à un moment donné. Comme dans les dames.

L'IA est plus forte qu'un joueur de viande, mais ce dernier au premier niveau a un handicap sous la forme d'une unité. Le 3, le joueur, au contraire, a un handicap d'une unité et il est beaucoup plus difficile de gagner (j'ai environ 15% de victoires à ce stade). Vient ensuite la version plus aléatoire de Game +.


Le jeu a été développé sur des styles natifs javascript: divs et css, et c'était la solution la plus malheureuse possible [ 2 ]. Ceci est un jeu par navigateur. Le moteur n'a pas été utilisé. Le seul objectif du projet est de créer un joueur informatique fort "avec du caractère" et la capacité de changer ce personnage (calcul des cyborgs, des orcs agressifs, des elfes perfides, des zombies stupides).

Pour réduire le "style informatique" de l'ennemi, quelques astuces ont été appliquées:

• Le joueur après son tour n'attend pas que l'IA pense à son coup. L'ennemi commence «immédiatement» à faire ses mouvements ( en réalité, c'est une illusion ).
• Le joueur informatisé contrôle également les unités à l'aide de son curseur ( et c'est aussi une illusion, le curseur vole juste en même temps que les animations des unités ).
• L'IA peut utiliser des appâts insidieux pour forcer un combat ( tout est juste ).

Et qu'est-ce qui est si compliqué?

Au début, il peut sembler que tout est simple: vous pouvez simplement trier toutes les options de tous les mouvements et choisir la meilleure. Mais très vite, il devient évident que tout est très difficile.
L'énumération complète est impossible en raison de l'effet d'explosion combinatoire [ 3 ], qui consiste dans le fait qu'au fur et à mesure que le nombre d'éléments à vérifier dans les scénarios augmente, la complexité de calcul augmente de façon exponentielle. Ensuite, je vais décrire ce que cela signifie dans mon jeu particulier.

D'abord parce que À chaque tour, les unités de l'équipe partent toutes en même temps , puis leur séquence peut être différente. Et avec 6 unités dans l'équipe de telles combinaisons devient 720 (1 * 2 * 3 * 4 * 5 * 6). S'il y aura plus d'unités, alors il y aura un grand nombre de combinaisons (à 7 - 5040, à 8 - 40320 ...). Si vous ne tenez pas compte du résultat maximal, le joueur risque d'essayer le plaisir en prévision du prochain mouvement pendant 5 à 10 minutes ( et s'il persiste, le retard augmentera jusqu'à des millions d'années, tout le monde ne souffrira pas ). C'est à cause de cette caractéristique que mon IA au début de la bataille est moins efficace qu'à la fin. En effet, vers la fin, la moitié de l'équipe est déjà décédée.


Deuxièmement, chaque unité peut se déplacer vers différents points de la carte . Les combattants avec une amplitude de mouvement de 4 peuvent ressembler à 1 à 41 positions différentes. Pour les magiciens et archers avec leur mouvement en 3, le nombre possible de mouvements est de 1-25. Par exemple, la composition de l'équipe peut être: 4 combattants, 1 mage et 1 archer. Nous obtenons le total de différentes combinaisons de mouvements pour cet article: 41 * 41 * 41 * 41 * 25 * 25 = 1766100625. En réalité, en raison des intersections mutuelles et du terrain infranchissable, il y aura moins de combinaisons, mais dans une rare situation de «dispersion sur la carte», le nombre de combinaisons sera se rapprocher de ce nombre.

Troisièmement, chaque unité après le mouvement peut sauter un mouvement ou attaquer dans l'une des 4 directions. Autrement dit, nous avons 5 actions finales possibles par unité. Combinaisons totales: 5 ^ 6 = 15625.

Combinaisons totales: 720 * 1766100625 * 15625 = 19868632031250000.

Et dans chaque combinaison valide, il sera nécessaire de calculer les points de l'état résultant. La fonction d'évaluation comprend: émulation de mouvements, attaque, causant des dégâts, mort d'unités et comptage des points de vie restants des survivants. Bien sûr, le nombre de combinaisons est surestimé, car en conditions réelles, la variabilité diminuera en raison des limites et des obstacles sur la carte, mais ce sera toujours un nombre insupportable de combinaisons. Et tout cela se passe après tout dans un navigateur normal.

Comment ça se passe?

Pour résoudre un problème similaire, une approche heuristique a été utilisée, dont l'algorithme généralisé peut être décrit comme suit:

1. Générez différents scénarios basés sur des stratégies prédéfinies (~ 20 pièces).
2. Tant qu'il reste du temps, muter les scripts, en laissant le plus rentable.
3. À la fin, sélectionnez le scénario avec la note la plus élevée.
4. Effectuez le premier mouvement de l'unité à partir du script, mais ne faites pas le reste. Démarrez l'animation du premier mouvement et pendant que l'animation est affichée, continuez d'améliorer les scripts pour les unités restantes.
5. Répétez l'opération pour les unités restantes de l'étape 1.

La méthode heuristique est une méthode qui peut fonctionner (selon McConnell [ 4 ]). Plus et plus strict sur Wikipédia [ 5 ].

Les points clés de cet algorithme sont: la génération de scénarios, les mutations et l’évaluation correcte de la rentabilité de l’État. Chacun de ces points utilise sa propre heuristique locale. Néanmoins, dans la mesure du possible, des algorithmes ont été utilisés avec un résultat optimal garanti, par exemple, A * pour trouver le chemin [ 6 ].

L'approche évolutive que j'ai utilisée ne peut pas être qualifiée de génétique à part entière [ 7 ], car Je n'ai utilisé que des mutations et la survie des «plus forts» de lui, et j'ai ajusté manuellement les coefficients de l'influence de l'heuristique individuelle. Les algorithmes de formation des populations et des croisements n'ont pas été utilisés. Après la mutation, un seul survit: un mutant ou un parent.



Je n'ai pas utilisé de réseaux neuronaux [ 8 ] en raison de la nature du problème. Tout d'abord, en raison de la complexité de leur mise en œuvre réussie dans un environnement en constante évolution (émergence de nouvelles mécaniques, compétences, capacités). Deuxièmement, en raison de la complexité de leur personnalisation contrôlée (si vous voulez faire deux comportements: Suvorov rapide et Kutuzov prudent [ 9 ]).

L'évolution d'un idiot artificiel en intelligence artificielle

0) Au début, seules 3 stratégies avec des mouvements aléatoires ont été introduites en IA. { Difficulté du jeu # 0 }. Le score de condition était juste un nombre aléatoire. Et comme l'IA n'est pas le seul élément de développement, j'ai dû supporter le comportement des poissons fous pendant un certain temps.

1) Ensuite, dans le calcul de l'évaluation de la stratégie, les contrôles des unités restantes et de leur vie avec l'IA et le joueur ont été ajoutés. { Difficulté du jeu # 10 }. Pour une unité morte, l'équipe a obtenu 0 point. Pour des points X complètement sains (par exemple, 100 000 pour le combattant F, 70 000 pour l'archer A, 85 000 pour le sorcier W). Pour les blessés ont été facturés 50% de la valeur de base, et les 50% restants en proportion de la durée de vie restante du maximum. Grâce à cela, il était plus rentable pour l'IA de tuer des ennemis, et s'il ne pouvait que blesser, alors il choisissait des adversaires avec moins de vies - plus vulnérables.

Les mouvements aléatoires sont devenus plus significatifs - l'IA a parfois redonné.

2) Ensuite, une stratégie de départ plus significative a été ajoutée:
max_agro - tous les soldats ont couru le plus près possible des ennemis et ont essayé d'infliger autant de dégâts que possible . { Difficulté du jeu # 20 }. Une stratégie a utilisé l'ordre de déplacement d'origine de l'unité, la seconde est passée dans l'ordre inverse.

L'IA a commencé à se comporter comme l'idiot artificiel le plus primitif dans les jeux tactiques. Et bien souvent, une telle IA est utilisée dans les jeux tactiques. Il est populaire en raison de sa fiabilité et de sa simplicité. Celui-ci peut même gagner - mais très rarement.

C'est exactement à cela que ressemble le comportement de l'IA dans le jeu Master of Monsters - Disciples of Gaia qui a échoué, ce qui rend le jeu fastidieux [ 10 ].


3) Ensuite, des stratégies ont été ajoutées qui prennent en compte les dommages possibles des ennemis pendant le mouvement, et choisissent les mouvements qui ont conduit au moins de danger - de préférence zéro. { Difficulté du jeu # 30 }. Et l'IA est immédiatement devenue trop lâche, évitant toute proximité avec l'ennemi - il vaut mieux fuir que d'attaquer et de blesser, car l'ennemi peut donner plus de changement!

Par conséquent, l'évaluation des conditions a également commencé à prendre en compte les dommages possibles à l'ennemi . Les points de pénalité des dommages potentiels des ennemis ont commencé à être calculés avec un coefficient décroissant de 0,20 (le coefficient était constamment reconfiguré ). Cela a forcé l'IA à choisir une option agressive lors du choix entre l'attaque ou le vol, car elle rapportait 5 fois plus de points que le vol. Mais l'IA est restée lâche pendant longtemps, car pour entrer dans une telle situation de choix, l'ennemi devrait déjà être à portée de main, et l'IA elle-même, avec de telles évaluations, ne se mettra jamais en premier en attaque. Autrement dit, il n'ira pas au rapprochement. Bien sûr, le joueur se sentira trompé, car l'IA a une réserve infinie de patience et peut fuir le danger pour toujours, forçant le joueur à l'agression.

Il convient de noter que de tels calculs de dommages possibles sont très longs sans l'utilisation d'un cache. Une erreur de calcul complète d'une stratégie sans optimisation a initialement pris 700 millisecondes. Mais j'ai une limitation sur le cours entier d'une unité ~ 4000 ms! Après optimisations et caches dépensées, ce temps diminue à 20 millisecondes avec des stratégies très similaires ( malheureusement, le cache ne peut pas être calculé à l'avance en raison de l'effet d'explosion combinatoire, donc 20 ms ne sont pas toujours atteints ).

Par conséquent, lorsque j'ai introduit la technologie de calcul avec la prévision de plusieurs mouvements à venir , le temps de calcul pour une profondeur de seulement 2 mouvements (ennemi et IA) a déjà pris +700 millisecondes. Dans ce cas, l'optimisation est utilisée pour couper les branches "faibles". Si vous utilisez la stratégie primitive max_agro pour cela, l'augmentation de temps était de +30 millisecondes et la mise en cache n'a presque pas réduit cette différence ( car la position sur la carte était complètement nouvelle ).

En conséquence, j'ai fait 5 approches différentes pour le développement de cette approche, mais à la fin je l'ai complètement abandonnée, car les mutations avec l'heuristique ont donné des résultats meilleurs et plus rapides.

4) Les stratégies suivantes visaient à élargir la diversité initiale des stratégies:
far_attack_and_hide - les unités tentent d'attaquer le plus loin possible de l'ennemi, et si elles n'attaquent pas, elles se cachent de toute attaque.

close_group_flee - les unités s'éloignent de la bataille et se rapprochent le plus possible. Si vous pouvez attaquer l'ennemi en toute sécurité en même temps, attaquez.
{ Difficulté du jeu # 40 }.

Cela a amélioré le processus de la bataille elle-même, mais le début de la bataille n'a pas toujours été rentable pour l'IA: elle a constamment reculé, mais elle pouvait être attirée dans l'attaque et effrayée de sorte que le groupe AI était divisé en plusieurs petits groupes qui pouvaient être détruits séparément.

5) Il est alors temps pour les mutations . { Difficulté du jeu # 50 }.

L'algorithme de mutation était très simple:

• lors de l'itération sur les stratégies sélectionnées, une copie de la stratégie a été créée;
• dans cette copie, une mutation du cours a été faite;
• si le mouvement est devenu invalide, il a été corrigé en au moins un valide selon l'une des stratégies standard;
• les points de la stratégie mutée ont été calculés;
• si le mutant avait plus de points, alors le mutant a remplacé son parent.

Dans le même temps, les étrangers n'ont pas supprimé la stratégie et ont également participé à des mutations, car il y a toujours eu une probabilité notable d'une série de mutations très réussie.

Dans un premier temps, le type de mutation le plus primitif a été mis en œuvre: de 1 à 3 mouvements ont été remplacés par des mouvements aléatoires, l'ordre des mouvements est resté le même. Au cours d'une itération de calculs, en moyenne, environ 5 à 15 mutations ont été créées pour chaque stratégie. De plus, en moyenne, une mutation sur cinq était plus rentable et remplaçait la stratégie du parent.

6) Appât heuristique . { Difficulté du jeu # 60 }.

Cette heuristique a répété la tactique avec laquelle j'ai attiré l'IA pour attaquer avec une unité afin de la tuer une à la fois. Cette astuce a également été enseignée à l'IA.

Pour ce faire, en fonction du calcul des points de l'état de la stratégie, on vérifie si l'état actuel correspond à la situation de l'appât:

• Un seul soldat IA peut être attaqué;
• Un seul ennemi peut attaquer une unité rampante;
• L'unité du joueur informatique doit survivre après cette attaque;
• Au moins deux unités de l'ordinateur pourront attaquer en réponse. Plus ces unités punitives sont nombreuses, plus il y a de points pour l'heuristique.

L'effet s'est avéré excellent: il devient plus facile pour le joueur de commencer la bataille lui-même. De plus, le plus souvent, il est encore plus rentable pour un joueur de «s'accrocher» à cet appât, car après une attaque de retour, il pourra tomber sur l'IA avec toute son équipe ( c'est s'il est raisonnablement groupé au préalable ). Et là, toutes les décisions tactiques locales compétentes résoudront tout.


7) Puis j'ai commencé à attirer mon attention sur le fait que les combattants de l'IA se dispersent constamment comme des cafards . { Difficulté du jeu # 70 }. De plus, les soldats pouvaient se cacher dans un coin ou entrer dans des tunnels étroits, dans lesquels l'IA avait grandement perdu de son efficacité à trier les attaques possibles.
Par conséquent, une heuristique pour estimer les distances entre les unités et la topographie de la carte avec les hypothèses suivantes a été ajoutée à la fonction d'évaluation:

• Plus les alliés sont proches "en moyenne" - mieux c'est (les unités ont commencé à se disperser moins souvent dans différentes parties de la carte).
• Plus les soldats de l'IA sont proches des soldats «moyens» de l'ennemi, mieux c'est (j'avais besoin d'une IA offensive).
• Plus la distance maximale entre n'importe quelle paire d'alliés est grande, pire c'est. Dans le même temps, une distance de 4 n'est pas pénalisée, et tout ce qui est plus grand est pénalisé de façon exponentielle (cela a cessé d'attirer des soldats dans des rangs vulnérables).
• Si un soldat IA ne peut pas courir et attaquer l'ennemi dans au moins 2 tours, alors il doit être condamné à une amende (cela l'oblige à avancer, mais pas à se tenir sous l'attaque lui-même).
• Si dans un rayon de 2 pas du soldat il y a trop de positions de blocage, alors infligez-lui une amende (moins souvent, ils ont commencé à courir dans des tunnels).
• Si un soldat se trouve à la frontière de la carte, infligez-lui encore une amende. En conséquence, la maniabilité de l'IA a considérablement augmenté, car Une unité peut fonctionner depuis une zone ouverte vers un nombre beaucoup plus grand de positions que depuis un coin ou un tunnel.

8) Ensuite, il est temps d'élargir les stratégies. { Difficulté du jeu # 80 }. Je ne pouvais pas ajouter une énumération complète de l'ordre possible des mouvements d'unité, mais je pouvais énumérer leurs mouvements par type : combattant, archer, sorcier. Par conséquent, des stratégies sont apparues pour la séquence de mouvements, de la forme W_A_F: d'abord tous les sorciers marchent, puis tous les archers, puis tous les combattants.

Ainsi, 6 nouvelles stratégies ont été ajoutées: W_A_F, W_F_A, A_W_F, A_F_W, F_A_W, F_W_A. Ils n'ont pas résolu tous les problèmes, mais ont considérablement amélioré la qualité du jeu.

9) J'ai eu des mutations, mais elles étaient de peu d'utilité. { Difficulté du jeu # 90 }. Généralement, ils ont amélioré les stratégies faibles, tandis que celles qui ont réussi se sont rarement améliorées. Par conséquent, les mutations ont été modifiées et à chaque fois l'un des types de mutations aléatoires a fonctionné:

• De 1 à 3 mouvements ont été remplacés par des mouvements aléatoires, l'ordre des mouvements est resté le même (à l'ancienne);
• Échangez l'ordre de déplacement de deux unités aléatoires. Laissez-les inchangées, même si elles ne sont pas optimales. Si le mouvement ne peut pas être répété, il est recréé au hasard par l'une des stratégies habituelles dans un état valide;
• Échangez l'ordre des mouvements de deux unités aléatoires et recomptez à nouveau leurs mouvements. Tous les coups échoués dans les unités suivantes sont réparés par des stratégies conventionnelles aléatoires.

L'introduction de ces mutations a commencé à compenser sérieusement l'impossibilité d'énumérer complètement toutes les combinaisons de mouvements unitaires. Bien qu'en raison de son caractère aléatoire, il ne donne aucune garantie qu'un coup d'État sera trouvé dans le temps limité disponible.

10) Ensuite, plus de stratégies semi-aléatoires ont été ajoutées . { Difficulté du jeu # 100 }. L'ordre des mouvements a été généré de manière aléatoire, et les mouvements eux-mêmes ont été sélectionnés selon les principes suivants (pour réduire leur importance):

• infliger un maximum de dégâts;
• prendre le moins de dégâts possible en réponse;
• Rapprochez-vous le plus possible de vos ennemis.

Je n'ai pas vu d'amélioration notable ici, mais le projet est déjà passé au stade où chaque amélioration conduit à des effets reproductibles moins visibles.

11) J'étais fatigué des erreurs flagrantes de l'IA, quand il a attaqué mes soldats en attaquant avec son sorcier, mais en même temps blessé ses alliés. { Difficulté du jeu # 110 }. Bien qu'avant cela, il pouvait réellement se promener avec eux et les retirer de la ligne de feu. Par conséquent, une stratégie générée en dur avec des vérifications manuelles a été créée :

• s'il y a un sorcier, alors trouvez un endroit d'où il infligera un maximum de dégâts;
• s'il y a des alliés à cet endroit ou sur le chemin de la grève, souvenez-vous-en;
• tout d'abord, tous les alliés dont ils se souviennent s'en vont et ils ne peuvent pas occuper des positions réservées par le sorcier (c'est-à-dire ouvrir la voie);
• le sorcier marche;
• les autres unités marchent.

La stratégie est facilement décrite par des mots, mais c'est cool pour la programmer.

12) Parfois, des unités " s'échappaient dans les buissons " juste avant le début des hostilités. { Difficulté du jeu # 120 }. En conséquence, lorsque l'échange d'attaques a commencé, une ou même deux unités pouvaient être trop éloignées des opérations militaires et n'ont pas aidé les alliés. Si cela se produisait, j'étais presque assuré de battre l'IA. Si cela ne s'est pas produit, j'ai souvent perdu. Je m'en suis débarrassé en introduisant une nouvelle heuristique pour évaluer les points résultants de la stratégie. Un contrôle a été effectué pour chaque unité:

1. Si l'unité a attaqué ce tour, alors elle a reçu +1500 points.
2. Si vous n'avez pas attaqué, les positions ont été calculées à partir desquelles les ennemis pouvaient infliger des dégâts aux alliés. Continuez à compter s'il y a plus de 0 de ces positions (N> 0).
2.1. Si une unité ne peut pas atteindre et toucher à n'importe quelle position (n = 0), alors elle reçoit une pénalité de -1000 points.
2.2. Si une unité peut atteindre toutes les positions, elle obtient +1200 points.
2.3.Si une unité peut attaquer jusqu'à certaines positions, elle obtient + (n / N) * 1000 points.

Cela a considérablement amélioré la «cohésion» des unités IA. Malheureusement, des cas de «déserteur» ont commencé à apparaître, lorsqu'en situation de perte l'une des unités blessées a préféré se cacher derrière le dos de leurs camarades au lieu de contribuer en attaquant l'ennemi. Cela semblait ridicule quand l'ordinateur n'avait plus que 2 unités et que le joueur en avait 3 ou même plus. Une heuristique corrective supplémentaire est la règle suivante:

IF ("   ,   " AND "    3 ") THEN "      " 

13) À la fin de l'introduction des stratégies, elles s'étaient déjà accumulées sous 25 pièces. { Difficulté du jeu # 130 }.

Muter chacun d'eux est devenu trop cher. Par conséquent, il a été décidé de supprimer les plus infructueuses et de ne laisser que 8 pièces. Dès le début, je n'ai pas voulu utiliser cette approche dans l'espoir que la mutation des étrangers puisse conduire à un excellent résultat inattendu, au lieu d'un bon. La saisie de ce traitement a finalement conduit à une amélioration du jeu AI.

14) Au début, il y avait encore une révision intéressante. Initialement, la valeur du scénario a été calculée comme la différence dans la somme des points:

 _ = _ - _ 

Mais après plusieurs améliorations, je me suis souvenu que ce n'était pas la meilleure solution, car puis pour AI, les situations «2 soldats contre 1 seul soldat» et «4 soldats contre 3 soldats» seront les mêmes. Par conséquent, les points ont commencé à être calculés comme le rapport:

 _ = _ / _ 

Le changement est faible et le résultat est très grave. Sans modification, le prix d'une erreur à risque accru a toujours été le même. Après raffinement, l'IA a commencé à risquer moins négligemment vers la fin de la bataille, ce qui l'a considérablement renforcée.

Je veux noter que toutes ces améliorations ont été introduites progressivement, bien que dans l'ordre indiqué, mais beaucoup d'entre elles ont été améliorées, traitées et corrigées des bogues dans un ordre plus chaotique. Il y a eu plus de 100 itérations réelles.

Voici comment joue l'IA finale { Difficulté du jeu # 9999 }:

L'IA marche tout de suite, sans perdre de temps à penser

Pour accélérer les calculs eux-mêmes, des algorithmes d'optimisation ont été activement utilisés sous la forme de partitions de boucles imbriquées en boucles séquentielles ( réduisant la complexité ) et l'introduction de plusieurs tableaux avec des calculs préliminaires mis en cache ( et l'optimisation ultérieure de ces mêmes caches ). Selon mes estimations, de nouvelles optimisations pourraient me fournir une augmentation de vitesse double (voire plus), mais cela entraînerait une augmentation injustifiée des coûts de temps et une perte encore plus importante de lisibilité du code.

La principale technologie de haute vitesse est les calculs préliminaires pendant les temps d'arrêt. Cette méthode consiste à diviser le processus en deux parties: les calculs eux-mêmes et l'animation des résultats des calculs:

• les calculs du cours de la première unité commencent immédiatement après le tour du joueur, tandis qu’une fenêtre s’ouvre pour indiquer que le tour de l’adversaire commencera. Et cela représente jusqu'à 4 secondes, ce que le joueur ne perçoit pas comme une attente vide;
• les calculs du deuxième mouvement et des mouvements suivants commencent lorsque l'animation du cours de la dernière unité commence seulement (c'est-à-dire lorsque le curseur AI commence juste son mouvement). Et le temps de toutes les animations est déjà de 4,5 secondes. Bien qu'il serait plus correct d'appeler cela non pas le calcul du prochain mouvement, mais l'amélioration de la stratégie passée déjà développée et la recherche d'une nouvelle, car à chaque itération, les déplacements de toute l'équipe sont calculés;
• lorsque l'animation de l'IA se déplace vers des unités en mouvement, le curseur de l'IA vole, qui prétend qu'il clique dessus. Le curseur vole aussi vite que possible, mais pour que le confort de le suivre reste. De plus, l'ajout d'un curseur a non seulement permis d'augmenter la marge de temps de calcul de 2 secondes à 4,5, mais a également rendu la visualisation de la progression de l'ordinateur plus confortable pour une personne;
• le temps de tour du joueur n'est pas non plus perdu. Tant que le joueur le pense, presque aucun calcul n'est effectué, donc à ce moment les caches possibles pour le futur mouvement de l'adversaire informatique sont intensivement calculées.

Pour éviter que tout cela ne traîne dans le navigateur et ne fonctionne avec un FPS assez stable, les calculs sont effectués de manière asynchrone par le travailleur ( travailleurs Web ) [ 11 ].

En faisant cela, je voulais me débarrasser de la fâcheuse fenêtre d'attente «Computer promenades». Un tel dé désagréable est dans de nombreux bons jeux, par exemple, dans Xenonauts [ 12 ]. Je crois que j'ai pu faire face à ce problème.


Ainsi, l'IA passe toujours le même temps à penser à son mouvement - quelle que soit sa complexité. Une caractéristique très curieuse de cette approche est que plus le joueur a un ordinateur fort, plus les mutations de l'IA auront le temps de trier, et donc seront plus fortes, plus l'ordinateur du joueur sera puissant. J'ai d'abord supprimé cet effet en fixant le temps de fonctionnement et en pré-calculant la vitesse de l'ordinateur. Cependant, j'ai ensuite supprimé cette fixation, car possesseurs d'ordinateurs puissants, cela leur permettra de se battre avec "leur" ordinateur, plutôt qu'avec l'ordinateur moyen.

Quel est le résultat et quels sont les inconvénients

Ainsi, l'adversaire informatique qui en résulte sait comment se battre dignement et fait bon usage des oublis de n'importe quel joueur, et n'en fait pas trop. Néanmoins, moi, connaissant toutes les caractéristiques de son travail, quoique avec tension, mais je le vainc presque toujours (dans des conditions égales). Mais je voudrais le contraire: même en connaissant ses caractéristiques, il perd presque toujours pour lui. L'IA est loin d'être idéale, car l'ensemble d'heuristiques que j'utilise conduit au chevauchement synergique des «erreurs de ma perception» les unes sur les autres. Ces erreurs sont:

1. L'imperfection et l'incomplétude de ma propre stratégie, je ne connais pas toutes les meilleures stratégies, et donc je ne peux pas les identifier et les mettre en œuvre dans le jeu.
2. Perte d'efficacité (qui n'est pas si idéale) des heuristiques élaborées lors de leur transfert vers le code programme. Par exemple, mon heuristique humaine: "Les unités restent proches, mais pas trop près pour éviter le double dommage des magiciens et ne pas se coincer dans des passages étroits." Cette heuristique m'aide à vaincre l'IA, mais quand je l'enseigne à mon adversaire informatique, je dois traduire une description qualitative en une description algorithmique avec des estimations quantitatives, et ici la perte de données est possible.
3. Conflits mutuels entre heuristiques. Lorsqu'il y a trop d'heuristiques, elles commencent progressivement à se chevaucher. En conséquence, une amplification inattendue peut se produire en raison d'un double comptage caché ou d'une duplication partielle. Ou une sorte d'heuristique cessera d'influencer quoi que ce soit, car sa contribution est complètement bloquée par de grands coefficients concurrents.
4. Des contraintes de temps serrées et des améliorations pas à pas des stratégies choisies conduisent au fait que le premier mouvement sera toujours moins réfléchi. Cela signifie qu'un premier coup infructueux peut bloquer les mouvements évidents et plus efficaces des unités restantes de l'équipe. Cela s'exprime dans le fait que le premier combattant F au lieu de s'éloigner peut attaquer l'ennemi avec ironie et que son allié sorcier W devra blesser le sien afin de finir l'ennemi.

Des algorithmes génétiques à part entière, au lieu de «l'appariement à l'œil», permettraient très probablement de sélectionner des coefficients plus optimaux en heuristique. Mais c'est déjà une tâche pour de futurs projets à part entière - je ne veux pas rester bloqué avec un prototype pendant longtemps. Je suis assez satisfait de l'IA actuelle: elle est prudente, un peu insidieuse, assez agressive et ne permettra pas au joueur de se vaincre à sec ( en réalité, il est extrêmement rare de le permettre ).

Fonctionnalités supplémentaires

Cette méthode de mise en œuvre vous permet d'obtenir des bonus supplémentaires dans le développement de jeux ( à bien des égards du point de vue du développeur et de ses termes brûlants ):

1. L'apparition de nouvelles mécaniques dans le jeu ne détruira pas la force du joueur informatique, même si elle l'affaiblira progressivement par rapport au joueur. Cet affaiblissement peut être compensé par l'introduction d'heuristiques supplémentaires. Pour que cela n'entraîne pas de dépenses progressives de ressources, il n'est possible d'appliquer ces nouvelles heuristiques que si ces nouvelles mécaniques sont présentes dans la bataille actuelle.
2. Niveaux de difficulté vraiment intelligents. Maintenant, fondamentalement, le niveau de difficulté détermine quels bonus un joueur d'ordinateur recevra comme ressources ( plus d'or au début ou un bonus dans les mines ) ou combien ses soldats battront ( + 50% aux dégâts ). Cela fonctionne, mais vous pouvez rendre l'IA un peu moins intelligente simplement en désactivant progressivement certaines heuristiques à mesure que la complexité diminue.
3. Dans la suite du deuxième paragraphe, vous pouvez créer différentes races / factions d'adversaires informatiques : seules les stratégies agressives fonctionnent pour les orcs; dans les foules de zombies, seuls les primitifs «courent en avant et attaquent»; et les cyborgs utilisent toute la puissance de l'IA. Merci à ce joueur avant l'attaque devra évaluer non seulement le nombre d'adversaires, mais aussi leur intelligence.

Tout cela semble prometteur, mais rappelez-vous que tout cela est beau sur le papier, et dans un vrai jeu, cela peut tout simplement ne pas fonctionner, se révéler inintéressant, voire invisible pour le joueur. Mais c'est une bonne raison d'expérimenter.

Où se sentir

Vous pouvez tester la puissance de cette IA dans le navigateur de rumble tactique de l'IA. Test subject ”gratuit sur des sites comme itch.io [ 13 ]. Le paramètre GET ai (valeurs de 0 à 140 par pas de 10) réduira la complexité de l'IA.

Selon mes attentes, vaincre l'IA sur un pied d'égalité sera très, très difficile pour vous. Même après s'être habitué aux règles du jeu. Je recommande de considérer ce jeu comme un prototype, ce qu'il est essentiellement (il n'y a pas de musique, de sons et de prix ).

Veuillez laisser votre avis dans les commentaires sur l'intérêt de l'IA, des conseils et des critiques sur la mise en œuvre possible de l'IA à l'aide de diverses méthodes d'enseignement. Si vous vous êtes soudainement intéressé à mes autres recherches, pensez à vous inscrire ici à mon compte.

Les références

1. DeepMind - articles sur Habré .
2. Jeux HTML5: Canvas vs SVG contre div sur stackoverflow .
3. Explosion combinatoire - Wikipedia .
4. Le code parfait de Steve McConnell est Habr .
5. Méthodes heuristiques - Wikipedia .
6. A * - Red Blob Games .
7. L' algorithme génétique. À peu près le difficile - Habr .
8. Huit jeux incroyables avec intelligence artificielle de la société Google - Habr .
9. Très brièvement sur Suvorov et Kutuzov .
10. Master of Monsters - Disciples of Gaia - Revue sur IGN .
11. Une explication détaillée des boucles et du timing du jeu JavaScript .
12. Xenonauts et un long écran de veille AI .
13. Grondement tactique de l'IA. Sujet de test - sur itch.io.