49 réponses à ce sujet

[dte]

edk, le 29 April 2016 - 08:17 , dit :

C'est négatif si l'IA considère comme bons des mauvais plays qui l'ont quand même fait gagner. C'est vrai sur un petit échantillon de match, mais quand tu passes sur une échelle beaucoup plus grande il y a peu de chance que les mêmes mauvais plays la fasse gagner à chaque fois, et donc l'IA est capable de revoir son jugement.

"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."

Comme le dataset c'était l’entièreté des games de kgs, on est donc dans l'"échelle  beaucoup plus grande". Et ça donnait une IA pas très bonne.  

lotus2862, le 29 April 2016 - 15:47 , dit :

J'avoue que j'ai du mal à envisager un résultat significatif d'un tel test. Aux échecs et au Go, les 2 joueurs ont le même jeu. A mtg, il y a une question de méta. Si je donne un même deck à l'IA qui à un MU moisi face au joueur humain, elle va se faire défoncer quoi qu'elle face. De plus, la chance entre en jeu ce qui n'est pas le cas du Go et des échecs. Si l'IA pioche de la merde, elle fera de la merde. Comment valider qu'une IA est meilleure qu'un joueur humain à MTG? Je crois que la question de poserait déjà entre 2 joueurs avec la même expérience...

Les deux (mtg et go/chess) s'évaluent exactement de la même manière: par le winning rate. Je ne vois pas la moindre différence. Quel que soit le jeu, une partie ne veut rien dire. Le taux de victoires, une fois passé un certain nombre de parties, reflète assez correctement la probabilité de victoire.

[Wycliff]

dte, le 29 April 2016 - 16:09 , dit :

Les deux (mtg et go/chess) s'évaluent exactement de la même manière: par le winning rate.

Au go ou aux échecs, les probabilités recherchées ne sont pas les mêmes.
Aux échecs, tu vas rechercher, en fonction du coup de ton adversaire, les probabilités des plays suivants par leur logique de jeu (plus grande probabilité de faire tel play car il mène à la victoire). Les victoires humaines reposaient d'ailleurs sur le caractère illogique de leurs plays. Ce n'est pas le cas à MtG où tu parles de probabilité de victoires; pas la probabilité de jouer telle ou telle carte à un instant T.

Le fait même que l'IA ne puisse pas anticiper plusieurs coups à l'avance et réajuster ses probabilités à chaque fois fait qu'un équilibre s'établit entre l'IA et l'humain.

d'ailleurs, le fait même qu'on parle de probabilité de victoire, et non pas probabilité des coups, fait que sur une partie (comme pour la confrontation au Go), l'IA ou l'humain peut se ramasser 5-0 sans qu'on puisse dire celui qui est le meilleur; car les probas peuvent avoir été contre lui.

Et l'IA risque probablement de choisir le deck qui présente le plus de probabilités d'avoir un bon MU contre le plus de decks possible. de ce fait, il est possible d'anticiper cela (l'humain peut aussi déterminer ce deck) en l'affrontant avec un deck ad hoc qui défonce celui choisit par l'IA.

je trouve que vous écartez trop rapidement la dimension humaine du jeu au profit de la dimension calcul. L'humain sait être un salop quand il le veut.

Modifié par Wycliff, 29 April 2016 - 18:02 .

[dte]

Wycliff, le 29 April 2016 - 17:54 , dit :

Au go ou aux échecs, les probabilités recherchées ne sont pas les mêmes.
Aux échecs, tu vas rechercher, en fonction du coup de ton adversaire, les probabilités des plays suivants par leur logique de jeu (plus grande probabilité de faire tel play car il mène à la victoire). Les victoires humaines reposaient d'ailleurs sur le caractère illogique de leurs plays. Ce n'est pas le cas à MtG où tu parles de probabilité de victoires; pas la probabilité de jouer telle ou telle carte à un instant T.

Tu peux me dire d'où tu tires cette information sur les victoires humaines via des plays à caractère illogique?

Sinon tu me quotes pour une réponse que je faisais sur comment évaluer si l'IA est efficace. Dans tous les cas (mtg ou go), tu évalues la valeur d'un joueur, humain ou non, via son pourcentage de victoires sur un grand nombre de parties.

Wycliff, le 29 April 2016 - 17:54 , dit :

