Comment écrire une IA pour un jeu de cartes

Mardi 2 juillet 2024

Depuis l'arrivée de ChatGPT en novembre 2022, l'IA semble être partout. On me demande parfois comment fonctionne l'IA des jeux de cartes sur Whisthub, donc il m'a semblé être le bon moment pour écrire un article de blog à ce sujet. Attention, cet article est long et peut devenir un peu technique ! C'est parti.

Tout d'abord, la façon dont l'IA de Whisthub fonctionne n'est pas nécessairement la seule bonne manière de construire une IA pour un jeu de cartes. Je ne suis absolument pas un expert en IA, mais j'ai constaté que cette approche fonctionnait vraiment bien, et après tout, ce ne sont que des jeux de cartes, ce n'est pas comme si je construisais des voitures autonomes.

Avant de commencer, il est utile de rappeler comment fonctionnent des modèles d'IA comme ChatGPT. Ce sont des réseaux de neurones gigantesques, comptant des milliards de paramètres, entraînés sur d'énormes quantités de données – dans le cas de ChatGPT, quasiment l'ensemble de l'internet public. Bien qu'il soit tout à fait possible d'entraîner un tel modèle pour des jeux de cartes aussi, le problème est qu'il faut des données d'entraînement. Beaucoup de données. Si vous écrivez une IA pour un jeu de cartes de niche, il y a fort peu de chances que vous trouviez un jeu de données contenant des millions de parties jouées par des humains.

Si vous avez lu l'histoire de Whisthub, vous savez que j'étais tout à fait conscient de ce problème lors du développement initial de Whisthub. En théorie, il est aussi possible d'entraîner un modèle d'IA en le laissant jouer des cartes aléatoires autorisées par les règles, puis en le laissant apprendre du résultat, mais je n'avais absolument aucune idée de comment m'attaquer à une tâche aussi colossale. C'est pourquoi j'ai opté pour une approche plus simple, avec une IA qui se contente de suivre un ensemble de règles simples et déterministes.

Fondamentalement, l'IA de tous les jeux de cartes sur Whisthub se compose de deux parties : chaque joueur IA garde une trace de la probabilité qu'une carte donnée soit détenue par un joueur donné. On appelle cela la matrice des hypothèses, et elle est constamment mise à jour tout au long de la partie en fonction de ce que font les joueurs. Notez que cela signifie que l'IA joue avec exactement la même information qu'un joueur humain. L'IA ne connaît pas les cartes de ses adversaires, elle ne fait qu'estimer leurs probabilités.

À partir de la matrice des hypothèses, on peut alors effectuer des calculs plus complexes, comme « quelle est la probabilité que ce joueur ait encore du cœur ♥ ? ». Ces probabilités dérivées sont ensuite utilisées par la seconde partie de l'IA : un immense arbre de décision qui contient essentiellement un ensemble de règles déterministes, par exemple « si la probabilité que mon partenaire soit démuni dans cette couleur est supérieure à x, jouer cette carte ». Cet arbre de décision est ensuite ajusté manuellement à l'aide de centaines de tests pour s'assurer que le résultat ressemble un minimum à ce qu'un humain ferait.

La matrice des hypothèses

Comme mentionné, la matrice des hypothèses contient les probabilités qu'une carte donnée soit détenue par un joueur donné. Imaginons que nous jouions à un jeu de cartes à 3 joueurs et que chaque joueur ait deux cartes en main : la matrice des hypothèses ressemblerait alors initialement à ceci

Nous n'avons encore aucune information sur les cartes, mais nous savons que chaque carte doit forcément être détenue soit par Ross, soit par Rachel, donc la somme verticale doit valoir 1, soit

Comme il n'y a aucune raison qu'une carte donnée soit plutôt détenue par Ross que par Rachel, les probabilités sont initialement uniformes, ce qui signifie qu'elles valent toutes $\frac{1}{2}$. Pour un jeu de cartes joué à 4 joueurs – comme c'est le cas pour tous les jeux sur Whisthub – cela signifierait qu'elles valent toutes $\frac{1}{3}$ au départ, mais gardons l'exemple simple avec seulement deux adversaires.

