Comment simuler la bataille entre deux joueurs?

Question

J'ai deux joueurs et je veux simuler un jeu entre eux. Les deux ont des attributs (puissance, intelligence ...) et des actions différentes. Le résultat d'une action est basé sur les valeurs d'attribut et un facteur de chance.

Algorithme:

• Construire un arbre de jeu de tous les mouvements possibles pour les deux joueurs
  • L'arbre de jeu aurait probablement une profondeur limitée
  • Chaque niveau appartiendrait à un joueur différent
• Utilisez une certaine heuristique sur les nœuds foliaires pour découvrir la probabilité de gagner pour le joueur qui doit faire un mouvement
• propager les probabilités vers le haut (comme le fait l'algorithme minimax)
• Choisissez un mouvement avec une probabilité la plus élevée
• Continuez au début de cet algorithme

Donc, en gros, il s'agit d'un algorithme minimax. J'ai peu de questions cependant:

1. Comment prendre le facteur de chance dans le compte?
2. Quand je fais un mouvement, dois-je exécuter à nouveau l'algorithme entier? (Construire l'arbre avec une profondeur +1 et un nouveau nœud racine, calculer de nouvelles probabilités ...)
3. Une autre idée pour simuler une bataille?

Merci.

Answer 1

Bien que généralement votre algorithme soit logique, nous ne pouvons garantir que cet algorithme est le meilleur. Par exemple, imaginons deux jeux:

1. Dans le premier jeu, chaque joueur a 2 actions: feu avec un pistolet et frapper avec une épée. Dans ce jeu, chaque étape n'affecte pas d'autres étapes afin de construire un déplacer des arbres Je n'aurai aucun sens ici. Chaque joueur n'a qu'à choisir l'arme et continuer à tirer / frapper et crier 'avec le bouclier ou dessus!«jusqu'à la mort ou gagner.
2. Le deuxième jeu a également la troisième action - Voler le bouclier de l'adversaire. Dans ce cas déplacer des arbres aura plus de sens car il est assez clair que si vous avez décidé de voler le bouclier ennemi de toute façon, il sera plus logique de le voler avant de frapper avec une épée.

Alors que vous ayez besoin de ça déplacer des arbres ou ne dépend pas fortement de vos règles de jeu.

L'option principale concernant facteur de chance Comme je vois, c'est l'inclusion de son influence dans déplacer des arbres ou non. Cela dépend de savoir si facteur de chance affecte chaque action de la même manière. Si c'est vrai, le facteur de chance peut être omis pendant le calcul déplacer des arbres puis appliqué lorsque vous calculerez le résultat de l'action choisie. Sinon, si le facteur de chance affecte différentes actions de manière différente (par exemple, même le perdant complet est capable de tirer sur un ennemi avec un pistolet mais tuer avec une cuillère La compétence nécessite bonne chance), alors le facteur de chance doit être pris en compte lors du calcul des probabilités dans Move Tree.

Que vous ayez besoin ou de ne pas recalculer l'ensemble de l'arbre après chaque nœud dépend si vous pouvez prédire le résultat de l'action choisie avec 100%. Par exemple, dans les échecs, vous pouvez prédire que si vous décidez de déplacer un pion, ce pion se déplacera certainement là où vous avez décidé de le faire. Cela vous permet à chaque étape de prendre la branche choisie dans un arbre de déplacement et de calculer un mouvement de plus pour chaque scénario dedans au lieu de recalculer l'arbre complet de rien. Mais ce n'est pas applicable si le joueur peut décider de tirer avec une arme à feu, mais à cause de la journée malchanceuse, il se tirera en tirerie dans une jambe.

Answer 2

Vous devriez consulter la recherche de Monte Carlo Tree, cela sonne car il s'adaptera très bien à votre problème.

Plutôt que d'utiliser une heuristique, il exécute un jeu complet en utilisant des joueurs aléatoires à chaque branche avant d'élargir l'arbre. La bonne chose à ce sujet est que vous construisez réellement un arbre de probabilités, et vous n'avez pas à étendre l'arbre à la fin ou à un coup sûr avec une heuristique comme Minmax.

MCTS est également la meilleure méthode actuelle du jeu, et actuellement la meilleure pour jouer à des jeux avec des règles inconnues. Pour plus d'effet, vous pouvez utiliser des agents de machine d'état finis au lieu de joueurs aléatoires pour rendre la probabilité plus précise. Et vous pouvez également réduire le facteur de ramification en utilisant un décideur qui saute certaines branches, en utilisant une heuristique dérivée d'apprentissage automatique. (Mais c'est quelque chose que vous feriez pour augmenter la vitesse de la technique)

Si vous pouvez faire Minmax, vous pouvez faire MCTS sans trop de problèmes :) et MCTS peut jouer à des jeux beaucoup plus complexes que Minmax ne le fera jamais, en raison de sa complexité considérablement réduite en comparaison. (Bon si vous avez l'intention d'étendre les règles du jeu en continu)

Jetez un œil ici si vous êtes intéressé:

http://www.aaai.org/papers/aiide/2008/aiide08-036.pdf

Et oui, vous devez le faire à chaque mouvement pour chaque joueur. Ainsi, Minmax et MCTS seront lents; Toutes les techniques basées sur l'arbre de jeu sont lentes.

Avec Minmax, vous pouvez cependant préserver une partie de votre arbre; Déplacez-vous vers la branche qui est votre nouvel état et retirez son parent et les sous-arbres qui y sont connectés. Ensuite, développez une profondeur plus loin dans le sous-arbre qui demeure. Mais c'est de la spéculation; Je n'ai jamais eu le temps de le faire auparavant :) (vous préserverez cependant les erreurs dans vos calculs de probabilité)

Une bonne chose à propos de ces techniques, c'est que lorsque vous les avez construites, ils travaillent. Les techniques d'apprentissage automatique fonctionnent beaucoup plus rapidement, mais nécessitent des heures sinon des jours de formation avant l'utilisation;)

Answer 3

Ce que vous demandez est très "vaste" ... mais a été fait par de nombreux développeurs.

Je vous conseille de commencer à lire un livre sur la conception de jeux comme celui-ci:http://www.amazon.com/game-design-practice-wordware-developers/dp/1556229127/ref=cm_cr_pr_product_top

... et aussi chercher dans www.codeproject.com et www.codeplex.com Pour des exemples d'implémentations de jeux.

Bonne chance,