Le fait même que l'IA ne puisse pas anticiper plusieurs coups à l'avance et réajuster ses probabilités à chaque fois fait qu'un équilibre s'établit entre l'IA et l'humain.

Et pour quoi non? En tout cas dans les deux jeux, je joue pareil: devant un choix, je réfléchis en fonction des réactions que je suppose que mon adversaire peut avoir.
Et c'est bien plus facilement prévisible à mtg qu'au go, du moins à mon niveau de jeu.

Wycliff, le 29 April 2016 - 17:54 , dit :

d'ailleurs, le fait même qu'on parle de probabilité de victoire, et non pas probabilité des coups, fait que sur une partie (comme pour la confrontation au Go), l'IA ou l'humain peut se ramasser 5-0 sans qu'on puisse dire celui qui est le meilleur; car les probas peuvent avoir été contre lui.

pareil au Go. D'ailleurs l'article ne dit pas qu'AlphaGo est meilleur que Fan Hui, mais que c'est une IA "that plays at the level of the strongest human players".
Si tu peux gagner 5-0, ça ne veux pas dire que tu es le meilleur. Mais ça veut dire que ton adversaire ne peut pas prétendre qu'il n'y a pas match.

Wycliff, le 29 April 2016 - 17:54 , dit :

Et l'IA risque probablement de choisir le deck qui présente le plus de probabilités d'avoir un bon MU contre le plus de decks possible. de ce fait, il est possible d'anticiper cela (l'humain peut aussi déterminer ce deck) en l'affrontant avec un deck ad hoc qui défonce celui choisit par l'IA.

je trouve que vous écartez trop rapidement la dimension humaine du jeu au profit de la dimension calcul. L'humain sait être un salop quand il le veut.

Là, tu parle encore au niveau du simple match. Tu va quand même gentiment perdre ton tournoi pendant que l'IA va peut être passer en top 8 à X-2 .
En plus l'IA ne va pas du tout choisir systématiquement le meilleur deck. Le type d'IA sur lequel est basé AlphaGo, c'est du Monte Carlo. Donc tu risques de franchement te ramasser

[FoW87]

Je veux pas paraître brutal mais j'ai l'impression que beaucoup de personnes n'ont aucune idée du fonctionnement des IA actuelles.

Et non mtg n'est pas un jeu démesurément compliqué dans son fonctionnement pour une IA.

Mais ça, dte l'explique très bien (d'ailleurs tu bosses dans le domaine ?)

[falcry]

C'est pas du Monté-Carlo, bien que l'on doit avoir des phases exploratoires (choisir un truc sous optimal pour voir si cela ne peut pas améliorer les choses à la fin. Comme double bolt sur un tarmo par exemple mais de l'apprentissage par renforcement.

Grossi modo, l'idée est d'associer à chaque coup une probabilité de gain (pas forcément de victoire, mais cela doit rester le but final).
L'apprentissage permet de construire ces probas.

Il y'a quand même un gros soucis à magic. C'est la non observabilité.
Si on ne connais pas assez le système (tout le jeu, les mains etc.) rien ne prouve que l'on peut amener le système à l'état désiré (la victoire).
Du coup l'apprentissage peut amener à avoir des stratégies sous optimales, genre gagner seulement la première ronde, ou alors, all in car s'empaller sur daze ou fow est statistiquement négligeable...
Sans même compter que à mtg des fois on ne peut juste pas gagner.
Et des cas comme ça, c'est vraiment pas cool lors de l'apprentissage ^^

[dte]

FoW87, le 30 April 2016 - 13:23 , dit :

Je veux pas paraître brutal mais j'ai l'impression que beaucoup de personnes n'ont aucune idée du fonctionnement des IA actuelles.

Et non mtg n'est pas un jeu démesurément compliqué dans son fonctionnement pour une IA.

Mais ça, dte l'explique très bien (d'ailleurs tu bosses dans le domaine ?)

Non, je ne bosse pas dans le domaine mais vu que la discussion part d'un article, je l'ai lu. La plupart des choses que j'ai dites sont en faites des redites, la partie mtg mise à part.