Notez que la matrice des hypothèses a une autre propriété intéressante : la somme horizontale doit toujours être égale au nombre de cartes $n$ que possède chaque joueur. En théorie, cela revient à dire que l'espérance du nombre de cartes détenues par un joueur $E\left(n_i\right)$ est égale à la somme des probabilités individuelles $p_{ij}$, soit

Dans notre exemple, on sait que chaque joueur a deux cartes, donc la somme horizontale doit toujours être égale à 2, ce que vous pouvez effectivement vérifier. Le fait que l'on connaisse toutes les sommes verticales et horizontales constitue les conditions aux limites de la matrice des hypothèses : peu importe comment les valeurs de la matrice évoluent, elles doivent toujours respecter ces contraintes de sommes horizontale et verticale.

Tout cela est bien joli, mais des probabilités uniformes ne sont pas vraiment utiles. C'est pourquoi la matrice des hypothèses est constamment mise à jour en fonction de ce qui se passe dans la partie. L'exemple le plus évident est celui d'une carte qui est jouée. Imaginons que, dans l'exemple ci-dessus, Ross joue ♥A. Nous pourrions alors mettre à jour notre matrice comme suit

Vous voyez ce qui s'est passé ? Ross a joué ♥A, ce qui révèle qu'il détenait effectivement cette carte, donc $p_{\text{Ross},\text{A}} = 1$. Cela signifie évidemment aussi que Rachel ne peut plus avoir ♥A, donc cette probabilité devient 0. On peut ensuite mettre à jour le reste de la matrice en se basant sur nos conditions aux limites. On n'a rien appris de spécial sur les autres cartes de Ross, donc on suppose que les probabilités sont restées uniformes, ce qui ne peut signifier qu'une chose : elles valent désormais $\frac{1}{3}$ au lieu de $\frac{1}{2}$, puisque la somme horizontale doit toujours valoir 2. On peut alors facilement trouver les probabilités restantes des cartes de Rachel, soit $\frac{2}{3}$, grâce à nos sommes verticales qui doivent elles aussi toujours valoir 1.

Notez que mettre à jour la matrice est facile dans l'exemple ci-dessus, mais cela devient beaucoup plus compliqué pour des jeux à 4 joueurs (et donc trois adversaires). Le problème ici est que nos conditions aux limites ne sont pas linéairement indépendantes, ce qui signifie que si on en fait un système d'équations, le déterminant devient nul et il faut des conditions aux limites supplémentaires pour résoudre les probabilités inconnues. C'était en fait l'un des problèmes les plus difficiles à résoudre pour l'IA, et j'ai fini par résoudre la matrice des hypothèses avec une approche itérative. Concrètement, cela signifie que l'on redistribue itérativement les probabilités restantes jusqu'à ce que les conditions aux limites soient à nouveau suffisamment respectées.

Il est évident que jouer une certaine carte révèle une certaine information, mais il existe d'autres façons de révéler de l'information. Dans les jeux de cartes, ne pas pouvoir fournir la couleur demandée indique souvent que ce joueur est démuni dans cette couleur. Dans ce cas, on peut mettre à 0 les probabilités dans la matrice pour ce joueur pour toutes les cartes de cette couleur, puis relancer l'algorithme de mise à jour. On peut voir les choses ainsi : si le jeu révèle qu'un joueur est démuni dans une couleur, alors il y a une probabilité plus élevée qu'il détienne des cartes dans les autres couleurs, et inversement, il y a une probabilité plus élevée que les autres joueurs détiennent les cartes de la couleur en question. La mise à jour de la matrice des hypothèses reflète cela de façon élégante.

Les fonctions de forme

Une autre façon intéressante de révéler de l'information sur les cartes se produit dans les jeux avec un système d'enchères, comme le whist à la couleur. Dans ce jeu, un joueur peut proposer une certaine couleur, ce qui indique souvent qu'il possède beaucoup de cartes dans cette couleur, et probablement des cartes hautes également. Nous pouvons également refléter cela dans la matrice des hypothèses.

Pour cela, l'IA de Whisthub utilise le concept de fonctions de forme. Une fonction de forme contient essentiellement la probabilité qu'une carte donnée d'une couleur soit détenue par un joueur, en fonction de ce qu'il a proposé. La fonction de forme d'une enchère comme « Abondance ♥9 » peut par exemple ressembler à ceci

