Meilleures techniques pour une IA d'un jeu de cartes

27

J'essaie de développer une IA pour un jeu de cartes et je suis un peu coincé sur la technique / l'algorithme que je devrais utiliser. Voici quelques hypothèses sur le jeu:

  • Une fois les cartes distribuées aux joueurs, il n'y a plus de hasard. Je veux dire ici que chaque joueur peut choisir les cartes qu'il joue mais aucun processus aléatoire ne se produit comme lors de la distribution des cartes au début du jeu.
  • Il y a des restrictions sur les cartes qui peuvent être jouées lorsqu'une carte a déjà été jouée.
  • Le joueur qui remporte le pli joue ensuite en premier. Par exemple, le joueur 1 joue une carte, le joueur 2 joue une carte et gagne. Ensuite, le joueur 2 joue une carte, puis le joueur 1 joue.

Je connais beaucoup d'indices / règles (par exemple si je sais que le joueur a les cartes A, B, C alors je devrais jouer D) qui m'aide à gagner au jeu. J'ai donc d'abord voulu utiliser un réseau bayésien pour décrire ces règles. Le problème est que je ne connais aucune probabilité à attribuer, mais je pourrais calculer une heuristique en utilisant l'histoire des jeux joués (contre un humain). Deuxième problème, il est très probable que je ne connais pas toutes les règles et qu'il existe des règles implicites dont l'IA a besoin pour trouver le jeu optimal.

Je ne sais pas si ce serait un bon moyen de développer une IA pour un tel jeu de cartes?

Je me demande également s'il existe d'autres techniques qui seraient mieux adaptées au problème. Par exemple, j'ai jeté un œil à minimax (peut-être avec un algorithme d'élagage), mais serait-ce une bonne option pour ce problème? Je ne suis pas certain car les jeux les plus importants sont au début du jeu quand il y a les paramètres inconnus les plus élevés (la plupart des cartes ne sont pas encore jouées).