D'ailleurs pour ceux qui pensent que le hasard à la moindre influence, je vous invite à le relire (l'article, je remets le lien: http://www.nature.co...ature16961.html), et notamment la partie où est expliqué que ça fait un bail que les IA ont un niveau surhumain dans plusieurs jeux de hasard.

falcry, le 01 May 2016 - 13:01 , dit :

C'est pas du Monté-Carlo, bien que l'on doit avoir des phases exploratoires (choisir un truc sous optimal pour voir si cela ne peut pas améliorer les choses à la fin. Comme double bolt sur un tarmo par exemple mais de l'apprentissage par renforcement.

L'abstract de l'article:

The game of Go has long been viewed as the most challenging of classic games for artificial intelligence owing to its enormous search space and the difficulty of evaluating board positions and moves. Here we introduce a new approach to computer Go that uses ‘value networks’ to evaluate board positions and ‘policy networks’ to select moves. These deep neural networks are trained by a novel combination of supervised learning from human expert games, and reinforcement learning from games of self-play. Without any lookahead search, the neural networks play Go at the level of state-of-the-art Monte Carlo tree search programs that simulate thousands of random games of self-play. We also introduce a new search algorithm that combines Monte Carlo simulation with value and policy networks. Using this search algorithm, our program AlphaGo achieved a 99.8% winning rate against other Go programs, and defeated the human European Go champion by 5 games to 0. This is the first time that a computer program has defeated a human professional player in the full-sized game of Go, a feat previously thought to be at least a decade away.


J'ai peut-être raté un truc, mais il me semble que la base c'est du MC non? Après ce n'est pas que du MC, mais ça l'utilise quand même pour construire les arbres de débouchés possibles.

Après l'innovation apportée par AlphaGo (par rapport à d'autres IA de Go qui utilisaient déjà ces arbres créés parMC) réside effectivement dans la méthode d'apprentissage.

falcry, le 01 May 2016 - 13:01 , dit :

Il y'a quand même un gros soucis à magic. C'est la non observabilité.
Si on ne connais pas assez le système (tout le jeu, les mains etc.) rien ne prouve que l'on peut amener le système à l'état désiré (la victoire).
Du coup l'apprentissage peut amener à avoir des stratégies sous optimales, genre gagner seulement la première ronde, ou alors, all in car s'empaller sur daze ou fow est statistiquement négligeable...

Quel que soit le niveau du joueur, il va s'empaler régulièrement sur du All in into daze ou trop d'attente par peur de Daze.
Un bon joueur, humain ou IA, gagnera plus souvent car il sera capable d'évaluer plus correctement s'il y a plus de chance de gain en se lançant maintenant ou s'il vaut mieux garder son Natural Order en main.

Sinon, voir encore le fait que les IA battent allègrement les humains à pas mal de jeux de stratégie qui utilisent des lancés de dés.
Don je pense que la "non observabilité" est irrelevante. (mais là c'est juste un avis personnel, si quelqu'un à des contre arguments, je suis tout ouïe).

Modifié par dte, 01 May 2016 - 19:29 .

[falcry]

Alors, pour la partie
" We also introduce a new search algorithm that combines Monte Carlo simulation with value and policy networks. "
En vrai, c est la partie, comme je disais, exploratoire qui est du MC. Ils n'ont pas non plus inventé d'algo. Ils ont "juste" affiné (et les capacités, c'est Google) et applliqué des algos très lourds d'apprentissage (Apprentissage par renforcement, une branche du supervised machine learning.).
Le "we introduce" dans les articles scientifiques, c'est la plus part du temps juste une presentation.
De plus, c'est un Science, donc toujours un peu vulgarisé.
Le gros du boulot est en pratique d'arriver à trouver comment savoir si un coup est bon (la "value" V. C'est lié à ce que j'appelais gain. En pratique, V = somme gamma^k r_k. Il faut pouvoir affecter à chaque coup un gain (reward), afin de savoir si telle ou telle stratégie est bonne). Cela a un impact terrible sur l'apprentissage.

L'observabilité (et la controlabilité, des notions duales -liées de manières très fortes- ) est juste fondamentale. C'est LE fondement mathématique et universel de toutes les méthodes visant à modifier un système. Si l'observation n'est pas suffisante, on ne peut pas comprendre assez bien le système, et donc on n'a aucune chance de pouvoir le controler (si ce n'est par hasard). C'est pas pour rien si l'article arxiv parlant de MTG met (entre autre) l'accent sur le fait que c'est bien plus complexe que le go, où l'ensemble du système est connu.

