Magic : The Gathering est officiellement le jeu le plus complexe au monde

Une image de paquets de cartes à jouer Magic: The Gathering Nathan Rupert

Magic: The Gathering est un jeu de cartes dans lequel des sorciers lancent des sorts, invoquent des créatures et exploitent des objets magiques pour vaincre leurs adversaires.

Dans le jeu, deux joueurs ou plus assemblent chacun un jeu de 60 cartes aux pouvoirs variables. Ils choisissent ces decks parmi un pool de quelque 20 000 cartes créées au fur et à mesure de l'évolution du jeu. Bien que similaire aux jeux de rôle fantastiques tels que Donjons et Dragons, il contient beaucoup plus de cartes et des règles plus complexes que les autres jeux de cartes.

Et cela soulève une question intéressante : parmi les jeux du monde réel (ceux auxquels les gens jouent réellement, par opposition aux jeux hypothétiques que les théoriciens des jeux considèrent habituellement), où Magic tombe-t-il en complexité ?

Aujourd'hui, nous obtenons une réponse grâce au travail d'Alex Churchill, chercheur indépendant et concepteur de jeux de société à Cambridge, au Royaume-Uni ; Stella Biderman au Georgia Institute of Technology ; et Austin Herrick à l'Université de Pennsylvanie.

Son équipe a mesuré pour la première fois la complexité informatique du jeu en l'encodant d'une manière qui peut être jouée par un ordinateur ou une machine de Turing. Cette construction établit que Magie : le rassemblement est le jeu du monde réel le plus complexe sur le plan informatique connu dans la littérature, disent-ils.

Tout d'abord, un peu de contexte. Une tâche importante en informatique consiste à déterminer si un problème peut être résolu en principe. Par exemple, décider si deux nombres sont relativement premiers (en d'autres termes, si leur plus grand diviseur commun est supérieur à 1) est une tâche qui peut être effectuée en un nombre fini d'étapes bien définies et qui est donc calculable.

Dans une partie d'échecs ordinaire, décider si les blancs ont une stratégie gagnante est également calculable. Le processus implique de tester toutes les séquences possibles de coups pour voir si les blancs peuvent forcer une victoire.

Mais bien que ces deux problèmes soient calculables, les ressources nécessaires pour les résoudre sont très différentes.

C'est là qu'intervient la notion de complexité de calcul. Il s'agit d'un classement basé sur les ressources nécessaires pour résoudre les problèmes.

Dans ce cas, décider si deux nombres sont relativement premiers peut être résolu en un certain nombre d'étapes proportionnelles à une fonction polynomiale des nombres d'entrée. Si l'entrée est X , le terme le plus important dans une fonction polynomiale est de la forme Cxn , où C et n sont des constantes. Cela tombe dans une classe connue sous le nom de P , où P représente le temps polynomial.

En revanche, le problème d'échecs doit être résolu par la force brute, et le nombre d'étapes nécessaires augmente proportionnellement à une fonction exponentielle de l'entrée. Si l'entrée est X , le terme le plus important dans une fonction exponentielle est de la forme Cx , où C et n sont des constantes. Et comme X augmente, cela devient beaucoup plus rapide que Cxn . Cela tombe donc dans une catégorie de plus grande complexité appelée EXP, ou temps exponentiel.

Au-delà de cela, il existe diverses autres catégories de complexité variable, et même des problèmes pour lesquels il n'existe pas d'algorithmes pour les résoudre. Ceux-ci sont dits non calculables.

Déterminer à quelle classe de complexité appartiennent les jeux est une tâche délicate. La plupart des jeux du monde réel ont des limites finies sur leur complexité, comme la taille d'un plateau de jeu. Et cela rend beaucoup d'entre eux triviaux du point de vue de la complexité. La plupart des recherches sur la théorie algorithmique des jeux des jeux du monde réel ont principalement porté sur les généralisations des jeux couramment joués plutôt que sur les versions réelles des jeux, disent Churchill et co.

Ainsi, seuls quelques jeux du monde réel sont connus pour avoir une complexité non triviale. Ceux-ci incluent Dots-and-Boxes, Jenga et Tetris. Nous pensons qu'aucun jeu du monde réel n'est connu pour être plus difficile que NP avant ce travail, déclarent Churchill et co.

Le nouveau travail montre que Magic: the Gathering est nettement plus complexe. La méthode est simple dans son principe. Churchill et co commencent par traduire les pouvoirs et les propriétés de chaque carte en un ensemble d'étapes qui peuvent être encodées.

Ils jouent ensuite un jeu entre deux joueurs dans lequel le jeu se déroule dans une machine de Turing. Et enfin ils montrent que déterminer si un joueur a une stratégie gagnante équivaut au fameux problème d'arrêt en informatique.

C'est le problème de décider si un programme informatique avec une entrée spécifique finira de s'exécuter ou continuera indéfiniment. En 1936, Alan Turing a prouvé qu'aucun algorithme ne peut déterminer la réponse. En d'autres termes, le problème n'est pas calculable.

Ainsi, le résultat clé de Churchill et co est que la détermination du résultat d'une partie de Magic n'est pas calculable. C'est le premier résultat montrant qu'il existe un jeu du monde réel pour lequel la détermination de la stratégie gagnante n'est pas calculable, disent-ils.

C'est un travail intéressant qui soulève d'importantes questions fondamentales pour la théorie des jeux. Par exemple, Churchill et co disent que la principale théorie formelle des jeux suppose que tout jeu doit être calculable. Magie : le rassemblement ne correspond pas aux hypothèses couramment formulées par les informaticiens lors de la modélisation des jeux, disent-ils.

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. De toute évidence, Magic représente une mouche dans l'onguent enchanté en ce qui concerne cela.

Réf : arxiv.org/abs/1904.09828 : Magic : The Gathering is Turing terminé

cacher