Récemment un ami passionné par les jeux de sociétés (et notamment les jeux de cartes type CCG / deck building — et non, ce n’est pas @MoDDiB ) m’a demandé s’il était possible d’écrire une I.A. pour des jeux de cartes de ce type (notamment afin de tester des designs de cartes).
La plupart des versions “jeu vidéo” de ces jeux de cartes disposent d’une I.A., qui même si elle n’est pas experte (ie. ne battra pas un joueur professionnel) est tout à fait capable de faire quelques parties contre des humains, tout en restant un challenge pour ceux qui découvrent le jeu.
Je me suis donc posé la question: Mais comment est implémentée cette I.A.? J’ai fouillé le net, et je suis tombé sur plusieurs articles qui pourraient répondre à cette problématique:
Le dernier lien était le plus intéressant, car décrivant un cas concret (je suis pas vraiment un théoricien). En gros, le joueur applique une règle qui calcule ce qu’on nomme le card advantage (ce qui correspond en gros au delta de cartes jouables entre sa main et la main de l’adversaire) et une autre valeur nommée le tempo (qui correspond au nombre de cartes en jeu).
Après réflexion, je me suis dit que ces deux valeurs étaient plus ou moins liées, et qu’on pouvait lier ces deux valeurs en une seule, qui serait en fait la valeur de “puissance” d’une carte (je reviendrai dessus après). On m’a aussi demandé à ce que l’intelligence artificielle soit la plus générique possible. Impossible donc de coder en dur des comportements de jeu.
Chaque carte dispose d’options de jeu, comme “sortez la carte de la main, mettez là en jeu”, ou “tourner cette carte, recevez X ressources”, ou encore “sortez la carte de la main, choisissez une carte de l’adversaire, mettez la dans la défausse”. Du classique pour ceux qui connaissent les CCG et autres jeux de deck-building.
Il est important de préciser que les ressources ont aussi une puissance, étant donné que la plupart des jeux se servent de ressources pour décider si le jeu est fini (par exemple à Magic, la ressource “Points de vie” décide de la fin de la partie, mais dans un autre jeu, ca serait des “Points de victoire”).
J’en suis arrivé à la philosophie suivante:
- Pendant la phase de jeu, l’I.A. regarde la somme de la puissance de chaque carte en jeu pour son coté (main + jeu posé) et la compare à la puissance de l’adversaire. La main de l’adversaire n’étant pas connue, on assigne une valeur par défaut pour chaque carte inconnue, par exemple 100.
- L’I.A. explore toutes les possibilités de jeu en construisant un arbre ordonnée des options de jeu de carte. Par exemple pour l’option “détruisez une carte adverse”, il y aura n entrées dans les possibilités, chacune correspondant à une carte de l’adversaire.
- On trie cet arbre de possibilités en fonction du plus gros avantage reçu. Par exemple, dans le cas de “détruisez la carte adverse”, la carte détruite ayant le plus de puissance sera prioritaire dans l’arbre par rapport à une carte ayant moins de puissance. De plus dans cet exemple précis, la carte que l’IA a joué ayant aussi une puissance, l’option peut se montrer non viable (ie la carte “détruisez la carte adverse” a plus de puissance que toutes les cartes adversaires pouvant être détruites).
- On joue les options dans l’ordre du gain d’avantage.
On fait jouer l’I.A. comme ça jusqu’à la fin de la partie et on note si elle a réussi ou pas, et on applique un algorithme génétique sur les puissances des cartes, en mélangeant plusieurs sets de puissances et en mutant la puissance de chaque carte entre chaque partie (du classique en algorithmique génétique je pense, mais je ne suis pas un spécialiste).
Au bout de n parties (n > 1000?), on devrait normalement avoir une tendance qui se dégage et les puissances des cartes qui devraient être approximativement correctes.
Mes questions maintenant:
- Est ce que la logique de base pour l’I.A. vous semble correcte?
- Dans le cas d’un jeu qui nécessite un deck à construire, certaines cartes peuvent avoir une puissance complètement différentes à causes des différentes synergies possibles. Par exemple, à Magic, personne ne mettrait des gobelins (nécessitant de la mana rouge) dans un deck bleu. Dans ce cas, il y a fort à parier que la carte gobelin perde en puissance si on n’évalue que le deck courant au lieu d’évaluer toutes les cartes. La puissance des cartes est elle donc dépendante du deck, ou de la collection complète de cartes?
