Aide avec l'IA de jeu de stratégie

Je développe une IA de jeu de stratégie (pensez: Final Fantasy Tactics), et j'ai du mal à proposer la conception de l'IA. Mon principal problème est de déterminer quelle est la chose optimale à faire.

Permettez-moi d'abord de décrire la priorité de l'action que je voudrais que l'IA prenne:

1. Tuez l'unité de joueur la plus proche

2. Remplissez la directive principale (tuez toutes les unités de joueur, tuez l'unité cible, survivez pendant x tours)

3. Guérir l'unité alliée / tampon de lancement

Désormais, l'IA peut effectuer les opérations suivantes à son tour:

• Déplacer -> {Attaque / Capacité / Objet} (soit attaque ou capacité ou objet)

• {Attaque / Capacité / Objet} -> Déplacer

• Rapprochez-vous (si les cibles ne sont pas à portée)

• {Attaque / Capacité / Objet} (si le mouvement n'est pas disponible)

Remarques

Les capacités ont différentes gammes / effets / coûts / effets. Chaque unité ai peut choisir entre 5 et 10 capacités. L'IA donnera la priorité à la mise à mort plutôt qu'à la sécurité à moins que sa directive ne soit de survivre pendant x tours. Il ne se soucie pas non plus du coût de la capacité. Alors qu'un joueur peut vouloir sauvegarder un gros sort pour plus tard, l'IA l'utilisera très probablement dès que possible.

Le mouvement se fait sur une grille (hex)

nombre d'unités de joueur: 3-6

nombre d'unités ai: 3-7 ou plus. Probablement max 10.

L'IA et le joueur contrôlent à tour de rôle UNE unité, au lieu de tous en même temps.

La plate-forme est Android (si le programme ne répond pas après un certain temps, il y aura une fenêtre contextuelle disant de forcer la fermeture ou l'attente - ce qui semble vraiment mauvais!).

Maintenant vient les questions:

• La meilleure capacité d'utilisation serait évidemment celle qui frappe le plus de cibles pour le plus de dégâts. Mais comme chaque capacité a des portées différentes, je ne saurai pas si elles sont à portée sans explorer chaque endroit possible où je peux me déplacer.

• Une solution serait de passer par chaque endroit possible pour se déplacer, de déterminer l'attaque optimale à cet endroit - ce qui me donne une liste de mouvements optimaux pour chaque emplacement. Ensuite, choisissez l' optimal hors de la liste et exécutez-le. Mais cela prendra beaucoup de temps CPU. Y a-t-il une meilleure solution?

• Mon idée actuelle est de me rapprocher le plus possible du groupe de personnes le plus proche et le plus grand, et de déterminer l'attaque / la capacité optimale à partir de là. Je pense que ce serait beaucoup moins de travail pour le CPU et permettrait toujours des attaques à large spectre. C'est sous-optimal mais l'IA semblera toujours `` intelligente ''.

Autres notes / questions:

• Suis-je trop réfléchi / trop compliqué? Une meilleure solution? Je suis ouvert à toutes sortes de suggestions
• J'ai jeté un coup d'œil à la question de lancement de sorts , mais elle ne prend pas en compte le mouvement - alors peut-être utiliser cet algo pour chaque emplacement de mouvement possible? La première réponse mentionnait que ce n'était pas génial pour les combats de zone d'effet et de groupe - alors peut-être qu'il faut plus de peaufinage?
• S'il vous plaît , si vous mentionnez un graphique / arbre, laissez - moi savoir essentiellement comment l'utiliser. Par exemple, Node signifie capacité, le niveau correspond aux dégâts, puis recherchez le nœud le plus profond.

Il existe de nombreuses applications que vous pouvez utiliser pour ce type d'IA. Personnellement, l'une des techniques les plus évidentes que vous pourriez utiliser est une fonction d'évaluation de position. Killzone a utilisé cette technique et elle est décrite dans l'article suivant:

http://www.cgf-ai.com/docs/straatman_remco_killzone_ai.pdf

En fait, vous pourriez probablement utiliser une grande partie de cet article car il décrit la représentation du monde, les données de ligne de vue, les tables de recherche, etc., et vous avez déjà un graphique avec votre grille hexadécimale (il vous suffit d'ajouter des nœuds voisins, qui dans ce cas serait les hexagones voisins à un seul hexagone).

Une autre chose à examiner (c'est assez impressionnant pour le moment, mais un peu plus avancé) est les planificateurs. Je n'ai pas beaucoup lu sur les réseaux de tâches hiérarchiques, je vous laisse le soin. Un planificateur qui pourrait aider est GOAP (Goal Oriented Action Planning)

Ce lien contient de nombreuses informations concernant GOAP: http://web.media.mit.edu/~jorkin/goap.html

Quelque chose que je viens de penser en ce qui concerne votre objectif "Survivre pour X nombre de tours" est l'utilisation d'une carte d'influence. Une carte d'influence est juste une représentation très simple de votre monde où chaque nœud (hexagone) a une seule valeur qui lui est associée (appelée influence).

L'influence peut être calculée de plusieurs façons, mais un exemple pour votre cas pourrait être que les joueurs génèrent +10 d'influence sur l'hexagone sur lequel ils sont placés et +1 d'influence sur l'hexagone qui est désigné comme la portée maximale de la joueur.

Ainsi, par exemple, si vous avez un groupe de joueurs regroupés, l'influence autour d'eux serait relativement élevée. Cela pourrait être interprété par l'IA comme une menace pour sa vie et s'éloigne des points de plus haute influence.

Ce ne sont que quelques techniques que vous pourriez utiliser, mais il y en a d'autres. Si vous voulez quelque chose de simple, utilisez quelque chose comme des FSM hiérarchiques (à peu près des FSM avec chaque état contenant un autre FSM avec un niveau de détail plus élevé). Si vous voulez quelque chose de complexe mais fonctionnel et pratique, utilisez GOAP et les cartes d'influence. Ce n'est pas vraiment important d'être honnête car le POINT PRINCIPAL est de rendre l'IA amusante, et pour ce faire, vous devez implémenter une sorte de "stupidité artificielle". Personne ne voudra jouer une IA infiniment plus intelligente qu'eux, quel que soit l'effort que vous y investissez. Je ne dis pas cela pour paraître dur, je le dis parce qu'il est important que l'IA fasse des erreurs parce que leurs homologues humains le font bien sûr!

Bonne chance! :)

Au fil des ans, j'ai écrit 3 IA de jeu, qui ont toutes joué un jeu respectable.

Deux des cas avaient des options limitées par tour et j'ai donc exploré toutes les possibilités et évalué les positions résultantes - j'ai modifié la profondeur que j'ai recherchée en fonction de la difficulté et il n'a pas fallu beaucoup de couches pour faire un adversaire tout à fait respectable. Je pourrais obtenir quelques couches et toujours avoir une réponse dans une seconde ou deux et c'était sur des processeurs assez anciens. (Tout cela était avant que Windows ne soit sur les lieux.) La qualité de l'analyse de position est TRÈS importante lors de l'utilisation de cette approche.

Le troisième cas n'a pas permis une telle analyse car le nombre de mouvements possibles par tour pourrait facilement dépasser les particules dans l'univers. C'était une situation un peu comme Risque - un territoire avec un certain nombre d'armées, mais vous pouviez effectuer n'importe quel nombre de mouvements par tour, le facteur clé étant que les mouvements prenaient du temps. Une province voisine a généralement pris 1 tour, une de l'autre côté de la carte pourrait en prendre 9.

J'ai utilisé une approche totalement différente ici. J'ai décidé du pourcentage des forces à affecter à la défense et réparti celles-ci en fonction de la valeur du territoire et de la menace ennemie estimée (bien que vous puissiez voir quelles forces votre adversaire a déplacées, vous ne pouviez pas voir où elles allaient - cela supposait l'humain concentrerait ses forces quelque part et pensait qu'il était beaucoup plus probable que ce soit là où ils pourraient tous arriver en même temps plutôt que de façon fragmentaire.) Tout ce qui n'était pas nécessaire pour la défense devenait disponible pour l'attaque. J'ai regardé chaque objectif possible et calculé ce qu'il faudrait pour avoir une bonne chance de le prendre rapidement (une bataille prolongée détruirait essentiellement toute sa production) et j'ai généré un ensemble d'ordres d'attaque pour cela. La valeur de la commande était la valeur de la province, le coût était le nombre d'armées / tours commis à l'attaque. Choisissez la valeur la plus élevée et exécutez les ordres, répétez jusqu'à ce que les forces disponibles ne puissent rien prendre. Le temps d'exécution a été trivial.

J'espère que je vous ai donné quelques idées ici.

Votre note sur l'arrêt / l'attente me suggère que vous faites tout le travail de traitement sur le thread principal de l'application. Vous pouvez, en supposant qu'il existe une prise en charge suffisante des threads dans le SDK d'Android (ce que je suppose qu'il doit y en avoir), décharger la partie "réfléchie" de votre IA sur un thread de travail pendant que le thread principal affiche une IA dans le jeu. .. "UI mais rend autrement normalement.

Bien sûr, il y a de bonnes raisons de ne pas vouloir faire cela, comme ne pas vouloir que l'IA prenne si longtemps de toute façon parce que le joueur s'ennuiera.

Quant à votre question réelle, bien que votre "idée actuelle" soit réalisable, elle est très simple. Mais c'est un bon point de départ. C'est un système où l'IA est purement axée sur les résultats - essayant de maximiser une valeur (dégâts). D'autres options incluent une approche ciblée, où vous choisissez une cible de l'équipe adverse (au hasard, une avec le plus de PV, une combinaison de celles-ci, et cetera), et vous déplacez vers cette cible, en essayant de l'endommager.

Une chose que vous voudrez peut-être envisager est de donner à chaque capacité une statistique de «puissance» ou «d'efficacité» qui est cachée au joueur et qui n'est utilisée qu'en interne par votre IA. Vous déterminez vous-même les valeurs de cette statistique, sur la base de votre propre connaissance des capacités en tant que programmeur du jeu.

Votre IA sélectionnerait ensuite sa capacité la plus élevée et essayerait de l'utiliser, si elle ne peut pas pour une raison quelconque, choisir la suivante, et cetera. S'il est construit de manière suffisamment générale, vous pouvez commencer à lier ces deux systèmes, de sorte qu'une fois que vous avez établi une cible, vous disposez d'heuristiques pour les meilleurs types d'attaques sur cette cible (par exemple, pondérer une attaque qui inflige des dégâts MP plus efficace si la cible a un PM élevé).