MtG : Humans Vs Computer

nicofromtokyo · 11 Août 2007, 05:56:17

Il existe des programmes d'echecs capablent desormais de battre les humains. J'ai entendu dire que recemment un programme avait ete mis au point pour battre les champions du monde de Poker (Y est-il parvenu?). Et je me demandais si un joueur virtuel de Magic pourrait systematiquement battre n'importe qui avec n'importe quel deck, en diminuant les missplays a zero. J'ai deja entendu parle d'un jeu MtG sur PC il y a tres longtemps, donc a priori c'est programmable.
En sachant que ce qui fait la difference entre des joueurs, c'est la capacite a analyser la situation et a gerer la partie en utilisant ses ressources tout en faisant le moins d'erreurs possibles, je me posais la question d'un software qui gagnerait tous les tournois du monde ou qui creerait tous les meilleurs du monde... Possible or not??

Juju · 11 Août 2007, 07:25:28

(/me parle en tant que deja implique dans le domaine :mrgreen:)

Le programme de poker dont tu parles, developpe a Alberta, ca fait quelques temps qu'il existe deja. Enfin, juste pour dire :)
Les humains ont gagne; de peu, visiblement.

Pour ce qui est du jeu PC de magic, c'etait un super vieux jeu qui fonctionnait assez mal, et a un temps ou moins de cartes existaient. Pas une reussite.

La programmation d'un joueur de magic qui battrait tout le monde exige deja que tu definisses ce que tu entends par battre tout le monde. Est ce que tu parles d'un programe qui, quand tu lui donnes un deck, joue au mieux? Ou d'un programme qui se comporte comme un vrai humain, donc construit son deck aussi?

Dans le premier cas pourquoi pas. Meme si l'environnement est assez enorme (bcp d'actions possibles, a ordonnancer etc...), le challenge est relativement similaire. Dans le second no way: l'environnement est *beaucoup trop* enorme. Ou alors dans un futur lointain, tres lointain.

Le gros soucis, c'est que ca serait, dans les deux cas, un boulot absolument fabuleux pour quasiment rien. Boulot fabuleux puisqu'il faudrait programmer tout le jeu, et travailler sur un environnement avec un nombre de variables/actions/etats/... totalement delirant compare aux jeux plus classiques. Dans le deuxieme cas ca devient carrement du suicide amha. Pour quasiment rien, puisque un mec qui bat les champions du monde de poker, d'echecs, de dames... ca parle. Un mec qui cree un champion du monde de magic, la majorite des gens vont te dire "c'est quoi?" Et pour enfoncer le clou, je suis meme pas sur que wizards serait interesse pour financer un boulot pareil.

Bref, avec un tel ratio difficultes * temps / resultats potentiels, j'y crois pas du tout.

Lionceau · 11 Août 2007, 09:37:38

T'inquiete juju, c'est nicofromtokyo qui finance la these/le projet, tu peux meme programmer en jap si tu veux :mrgreen:

Juju · 11 Août 2007, 09:52:48

Aucune envie; comme j'ai dit, le ratio interet/boulot est totalement risible ;)

nicofromtokyo · 11 Août 2007, 11:55:42

Citation de: Juju le 11 Août 2007, 07:25:28
La programmation d'un joueur de magic qui battrait tout le monde exige deja que tu definisses ce que tu entends par battre tout le monde. Est ce que tu parles d'un programe qui, quand tu lui donnes un deck, joue au mieux? Ou d'un programme qui se comporte comme un vrai humain, donc construit son deck aussi?

Je pensais en fait au deux: a un joueur virtuel qui ferait ZERO missplay avec n'importe quel deck, et a un programme qui construirait le MEILLEUR deck contre un environnement donné, voire qu'il créerait lui-même l'environnement avec les decks les plus optimisés possibles.
Le meilleur joueur virtuel de dames existe bien, et je suis pas sur que ça ait été financé par l'Etat. Je parle de toute façon pas de l'intêret de la chose, qui est nul (si ce n'est qu'on aurait plus à subit les théories parfaites de Smennen), mais simplement d'un point de vue idéaliste. Est-ce qu'on peut résumer Magic à des lignes de codes quoi...

Juju · 11 Août 2007, 12:13:17

Comme j'ai dit, vu la complexite de l'espace d'etats et les paquets d'interaction qui existent, j'ai du mal a le concevoir.

Les dames sont resolues si je ne m'abuse.

-- verif: effectivement (http://news.bbc.co.uk/1/hi/sci/tech/6907018.stm). Par contre, pas encore d'oracle.

Sinon qu'apelle tu un misplay? tu veux dire un play optimal sachant ce qu'il y a en jeu et ce qu'on a en main? Ou un play qui maximise la probabilite d'avoir la meilleure situation possible?

Exemple: tu as deux bleus en jeu et deux rouges. Tu as counterspell en main ainsi qu'un piocheur pour 1U, et des foudres/incinerate dans ton deck. Ton adversaire est a 2, joue combo sans contre, pas de creature en jeu, et tu as une 2/2 engagee en jeu (elle vient d'attaquer). Deux options majeures: jouer le piocheur pour esperer avoir un burn mais si tu en pioches pas t'es mal parce que ton adversaire est libre de ses mouvements au prochain tour sauf si tu pioches un contre, ou alors garder UU pour jouer le counterspell en se disant que si ca se trouve ton adversaire va avoir une duress ou assez de mana/storm pour passer ton contre?

