Lettres persanes

[papachu]

Le moteur de jeu de TCGOne est vraiment bon ?

Le moteur de jeu c'est ce qui maintient l'état du jeu (effets compris), sait ce qui est jouable et calcule ce qui change quand on le joue. Donc oui il est bon aux bugs près

[Ankylosaure]

OK, l'IA si tu préfères. Je ne me rappelle plus s'il y en a une dans TCGOne. Dans PTCGO, finalement, elle se limite au défi du dresseur et à la fonction "test" dans le gestionnaire de decks.

[Mew Antique]

Il n'y a pas d'IA dans TCGone. L'équipe bénévole a du mal à maintenir les extensions à jour, alors une IA ...

[Ankylosaure]

C'est déjà énorme ce qu'ils font.

Faire une IA correcte sur un jeu comme PTCG est vraiment difficile, car il me paraît impossible de résoudre le jeu par un arbre de décisions. Une des difficultés les plus importantes concerne les "setups", c'est-à-dire les installations optimales qui varient fortement selon les decks. Ensuite, le but recherché par tour peut lui aussi être très variable. Nous ne pouvons pas dire que le meilleur coup sur un tour est celui qui occasionne le plus de dégâts aux pokémons adverses, ni même raisonner en termes de récompenses récupérées (ce serait cependant l'approche la plus pertinente pour une première ébauche d'IA). En gros, il faudrait presque une IA Malamar, une IA ReshiZard, une autre Pikarom... etc...

Et là, nous parlons juste de simuler sur des archétypes connus. Or, la question initiale de CaressaEX est : "selon un tas de cartes donné (format légal), peut-on prédire les archétypes dominants, voire constituer des decks entiers qui ont statistiquement le plus fort potentiel de victoires ?" Si l'on considère que nous ne pouvons développer une IA performante qu'une fois le deck connu, cela pose un sérieux problème conceptuel.

[caressaEX]

Indexer les cartes ?

Si nous prenons le déroulé d'un match comme une droite, sur cette droite, nous pouvons mentionner les étapes d'un match : début, milieu, fin. Or, toutes les cartes n'ont pas la même valeur si l'on les jouent au début ou à la fin du match. Par exemple, la GX de l'escouade Arceus Dialga Palkia est plus utile au début du match qu'à la fin.
C'est pareil pour N : il est plus utile (optimisé) dans le cas ou la partie adverse mène au score afin de pouvoir restreindre son accès aux cartes. Ça me parait accessible, avec l'aide d'un humain créatif à une AI.

[papachu]

Faire une IA correcte sur un jeu comme PTCG est vraiment difficile, car il me paraît impossible de résoudre le jeu par un arbre de décisions.

