Minimax pour Bomberman

Je développe un clone du jeu Bomberman et j'expérimente différents types d'IA. J'ai d'abord utilisé la recherche dans l'espace d'état avec A * et maintenant je veux essayer une approche différente avec l'algorithme Minimax. Mon problème est que chaque article de minimax que j'ai trouvé remplaçait les joueurs supposés. Mais à Bomberman, chaque joueur fait une action en même temps. Je pense que je pourrais générer tous les états possibles pour un tick de jeu, mais avec quatre joueurs et 5 actions de base (4 mouvements et bombe), cela donne 5 ^ 4 états au premier niveau de l'arbre de jeu. Cette valeur augmentera de façon exponentielle à chaque niveau suivant. Suis-je en train de manquer quelque chose? Existe-t-il des moyens de le mettre en œuvre ou dois-je utiliser un algorithme totalement différent? Merci pour toutes suggestions

Les jeux de stratégie en temps réel comme Bomber Man ont du mal avec l'IA. Vous voulez qu'il soit intelligent, mais en même temps il ne peut pas être parfait.

Si l'IA est parfaite, vos joueurs seront frustrés. Soit parce qu'ils perdent toujours, soit que vous obtenez 0,3 images par seconde.

S'il n'est pas assez intelligent, vos joueurs s'ennuieront.

Ma recommandation est d'avoir deux fonctions d'IA, l'une qui détermine où va l'IA, l'autre qui détermine le meilleur moment pour larguer une bombe. Vous pouvez utiliser des choses comme la prédiction de mouvement pour déterminer si un ennemi se déplace vers un endroit qui sera dangereux si une bombe est larguée à l'emplacement actuel.

Selon la difficulté, vous pouvez modifier ces fonctions pour améliorer ou diminuer la difficulté.

Comme vous l'avez remarqué, Bomberman est beaucoup trop complexe pour être simulé comme un jeu au tour par tour. L'extrapolation de toute décision propre possible et de toutes les décisions possibles de tous les autres joueurs ne fonctionne tout simplement pas.

Au lieu de cela, vous devriez plutôt utiliser une approche plus stratégique.

Vous devriez vous demander: comment un joueur humain prend-il des décisions en jouant à Bomberman? Habituellement, un joueur doit suivre quatre priorités de base:

1. éviter les zones d'explosion des bombes
2. placer des bombes pour que les autres ne puissent pas éviter leurs zones d'explosion
3. collecter des bonus
4. placer des bombes pour faire exploser des rochers

La première priorité peut être remplie en créant une "carte des dangers". Lorsqu'une bombe est placée, toutes les tuiles couvertes doivent être marquées comme "dangereuses". Plus tôt la bombe explose (gardez à l'esprit les réactions en chaîne!), Plus le niveau de danger est élevé. Chaque fois que l'IA remarque qu'elle se trouve sur un terrain à haut risque, elle doit s'éloigner. Quand il trace un chemin (pour une raison quelconque), les champs avec un niveau de danger élevé doivent être évités (peuvent être mis en œuvre en leur ajoutant artificiellement un coût de chemin plus élevé).

Le calcul de la carte des dangers peut être encore amélioré pour protéger l'IA des décisions stupides (comme entrer dans des zones difficiles à échapper lorsqu'un autre joueur est proche).

Cela devrait déjà créer une IA défensive raisonnable. Et qu'en est-il de l'offense?

Lorsque l'IA se rend compte qu'elle est raisonnablement sûre en ce moment, elle doit planifier des manœuvres offensives: elle doit envisager comment elle peut augmenter la carte des dangers autour des autres joueurs en plaçant des bombes elle-même. Lors du choix d'un emplacement pour planter une bombe, il doit préférer des emplacements proches afin qu'il n'ait pas à se déplacer aussi loin. Il devrait également ignorer les emplacements des bombes lorsque la carte de danger qui en résulte ne permet pas une issue de secours raisonnable.

Je pense que je pourrais générer tous les états possibles pour un tick de jeu, mais avec quatre joueurs et 5 actions de base (4 coups et bombe), cela donne 5 ^ 4 états au premier niveau de l'arbre de jeu.