Cela signifie que si un joueur annonce Abondance ♥9, l'IA suppose que la probabilité que ce joueur ait ♥A est d'environ 89 %, 86 % pour ♥K, et ainsi de suite. La somme de toutes ces probabilités $\sum{p_{i}}$ est donc l'espérance $E\left(n\right)$ du nombre de cartes que le joueur détient dans cette couleur.

Attendez une minute. La fonction de forme a des valeurs pour les 13 cartes, mais que se passe-t-il si j'en détiens moi-même certaines ? Dans ce cas, je sais que l'adversaire ne peut pas avoir ces cartes-là !

Eh bien, les fonctions de forme doivent être considérées comme des formes générales, qui sont ensuite ajustées à ce qu'un joueur peut effectivement avoir en main, sur la base des informations que nous avons de notre propre main. Nous avons développé un algorithme spécifique pour cela, qui a la propriété de préserver l'espérance de la fonction de forme. Par exemple, si la somme de toutes les valeurs de la fonction de forme est 6, cela signifie que nous nous attendons à ce que ce joueur détienne 6 cartes dans la couleur donnée, et l'algorithme d'ajustement redistribue les probabilités de façon à préserver cette espérance.

Par exemple, imaginons que notre propre main ressemble à

et que notre adversaire annonce Abondance ♥9, alors la fonction de forme se transforme en

Si vous regardez attentivement, vous voyez que les probabilités de ♥Q et ♥6 sont « redistribuées » sur les autres cartes, de sorte que le nombre attendu de cartes détenues par le joueur d'abondance reste le même. Par conséquent, les probabilités des autres cartes deviennent toutes légèrement plus élevées. Notez d'ailleurs que l'algorithme de redistribution ne redistribue pas les probabilités « à l'aveugle » : il s'assure qu'aucune probabilité ne peut jamais dépasser 1.

Les différentes fonctions de forme utilisées dans l'IA ont initialement été construites de façon purement intuitive, par moi-même. Simplement quelque chose qui me semblait raisonnable, mais qui ne reposait sur rien de concret. Cependant, une fois que j'ai disposé de quelques millions de journaux de parties réellement jouées, j'ai retravaillé les fonctions de forme pour qu'elles se basent réellement sur ce qui se passe dans de vraies parties. Par exemple, j'ai enregistré la fréquence à laquelle quelqu'un détient ♥A lorsqu'il propose une couleur, la fréquence pour ♥K, et ainsi de suite. C'est cela qui devient alors la fonction de forme.

D'une certaine manière, on pourrait considérer cela comme un entraînement de l'IA. Ce n'est pas vraiment comme cela que fonctionne l'entraînement dans des modèles d'IA comme ChatGPT, mais il y avait au moins désormais une boucle de rétroaction. Le meilleur dans tout ça, c'est qu'une fois que j'ai mis à jour les fonctions de forme pour qu'elles se basent sur des situations réelles – qui différaient honnêtement beaucoup de mes estimations initiales – l'IA a commencé à jouer nettement mieux et de façon plus humaine. C'est difficile à décrire précisément ce qui m'a fait le remarquer, mais ce fut l'une des sensations les plus gratifiantes que j'ai ressenties durant tout le développement de Whisthub !

Les répartitions des cartes

Connaître les probabilités individuelles qu'une carte soit détenue par un joueur donné, c'est bien joli, mais ce n'est pas très utile en soi. La véritable force réside dans la capacité à en faire des calculs dérivés. Par exemple, à l'aide de la matrice des hypothèses, on peut calculer la probabilité qu'un joueur donné soit démuni dans une couleur, ou la probabilité que, si l'on joue une certaine carte, plus personne ne puisse encore la surpasser.

Un grand nombre de ces probabilités dérivées se calculent en parcourant toutes les façons possibles de répartir les cartes restantes entre les autres joueurs, ce que nous appelons les répartitions. Par exemple, imaginons que l'on sache qu'il reste 2 cartes de trèfle ♣. On peut modéliser ces répartitions comme 2 boules à répartir sur 3 compartiments

