Aller au contenu


Magic, hearthstone et l'IA


  • Veuillez vous connecter pour répondre
49 réponses à ce sujet

#46 falcry

falcry
  • Membres
  • 400 messages

Posté 02 May 2016 - 09:37

Alors, il me faut sans doute préciser comment marche l'IA de google (et l'apprentissage par renforcement). Note bien que je ne parle QUE de ce type de technique depuis le début. Il en existe d'autres.
Pour l'IA, jouer des coups optimaux DOIT amener à un bon score (normalement la victoire si on a bien décrit le score. C'est loin d'être trivial). Le coup optimal doit donc tout prendre en compte. Pas seulement l'état de la partie au troisième tour, mais l'état de la partie jusqu'à la fin.
Ce que tu décris est ce que l'on appelle la greedy action: faire la meilleure action au temps t. Cela ne veut pas dire que c'est la meilleure action au sens partie, et c'est donc pas ce qui est recherchée par les IA.

C'est pas très très naturel, mais c'est vraiment un point clé de l'apprentissage. C'est d'ailleurs pour cela que les phases exploratoires (faire des actions non optimales) sont absolument indispensables pour avoir une phase d'apprentissage réussie.
Un exemple: si tu es pilote de course, et que tu passes super vite les tours, mais que tu vas tellement vite que tu dois freiner sur un virage, ce qui use tes pneus et te faire faire un changement plus tard, ben, au final tu es pas victorieux. Pourtant, chaque tour est optimal.
Après, certains jeux à mtg doivent être très greedy (les jeux aggros qui se jouent en peu d'actions), tandis que c'est à priori moins le cas pour les jeux control.

D'ailleurs, les actions d'une IA (dans le présent cadre) ne visent qu'à maximiser une fonction, appelée la Value. Elle est constituée de l'ensemble des gains successifs. Chaque coup est paramétré par une autre fonction, qui est nommée la politique.
La politique optimale est une fonction qui map les informations disponible sur le coup à faire pour maximiser à la fin la Value. C'est donc bien un ensemble de coups qui est systématiquement (bien qu'intrinséquement) considéré.


"L'information n'est pas cachée, l'information c'est que ton adversaire à 3 cartes en main."
De l'information est cachée. C'est évident, sauf si tu vois les cartes dans les lunettes de ton adversaire (et encore, il manque le deck et tout). Après, on fait ce qu'on peut avec l'information que l'on a. C'est pour cela que c'est bien plus complexe à traiter que le go. Je ne dis pas que le jeu est plus dur. Le problème est plus dur. Certains problèmes sont extrement dur à poser, mais relativement facile à résoudre une fois bien posé. Et tout l'intérêt est d'ailleurs de les poser :)

"Il est pour moi toujours possible à l'instant t, de déterminer quel est le play optimal et il n'y a pas vraiment d'information cachée: tu sais que ton adversaire à x cartes en main, tu en ignores la nature exacte, tu as des indices au vu de ses précédents plays.
Tout cela est l'information que tu as, en plus du board state, visible, de ta main, de ta liste, et de la liste adverse supposée. C'est en général pas trop complexe à appréhender (mais parfois ça l'est).
Il y a un coup optimal en fonction de ces informations, qui ne sont pas cachées.
"
Tu viens de décrire assez joliement ce qu'est l'observabilité :) Mais il est loin d'être possible de toujours pouvoir le faire. Ton thermomètre te permet pas de savoir le temps qu'il fait dehors.
Peut on remonter à l'état du système (savoir quel jeu joue l'adversaire, ce qu'il a probablement en main) à partir des infos visibles et passées. Ce qui est pas encore trop complexe à appréhender pour l'humain l'est, à l'heure actuel, immensément pour une machine. Mais cela devrait sauter d'ici moins de 5 ans (enfin, ça a déjà partiellement sauté dans les systèmes physiques. Et je sais vraiment de quoi je parle là :brag:).


Il me semble que ce review est pas mal: Il parle brievement de l'observabilité et controlabilité, et également de l'importance de connaitre le systeme.
Van De Wal, Marc, and Bram De Jager. "A review of methods for input/output selection." Automatica 37.4 (2001): 487-510.



PS:
Pourquoi j'ai ça:
"Vous pouvez poster encore 12 message(s) jusqu'au aujourd'hui, 14:01." ?! oO
Merci pour la réponse!

Modifié par falcry, 02 May 2016 - 10:30 .


#47 Adibou1er

Adibou1er
  • Modérateurs
  • 3426 messages

Posté 02 May 2016 - 10:27

Pour ton PS : il y a une limite de 20 posts/personne/24h.
Pour lutter contre les spammeurs qui nous saoulent en ce moment.

edit Bens: limitation passée à 50 msg/24h, normalement ça ne devrait pas trop gêner pour une utilisation normale du forum.

Modifié par Bens, 02 May 2016 - 19:53 .

Voir le messageDebonair, le 08 October 2013 - 08:38 , dit :