Correct! Vous devez rechercher toutes les 5 ^ 4 (ou même 6 ^ 4, car vous pouvez marcher dans 4 directions, arrêter et "mettre une bombe"?) Pour chaque tick de jeu. MAIS, lorsqu'un joueur a déjà décidé de se déplacer, cela prend un certain temps avant que le mouvement ne soit exécuté (par exemple 10 ticks de jeu). Pendant cette période, le nombre de possibilités diminue.

Cette valeur augmentera de façon exponentielle à chaque niveau suivant. Suis-je en train de manquer quelque chose? Existe-t-il des moyens de le mettre en œuvre ou dois-je utiliser un algorithme totalement différent?

Vous pouvez utiliser une table de hachage pour calculer une seule fois le même état de jeu "sous-arbre". Imaginez que le joueur A monte et descend, tandis que tous les autres joueurs "attendent", vous vous retrouvez dans le même état de jeu. C'est la même chose que pour "gauche-droite" ou "droite-gauche". Déplacer également "vers le haut puis vers la gauche" et "vers la gauche puis vers le haut" entraîne le même état. En utilisant une table de hachage, vous pouvez "réutiliser" le score calculé pour un état de jeu qui a déjà été évalué. Cela réduit considérablement la vitesse de croissance. Mathématiquement, cela réduit la base de votre fonction de croissance exponentielle. Pour avoir une idée de combien cela réduit la complexité, regardons les mouvements possibles pour un seul joueur par rapport aux positions accessibles sur la carte (= différents états de jeu) si le joueur peut simplement se déplacer vers le haut / bas / gauche / droite / stop .

profondeur 1: 5 mouvements, 5 états différents, 5 états supplémentaires pour cette récursivité

profondeur 2:25 mouvements, 13 états différents, 8 états supplémentaires pour cette récursivité

profondeur 3: 6125 mouvements, 25 états différents, 12 états supplémentaires pour cette récursivité

Pour visualiser cela, répondez-vous: quels champs de la carte peuvent être atteints en un seul mouvement, deux mouvements, trois mouvements. La réponse est: tous les champs avec une distance maximale = 1, 2 ou 3 de la position de départ.

Lorsque vous utilisez un HashTable, vous n'avez qu'à évaluer une fois chaque état de jeu accessible (dans notre exemple 25 en profondeur 3). Alors que sans HashTable, vous devez les évaluer plusieurs fois, ce qui signifierait 6125 évaluations au lieu de 25 au niveau de profondeur 3. Le meilleur: Une fois que vous avez calculé une entrée HashTable, vous pouvez la réutiliser dans des étapes ultérieures ...

Vous pouvez également utiliser des sous-arbres d'approfondissement incrémentiel et d'élagage alpha-bêta qui ne valent pas la peine d'être approfondis. Pour les échecs, cela réduit le nombre de nœuds recherchés à environ 1%. Une courte introduction à l'élagage alpha-bêta peut être trouvée sous forme de vidéo ici: http://www.teachingtree.co/cs/watch?concept_name=Alpha-beta+Pruning

Un bon début pour d'autres études est http://chessprogramming.wikispaces.com/Search . La page est liée aux échecs, mais les algorithmes de recherche et d'optimisation sont tout à fait les mêmes.

Un autre algorithme d'intelligence artificielle (mais complexe) - qui conviendrait mieux au jeu - est "l'apprentissage par différence temporelle".

Cordialement

Stefan

PS: Si vous réduisez le nombre d'états de jeu possibles (par exemple très petite taille de la carte, une seule bombe par joueur, rien d'autre), il y a une chance de pré-calculer une évaluation pour tous les états de jeu.

--Éditer--

Vous pouvez également utiliser les résultats calculés hors ligne des calculs minimax pour former un réseau neuronal. Ou vous pouvez les utiliser pour évaluer / comparer des stratégies mises en œuvre à la main. Par exemple, vous pouvez implémenter certaines des "personnalités" suggérées et des heuristiques qui détectent, dans quelles situations quelle stratégie est bonne. Par conséquent, vous devez "classer" les situations (par exemple, les états du jeu). Cela pourrait également être géré par un réseau neuronal: former un réseau neuronal pour prédire laquelle des stratégies codées à la main joue le mieux dans la situation actuelle et l'exécuter. Cela devrait produire de très bonnes décisions en temps réel pour un vrai jeu. Bien mieux qu'une recherche à faible profondeur qui peut être réalisée autrement, car peu importe le temps que prennent les calculs hors ligne (ils sont avant le jeu).