C'est pourquoi je parlais de machine learning, qui n'a rien à voir avec une approche algorithmique. Inutile de comprendre quoi que ce soit au problème à résoudre, il s'agit de brancher un système d'apprentissage, de voir ce que ça donne, et après c'est de la cuisine pour améliorer les performances ( = modifier les paramètres de l'apprentissage et c'est une question de chance / d'expérience de trouver ceux qui marchent le mieux ; ou, au plus haut niveau, monter une architecture d'apprentissage qui parvient à surmonter les difficultés rencontrées). Ça peut aussi bien marcher étonnamment bien qu'échouer lamentablement et on ne sait essentiellement pas pourquoi, c'est une question de recherche à part entière que de savoir pourquoi une IA qui marche marche.
Bon, pour donner un exemple les IAs sont mauvaises pour garder trace d'un contexte. Par exemple s'il s'agit de générer du texte elles ont tendance à faire n'importe quoi avec les pronoms, sans parler de générer un bout d'histoire avec des choses qui s'enchaînent. Alors pour le tcg, un humain va se dire "il a pris une communication pokémon avec son Jirachi donc il l'a en main donc il faut que je bumpe l'Ultra Dimension sinon il peut récupérer tel pokémon à coup sûr" alors que l'IA va choisir de bumper le stade ou non sur des bases statistiques plus générales.
L'IA serait aussi mauvaise pour se souvenir de ce qu'elle a en prix, mais ça c'est corrigeable : le moteur de jeu peut lui fournir l'info à la première occasion de deck-check. (EDIT en me relisant je me rends compte qu'en fait ça veut dire que le moteur doit aussi garder trace des cartes en main de l'adversaire... EDIT "il a joué X et pas Y donc il a Z en prix", voilà un exemple d'info que l'IA pourra "savoir" quand l'adversaire joue X mais oubliera ensuite.)
Inversement, s'il s'agit d'utiliser sa main de départ pour se setup avec un bon sequencing, dans le cadre d'un match-up fixé, je ne serais pas étonné qu'une IA soit meilleure qu'un humain parce que la force d'une IA est de condenser des résultats statistiques sur des milliers de parties.

Si l'on considère que nous ne pouvons développer une IA performante qu'une fois le deck connu, cela pose un sérieux problème conceptuel.

Non c'est un problème connu. Un exemple d'approche est la programmation génétique : à chaque génération les decks les plus performants donnent plus de copies d'eux-même, les moins performants diminuent en nombre, et pour chaque copie, il y a une possibilité de mutation (changer une ou plusieurs cartes). Au fil des générations les deck-lists s'améliorent vers un optimum local. Donc s'il s'agit de trouver un deck Malamar optimal, un humain pourrait fournir plusieurs decklists initiales et un pool de cartes qu'il pense envisageables dans l'archétype ; il va aussi fixer en face les decklists qu'il pense représentatives du méta ; à chaque génération il faut entraîner les IAs des nouveaux Malamar pour chaque match-up et leurs performances dictent la composition de la génération suivante. Donc si tu te demandes si ça fait sens de mettre 4 acrobikes dans le deck, ben tu les mets dans des decklists du début et tu vois s'il y a encore des acrobikes à la fin et comment les listes sont organisées.

En fait il n'est pas nécessaire de savoir faire une IA proche de l'optimal pour tirer profit de ce genre d'exploration : du moment que les IAs ne sont pas trop mauvaises il y a possibilité de faire sortir des decklists novatrices, qui pourraient paraître étranges au joueur jusqu'à ce qu'il voit l'IA les jouer. Parce qu''un humain a du mal à penser hors des sentiers battus et à remettre en question les bonnes idées reçues, alors que les IAs n'ont pas du tout ce problème !

[Ankylosaure]

Mais tu entraînes ton IA par rapport à quoi ?
Mettons que je veuille entraîner une IA pour battre la (supposée) meilleure decklist de Malamar. Je peux lui communiquer la decklist, mais comme il ne sait pas la jouer, les résultats seront mauvais. Il faudrait lui communiquer également des parties entières avec cette decklist. Sous quelle forme est-ce possible ?

[papachu]

Mais tu entraînes ton IA par rapport à quoi ?

Tu entraînes deux AI l'une contre l'autre. Chaque AI a la même structure et joue l'un des decks.

Les AIs sont en fait juste un tas de nombres (flottants) qui forment quelques grosses matrices, c'est l'interaction entre ces calculs linéaires et les fonctions non-linéaires qui permettent un comportement "intelligent". Il y a un tour de calcul pour chaque décision à prendre. Les entrées sont l'état du jeu mais aussi certaines valeurs intermédiaires du tour précédent si l'on veut, ce qui permet une forme de mémoire (ne semble pas utile dans notre cas : si l'état est que je suis en train de choisir un pokémon dans mon deck, peu importe que je me souvienne que c'est parce que je viens de jouer une Communication Pokémon. Sauf si l'on espère battre des humains en apprenant leur style de jeu, ce qui est d'un tout autre niveau ). En sortie sont une évaluation de l'intérêt de chaque décision possible. On joue l'une de ces décisions au hasard avec une pondération dans le choix exponentielle en l'évaluation, ce qui veut dire qu'on va jouer le meilleur coup ou l'un de ceux estimés à peu près aussi bons. Entre l'entrée et la sortie se trouve un diagramme de calcul assez simple dans le principe (en gros il faut choisir le nombre et la taille des étages intermédiaires, et les fonctions non-linéaires qu'on y met), sauf bien sûr si l'on s'appelle Google Deep Mind et qu'on mélange plein d'outils. Tout cela est très classique, il y a une difficulté du choix de codage de la sortie (les décisions à prendre sont de nature différente et en nombre de possibilités différents selon les moments) mais j'imagine que c'est très classique aussi, c'est juste au-delà de mes maigres savoirs.

Après vient l'entraînement des deux IAs. Au début les nombres composant les IAs sont tirés au hasard donc les AIs jouent n'importe quoi. Quand il y a un gagnant toutes les décisions prises pendant la parties sont renforcées chez le gagnant et diminuées chez le perdant. Ça veut dire que l'algorithme d'apprentissage reprend tous les calculs entrée → sortie en modifiant les paramètres de l'AI pour que l'évaluation de la sortie choisie soit un peu plus élevée ou basse à l'avenir (c'est simple dans le principe, il suffit de remonter le calcul en partant de la fin). Puis on passe à la partie suivante. Un million de parties après on a l'impression que les IAs savent jouer, et si l'on a de la chance 10 millions de parties après on a deux experts qui jouent.
L'apprentissage est lui-même dépendant d'un certain nombre de paramètres appelés méta-paramètres et dont le choix est important pour la réussite du projet. Par exemple en début d'apprentissage on veut que les IAs évoluent vite, alors qu'à la fin on ne doit pas modifier beaucoup les IAs sinon ça ne convergerait pas.

Comme toujours en informatique une difficulté pour le nouveau venu est de connaître les APIs des bibliothèques qui font tout ça pour toi, comme tensorflow de Google, si c'est le cas ça prend 10 min. Sinon bien sûr il faut passer du temps à interfacer le moteur de jeu pour présenter les données adéquates en entrée de l'IA. Après, un coup d'entraînement va prendre des heures ou des jours (ou se parallélise sur un cloud), donc le cycle de développement est assez long, parce qu'à chaque fois tu te dis "bon mon IA est bonne pour ceci mais nulle pour cela" mais tu dois attendre la fin de l'entraînement pour voir ce que donnent tes idées.

[Ankylosaure]

Quand il y a un gagnant toutes les décisions prises pendant la parties sont renforcées chez le gagnant et diminuées chez le perdant.

C'est un peu ça le problème. Une IA peut perdre parce qu'elle prend une décision absurde sur un coup, en ayant joué correctement le reste de la partie. Le point faible de tout système d'apprentissage par renforcement, inspiré par la cybernétique, est qu'il faut que le but ne soit pas ambigu. Dit autrement, il faut des tâches et des sous-tâches, auxquelles on peut répondre à la question : "est-ce que le but est atteint ?" La tâche est ici définie : gagner la partie. Mais les sous-tâches...

Je me demande s'il ne serait pas pertinent dans le cas de PTCG d'entraîner d'abord l'IA contre des joueurs humains, puis de la laisser en apprentissage non supervisé seulement lorsqu'elle commence à obtenir des victoires.

PS: Purée, nous sommes en train de pourrir le topic... Désolé CaressaEX.

[Willem59]

Je comprends pas la moitié de ce que vous racontez mais j’aime bien le concept d’avoir fait d’un topic peu intéressant, une discussion passionnante. Par contre ça serait dommage que ça parte dans les oubliettes, faudrait qu’un admin extrait la conversation pour en faire un topic (si ce genre de truc est possible).

[papachu]

Une IA peut perdre parce qu'elle prend une décision absurde sur un coup, en ayant joué correctement le reste de la partie.

Et elle peut aussi gagner en jouant mal parce que l'adversaire a encore plus mal joué. Je suis d'accord qu'il n'est pas évident que cela marche ; mais le fait est que des équipes ont réussi à faire marcher des choses comme ça. L'idée est "dans le passé, dans des situations similaires, quand j'ai joué x, ça s'est bien terminé dans y% des cas" ; tout est renforcé ou atténué au hasard mais les bons coups ont plus tendance à être renforcés et les mauvais à être atténués, puisque les parties avec des bons coups ont plus tendance à être gagnantes.

Le point faible de tout système d'apprentissage par renforcement, inspiré par la cybernétique, est qu'il faut que le but ne soit pas ambigu. Dit autrement, il faut des tâches et des sous-tâches, auxquelles on peut répondre à la question : "est-ce que le but est atteint ?" La tâche est ici définie : gagner la partie. Mais les sous-tâches...

C'est bien la force du machine learning d'arriver à "identifier" les sous-tâches par lui-même. Si tu peux le faire à sa place, ça va évidemment beaucoup accélérer l'apprentissage, mais quand il n'y a pas de moyen algorithmique accessibles à l'humain, tu laisses l'IA calculer des trucs au hasard dans les couches intermédiaires de son architecture de deep learning et "découvrir" que certains calculs sont corrélés avec le résultat souhaité (gagner) par le moyen d'un renforcement statistique. Une fois une bonne IA obtenue un humain peut essayer de comprendre quel algorithme elle utilise, mais c'est loin d'être facile même pour avoir un bout d'explication parce que les humains fonctionnent avec des concepts alors que ces concepts (je ne sais même pas si on peut affirmer qu'il y en a) sont cachés derrière des manipulations simples d'un nombre colossal de nombres (colossal parce que l'humain a une mémoire de travail d'environ 7 trucs alors que l'IA contient des millions de paramètres). C'est le même type de difficulté que pour comprendre comment un cerveau fonctionne.

Je me demande s'il ne serait pas pertinent dans le cas de PTCG d'entraîner d'abord l'IA contre des joueurs humains, puis de la laisser en apprentissage non supervisé seulement lorsqu'elle commence à obtenir des victoires.

Cela serait pertinent si l'on avait ces données...
Historiquement AlphaGo a fonctionné comme cela et battu les champions de Go. Puis AlphaGo Zéro a battu tout le monde y compris AlphaGo en s'entraînant uniquement en jouant contre lui-même, avec zéro connaissance initiale du jeu et avec une architecture beaucoup plus simple. Puis il a encore été amélioré sous la forme d'AlphaZéro qui peut apprendre semble-t-il à jouer à n'importe quel jeu à information totale (l'algorithme de jeu est basé sur un arbre d'exploration des coups donc ne tolère pas facilement le hasard ou les informations cachées ; la difficulté de ce type d'algorithme est d'identifier les branches à explorer, et d'évaluer la situation du jeu au bout des branches quand on arrête d'explorer, et AlphaZéro consiste à entraîner deux IAs pour résoudre ces deux questions). J'ai vu hier qu'un champion de Go avait jeté l'éponge, dégoûté d'avoir été battu par un bot qui a été battu par un bot qui a été battu par un bot qui s'est entraîné 24h...

La difficulté point de vue IA dans le cas du TCG est effectivement d'arriver à une convergence, plutôt qu'avoir des IAs qui jouent encore au hasard après des millions de parties. On sait que des difficultés semblables ont été résolues par self-play par des équipes qui jouent au poker ou à Dota2, mais ce sont des équipes de pointe qui ont beaucoup de compétences et de moyens de calcul. Alors OK je ne mettrais pas ma main à couper que le principe simple que j'ai décrit suffirait à résoudre le problème. S'il faut donner des coups de pouce au début de l'apprentissage sous la forme de fonctions d'évaluation d'une suite de coups (je ne crois pas que tu pourrais obtenir facilement des milliers de parties jouées par des humains), par exemple récompenser que tu as réussi à remplir un objectif du deck (genre prendre des récompenses), ce serait plutôt un échec des techniques d'IA parce que cela empêcherait de monter des systèmes qui ne font pas d'hypothèses sur ce que veulent faire les decks. Un étudiant en IA chercherait à trouver une architecture d'IA et une méthode d'entraînement qui résoudrait le problème sans rien programmer d'autre ! (Programmer l'interface avec le moteur de jeu n'est déjà pas simple, il faut recenser tous les effets possibles pour le match-up etc.)

EDIT un pdf anglais avec beaucoup de détails sur AlphaZéro https://kstatic.googleusercontent.com/f ... 45072dc7bd

Quelqu'un a abordé la question pour Heartstone pour sa thèse de Master. https://era.library.ualberta.ca/items/7 ... 7364723d98
Il a utilisé un arbre de recherche de Monte-Carlo (comme AlphaZero). L'idée reste de simuler un arbre des possibilités (qui sont multiples à chaque fois qu'elles sont imprévisibles) en se basant sur du machine learning pour évaluer la proba de chaque branche et ne pas passer de temps sur des mauvaises idées de jeu ; si j'ai bien compris il utilise dans les feuilles de l'arbre de recherche une fonction d'évaluation développée par des humains experts du domaine. Il obtient une IA qui joue mieux que le joueur moyen.

[caressaEX]

Il faudrait essayer d'éviter l'effet indésirable qu'à introduit la trop belle réussite de l'AlphaGo : l'abandon du jeu par son champion du monde, Lee Se-Dol
https://www.generation-nt.com/lee-se-do ... 71001.html

Il me semble que ce sera plus que le départ d'une seule personne, il est probable que beaucoup d'amateurs de ce jeu suivrons l'exemple de leur champion. Au-delà de la question de performance, il est possible que nous soyons devant un scénario cauchemardesque tout droit sorti de la science fiction : le déclassement de l'homme par la machine, la IA devenant la norme et l'homme une espèce de précurseur, de Neandertal de la machine... le front bas, en somme.

[Ankylosaure]

Tu sais, cela fait longtemps que les IA battent les humains aux échecs, pourtant les tournois continuent. Ce sera pareil pour les TCG. En réalité, battre une IA n'a aucun intérêt pour un humain. L'objectif serait plutôt de l'utiliser en deckbuilding, pour répondre à la question : "est-ce que cela vaut le coup que je m'entraîne à jouer ce tas de cartes ?" A la limite, cela pourrait diminuer ou augmenter le nombre d'archétypes joués en tournoi.

L'homme n'est pas du tout déclassé par la machine. C'est comme dire que le paysan qui labourait avec un attelage de bœufs est déclassé par le tracteur. Il n'est pas déclassé, il est monté dans le tracteur ! Lee Se-Dol n'a pas été battu par une entité. Il a été battu par une équipe d'ingénieurs, épaulée d'une sorte de super-calculatrice qui a tourné pendant des milliers d'heures.

Par ailleurs, une IA a des tas de faiblesses. Dans certains domaines, comme l'a expliqué Papachu avec la production de texte, elle est totalement nulle. En réalité, le terme "intelligence" est inapproprié. Il faudrait démystifier l'IA en expliquant aux gens la cybernétique et l'ensemble de ses développements. J'ai ma petite idée sur les raisons pour lesquelles on ne le fait pas, mais cela nous emmènerait sur des sentiers bien éloignés de ce sujet sur les cartes Pokémon.

[papachu]

J'ai ma petite idée sur les raisons pour lesquelles on ne le fait pas, mais cela nous emmènerait sur des sentiers bien éloignés de ce sujet sur les cartes Pokémon.

Oui il serait dommage que ce topic dévie de son objectif initial
Je ne sais pas trop à quoi tu penses mais je sais que le grand public n'est pas preneur de démystification. On veut faire un film où quelqu'un se transforme en homme-reptile → on invoque le mot "génétique" dans une explication "scientifique" et hop ! c'est parti pour les effets spéciaux. Qui veut se gâcher le spectacle en étant informé sur des détails techniques ennuyeux ?

L'homme est bien surclassé par la machine dans des domaines comme le Go, et l'automatisation gagne du terrain dans de plus en plus de domaines professionnels. Tu cites les tracteurs, mais ils commencent à se conduire tout seul. On ne sait pas trop où cela va nous mener parce que l'on ne sait pas si les difficultés actuelles pour les IAs sont faciles ou difficiles à résoudre. Les chercheurs ont déjà développé des outils destinés à attraper la sémantique d'un texte (ex https://en.wikipedia.org/wiki/Word2vec ), on sait que les progrès sont rapides et on n'a aucune idée de ce que ces systèmes sauront faire dans 10 ans. On ne s'attend pas à ce qu'une "intelligence" globale surgisse un peu de nulle part (même si rien ne permet d'affirmer que cela ne va pas venir vite), mais on peut s'attendre à une montée des performances des outils à disposition des influenceurs : hier les partisans du Brexit ont gagné grâce à des pubs ciblées sur FB, demain peut-être des comptes bot difficiles à repérer sur tous les réseaux.

Tout ça pour dire que je me garderais bien de donner l'impression que "tout va bien se passer, ne vous inquiétez pas". Bon s'inquiéter ne sert à rien mais une vigilance citoyenne serait bienvenue

Je suis d'accord que le TCG n'est pas menacé. Une bonne IA ferait de meilleurs joueurs grâce à un meilleur entraînement.

[caressaEX]

Merci Papachu,
il est possible de faire un parallèle entre le développement de l'IA et la progression des connaissances des personnes en activité professionnelle dans un pays donné. je m'explique : on nous répète suffisamment fréquemment (dans un but pédagogique sans doute) que pour intégrer avec succès le marché de l'emploi il est important d’être très hautement qualifié. Or, même avec l'amélioration de l'enseignement à l'école et au collège, le nombre de personnes hautement qualifiées n'est pas augmenté d'une manière exponentielle.

Par contre, ce qui se passe, c'est que déjà avec la robotisation nous avons perdu les emplois humaines dans les taches manuelles (usine, industrie, textile). Il y a eu un déclassement des ouvriers par les robots.
Aujourd'hui, nous sommes sur le point de déclasser les professions intellectuelles par la IA qui est plus puissante, notamment en matière stratégique et d'apprentissage que la population normale et éduquée d'un pays comme la France. Nous jouons une partie avec des machines dans laquelle la plus grande partie de la population (et pas seulement les champions comme Lee Se-Dol) devra abandonner le combat.
Pour le parallèle avec PTCG, c'est comme jouer Miaouss contre un Darkray GX...

[papachu]

[HS]Les emplois qui disparaissent sont plutôt des tâches ingrates, répétitives. Le problème n'est pas que les IAs deviennent trop intelligentes. Le problème est que notre espèce est trop bête pour tirer profit des outils qu'elle développe. Les emplois qui disparaissent ne sont pas facilement remplacés par d'autres emplois.
Aujourd'hui presque tout le monde laisse traîner de nombreuses données numériques le concernant, juste parce qu'il est coûteux de ne pas le faire. (Il est coûteux socialement de ne pas avoir de FB etc. Il est difficile de penser que cela pourrait poser problème un jour parce que le penser amènerait à subir tous ces coûts, et comme cela semble trop difficile, la solution est de penser que ce n'est pas un problème.) Ces données suffisent en principe à déterminer qui nous sommes : la structure de notre personnalité, les croyances auxquelles nous adhérons, ce qui peut nous motiver à agir dans un sens ou dans un autre, tout ça est en filigrane de ce que nous faisons sur le web. Aujourd'hui ceci n'est que très partiellement accessible aux IAs. Une des raisons est que la "structure de la personnalité" n'est pas une notion bien définie, c'est plutôt une intuition de psychologue qu'il y en a une mais les modèles théoriques proposés n'ont pas atteint une grande solidité scientifique — et justement il y a beaucoup de recherches utilisant l'IA pour tenter d'y voir plus clair. Alors demain ? Mystère.
Un des enjeux majeurs de l'IA est le contrôle des humains — pas par des IAs intelligentes, mais par des humains qui pilotent des IAs qui permettent d'influencer bien plus efficacement que les méthodes de pub actuelles. (Enquête SOFRES 2005 75% des gens se pensent non influencés (.doc) dans le sens que veut la pub — les publicitaires se marrent...) Notre seule certitude est que cette influence grandit...
[/HS]