Pour chacune de ces répartitions, on peut facilement déterminer si elle satisfait la condition recherchée, par exemple lorsqu'on calcule la probabilité que tous les joueurs après nous soient démunis dans une couleur. À l'aide des probabilités de notre matrice des hypothèses, on peut calculer la probabilité de chaque répartition, et en les additionnant, on obtient la probabilité de la condition recherchée.

Notez que dans les répartitions ci-dessus, on a fait abstraction de la valeur des cartes. En réalité, ♣A| |♣2 pourrait donner lieu à une situation fondamentalement différente de ♣2| |♣A ! Cependant, le nombre de répartitions possibles devient alors tellement énorme que ce n'est simplement plus faisable. Souvent, on n'en a d'ailleurs pas vraiment besoin. Par exemple, si l'on a besoin de la probabilité que le joueur derrière nous puisse surpasser notre ♦Q avec ♦A ou ♦K, on n'a pas besoin des répartitions pour cela : on peut simplement la calculer comme la probabilité que ce joueur ne manque pas à la fois de ♦A et de ♦K, soit en termes mathématiques

L'approche consistant à examiner toutes les répartitions et à leur attribuer des probabilités peut être considérée comme une forme de simulation de Monte-Carlo à profondeur limitée. C'est par exemple une technique courante dans les programmes d'IA aux échecs, mais dans ce cas, les simulations anticipent plusieurs coups à l'avance, alors qu'avec les répartitions, on ne regarde que les situations actuellement possibles.

L'arbre de décision

Le fait que nous ayons désormais un moyen de calculer des probabilités pour des situations spécifiques nous permet de simuler la façon dont un humain raisonnerait en jouant aux cartes. Prenons par exemple le cas où l'on tire l'atout au whist à la couleur, c'est-à-dire qu'on joue l'atout à plusieurs reprises pour s'assurer que les adversaires ne puissent plus couper les plis suivants dans d'autres couleurs. On tire généralement l'atout au moins deux fois, mais la question de savoir s'il faut le faire une troisième fois peut dépendre de la probabilité que les adversaires aient encore de l'atout.

Bien que cela paraisse simple sur papier, la question ici est bien sûr de savoir quelle limite utiliser pour ces probabilités. À partir de quelle probabilité que les adversaires aient encore de l'atout faut-il tirer une troisième fois ? 50 % ? 75 % ? 90 % ? La vérité, c'est qu'il n'existe pas de réponse unique à cela – tout comme deux humains n'ont jamais exactement le même style de jeu – et c'est là qu'entre en jeu ce que j'appelle l'arbre de décision. Cet arbre de décision identifie certaines situations de jeu et prend ensuite une décision sur la base d'une probabilité et d'un seuil arbitraire pour cette probabilité. Au fond, il s'agit en réalité tout simplement d'une immense structure de conditions (if-else).

Mais alors, comment détermine-t-on les seuils de probabilité utilisés par l'arbre de décision ? Eh bien, essentiellement au feeling, en se posant constamment la question

En tant qu'humain, quelle probabilité aurait du sens dans cette situation ?

Cependant, rappelez-vous que les valeurs exactes des seuils n'ont en réalité pas énormément d'importance. Ce qui compte, c'est que l'IA joue de façon raisonnable et humaine vue de l'extérieur. Ce qui se passe en coulisses n'a en fait aucune importance.

Pour s'en assurer, nous avons mis en place des centaines de cas de test qui vérifient ce que fait l'IA dans des situations spécifiques. Ce genre de cas de test ressemble typiquement à ceci

it('sortir avec la carte d\'atout la plus haute', function() {

  this.log = `
    1: ♥Q64 ♦AJ106 ♣642 ♠AJ7
    2: ♥K973 ♦K5 ♣1085 ♠Q432
    3: ♥J85 ♦Q7432 ♣AQJ ♠K6
    0: ♥A102 ♦98 ♣K973 ♠10985
    1: Propose ♦
    2: Propose ♠
    3: Accept ♦8
    0: Propose ♣
    2: Pass
    0: Pass
  `;
  let card = this.decide();
  expect(card).to.equal('♦A');

});