LaurentG
la source
1
Grande question! Je n'ai pas de réponse complète. Je voudrais juste ajouter mon 2c: si vous connaissez tous les états possibles dans lesquels votre jeu peut se trouver, alors Minimax serait théoriquement un bon moyen de parcourir cet arbre d'états de jeu. Pourrait avoir des problèmes de performances si cet arbre indique que le jeu est trop grand ...
Shivan Dragon
1
Quel est le but du jeu? Qui gagne? Serait-il possible pour un joueur d'estimer ses chances de gagner le jeu à un moment donné?
VENIR DU
Je ne peux pas expliquer en détails le jeu. Pour gagner, il faut obtenir le plus grand nombre de points (plus que l'autre joueur). Au début, il est difficile / impossible de dire si nous allons gagner. À la fin, nous pouvons être sûrs que pour gagner si l'un a déjà assez de points (l'autre joueur ne peut plus gagner assez de points pour gagner).
LaurentG
1
Est-ce le jeu HeartStone? :)
Lescai Ionel
1
On dirait que je suis dans une situation très similaire à vous, aussi un jeu de cartes, aussi un local (pas la Suisse cependant) et j'essaie aussi de comprendre par où commencer. Une chose que j'ai trouvée intéressante est un évolutif, où vous attribuez des ADN à des joueurs virtuels, puis les opposez les uns aux autres. Vous tuez les perdants et vous élevez les gagnants. Le résultat pourrait être des robots AI assez décents. Je n'ai pas compris comment adapter ce tropiceuro.com/puerto-rico-evolver pour mon jeu de cartes mais je pense que c'est possible.
Andrew Savinykh

Réponses:

11

Votre exemple ressemble à Bridge . Les meilleurs systèmes de bridge utilisent des méthodes Monte Carlo pour sélectionner les mouvements. À un haut niveau:

  • Déterminez les probabilités que chaque carte soit dans une main donnée. Vous savez avec certitude quelles cartes sont dans votre main et quelles cartes ont été jouées. Déterminez la probabilité de toutes les autres cartes en fonction des cartes qui ont été jouées et éventuellement de l'enchère d'un joueur s'il y a enchère. Pour commencer, vous pouvez simplement utiliser une probabilité naïve et égale qu'une carte se trouve dans la main d'un joueur.
  • Maintenant, parcourez autant de jeux "virtuels" que possible. Simulez le jeu d'une carte de votre main, puis déterminez les réponses de vos adversaires en utilisant les règles du jeu et vos probabilités. Pour chaque jeu virtuel, utilisez vos probabilités pour attribuer des cartes à un joueur, puis simulez rapidement le jeu. Supposons que chaque joueur jouera au mieux de ses capacités. Vous connaissez toutes les cartes de votre jeu virtuel pour que chaque joueur puisse jouer parfaitement.
  • Lorsque vous disposez d'un échantillon solide (ou que vous manquez de temps), choisissez le mouvement légal qui vous a donné le meilleur résultat le plus souvent.

Une fois que quelque chose fonctionne, vous pouvez ajouter toutes sortes de stratégies enrichies. Par exemple, modifiez vos probabilités en fonction des jeux historiques d'un joueur, modifiez les probabilités en fonction du style d'un joueur (passif, prudent, agressif), ou même envisagez les effets de joueurs spécifiques jouant ensemble.


Modifier selon le commentaire de LaurentG:

En fin de compte, vous voudrez peut-être abandonner l'idée d'un jeu parfait pour tous les joueurs et remplacer quelque chose de plus réaliste. Conceptuellement, séparez les probabilités qu'une carte se trouve dans la main de quelqu'un (distribution de cartes) de la probabilité qu'un joueur joue une carte légale donnée pendant une main (sélection de cartes).

La sélection des cartes est mûre pour l'apprentissage. Si vous suivez les jeux sur plusieurs jeux, vous pouvez apprendre comment un joueur donné, ou les joueurs en général, ont tendance à jouer en fonction des cartes en main et des cartes qui ont été jouées. Vous pouvez même devenir fantaisiste et modéliser leurs hypothèses sur les cartes qui leur sont cachées.

Il existe également des possibilités d'apprentissage pour la distribution de cartes. Les enchères passées et la sélection de cartes d'un joueur au cours d'une main peuvent révéler un "tell" sur ce qui est caché dans sa main. Vous pouvez utiliser des données historiques pour ajuster les probabilités lors de la création de chaque jeu virtuel.

Marche de Corbin
la source
Merci pour votre réponse intéressante. Vous avez raison, le jeu partage quelques règles avec Bridge. Si je comprends bien, votre IA ne sera pas meilleure que ce que vous avez codé. Existe-t-il un moyen d'utiliser une méthode Monte Carlo et de faire apprendre à l'IA? Serait-il possible d'attribuer les probabilités pour chaque carte en utilisant les événements passés (de tous les jeux précédents)?
LaurentG
Vous pouvez certainement faire apprendre à l'IA. L'astuce serait de séparer les probabilités qu'une carte se trouve dans une main particulière de la probabilité qu'un joueur joue une carte légale donnée une fois qu'elle est dans sa main. Je développerai ci-dessus.
Corbin
6

Un cas d'expérience personnelle récente:

J'ai moi-même travaillé sur un jeu de cartes (Bisca, un jeu portugais à 2 joueurs) et j'ai obtenu de bons résultats en utilisant les méthodes de Monte Carlo, en particulier en utilisant le récent algorithme Information Set Monte Carlo Tree Search (ISMCTS, décrit avec exemple de code source en Python sur http://www.aifactory.co.uk/newsletter/2013_01_reduce_burden.htm ).

Il joue assez bien, avec le coup incorrect occasionnel, juste avec la connaissance des règles du jeu. J'essaie actuellement de le faire pour pouvoir l'améliorer, car selon les informations que j'ai lues à ce sujet (et ses SCTM "parents"), il est possible d'améliorer son jeu avec de l'heuristique ( http: // www .orangehelicopter.com / ed / papers / aiide13.pdf ) et l'inférence de la carte de l'adversaire.

Chat noir
la source
1
ce post est assez difficile à lire (mur de texte). Pourriez-vous le modifier sous une meilleure forme?
gnat
merci pour la réponse de quelqu'un ayant une réelle expérience du problème. d'excellents liens!
luben
3

Je pense que cela dépend des règles du jeu.

Voici ce que je comprends de votre question:

  • Le jeu se joue en tours, chaque joueur jouant une carte par tour
  • Le joueur qui passe en premier peut jouer n'importe quelle carte de son choix
  • Le joueur qui passe en second ne peut jouer que certaines cartes, selon ce qui a été joué en premier
  • Le joueur qui remporte le tour passe en premier au tour suivant
  • Toutes les cartes sont distribuées avant le premier tour

Hypothèses :

  • En pleine connaissance des cartes de l'autre joueur, le joueur qui passe en premier peut décider, pour chacune des siennes, si une carte gagnera le tour ou non (le premier joueur peut jouer une carte de victoire sûre)
  • Si les cartes A et B gagnent toutes les deux lorsqu'elles sont jouées en premier ce tour, jouer A ce tour (et gagner) puis jouer B le tour suivant signifie que B gagnera aussi (les cartes ne perdent pas de valeur)
  • En pleine connaissance des cartes de l'autre joueur, le joueur qui passe en second peut décider si une carte peut gagner ce tour, mais perdra s'il est joué en premier au tour suivant (choisissez la pire carte gagnante)

Exemple de jeu qui suit ces règles:

Le premier joueur joue une carte. Le deuxième joueur doit jouer une carte de la même suite ou perdre. Si les suites correspondent, la carte la plus élevée gagne.

Maintenant, ce jeu est décidé par la chance du tirage au sort et en étant capable de mémoriser quelles cartes ont été jouées afin de connaître la main de votre adversaire.
Dans cette situation, je ferais en sorte que l'IA ne se souvienne que partiellement des cartes jouées, c'est-à-dire que je supprime au hasard de la liste mémorisée un certain pourcentage des cartes jouées (nombre inférieur = IA de difficulté plus élevée), mais pas les plus importantes comme les As ou les Rois. De cette façon, par exemple, l'IA saura qu'il est sûr de jouer une reine de cœur car il se souviendra que l'adversaire n'a pas l'as ou le roi, mais devra calculer une probabilité s'il veut jouer ensuite le 10, parce qu'il pourrait ne pas se rappeler si le Jack est toujours en jeu.
Cela imite la durée d'attention humaine.

TL; DR
Limitez ce que l'IA sait, donc ses décisions ne sont pas parfaites, juste assez bonnes.

Cezar Moise
la source
Merci pour votre réponse. Mais comme dit dans la question, il n'y a pas de chance / pas de hasard après la distribution des cartes. Et un joueur ne connaît pas les cartes des autres joueurs. Il doit faire des hypothèses en utilisant les cartes déjà jouées et certaines "règles".
LaurentG
2
Comme l'idée de retirer au hasard des cartes mémorisées. Cela donne un indice sur le développement de niveaux comme facile, moyen et difficile.
superM