Allez, comme dirait Adibou, soubi.


#48 dte

dte
  • Modérateurs
  • 2282 messages

Posté 02 May 2016 - 19:05

 falcry, le 02 May 2016 - 09:37 , dit :

Alors, il me faut sans doute préciser comment marche l'IA de google (et l'apprentissage par renforcement). Note bien que je ne parle QUE de ce type de technique depuis le début. Il en existe d'autres.
Pour l'IA, jouer des coups optimaux DOIT amener à un bon score (normalement la victoire si on a bien décrit le score. C'est loin d'être trivial). Le coup optimal doit donc tout prendre en compte. Pas seulement l'état de la partie au troisième tour, mais l'état de la partie jusqu'à la fin.
Ce que tu décris est ce que l'on appelle la greedy action: faire la meilleure action au temps t. Cela ne veut pas dire que c'est la meilleure action au sens partie, et c'est donc pas ce qui est recherchée par les IA.

Non, il vaut mieux considérer un coup qu'une partie.
Si j'ai bien compris, justement c'est un écueil qu'ils ont dû éviter: si ils ne considéraient dans leur fonction de scoring que le résultat de la partie (victoire / défaite), ça résultait en de l'overfitting.
Du coup impossible de savoir si un coup est bon ou pas, vu que pour gagner une partie de Go il faut jouer un tas de mauvais coup (non pas que ça aide, mais tu dois bien jouer à ton tour, et ce sera probablement un coup pas terrible assez souvent).

Ici:
The naive approach of predicting game outcomes from data consisting
of complete games leads to overfitting. The problem is that
successive positions are strongly correlated, differing by just one stone,
but the regression target is shared for the entire game.
When trained
on the KGS data set in this way, the value network memorized the
game outcomes rather than generalizing to new positions, achieving a
minimum MSE of 0.37 on the test set, compared to 0.19 on the training
set. To mitigate this problem, we generated a new self-play data set
consisting of 30 million distinct positions, each sampled from a separate
game. Each game was played between the RL policy network and
itself until the game terminated. Training on this data set led to MSEs
of 0.226 and 0.234 on the training and test set respectively, indicating
minimal overfitting.


 falcry, le 02 May 2016 - 09:37 , dit :

Il me semble que ce review est pas mal: Il parle brievement de l'observabilité et controlabilité, et également de l'importance de connaitre le systeme.
Van De Wal, Marc, and Bram De Jager. "A review of methods for input/output selection." Automatica 37.4 (2001): 487-510.

Merci, je l'ai récupérée. Par chance, tu ne va pas au bom? Si oui, j'aurais des questions.

Modifié par dte, 02 May 2016 - 19:07 .


#49 falcry

falcry
  • Membres
  • 400 messages

Posté 02 May 2016 - 20:43

Tu as mal compris. Je reconnais que c'est moyennement bien écrit et difficle à comprendre si on ne connait pas parfaitement le domaine.

Les coups sont appris en jouant les parties.
Pour savoir comment démarrer, ils sont parti du coup non de parties existantes (donc une suite de coups), mais de positions randomisés (qui peuvent elles provenir de parties).  C'est classique en RL, par rapport aux réseaux de neurones et à l'apprentissage non supervisé. On apprend en faisant tourner le système et en l'updatant.
Mais c'est bien ensuite une suite de coups qui est utilisé pour l'apprentissage. Tu te doutes bien qu'ils n'ont pas entraîné l'IA avec seulement 30 millions de coups (en pratique, c'est vraiment pas grand chose) quand l'issue d'une partie est de plus très incertaine! Ils ont par contre accordé une importance particulière aux conditions initiales. Je suppose, du moins ; l'article reste assez cryptique sur l'algo utilisé.
Enfin au final, c'est classique : en RL, le soucis principal est d'avoir de bons rewards. L'intuition est parfois vraiment traitre pour les identifier.

À priori je serais pas au bom. Un peu short en thunes, plus d'autres histoires, avant de repartir aux USA :(
Toujours prêt , par contre, pour discuter, ici, par MP, ou même autour d'un verre pour les parisiens !

Edit: un peu de mise en page+typo+enlevage de brag toussa. C'est mal d'écrire d'un tel ><

Modifié par falcry, 03 May 2016 - 10:01 .


#50 dte

dte
  • Modérateurs
  • 2282 messages

Posté 09 March 2017 - 23:15

La semaine dernière, une nouvelle percée de l'IA dans le domaine des jeux a été publiée, cette fois pour un jeu à caractère aléatoire et information cachée: le poker.
Il semblerait que deux IA différentes puissent jouer en 1 vs 1 à un niveau équivalent ou meilleur que des joueurs professionnels.

L'une d'elles (après la phase d'apprentissage, là encore c'est du deep learning et demande une grande capa de calcul) peut jouer à ce niveau sur un ordi portable normal:
http://science.scien...ce.aam6960.full