Les cas de test sont généralement trouvés en jouant manuellement contre l'IA jusqu'à ce qu'on remarque qu'elle fait quelque chose d'étrange. Quand cela arrive, on crée un test pour cette situation de jeu spécifique, ce qui permet ensuite de plonger dans l'arbre de décision et de voir où l'IA prend réellement sa décision. Cela signifie souvent qu'il faut ajouter une condition spécifique à l'arbre de décision pour cette situation, mais il arrive aussi qu'il s'avère que les seuils mentionnés plus haut doivent être affinés.

Une fois la décision de l'IA corrigée dans un cas de test spécifique, il est également essentiel de relancer tous les cas de test existants pour s'assurer que le comportement existant n'a pas changé à cause de notre correction. En génie logiciel, on appelle cela une régression : on veut éviter qu'en corrigeant quelque chose à un endroit, on ne casse quelque chose ailleurs.

Notez que c'est l'un des grands avantages d'un arbre de décision : il est extrêmement facile de suivre le raisonnement de l'IA et de comprendre pourquoi elle prend une décision donnée. C'est bien plus difficile avec des réseaux de neurones, comme ChatGPT par exemple, qui se comportent essentiellement comme une boîte noire où il est impossible de comprendre pourquoi l'IA a pris une décision donnée. Cela rendrait aussi plus difficile l'amélioration de l'IA, la réponse consistant alors souvent simplement à obtenir plus – ou de meilleures – données d'entraînement. Je considère donc le fait que l'IA de Whisthub ne soit pas une boîte noire comme un avantage considérable.

Une autre façon de trouver des cas de test pertinents consiste à faire tourner des simulations où l'IA joue contre elle-même. Cela est particulièrement utile pour les situations de jeu rares et donc difficiles à rencontrer en jouant manuellement contre l'IA. Dans ce cas, on programme temporairement une condition dans l'IA qui enregistre la partie si l'on atteint une situation spécifique, puis on peut utiliser ce journal pour s'assurer que l'IA joue correctement.

Enfin, les simulations sont également importantes pour s'assurer qu'il n'y a pas de bugs dans l'IA, plus précisément des bugs qui la feraient planter. Grâce à la nature déterministe de l'IA, je peux facilement simuler plus de 200 parties par seconde sur mon propre PC, donc si on la laisse tourner pendant quelques minutes et qu'elle n'a pas planté après 100 000 parties, on peut être à peu près sûr que l'IA est exempte de bugs.

Situations de jeu ambiguës

Bien que le concept d'arbre de décision soit simple, le problème est qu'il y aura toujours des situations de jeu où le bon coup n'est pas clairement évident. Ajouter des cas de test et ajuster les seuils ne nous aide pas non plus, car par définition, une situation ambiguë signifie que tous les humains ne joueraient pas la même carte.

Pour tester ces situations ambiguës, cela signifie qu'on ne teste pas quel devrait être le prochain coup, mais plutôt qu'on s'assure que ce coup n'est pas une bourde. Cela permet aux modifications de l'IA de faire évoluer sa décision dans les situations ambiguës, tout en garantissant que l'IA ne décidera pas soudainement de faire un coup qui serait, lui, clairement considéré comme une bourde !

Cependant, dans des jeux comme le king et la dame de pique, nous avons développé un algorithme spécifique utilisé dans ces situations ambiguës. Le king et la dame de pique sont tous les deux des jeux dits négatifs, ce qui signifie qu'il faut éviter de prendre des points de pénalité. Si l'on n'est pas sûr de quelle carte jouer, l'IA calcule les pénalités attendues pour chaque carte jouable, puis essaie de minimiser ce nombre.

Par exemple, considérons la situation suivante à la dame de pique :

Imaginons que nous ayons à la fois ♥3 et ♥K, et que ♠Q ne soit pas encore tombée : nous avons alors deux options dans cette situation :

1. Nous pouvons défausser ♥3 maintenant et éviter les pénalités déjà présentes dans le pli, mais risquer de nous faire prendre plus tard par la dame de pique ♠Q et ses 13 points de pénalité en gardant ♥K.
2. Nous pouvons défausser ♥K maintenant et prendre les 4 points de pénalité, mais garder notre ♥3 sûre pour plus tard, ce qui signifie que nous ne pourrons pas être forcés de prendre ♠Q sur un pli de cœur ♥.

