Meilleures techniques pour une IA d'un jeu de cartes

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).

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.

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.

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.