Bref, je peux appronfondir des points spécifiques si vous le souhaitez ^.^

Modifié par falcry, 01 May 2016 - 20:06 .

[dte]

falcry, le 01 May 2016 - 20:04 , dit :

Alors, pour la partie
" We also introduce a new search algorithm that combines Monte Carlo simulation with value and policy networks. "
En vrai, c est la partie, comme je disais, exploratoire qui est du MC. Ils n'ont pas non plus inventé d'algo. Ils ont "juste" affiné (et les capacités, c'est Google) et applliqué des algos très lourds d'apprentissage (Apprentissage par renforcement, une branche du supervised machine learning.).
Le "we introduce" dans les articles scientifiques, c'est la plus part du temps juste une presentation.
De plus, c'est un Science, donc toujours un peu vulgarisé.
Le gros du boulot est en pratique d'arriver à trouver comment savoir si un coup est bon (la "value" V. C'est lié à ce que j'appelais gain. En pratique, V = somme gamma^k r_k. Il faut pouvoir affecter à chaque coup un gain (reward), afin de savoir si telle ou telle stratégie est bonne). Cela a un impact terrible sur l'apprentissage.

Pas de problème là-dessus. Leur innovation n'est pas la combination, mais une combination.
Je pense qu'on s'est mal compris mais qu'on est d'accord là dessus.

Là où on est pas d'accord, c'est là-dessus:

falcry, le 01 May 2016 - 20:04 , dit :

L'observabilité (et la controlabilité, des notions duales -liées de manières très fortes- ) est juste fondamentale. C'est LE fondement mathématique et universel de toutes les méthodes visant à modifier un système. Si l'observation n'est pas suffisante, on ne peut pas comprendre assez bien le système, et donc on n'a aucune chance de pouvoir le controler (si ce n'est par hasard). C'est pas pour rien si l'article arxiv parlant de MTG met (entre autre) l'accent sur le fait que c'est bien plus complexe que le go, où l'ensemble du système est connu.

Bref, je peux appronfondir des points spécifiques si vous le souhaitez ^.^

Je ne vois pas en quoi mtg présenterait plus de non-observabilité que le backgammon. (mais je me plante peut-être)
Par rapport au go, il n'y a pas plus de possibilités dans les réponses qu'un adversaire peut avoir.
Tu fais tes arbres de recherches par rapport à tes probas de tirage et celles de ton adversaire. Et oui, pour moi la liste adverse est largement connue. Quand on joue, dans 95 % des cas après 3 tours on connaît la liste adverse à 2-3 slots près pour le MD, un peu plus pour le side. Le fait que l'information ne soit pas parfaite n'empêche pas que la qualité de play est notre capacité à agir par rapport à cette information.

Donc si tu peux approfondir pourquoi mtg serait plus complexe que le go, ça m'intéresse.

[falcry]

