ZeSword
Bruxelles, Belgique

AVATAR
Après le GO, StarCraft II
le 16/12/2019 12:27
Les équipes de DeepMind chez Google viennent de créer une intelligence artificielle capable de se placer dans les meilleurs joueurs de StarCraft II. Ils avaient déjà réussi à créer une intelligence artificielle avec des techniques similaires (apprentissage profond) pour le GO. À quand une intelligence artificielle pour MtG ? :)

https://deepmind.com/blog/article/AlphaStar-Grandmaster-level-in-StarC...

https://www.nature.com/articles/s41586-019-1724-z
haut de page - Les forums de MV >> Général >> Discussion : page 1 | 2
Rekyem
Maender Alkoor
le 16/12/2019 12:38
J'ai lu, je ne sais plus ou, que MtG était certainement le jeu le plus compliqué pour une AI. :/
ZeSword
Bruxelles, Belgique

AVATAR
le 16/12/2019 12:54
Si on prend la définition la plus générale, certes (c'est lié à un truc un peu technique, le fait que le jeu soit "NP-complet").

Sauf qu'en pratique, dans MTGO on n'a pas le droit aux boucles et on n'a pas le droit de créer plus de 200 jetons (à peu de choses près, cf. ce lien et cet autre qui casse parfois la limite).

Du coup, dans ces limites-là, je ne vois vraiment pas ce qui empêche un apprentissage automatique pour une intelligence artificielle. Ça m'étonne même, vu l'argent que WotC a, et vu le nombre de parties numériques qui doivent être sauvegardées et sur la base desquelles apprendre, que ça ne soit pas encore sorti.
Gwath
le 17/12/2019 10:51
Il faut savoir que ça fait un moment qu'on avait fait une IA débridée qui écrasait les joueurs pro à SC2.

Bon là l'IA joue dans des conditions humaines, ce qui rend la chose beaucoup plus impressionnantes. La réserve à émettre par rapport au Go par contre, c'est que cette fois, pour en arriver là, ils ont d'abord du booster l'IA en lui apprenant à jouer à haut niveau, parce que sinon, l'IA explorait beaucoup trop de piste morte qui l'empêchait de progresser.

Donc concrétement, l'IA a pu en arriver là parce que es humains avait déjà exploré le jeu, et que l'on avait déjà des solutions sous optimales à proposer à la machine.
ZeSword
Bruxelles, Belgique

AVATAR
Effectivement
le 17/12/2019 11:06
Merci de ta précision. Il y a une grande différence entre un jeu "tour par tour" ou "action par action" (GO, Magic, etc.) et un jeu en temps réel comme StarCraft 2. Ici, pour éviter d'être "trop forte", ils ont du limiter "dans des proportions humaines" ce que pouvait voir (et faire) l'IA, alors que pour le GO, les échecs, etc. ce n'est pas nécessaire.

Par contre, le fait que l'IA a appris des humains, ce n'est pas nouveau. Comme je l'écrivais, c'est le principe de l'apprentissage automatique (déjà utilisé, justement, par AlphaGO) de regarder un gros flot de données, et d'en tirer partie. Et pour Magic c'est également la piste que j'explorerais si je devais faire une IA compétitive : j'apprendrais des parties jouées par des joueurs pro.

Le seul hic étant qu'il faut prévoir que faire contre un deck nouveau, notamment un deck combo nouveau (le reste étant "suffisamment proche" de ce qui existe déjà, je pense), et ça, je ne me rends pas compte de la difficulté. L'IA reconnaîtra probablement que le style de jeu est proche d'un deck combo, mais verra-t-elle comment disrupter la combo à un moment où elle pourrait le faire, si elle ne l'a jamais vue avant ?
Gwath
le 17/12/2019 11:21
Oui, ce que je voulais dire c'est que contrairement au Go, ou tu peux jouer l'IA toute seule, et ou elle finit par trouver des patterns (globalement, à chaque coup l'IA tend vers l'option qui lui crée le plus d'option de jeu intéressante par la suite), sur SC2, ils ont du d'abord la programmer plus ou moins en dur pour la rendre bonne, et ensuite laisser le machine learning faire le taf pour la faire passer en GM.

Ce qui n'enlève rien à la prouesse.

Concernant MtG, elle pourrait rater le coche pour la combo, mais si on considère Magic (enfin les cartes), comme des fonctions, alors c'est beaucoup plus simple.

Une combo de deux cartes random, t'as souvent toujours les mêmes trucs qui reviennent. Moteur à mana. Moteur à jetons. Moteur à pioche. Dès le moment ou tu classes les cartes comme ça, t'as toujours une clé de voute au sens ou c'est la carte limitante. Genre KCI, tu manquait souvent de cartes. Pas de mana. Du coup les contres tu les cales soit sur la KCI si tu en as la chance, mais si c'est trop tard pour ça, ça va souvent partir dans les sources de Sanie and co.
Je pense que l'ia est capable de comprendre ça.
Azahir
Frappe, je te dirai quand arrêter

DRAGON
le 17/12/2019 12:21
ZS, on en a déjà parlé ici non? C'est pas toi qui avait programmé une IA d'un weenie white?

Comparer ce que l'on fait pour les échecs et le go à ce que doit faire une IA pour Magic n'a pas vraiment de sens. Fondamentalement, aux échecs, chaque tour consiste à sélectionner une piece et sa destination, 2 choix à faire (sachant que le 2eme est tellement lié au premier que l'on peut considérer cela comme un seul choix), au go, c'est encore plus simple, c'est choisir ou mettre une pièce indifférencié.

Magic à CHAQUE fois que la priorité est rendu à un joueur il y a une décision à prendre et en fait 15 décisions (prendre la décision de jouer tel sort/capacité, déterminer sa/ses cibles, quels lands engagés pour payer,etc...). Sans compter que les choix sont plus complexes car il y a plus de paramètres à prendre.

L'IA a Starcraft est en fait beaucoup plus simple, c'est juste une suite de quoi builder. La force d'une IA est qu'elle n'a pas à scroller l'écran, elle contrôle tous ses batiments et ses unités tellement rapidement par rapport à un humain qui va péniblement atteindre les quelques ordres par seconde que l'on peut parler de simultanéité ou meme d'ubiquité. Si elle fait pas trop n'importe quoi dans l'ordre dans lequel elle lance ses productions/recherches, l'humain n'a aucune chance. En gros, elle ne prend pas l'avantage sur l'etre humain sur l'aspect tactique du jeu mais sur l'aspect physique, le clic/seconde. Oui il l'a limite, mais c'est juste une modelisation et les IAs qui "defoncent" les humains ont un bridage moins élevé. Et le pro il n'est pas à 5 clic/seconde tout le temps, il y a des pauses, l'IA, même bridé, reste à 5 clic/secondes.

Comme tous les jeux temps réels, l'aspect physique et pratique de l'activité prend le pas sur la réflexion dans Starcraft. Je ne dis pas qu'il n'y en a pas, mais vous pouvez avoir la meilleure tactique du monde, si vous jouez tout à la souris à 0,5 action/seconde, le noob qui explose son clavier sans regarder l'ecran de jeu et qui monte à 3 action/seconde, il va vous défoncez.

Tout ça pour dire que je suis plus impressionné par l'IA de Go qui bat l'humain que l'IA de Starcraft qui bat l'humain.

Pour revenir à la comparaison go/magic, je n'évoque même pas le fait que l'information est non complète et non parfaite donc les décisions sont à prendre avec une part d'inconnu probabiliste, alors qu'aux échecs/go tu as toutes les infos pour TA décision.

Déjà si on arrive à programmer une IA qui joue WW parfaitement sans connaitre le matchup en face mais en s'adaptant quand meme à la situation en cours de partie selon ce que l'autre joue, ce sera déjà gros.
zombie33

Légende
le 17/12/2019 13:19
Citation :
Déjà si on arrive à programmer une IA qui joue WW parfaitement sans connaitre le matchup en face mais en s'adaptant quand même à la situation en cours de partie selon ce que l'autre joue, ce sera déjà gros.


Programmer c'est pas dur. Ce qui est compliqué c'est de s'entendre sur ce que signifie "jouer parfaitement".

Est-ce que l'I.A. doit prendre en compte toutes les cartes de Magic pour jouer ou seulement une selection de carte classiques. Enfin la manière de jouer de l'IA dépend obligatoirement d'une variable : l'aversion au risque. Et à moins de faire plein de parties pour optimiser ce paramètres, il restera un paramètre variable.

Sinon faire une IA qui joue à peu prêt bien et en fonction de ce que fait l'adversaire c'est pas très dur. A condition que les cartes soient au préalable implémentées dans le programme (c'est ça le plus long en fait).
zombie33

Légende
le 17/12/2019 13:50
Citation :
J'ai lu, je ne sais plus ou, que MtG était certainement le jeu le plus compliqué pour une AI. :/


Peut-être ici
Madmox
I guess Warhol wasn't wrong, Fame fifteen minutes long

Légende
le 17/12/2019 14:14
Citation :
Par contre, le fait que l'IA a appris des humains, ce n'est pas nouveau. Comme je l'écrivais, c'est le principe de l'apprentissage automatique (déjà utilisé, justement, par AlphaGO) de regarder un gros flot de données, et d'en tirer partie.
Non ça c'est le principe de l'apprentissage supervisé. Des IA comme AlphaZero, qui fonctionnent selon le principe d'apprentissage par renforcement, ne se basent que sur les règles du jeu et les parties simulées avec elle-même. D'ailleurs AlphaZero a mis 100-0 à AlphaGo lors de leur première confrontation officielle...

Citation :
L'IA a Starcraft est en fait beaucoup plus simple, c'est juste une suite de quoi builder. La force d'une IA est qu'elle n'a pas à scroller l'écran, elle contrôle tous ses batiments et ses unités tellement rapidement par rapport à un humain qui va péniblement atteindre les quelques ordres par seconde que l'on peut parler de simultanéité ou meme d'ubiquité.
En l'occurrence non, ils ont aussi modélisé la caméra et ce genre de limitations humaines. Du coup je trouve la performance plutôt sympa.
Azahir
Frappe, je te dirai quand arrêter

DRAGON
le 17/12/2019 14:15
Certes, aucun humain ne joue parfaitement (systématiquement, à chacun des trouzemille choix par tour faire le meilleur, donc celui qui a la meilleure espérance de victoire, notion qui est déjà impossible à déterminer).

Franchement quand on voit que l'algo de détermination des lands à taper pour payer un sort dans Arena, qui n'est qu'un des sous-algo pour pouvoir faire jouer une IA à Magic, on se dit quand même qu'on est loin du compte. Alors d'accord, il cherche à maximiser le nombre de sort que tu pourras jouer après le paiement du sort en cours et il le fait mieux qu'au début, mais on voit qu'il a encore des ratés.

Quand je disais programmer, je voulais bien évidemment parler conception et algorithmie, la partie pissage de code ne sera effectivement pas le plus compliqué, mais comme d'hab non?
Mais tu vois zombie, moi je pense que c'est déjà tres tres compliqué (sans comparaison possible avec les échecs ou le go) même en faisant WW (donc peu d'éphémère, peu d'effet, plutot axé sur la phase d'attaque) contre un jeu qu'il connait. Alors un jeu connu de l'IA face à un jeu adverse inconnu...
ZeSword
Bruxelles, Belgique

AVATAR
le 17/12/2019 14:26
Azahir a écrit :
ZS, on en a déjà parlé ici non? C'est pas toi qui avait programmé une IA d'un weenie white?

Presque, c'est un pote dans un projet de master qu'on avait fait ensemble (un 3e pote avait codé toute la partie réseau, et j'avais codé toute la partie règles + cartes).

Et effectivement, mon pote avait à l'époque introduit une variable "prendre des risques" dans son IA :)

zombie33 a écrit :
Sinon faire une IA qui joue à peu prêt bien et en fonction de ce que fait l'adversaire c'est pas très dur. A condition que les cartes soient au préalable implémentées dans le programme (c'est ça le plus long en fait).

Il y a certes la distinction entre MWS / Cockatrice et le reste du monde (MTGO, MTG Arena, à l'époque Shandalar, Duels of the Planeswalkers, de manière non payante Forge...). Mais si le reste du monde a réussi à implémenter les règles des cartes, il n'y a pas de raison ! Je ne sais pas si c'est ça ou pas la partie la plus longue en tout cas. Parce que, même si ça prend beaucoup de temps, une fois que tu as encodé les règles, c'est fait. Autant, pour l'IA, il y a toujours la tentation de continuer à écrire du code pour l'améliorer, donc ça peut potentiellement prendre beaucoup, beaucoup plus de temps :)
Rekyem
Maender Alkoor
le 17/12/2019 14:35
Citation :
Et effectivement, mon pote avait à l'époque introduit une variable "prendre des risques" dans son IA :)

C'était une machine à état du coup ?
Ça n'a rien à voir avec ce que tu présentes en entré de topic. 'Fin j'entends par la que l'approche est drastiquement différente.
ZeSword
Bruxelles, Belgique

AVATAR
Madmox
le 17/12/2019 14:35
Madmox a écrit :
ZeSword a écrit :
Par contre, le fait que l'IA a appris des humains, ce n'est pas nouveau. Comme je l'écrivais, c'est le principe de l'apprentissage automatique (déjà utilisé, justement, par AlphaGO) de regarder un gros flot de données, et d'en tirer partie.

Non ça c'est le principe de l'apprentissage supervisé. Des IA comme AlphaZero, qui fonctionnent selon le principe d'apprentissage par renforcement, ne se basent que sur les règles du jeu et les parties simulées avec elle-même. D'ailleurs AlphaZero a mis 100-0 à AlphaGo lors de leur première confrontation officielle...

Effectivement, l'apprentissage supervisé (AlphaGo, AlphaStar) est une sous-catégorie de l'apprentissage automatique, et je suis désolé d'avoir écrit trop vite. Néanmoins, je crois que dans le domaine de l'apprentissage automatique, le concept d'apprendre à partir de données (donc, apprentissage supervisé) est majoritaire, non ? (d'où l'effervescence autour du "big data").

https://xkcd.com/1838/
Madmox
I guess Warhol wasn't wrong, Fame fifteen minutes long

Légende
le 17/12/2019 14:55
Ma remarque ne visait pas spécialement à te corriger sur le vocabulaire (je l'ai redécouvert en même temps que j'ai retrouvé la vidéo de ScienceEtonnante en lien plus haut) mais plutôt sur le fait que la remarque suivante de Gwath :
Gwath a écrit :
La réserve à émettre par rapport au Go par contre, c'est que cette fois, pour en arriver là, ils ont d'abord du booster l'IA en lui apprenant à jouer à haut niveau, parce que sinon, l'IA explorait beaucoup trop de piste morte qui l'empêchait de progresser.
était plutôt pertinente : si ça n'a pas encore changé depuis, les meilleures IA de Go n'utilisent plus d'algorithme basé sur l'apprentissage supervisé. Du coup ta réponse (celle que j'ai citée dans mon 1er post) me semblait un peu confuse.

Par contre, je n'ai aucune idée de si l'apprentissage supervisé est aujourd'hui la branche majoritaire du machine learning. Mes connaissances en IA se limitent aux vidéos de vulgarisation sur le sujet.
zombie33

Légende
le 17/12/2019 15:17
Citation :
Il y a certes la distinction entre MWS / Cockatrice et le reste du monde (MTGO, MTG Arena, à l'époque Shandalar, Duels of the Planeswalkers, de manière non payante Forge...). Mais si le reste du monde a réussi à implémenter les règles des cartes, il n'y a pas de raison !


ZS actuellement aucune plateforme a d'implémenté l'intégralité des cartes et par corollaire aucune ne sait gérer l'intégralité des interactions entre ces dernières. D'ailleurs c'est impossible de faire un programme qui peut gérer tout les cas de figures (cf. le fait que magic soit turing-complet).

Enfin sans aller jusque là, tous les exemples que tu as cité tu en conviendra sont très restrictifs :
- MTG Arena ne gère que des cartes très récentes
- Shandalar et MTGO ne gèrent pas bien les boucles entre autres si je ne dis pas de bétises

Et aucune plateforme a l'intégralité des cartes implémentée. Pouvoir gérer l'intégralité des interactions du jeu c'est donc impossible pour un programme, mais gérer les interactions les plus basiques (ce qui reste à définir) pour l'intégralité des cartes ça demande déjà un boulot monstre, certes entamé mais loin d'être fini.
ZeSword
Bruxelles, Belgique

AVATAR
zombie33
le 17/12/2019 16:08
zombie33 a écrit :
ZS actuellement aucune plateforme a d'implémenté l'intégralité des cartes et par corollaire aucune ne sait gérer l'intégralité des interactions entre ces dernières. D'ailleurs c'est impossible de faire un programme qui peut gérer tout les cas de figures (cf. le fait que magic soit turing-complet).

Je ne comprends pas le résultat d'impossibilité que tu sembles donner. Pour avoir moi-même programmé ce projet, à aucun moment dans la conception je n'ai rencontré un point qui me fasse douter de réussir à le finir si j'en avais le temps.

zombie33 a écrit :
- Shandalar et MTGO ne gèrent pas bien les boucles entre autres si je ne dis pas de bétises

MTGO ne gère pas les boucles, et plus généralement, ne gère pas les effets qui devraient donner des nombres trop grands (https://www.mtgsalvation.com/forums/the-game/other-formats/775540-is-t...). Je pense que c'est raisonnable de fixer une limite, car il y a forcément une limite au nombre de choses qui peuvent être gérées à la fois. En terme de choses qui tiennent sur l'écran déjà, mais même, en terme de représentation des nombres (et même si on s'affranchit de la contrainte des nombres sur 64 bits, il y a bien une limite au nombre de bits qu'on peut stocker), et même si on n'avait pas cette contrainte, il faut que le jeu puisse renvoyer en temps raisonnable le résultat d'une action. On se doute bien que calculer le résultat d'une action de jeu quand il y a 10^9 jetons de plein de trucs bizarres sur le champ de bataille, ça devient impossible à faire en temps raisonnable.

Du coup, il faut bien définir ce que ça veut dire de "programmer un logiciel qui permet de jouer à Magic de manière non restrictive".

Par ailleurs, comme je le disais, même si coder les cartes demande un "boulot monstre", ça ne doit être fait qu'une fois, alors que l'I.A. a priori c'est un processus qui demande à repasser sur l'algo plein de fois. Donc je ne vois pas en quoi ça serait forcément la partie la plus rapide !
zombie33

Légende
le 17/12/2019 16:27
Citation :
Je ne comprends pas le résultat d'impossibilité que tu sembles donner. Pour avoir moi-même programmé ce projet, à aucun moment dans la conception je n'ai rencontré un point qui me fasse douter de réussir à le finir si j'en avais le temps.


Ben je vais pas reprendre toute la preuve, mais par exemple si un joueur décide au milieu d'une partie de magic de créer une machine de turing, comme tu le sais, il n'existe aucun programme capable de prédire l'issue de la partie. Cela montre bien que quelque soit ton programme il ne peut pas gérer toutes les configurations de jeu. Après le cas d'une machine de turing est un cas très spécifique, mais absolument rien ne permet de nous assurer qu'il n'y a pas d'autres cas problématiques qui peuvent avoir lieu.

Un autre problème qui a été évoqué d'ailleurs dans mon article (qui est un faux problème mais quand même un problème), c'est le cas suivant :

Citation :
Prenons l'exemple de deux joueurs possédant tous les deux sur le champ de bataille : Lich, Transcendence et Laboratory Maniac. Un joueur joue Menacing Ogre et la partie se transforme immédiatement en : "Chaque joueur choisit secrètement un nombre et celui qui a choisit le plus grand a gagné".


Ce genre de jeu ne peut être réellement programmé vu qu'on est limité par la capacité de la machine pour choisir notre nombre.



Citation :
Par ailleurs, comme je le disais, même si coder les cartes demande un "boulot monstre", ça ne doit être fait qu'une fois, alors que l'I.A. a priori c'est un processus qui demande à repasser sur l'algo plein de fois. Donc je ne vois pas en quoi ça serait forcément la partie la plus rapide !


Le machine learning n'est pas forcément la partie la plus rapide en temps, mais si on est arrivé au point que c'est maintenant la machine qui doit travailler, alors je considère que le boulot de programmation est terminé et donc le gros du boulot pour nous humain il est en amont.
zombie33

Légende
le 17/12/2019 16:44
Citation :
MTGO ne gère pas les boucles, et plus généralement, ne gère pas les effets qui devraient donner des nombres trop grands. Je pense que c'est raisonnable de fixer une limite, car il y a forcément une limite au nombre de choses qui peuvent être gérées à la fois. En terme de choses qui tiennent sur l'écran déjà, mais même, en terme de représentation des nombres (et même si on s'affranchit de la contrainte des nombres sur 64 bits, il y a bien une limite au nombre de bits qu'on peut stocker), et même si on n'avait pas cette contrainte, il faut que le jeu puisse renvoyer en temps raisonnable le résultat d'une action. On se doute bien que calculer le résultat d'une action de jeu quand il y a 10^9 jetons de plein de trucs bizarres sur le champ de bataille, ça devient impossible à faire en temps raisonnable.


C'est un autre problème mais très profond au final surtout quand le but est de déterminer une stratgie pour gagner.

Il est tout à fait possible lors d'une partie que deux decks combos s'affrontent (chacun pouvant créer un nombre X arbitrairement grand de jeton mais qu'une seule fois.) On comprend bien que le premier qui crée ses jetons va l'avoir dans l'os, puisque son adversaire en fera alors deux fois plus par exemple. Cependant c'est une dimension stratégique que l'on perd totalement si on fixe un max au nombre de jetons qu'un joueur peut contrôler ou un max au nombre d'itération d'une boucle.

Cela dit il est possible de contourner le problème. En introduisant du calcul formel dans le programme en créant X et 2X jetons de chaque côté du board. Mais cela ouvre la voie à des problèmes mathématiques encore plus important pour la suite (qui je pense font parties des cas de figures qu'on peut délaisser sans trop de scrupule)
Madmox
I guess Warhol wasn't wrong, Fame fifteen minutes long

Légende
le 17/12/2019 17:58
Citation :
Le machine learning n'est pas forcément la partie la plus rapide en temps, mais si on est arrivé au point que c'est maintenant la machine qui doit travailler, alors je considère que le boulot de programmation est terminé et donc le gros du boulot pour nous humain il est en amont.
Je ne suis pas sûr de comprendre le raisonnement. Je ne connais pas très bien le domaine, mais il me semble qu'il n'y a pas "un algo unique de machine learning" : on peut faire varier la configuration du/des des réseaux de neurones, et donc faire intervenir des humains sur l'algorithme même après avoir implémenté les règles du jeu. Sinon toutes les IA tendraient déjà vers la perfection, moyennant le temps d'apprentissage suffisant, ce qui il me semble n'est pas le cas :/
ZeSword
Bruxelles, Belgique

AVATAR
le 17/12/2019 17:59
zombie33 a écrit :
ZeSword a écrit :
Je ne comprends pas le résultat d'impossibilité que tu sembles donner. Pour avoir moi-même programmé ce projet, à aucun moment dans la conception je n'ai rencontré un point qui me fasse douter de réussir à le finir si j'en avais le temps.

Ben je vais pas reprendre toute la preuve, mais par exemple si un joueur décide au milieu d'une partie de magic de créer une machine de turing, comme tu le sais, il n'existe aucun programme capable de prédire l'issue de la partie. Cela montre bien que quelque soit ton programme il ne peut pas gérer toutes les configurations de jeu. Après le cas d'une machine de turing est un cas très spécifique, mais absolument rien ne permet de nous assurer qu'il n'y a pas d'autres cas problématiques qui peuvent avoir lieu.

Ben je ne vois pas la contradiction, justement. Tu as lu la construction comme moi, et tu vois qu'à aucun moment de la partie on ne demande aux règles de savoir prédire la fin du jeu, ce n'est pas ça la question ? Il n'y a pas de problème avec la construction de la machine de turing au niveau de la gestion des règles.

Pour le problème de la finitude des points de vie et des jetons, c'est par contre un vrai problème, mais je pense qu'on peut s'accorder pour dire que tant pis si sur ces cas-là, le jeu sur ordinateur est différent du jeu papier. Il y a tellement d'autres situations où le jeu ordinateur est très différent du jeu papier de toute façon (impossible de rater un trigger sur ordinateur par ex., rien que ça, stratégiquement parlant, ça change énormément de choses).
haut de page - Les forums de MV >> Général >> Discussion : page 1 | 2
Vous devez être identifié pour pouvoir poster sur les forums.