Une nouvelle preuve avec des implications importantes pour la théorie des jeux montre qu’aucun algorithme ne peut déterminer le vainqueur.

Magic : The Gathering est un jeu de cartes dans lequel les sorciers jettent 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 avec des pouvoirs différents. Ils choisissent ces jeux à partir d’un pool d’environ 20 000 cartes créées au fur et à mesure de l’évolution du jeu. Bien que similaire aux jeux de rôle de fantaisie tels que Donjons et Dragons, il a 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 du jeu considèrent habituellement), où se situe la complexité de Magic ?

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, Royaume-Uni ; Stella Biderman au Georgia Institute of Technology ; et Austin Herrick à l’Université de Pennsylvanie.

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

Tout d’abord, un peu de contexte. Une tâche importante en informatique est de 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 est donc calculable.

Dans une partie d’échecs ordinaire, décider si les Blancs ont une stratégie gagnante est aussi calculable. Le processus consiste à tester toutes les séquences possibles de coups pour voir si les Blancs peuvent forcer une victoire.

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

C’est là qu’intervient la notion de complexité informatique. 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 qui est proportionnel à 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. Ceci tombe dans une classe connue sous le nom de P, où P représente le temps polynomial.

En revanche, le problème des échecs doit être résolu par la force brute, et le nombre de pas que cela prend 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 Cnx, où C et n sont des constantes. Et au fur et à mesure que x augmente, cela devient plus grand beaucoup plus vite que Cxn. Il s’agit donc d’une catégorie d’une 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. Ils sont dits non calculables.

Déterminer dans quelle classe de complexité se situent les jeux est une affaire 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 insignifiants du point de vue de la complexité. « La plupart des recherches sur la théorie algorithmique des jeux du monde réel ont principalement porté sur les généralisations des jeux courants plutôt que sur les versions réelles des jeux « , expliquent Churchill et al.

Ainsi, seuls quelques jeux du monde réel sont connus pour avoir une complexité non triviale. Il s’agit notamment de Dots-and-Boxes, Jenga et Tetris. « Nous croyons qu’aucun jeu du monde réel n’est connu comme étant plus difficile que NP avant ce travail « , dit Churchill et Cie.

Le nouvel ouvrage montre que Magic : the Gathering est beaucoup plus complexe. La méthode est simple en principe. Churchill et ses collaborateurs commencent par traduire les pouvoirs et les propriétés de chaque carte en un ensemble d’étapes qui peuvent être codé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 de l’arrêt en informatique.

C’est le problème de décider si un programme d’ordinateur avec une entrée spécifique va finir de fonctionner ou continuer pour toujours. 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.

Le principal résultat de Churchill and Co est donc que déterminer le résultat d’un jeu de magie n’est pas calculable. « C’est le premier résultat qui montre qu’il existe un jeu réel pour lequel déterminer 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 ses collaborateurs affirment que la théorie formelle des jeux suppose que tout jeu doit être calculable. « Magic : The Gathering ne correspond pas aux hypothèses couramment formulées par les informaticiens lors de la modélisation de 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.

Par ici pour commencer à jouer.

Publicités

Laisser un commentaire

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.