Si de l'information est cachée (la main de l'adversaire), il est bien plus difficile de prendre une décision que si elle est connue.
Cela veut dire que le play optimal est bien plus difficile à identifier (voir impossible à identifier).
C'est ça l'observabilité.
Pour quelqu'un d'omniscient (connaissant les mains et l'ordre des cartes dans les biblios)  les plays optimaux, (si l'on excepte le shuffle) existent.
Le backgamon (si je me souviens un peu du jeu ^^) c'est juste du hasard. Une approche purement probabiliste est donc possible, et surtout pertinente (nombre de lancés dans une seule partie).
Evidement, on voit le lien ici avec les probas à MTG:
Oui on connait pas l'ordre des cartes, mais on peut "deviner" (c'est de l'inférence bayesienne) ce que l'autre joue, ce qu'il peut avoir en main. On peut donc tenter des plays, malgé une information "partielle" (observabilité partielle). Rien ne dit qu'elle est suffisante.
On a donc un play "optimal" qui va être probabiliste. Cela ne veut pas dire qu'il amenera forcement à la victoire, alors qu'une autre séquence aurait pu. De plus, apprendre ces plays optimaux est du coup bien plus dur, puisque certains plays optimaux menent en fait à des defaites (genre je me prend pas une daze mais j'ai perdu un tour et perd quand même).

D'où l'importance, dans l'apprentissage, de faire des plays parfois "pourris", histoire de voir si au final ça peut pas parfois être meilleurs. C'est la partie Monté-Carlo (que l'on appelle en pratique exploration).

[dte]

ok, donc je vois là où on n'est pas d'accord assez clairement: c'est dans la définition d'un play optimal.

Donc voici ma définition: le play optimal c'est le choix qui présente la probabilité la plus élevée de t'amener à la victoire.
Le play qui te fait gagner n'a pour moi rien d'un play optimal. ça peut être un très mauvais play, et inversement, un play optimal peut te faire perdre.

Et pour moi cette définition s'applique au go, au backgammon, et à mtg.


C'est une erreur aussi (à mon avis) de considérer que tu as plus d'info cachée à mtg qu'au go.
Je pencherais pour dire que tu en as plus au go. Tu ne sais pas ce que ton adversaire va jouer dans les deux cas. Mais à mtg, tu peux restreindre à quelques cartes ce que tu as à prendre en compte, et tu n'es pas très souvent surpris. Au go, tu es très souvent surpris.

Pour moi évaluer la valeur d'un potentiel ko tardif est bien plus difficile que de savoir s'il faut lancer cabal therapy maintenant, et quoi nommer si elle se résout.

Pour ceux qui diraient qu'il n'y a pas de hasard au go, je dirais qu'il n'y en a pas non plus à pile ou face. Quand la pièce est lancée, la face sur laquelle elle retombe est entièrement fonction de sa vitesse, son accélération, de sa masse, et de la morphologie de l'endroit où elle est lancée. Mais comme on n'est absolument incapable de prédire le résultat, ça s'apparente à du hasard.
Au go, le coup que jouera votre adversaire dans 2 coups alors que vous en êtes au dixième s'apparente aussi à du hasard. Voire même son prochain coup si les deux joueurs sont bons.

[falcry]

Mathématiquement, c'est pas du tout la même chose. Donc c'est pas une erreur du tout, c'est juste la  théorie, très puissante (et pas parfaitement comprise dans le cadre de système hautement non linéaire, discret ou non standard, genre le go ou MTG ). Je peux donner des refs, ou tu peux regarder la théorie de Kalman. Elle est évidente en linéaire, bien moins en dynamique non linéaire

Le but est exclusivement de gagner. Et c'est pourquoi identifier un coup optimal qui te fait pas forcément gagner à la fin (par ce que pas de bol blabla déchatte), ou réciproquement, est vraiment une chose très dure.
C'est pas méchant du tout, mais dans ces domaines, il ne faut pas coller "ses" définitions quand elles ont un sens mathématique (ça me rappelle une discussion sur la variance ).

Par exemple, au go, IA contre IA (si c'est la même), et sans coup d'exploration (i.e., random), la partie se joue sur qui commence.
Pas à MTG (suivant les decks et les top decks).
Evidement, quand il y a un joueur humain en face, certains coups sont moins optimaux. Il y a un nombre relativement restreint de coups optimaux (relativement, c'est pour cela que les IA ont besoin de quantités énormes de données). C'est du pain béni pour l'IA (cf les scores de AlphaGo), sauf quand le coup est tellement non optimal qu'il est en fait génial (ou tellement stupide ><) qu'il ne peut pas être interprété par l'IA sur la base de ce qu'elle a déjà appris.

PS: Ce que l'humain interprète et traite comme information est incroyable. C'est ce que certaines théories essaient d'émuler. En particulier pour la reconstruction de l'information manquante (j'en reviens à l'observabilité).
PS2: le lancer de pièces est aléatoire en vrai statistique. On ne considère pas la physique. Qu'on arrive pas à produire un vrai aléatoire est une autre question

[dte]

falcry, le 01 May 2016 - 22:52 , dit :

C'est pas méchant du tout, mais dans ces domaines, il ne faut pas coller "ses" définitions quand elles ont un sens mathématique (ça me rappelle une discussion sur la variance ).

C'est pas pris comme méchant, pas de souci. Je me souviens bien de la discussion variance.
Par contre "ma" définition de ce qu'est un play optimal me semblait consensuelle, pas personnelle.
Que le play optimal soit celui qui a le plus de chances de te faire gagner, qu'il te fasse gagner ou non.

Quelle serait tla définition du "play optimal" selon toi?

falcry, le 01 May 2016 - 22:52 , dit :

Le but est exclusivement de gagner. Et c'est pourquoi identifier un coup optimal qui te fait pas forcément gagner à la fin (par ce que pas de bol blabla déchatte), ou réciproquement, est vraiment une chose très dure.

ça je suis d'accord, que ce soit quelque chose de difficile que d'identifier un bon play alors qu'il t'a amené à la défaite. Mais je pense que l'IA ici présente un avantage sur l'humain: elle peut jouer un nombre bien plus considérable de parties, et donc rejouer les variations un grand nombre de fois.

falcry, le 01 May 2016 - 22:52 , dit :

Mathématiquement, c'est pas du tout la même chose. Donc c'est pas une erreur du tout, c'est juste la  théorie, très puissante (et pas parfaitement comprise dans le cadre de système hautement non linéaire, discret ou non standard, genre le go ou MTG ). Je peux donner des refs, ou tu peux regarder la théorie de Kalman. Elle est évidente en linéaire, bien moins en dynamique non linéaire

Je veux bien des refs, si tu en as qui sont bien pédagogiques pour le non-initié. Je viens de lire ce que wikipedia avait à offrir sur "Kalman filter", et c'est le genre de trucs qui m'intéresse.

falcry, le 01 May 2016 - 22:52 , dit :

Par exemple, au go, IA contre IA (si c'est la même), et sans coup d'exploration (i.e., random), la partie se joue sur qui commence.
Pas à MTG (suivant les decks et les top decks).

ça en revanche ça me parait étonnant comme affirmation. Comment expliques-tu les statistiques de victoires entre différents programmes?
Et je ne sais pas exactement comment fonctionne AlphaGo , mais j'ai joué contre quelques programmes de go, et si tu reviens exactement au même état tous ceux que j'ai affronté pouvaient effectuer des choix différents.
C'était d'ailleurs instructif de récupérer une partie jouée contre un humain et de voir aux points décisifs "qu'est ce qui aurait changé si..." en jouant vs un ordi.

falcry, le 01 May 2016 - 22:52 , dit :

Evidement, quand il y a un joueur humain en face, certains coups sont moins optimaux. Il y a un nombre relativement restreint de coups optimaux (relativement, c'est pour cela que les IA ont besoin de quantités énormes de données). C'est du pain béni pour l'IA (cf les scores de AlphaGo), sauf quand le coup est tellement non optimal qu'il est en fait génial (ou tellement stupide ><) qu'il ne peut pas être interprété par l'IA sur la base de ce qu'elle a déjà appris.

humain ou pas, la séquence de play optimaux n'a toujours pas été trouvée au go.
Le go est sensé être déterministe, mais la séquence idéale reste à trouver.
Mais de ce que j'en sais ou ai observé, un coup stupide n'aide jamais. Jamais. L'IA ne "réponds"  pas aux coups humain, et n'essaye pas "d'interprêter" les coups adverses. Un humain non plus d'ailleurs, du moins moi je n'essayais pas de savoir pourquoi quelqu'un joue un truc, sauf si c'était vraiment bizarre. Dans ce cas je regardais et essayais de comprendre, au cas où. Au second coup bizarre d'un adversaire qui est derrière, je le considérais simplement malpoli.
Le go est souvent enseigné avec un florilège de proverbes plus ou moins douteux. Mais une chose sure, c'est que répondre au go c'est mal jouer.

[falcry]

Je réponds sur téléphone donc je risque de faire des phrases bizarres.

Je vais pas arguer sur le go d'un point de vue stratégique. Mais d'un point de vue mathématiques, même si il n'est pas calculable, il y a bel et bien des séquences optimales, le plateau étant parfaitement connu.
Le coup optimal te fait donc gagner. En pratique, le coup optimal est très peu probabiliste (on l'approxime juste, cette approximation l'est, par contre).

Si tu préfères, tu peux remplacer coup stupide par non optimal. C'est pareil ici.

À mtg, l'information manque. Il est donc possible de comprendre qu'un play est optimal que bien plus tard. Jouer le coup instantanément optimal (greedy action) (comme bolter a vue un delver) n'est pas forcément donc optimal au long terme (donc gagner la partie) (Il reste trois PVs à l'adversaire) J'avais peut être pas été clair. Et çà, c'est très dur voir impossible à trouver pour les systèmes à informations cachées.

Kalman (qui était une brutasse)
J'essaierai de regarder si j'ai un article qui traine demain si j'y repense. En attendant :
https://en.m.wikiped...i/Observability

[dte]

falcry, le 02 May 2016 - 00:25 , dit :

Je vais pas arguer sur le go d'un point de vue stratégique. Mais d'un point de vue mathématiques, même si il n'est pas calculable, il y a bel et bien des séquences optimales, le plateau étant parfaitement connu.
Le coup optimal te fait donc gagner. En pratique, le coup optimal est très peu probabiliste (on l'approxime juste, cette approximation l'est, par contre).

Ton "donc" est faux. Ne jouer que des coups optimaux t'amènera la victoire, ça d'accord. Un coup optimal, non, absolument pas. On arrive tous à en faire quelques uns
Et je suis aussi d'accord pour dire que ça ne s'applique pas à mtg: ne jouer que des coups optimaux pendant une game ne te garanti absolument pas la victoire.
Là où je suis en désaccord, c'est que pour moi à mtg il y a un coup optimal aussi, et qui est complètement indépendant de la nature des cartes dans la main de ton adversaire. L'information n'est pas cachée, l'information c'est que ton adversaire à 3 cartes en main.
Il y a un coup optimal à jouer considérant que l'adversaire à 3 cartes en main.
La différence, je te l'accorde, c'est qu'à mtg jouer des coups optimaux peut t'amener à la défaite alors que des coups sous-optimaux peuvent t'apporter la victoire. Mais moins souvent.


Ce que je tirerais de ta définition, c'est que le go est bien plus difficile à jouer que mtg: au go, personne ne joue jamais ce coup optimal, et l'approximation en est toujours franchement loin, que le joueur soit IA ou humain.
Et il est sûr qu'il y a bien plus de différence de chances de victoires entre un bon et un mauvais joueur de go (pour une partie sans handicap) qu'entre deux joueurs de niveau inégal à mtg.
Après, ça pour moi ce n'est pas forcément intéressant, ce qui l'est, dans chaque jeu, c'est d'essayer d'être le plus fréquemment possible proche d'un jeu "optimal".

falcry, le 02 May 2016 - 00:25 , dit :

À mtg, l'information manque. Il est donc possible de comprendre qu'un play est optimal que bien plus tard. Jouer le coup instantanément optimal (greedy action) (comme bolter a vue un delver) n'est pas forcément donc optimal au long terme (donc gagner la partie) (Il reste trois PVs à l'adversaire) J'avais peut être pas été clair. Et çà, c'est très dur voir impossible à trouver pour les systèmes à informations cachées.

Pour moi tu confonds "victorieux" et "optimal". 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.

Ton exemple est assez typique, tu as une bolt, il y a un delver en face, ton choix se résume à évaluer l'intérêt d'une bolt par rapport à celui d'un delver, en fonction des chances que ta bolt a de se résoudre, des totaux de pv, et des cartes dispos.
Par contre, que tu choisisse de bolter ou non, tu ne sais pas si tu va gagner ou pas. Mais une des deux options te donne une plus grande probabilité de gagner la partie, c'est le play optimal.

falcry, le 02 May 2016 - 00:25 , dit :

Kalman (qui était une brutasse)
J'essaierai de regarder si j'ai un article qui traine demain si j'y repense. En attendant :
https://en.m.wikiped...i/Observability

Merci, je regarderai!

[lotus2862]

Il faut vraiment que tu précises ce que tu attends de la machine qui va jouer à magic car sinon, le débat n'a pas de sens. D'après ce que je comprends de tes interventions, tu restreints énormément. Si je résume, ton IA va jouer un tournoi dans un méta connu avec la possibilité de choisir un deck qu'elle aura trouvé dans la base MTG top 8. Dans ces conditions, je te rejoins, on a probablement moins de choix qu'au Go encore que ...

Si ton IA doit fabriquer son propre deck dans un format choisi le jour même ou même faire un draft, je sens que ça va se compliquer pour elle.