{% extends "articles/complexite-et-machine-de-turing/_layout.html" %} {% block section %} {% trans trimmed %}
Commençons par enfoncer les portes ouvertes : Ce qui a été démontré
Ce qui a été démontré est que que déterminer à l'aide d'un algorithme l'issue d'une partie de Magic dans laquelle toutes les actions sont forcées est impossible.
Première conséquence contre-intuitive de ce résultat est qu'il n'existe aucun programme informatique qui, ayant une connaissance complète du jeu, pourrait déterminer l'issue d'une partie Magic. Même en connaissant l'ordre des cartes dans la bibliothèque à chaque instant, en connaissant toutes les décisions successives prises par les joueurs et en supprimant toutes les cartes à effet aléatoire, aucun algorithme ne serait capable de déterminer dans le cas général le gagnant de la partie.
Cela signifie que Magic the Gathering échoue à vérifier une des hypothèses couramment formulées par les informaticiens lors de la modélisation de jeux à deux joueurs. Cela suggère que les informaticiens doivent repenser leurs idées sur les jeux, en particulier s’ils espèrent produire une théorie informatique unifiée des jeux.
Pour parler de complexité il faut bien comprendre que l'on se place toujours dans le pire des cas et ce que cet article démontre, c'est que pour déterminer le gagnant d'une partie de Magic, le pire des cas de figure n'est pas un cas de figure calculable par ordinateur. Cela signifie que la complexité de Magic est belle est bien au delà de la complexité que l'on retrouve dans la plupart des jeux. Pour être précis, jusqu'à présent Magic est le premier jeu non vidéo- ludique commercialisé à grande échelle pour lequel cette propriété a été démontré et il est fort probable (mais non-démontré) qu'il s'agisse du seul. On remarquera que ce résultat n'a en définitive aucune conséquence particulière pour les joueurs, et qu'il n'en a pas beaucoup plus pour les développeurs d'intelligences artificielles. En effet on se doutait très fortement que créer une I.A. pour jouer à Magic à l'aide d'un arbre des possibilités serait une très mauvaise idée, entre autre parce qu'on sait que c'est une mauvaise idée pour des jeux apparemment plus simple tels que les échecs et le Go. Cet article ne fait que confirmer nos soupçons en affirmant que ce n'est pas juste une mauvaise idée, c'est tout simplement impossible d'y parvenir de cette façon.
La preuve de ce résultat à défaut d'être simple est très belle et je ne résiste pas à vous en donner ici les grandes lignes. Toute cette preuve repose sur un résultat d'Alan Turing. Cela peut sembler surprenant mais essayez de suivre aussi, son nom était dans le titre de l'article. Les moins scientifiques d'entre vous auront pu entendre parler d'Alan Turing grâce au film "Imitation Game" où il est interprété par Benedict Cumberbatch, ou encore plus récemment grâce à la pièce de Théâtre aux quatre Molières "La Machine de Turing". Outre avoir déchiffré le code de la machine Enigma lors de la seconde guerre mondiale, Alan Turing est aussi considéré comme le père de l'informatique et des ordinateurs. En effet une machine de Turing n'est ni plus ni moins qu'un ordinateur théorique au fonctionnement basique. C'est grâce à cette notion qu'Alan Turing pu définir formellement la notion d'algorithme et démontra un résultat fascinant connu sous le nom du problème de l'arrêt. Ce résultat stipule qu'il n'existe pas de programme informatique permettant de déterminer si un algorithme va s'arrêter ou non à la simple lecture de ce dernier. On parle de problème indécidable. La démonstration derrière ce résultat n'est pas si complexe mais je laisse aux lecteurs les plus aguerris le loisir de se pencher sur le sujet.
Revenons maintenant à notre problème et à son lien avec Magic. L'idée géniale est de montrer que l'on peut créer une partie de Magic dont le déroulé est identique à l’exécution d'un programme sur une machine de Turing. En somme, qu'il est possible de créer une machine de Turing avec des cartes Magic tout en forçant les joueurs à suivre son procédé sans qu'ils puissent à aucun moment interférer avec son fonctionnement ! Et, cerise sur le gâteau, l'issue du match en question ne dépend que d'une chose : savoir si le programme se termine ou non. Etant donné que l'on sait depuis Alan Turing qu'il s'agit d'un problème indécidable, on montre par la même occasion qu'aucun algorithme ne peut déterminer l'issue d'une partie de Magic même lorsque les actions possibles pour les joueurs sont forcées.
{% endtrans %} {% endblock %}