Quel est le missplay la dedans? Existe-t-il?

CwaM · 11 Août 2007, 13:16:49

question de proba ca ;)

Juju · 11 Août 2007, 13:35:50

effectivement, mais ce n'est pas ca qui repond a la question ;)

Zmx · 11 Août 2007, 14:28:13

Et il n'est pas rare de gagner grace a un misplay que l'on a fait ...

De plus pour etre le joueur "parfait" il faut connaitre le jeux de l'autre à la carte pret (on peux supossé que ça fait partie des prérequis, comme pour les TOP8)

neonico · 11 Août 2007, 23:00:52

Le problème est qu'une grande part de ton résultat d'un deck que tu joues contre un adversaire dépend du metagaming, ce qui est complètement différent des échecs et du poker et qui me semble une chose carrément plus dure à analyser pour une machine que juste analyser un play en fonction de ta stratégie de départ.

belcherized · 12 Août 2007, 00:04:39

+1 Neonico ;)... sachant qu'il restera de toute façon à Magic toujours cette part de hasard qui fait que , même en jouant les sorts optimalement, un ordinateur ne pourrait pas gagner toutes ses games.

Zmx · 12 Août 2007, 00:47:43

Part de chance qui existe au poker.
Mais pas au echec.

Le soucis de magic par rapport au echec (qui contient deja un grand nombre de possibilité) c'est que ça contient ENCORE PLUS de possibité, et qu'il y as une inconnu dans l'equation "les cartes non visibles" (main, bibal, etc)

Sur une partie de poker (hors bluffe) les statistique suffise à prévoir les "bon coup".
56 carte (52?) connu et deja les stats souffre, alors les stats avec des inconnu et 10 000 carte ....

Juju · 12 Août 2007, 03:03:42

Citation de: belcherized le 12 Août 2007, 00:04:39+1 Neonico ;)... sachant qu'il restera de toute façon à Magic toujours cette part de hasard qui fait que , même en jouant les sorts optimalement, un ordinateur ne pourrait pas gagner toutes ses games.

La part de hasard n'a rien a faire ici. On sait tres bien qu'on a un jeu avec du hasard et que la chance peut nous faire perdre n'importe quoi. Mais c'est pas pour ca qu'on a pas de champions pour des jeux avec du hasard: poker, backgammon, magic... Tous ces jeux ont leurs champions.

Pour tout jeu avec du hasard, on ne parle pas de construire un ordinateur qui puisse tout gagner, mais un ordinateur qui puisse battre les champions :)

(ou alors, comme ca a ate fait au poker, on joue en duplicate)

-- edit: et au passage, le principal soucis des programmes de poker developpes n'est pas de jouer u mieux des statistiques, ca c'est facile; le principal soucis, c'est la modelisation de l'adversaire. Et faut sans doute en plus rajouter cette modelisation de l'adversaire a magic...

nicofromtokyo · 12 Août 2007, 05:38:56

Ca serait quoi alors le plus réalisable? Un joueur qui joue parfaitement son deck préprogrammé en fonction de sa main, son yard et les carte devant lui + les connaissances qu'il a des cartes et du deck de son adversaire, tant en jouantl a stratégie de jeu la moins risquée pour perdre? Ca limite déjà beaucoup de conditions, mais ça reste quand même concrêt non?

Par exemple, avec SX, le joueur virtuel va décomposer le puzzle de sa première main sans erreur, en jouant avec les proba de pioche par rapport aux nombres de cartes de mana, restantes dans sa biblio etc etc, bref il va utiliser ses ressources parfaitement, en éventuellement essayant de zigzager entre des FoW.
On perd très souvent des games sur des missplays, par faut de connaissances des règles, par fatigue, par stupidité, par étourderie, par oubli, et ce joueur virtuel éliminerait tous ces facteurs d'emblé. Ca pourrait être un bon début non?

Juju · 12 Août 2007, 06:09:57

Citation de: nicofromtokyo le 12 Août 2007, 05:38:56Ca serait quoi alors le plus réalisable? Un joueur qui joue parfaitement son deck préprogrammé en fonction de sa main, son yard et les carte devant lui + les connaissances qu'il a des cartes et du deck de son adversaire, tant en jouantl a stratégie de jeu la moins risquée pour perdre? Ca limite déjà beaucoup de conditions, mais ça reste quand même concrêt non?

Je pense que le plus realisable serait encore plus restreint: ca serait de faire un programme qui joue parfaitement UN deck en fonction de ce qu'il a et de ce qu'il voit, mais sans prendre en compte l'adversaire. Amha le meilleur exemple est celui que tu donnes: SX (ptet meme belcher). Difficulte estimee: 1.

Ensuite, on pourrait lui donner des indications sur ce que pourrait potentielleent jouer l'adversaire: contres, discard, autres trucs (rule of law? cantique?), et ca commence deja a devenir plus complexe. Difficultee estimee: 2.

Apres, faudrait reussir a lui faire jouer n'importe quel deck sans prendre en compte les informations cachees de l'adversaire. Difficulte estimee: 1.000.

Puis rajouter le fait qu'il puisse prendre en compte le deck adverse, quel qu'il soit. Difficultee estimee: 1.000.000.000.000.

Et enfin rajouter deckbuilding, metagame et tout et tout. Difficultee estimee: trop. Sachant qu'en plus au fil des extensions et des changements de format tout ca evolue...

Enfin, encore une fois, amha :)