L'IA estime alors les pénalités attendues pour les deux cas – en tenant compte des informations de la matrice des hypothèses – puis choisit l'option qui résulte dans le moins de pénalités attendues. Notez que c'est en fait exactement le même raisonnement qu'un humain suivrait aussi : essayer d'évaluer quelle est la meilleure option sur le long terme.

Bien que l'approche semble simple, implémenter un algorithme pour les pénalités attendues était loin d'être facile. Il fait un usage intensif de la matrice des hypothèses et des répartitions, et il comporte aussi de nombreuses simplifications pour éviter de devoir examiner des milliers de possibilités. Tester cela se fait également souvent en vérifiant que l'IA ne fait pas de bourde, plutôt qu'en s'assurant qu'elle joue une carte précise.

La mémoire de l'IA

Bien que l'IA ne soit certainement pas capable de jouer au niveau d'un humain, elle reste meilleure que n'importe quel humain sur un point : elle a une mémoire parfaite. Dans les jeux de cartes, il est souvent utile de savoir à tout moment quelles cartes restent encore en jeu. Par exemple, on ne veut souvent pas gaspiller une carte d'atout si son partenaire a déjà joué la plus haute carte restante dans une couleur. Le problème, c'est qu'en tant qu'humain, il est naturel d'oublier quelles cartes ont déjà été jouées, et donc de finir par couper inutilement.

L'IA ne fera jamais ce genre d'erreur, car elle sait exactement quelles cartes restent encore en jeu – mais rappelez-vous qu'elle ne triche pas et ne peut voir que sa propre main ! On pourrait avancer qu'on pourrait rendre l'IA plus humaine en lui donnant à la place une mémoire imparfaite.

Cependant, nous avons explicitement décidé de ne pas faire cela. Non seulement cela compliquerait inutilement la logique de l'IA, mais les joueurs n'aiment généralement pas jouer avec des joueurs IA, donc si ces derniers se mettaient à faire des erreurs en oubliant quelles cartes ont été jouées, cela pourrait être extrêmement frustrant si vous vous retrouvez associé à une IA, surtout en tournoi. L'IA est loin d'être parfaite, donc cela n'a aucun sens de la faire jouer intentionnellement encore plus mal. Les ordinateurs ont une mémoire parfaite, c'est leur point fort, et ils ont bien le droit de s'en servir.

Conclusion

Je ne sais pas si c'est ainsi que vous vous attendiez à ce que l'IA fonctionne. L'IA de Whisthub fonctionne d'une manière fondamentalement différente des systèmes d'IA modernes comme ChatGPT, et d'une certaine façon, on pourrait même dire qu'il ne s'agit pas d'une IA du tout, puisqu'elle repose sur un ensemble déterministe de règles.

Il est tentant de penser que l'IA pourrait être améliorée en utilisant un réseau de neurones plutôt qu'un arbre de décision déterministe. Cependant, il ne faut pas oublier que, précisément parce qu'elle est déterministe, l'IA de Whisthub est légère et extrêmement rapide. Si l'on devait entraîner un réseau de neurones pour tous les jeux de cartes disponibles, la taille du modèle atteindrait facilement quelques mégaoctets – voire des gigaoctets –, alors que la taille de l'IA actuelle ne représente que quelques kilooctets.

Faire fonctionner des réseaux de neurones consomme également beaucoup de ressources de calcul, ce qui nécessiterait de faire tourner un serveur séparé – probablement même plusieurs – rien que pour l'IA. Le jeu n'en vaut pas la chandelle, d'autant plus que Whisthub met l'accent sur le jeu en multijoueur contre d'autres humains, même s'il est parfois impossible d'éviter les joueurs IA, par exemple lors des tournois.

Entre-temps, j'ai collecté quelques millions de journaux de parties pour différents jeux de cartes, donc entraîner un réseau de neurones est tout à fait envisageable, ne serait-ce que pour le plaisir ou à des fins éducatives. Je ne suis pas un expert du domaine, donc pour l'instant, je n'ai pas vraiment envie d'y consacrer mon temps – déjà limité. Cela dit, si vous préparez un doctorat en IA ou quelque chose du genre, je suis ouvert à une collaboration, ça pourrait être un projet sympa !