- modifier # 2 -

Si vous recalculez uniquement vos meilleurs coups toutes les 1 seconde, vous pouvez également essayer de faire un rabotage de niveau supérieur. Qu'est-ce que je veux dire par là? Vous savez combien de coups vous pouvez faire en 1 seconde. Ainsi, vous pouvez faire une liste de positions accessibles (par exemple, si cela devait être 3 mouvements en 1 seconde, vous auriez 25 positions accessibles). Ensuite, vous pourriez planifier comme: aller à "position x et placer une bombe". Comme certains l'ont suggéré, vous pouvez créer une carte "danger", qui est utilisée pour l'algorithme de routage (comment aller à la position x? Quel chemin devrait être préféré [il y a quelques variations possibles dans la plupart des cas]). Cela consomme moins de mémoire par rapport à un énorme HashTable, mais produit des résultats moins optimaux. Mais comme il utilise moins de mémoire, il pourrait être plus rapide en raison des effets de mise en cache (meilleure utilisation de vos caches de mémoire L1 / L2).

EN PLUS: Vous pouvez effectuer des recherches préalables qui ne contiennent que des mouvements pour un joueur chacun pour trier les variations qui entraînent une perte. Par conséquent, retirez tous les autres joueurs du jeu ... Enregistrez les combinaisons que chaque joueur peut choisir sans perdre. S'il n'y a que des coups perdus, recherchez les combinaisons de coups où le joueur reste en vie le plus longtemps. Pour stocker / traiter ce type de structures arborescentes, vous devez utiliser un tableau avec des pointeurs d'index comme celui-ci:

class Gamestate {
  int value;
  int bestmove;
  int moves[5];
};

#define MAX 1000000
Gamestate[MAX] tree;

int rootindex = 0;
int nextfree = 1;

Chaque état a une "valeur" d'évaluation et des liens vers les prochains Gamestates lors du déplacement (0 = arrêt, 1 = haut, 2 = droite, 3 = bas, 4 = gauche) en stockant l'index du tableau dans "arborescence" en mouvements [0 ] se déplace [4]. Pour construire votre arborescence de manière récursive, cela pourrait ressembler à ceci:

const int dx[5] = { 0,  0, 1, 0, -1 };
const int dy[5] = { 0, -1, 0, 1,  0 };

int search(int x, int y, int current_state, int depth_left) {
  // TODO: simulate bombs here...
  if (died) return RESULT_DEAD;

  if (depth_left == 0) {
    return estimate_result();
  }

  int bestresult = RESULT_DEAD;

  for(int m=0; m<5; ++m) {
    int nx = x + dx[m];
    int ny = y + dy[m];
    if (m == 0 || is_map_free(nx,ny)) {
      int newstateindex = nextfree;
      tree[current_state].move[m] = newstateindex ;
      ++nextfree;

      if (newstateindex >= MAX) { 
        // ERROR-MESSAGE!!!
      }

      do_move(m, &undodata);
      int result = search(nx, ny, newstateindex, depth_left-1);
      undo_move(undodata);

      if (result == RESULT_DEAD) {
        tree[current_state].move[m] = -1; // cut subtree...
      }

      if (result > bestresult) {
        bestresult = result;
        tree[current_state].bestmove = m;
      }
    }
  }

  return bestresult;
}

Ce type d'arborescence est beaucoup plus rapide, car l'allocation dynamique de la mémoire est vraiment très lente! Mais, le stockage de l'arbre de recherche est assez lent non plus ... C'est donc plus une inspiration.

Serait-il utile d' imaginer que tout le monde se relait?

Techniquement, dans le système sous-jacent, ils le font réellement, mais comme les choses sont entrelacées et se chevauchent, elles semblent fonctionner simultanément.

N'oubliez pas non plus que vous n'avez pas à exécuter l'IA après chaque image d'animation. De nombreux jeux occasionnels réussis n'exécutent l'algorithme d'IA qu'une fois par seconde environ, fournissant aux personnages contrôlés par l'IA des informations sur l'endroit où ils sont censés aller ou ce qu'ils sont censés faire, puis ces informations sont utilisées pour contrôler les personnages de l'IA sur les autres cadres.