Utilisation de la recherche minimax pour les jeux de cartes avec des informations imparfaites
https://stackoverflow.com//questions/12666119
-
11-12-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je souhaite utiliser la recherche minimax (avec élagage alpha-bêta), ou plutôt la recherche negamax, pour qu'un programme informatique joue à un jeu de cartes.
Le jeu de cartes se compose en réalité de 4 joueurs.Donc pour pouvoir utiliser minimax etc., je simplifie le jeu à "moi" contre les "autres".Après chaque "coup", vous pouvez lire objectivement l'évaluation de l'état actuel du jeu lui-même.Lorsque les 4 joueurs ont placé la carte, le plus haut les gagne tous - et la valeur des cartes compte.
Comme vous ne savez pas exactement comment se fait la répartition des cartes entre les 3 autres joueurs, j'ai pensé qu'il fallait simuler toutes les répartitions ("mondes") possibles avec les cartes qui ne sont pas les vôtres.Vous disposez de 12 cartes, les 3 autres joueurs ont 36 cartes au total.
Mon approche est donc cet algorithme, où player est un nombre compris entre 1 et 3 symbolisant les trois joueurs informatiques pour lesquels le programme pourrait avoir besoin de trouver des mouvements.Et -player représente les adversaires, à savoir les trois autres joueurs ensemble.
private Card computerPickCard(GameState state, ArrayList<Card> cards) {
int bestScore = Integer.MIN_VALUE;
Card bestMove = null;
int nCards = cards.size();
for (int i = 0; i < nCards; i++) {
if (state.moveIsLegal(cards.get(i))) { // if you are allowed to place this card
int score;
GameState futureState = state.testMove(cards.get(i)); // a move is the placing of a card (which returns a new game state)
score = negamaxSearch(-state.getPlayersTurn(), futureState, 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
if (score > bestScore) {
bestScore = score;
bestMove = cards.get(i);
}
}
}
// now bestMove is the card to place
}
private int negamaxSearch(int player, GameState state, int depthLeft, int alpha, int beta) {
ArrayList<Card> cards;
if (player >= 1 && player <= 3) {
cards = state.getCards(player);
}
else {
if (player == -1) {
cards = state.getCards(0);
cards.addAll(state.getCards(2));
cards.addAll(state.getCards(3));
}
else if (player == -2) {
cards = state.getCards(0);
cards.addAll(state.getCards(1));
cards.addAll(state.getCards(3));
}
else {
cards = state.getCards(0);
cards.addAll(state.getCards(1));
cards.addAll(state.getCards(2));
}
}
if (depthLeft <= 0 || state.isEnd()) { // end of recursion as the game is finished or max depth is reached
if (player >= 1 && player <= 3) {
return state.getCurrentPoints(player); // player's points as a positive value (for self)
}
else {
return -state.getCurrentPoints(-player); // player's points as a negative value (for others)
}
}
else {
int score;
int nCards = cards.size();
if (player > 0) { // make one move (it's player's turn)
for (int i = 0; i < nCards; i++) {
GameState futureState = state.testMove(cards.get(i));
if (futureState != null) { // wenn Zug gültig ist
score = negamaxSuche(-player, futureState, depthLeft-1, -beta, -alpha);
if (score >= beta) {
return score;
}
if (score > alpha) {
alpha = score; // alpha acts like max
}
}
}
return alpha;
}
else { // make three moves (it's the others' turn)
for (int i = 0; i < nCards; i++) {
GameState futureState = state.testMove(cards.get(i));
if (futureState != null) { // if move is valid
for (int k = 0; k < nCards; k++) {
if (k != i) {
GameState futureStateLevel2 = futureState.testMove(cards.get(k));
if (futureStateLevel2 != null) { // if move is valid
for (int m = 0; m < nCards; m++) {
if (m != i && m != k) {
GameState futureStateLevel3 = futureStateLevel2.testMove(cards.get(m));
if (futureStateLevel3 != null) { // if move is valid
score = negamaxSuche(-player, futureStateLevel3, depthLeft-1, -beta, -alpha);
if (score >= beta) {
return score;
}
if (score > alpha) {
alpha = score; // alpha acts like max
}
}
}
}
}
}
}
}
}
return alpha;
}
}
}
Cela semble bien fonctionner, mais pour une profondeur de 1 (depthLeft=1), le programme doit déjà calculer 50 000 coups (cartes placées) en moyenne.C'est trop, bien sûr !
Mes questions sont donc :
- La mise en œuvre est-elle correcte du tout ?Pouvez-vous simuler un jeu comme celui-ci ?Concernant les informations imparfaites, notamment ?
- Comment pouvez-vous améliorer l’algorithme en termes de vitesse et de charge de travail ?
- Puis-je, par exemple, réduire l'ensemble des mouvements possibles à un ensemble aléatoire de 50 % pour améliorer la vitesse, tout en gardant de bons résultats ?
- j'ai trouvé Algorithme UCT être une bonne solution (peut-être).Connaissez-vous cet algorithme ?Pouvez-vous m'aider à le mettre en œuvre ?
La solution
La recherche Minimax telle que vous l'avez implémentée n'est pas la bonne approche pour les jeux où il y a tant d'incertitude.Puisque vous ne connaissez pas la répartition des cartes entre les autres joueurs, votre recherche passera un temps exponentiel à explorer des jeux qui ne pourraient pas avoir lieu compte tenu de la répartition réelle des cartes.
Je pense qu'une meilleure approche serait de commencer par de bonnes règles de jeu lorsque vous avez peu ou pas d'informations sur les mains des autres joueurs.Des choses comme:
- Si vous jouez en premier dans un tour, jouez votre carte la plus basse car vous avez peu de chances de gagner le tour.
- Si vous jouez en dernier dans un tour, jouez votre carte la plus basse qui remportera le tour.Si vous ne parvenez pas à gagner la manche, jouez votre carte la plus basse.
Faites en sorte que votre programme ne se soucie pas initialement de la recherche et respecte simplement ces règles et faites-le supposer que tous les autres joueurs utiliseront également ces heuristiques. À mesure que le programme observe les cartes jouées par le premier et le dernier joueur de chaque tour, il peut créer un tableau d'informations sur les cartes que chaque joueur détient probablement.Par exemple.un 9 aurait gagné ce tour, mais le joueur 3 ne l'a pas joué donc il ne doit pas avoir de carte 9 ou plus.Au fur et à mesure que les informations sont collectées sur la main de chaque joueur, l'espace de recherche sera éventuellement limité au point où une recherche minimax de jeux possibles pourrait produire des informations utiles sur la prochaine carte à jouer.
Autres conseils
Je souhaite clarifier des détails sur lesquels la réponse acceptée n'entre pas vraiment en compte.
Dans de nombreux jeux de cartes, vous pouvez échantillonner les cartes inconnues que votre adversaire pourrait posséder au lieu de toutes les générer.Vous pouvez prendre en compte des informations telles que les couleurs courtes et la probabilité de détenir certaines cartes jouées jusqu'à présent lors de cet échantillonnage pour pondérer la probabilité de chaque main possible (chaque main est un monde possible que nous résoudrons indépendamment).Ensuite, vous résolvez chaque main en utilisant une recherche d'informations parfaite.Le meilleur coup sur tous ces mondes est souvent le meilleur coup dans l’ensemble – avec quelques réserves.
Dans des jeux comme le poker, cela ne fonctionnera pas très bien : le jeu repose uniquement sur les informations cachées.Vous devez équilibrer précisément vos actions pour garder cachées les informations sur votre main.
Mais, dans des jeux comme les jeux de cartes basés sur des astuces, cela fonctionne plutôt bien, d'autant plus que de nouvelles informations sont révélées en permanence.De toute façon, les très bons joueurs ont une bonne idée de ce que chacun détient.Ainsi, des programmes raisonnablement solides de Skat et de Bridge ont été basés sur ces idées.
Si vous pouvez résoudre complètement le monde sous-jacent, c'est mieux, mais si vous n'y parvenez pas, vous pouvez utiliser minimax ou UCT pour choisir le meilleur mouvement dans chaque monde.Il existe également des algorithmes hybrides (ISMCTS) qui tentent de mélanger ce processus.Faites attention aux affirmations ici.Les approches d'échantillonnage simples sont plus faciles à coder : vous devriez essayer l'approche la plus simple avant une approche plus complexe.
Voici quelques documents de recherche qui donneront plus d’informations sur les cas où l’approche d’échantillonnage des informations imparfaites a bien fonctionné :
Comprendre le succès de l'échantillonnage de Monte Carlo d'informations parfaites dans la recherche dans l'arbre de jeu (Cet article analyse dans quels cas l’approche d’échantillonnage est susceptible de fonctionner.)
Améliorer l'évaluation, l'inférence et la recherche d'état dans les jeux de cartes basés sur des astuces (Cet article décrit l'utilisation de l'échantillonnage dans Skat)
Informations imparfaites dans un jeu informatique complexe (Cet article décrit l'échantillonnage dans Bridge)
Ensemble d'informations Recherche par arbre de Monte Carlo (Cet article fusionne l'échantillonnage et la recherche arborescente UCT/Monte Carlo pour éviter les problèmes de la première référence.)
Le problème des approches basées sur des règles dans la réponse acceptée est qu'elles ne peuvent pas tirer parti des ressources informatiques au-delà de celles requises pour créer les règles initiales.De plus, les approches basées sur des règles seront limitées par la puissance des règles que vous pouvez écrire.Les approches basées sur la recherche peuvent utiliser la puissance de la recherche combinatoire pour produire un jeu beaucoup plus puissant que l'auteur du programme.
