Avez-vous déjà eu de la difficulté à compléter un niveau de Super Mario? Si c’est le cas, rassurez-vous, la science vient de déterminer que le jeu pourrait s’avérer particulièrement difficile. Du moins, si Shigeru Miyamoto et ses collègues ingénieurs de Nintendo ont envie de vous faire vivre un cauchemar, ils ont déjà en main tous les éléments nécessaires pour le faire.
C’est en effet la conclusion à laquelle sont arrivés des chercheurs en science informatique du Massachusetts Institute of Technology, de l’Université d’Ottawa, et du Bard College. Concrètement, à partir des ressources déjà présentes dans le jeu, il serait possible de poser un problème mathématique plus difficile que la factorisation de grands nombres, ou même le problème du voyageur de commerce – un classique problème d’optimisation utilisée abondamment comme introduction à l’algorithmique ou à la théorie de la complexité.
Mais si l’étude démontre que Super Mario Bros a la capacité d’être scientifiquement difficile, cela ne signifie pas que ce soit le cas des niveaux qui composent la série.
Alors que les travaux antérieurs de la même équipe avaient déjà déterminé que Super Mario Bros pouvait être «au moins aussi difficile que les plus difficiles problèmes de type NP» (d’une complexité qui nécessite généralement l’aide d’un ordinateur pour être résolu), les chercheurs catégorisent désormais le jeu comme pouvant générer des problèmes de type PSPACE, soit au niveau supérieur de complexité.
Mais si l’étude démontre que Super Mario Bros a la capacité d’être scientifiquement difficile, cela ne signifie pas que ce soit le cas des niveaux qui composent la série.
«La nouvelle étude ne cherche pas à établir qu’un niveau en particulier tiré de l’une des versions commerciales de Super Mario Bros soit d’une difficulté de type PSPACE, mais plutôt qu’il est possible de construire des problèmes d’une complexité de type PSPACE à partir des matières brutes que l’on retrouve dans le monde de Super Mario Bros», précise l’article dévoilant l’étude.
Aux dires des chercheurs, le fruit de leurs travaux pourrait avoir des implications au-delà de la conception de jeux vidéo. «Mathématiquement, les jeux vidéo ne sont pas bien différents des modèles de calcul des systèmes physiques du monde réel, et les outils utilisés pour prouver la complexité de l’un pourraient être adaptés à l’autre», a déclaré Erik Demaine, professeur de génie électrique et d’informatique au MIT et un coauteur de l’étude.
«Mon souhait est d’inciter plus de gens à [effectuer de telles recherches], parce que ça permet véritablement de construire une grande expertise qui permettra de vaincre plus facilement les problèmes. Plus nous nous pratiquerons en tant que collectivité, mieux nous seront aptes à résoudre ce type de problèmes complexes. Et il est important de connaître les limites des algorithmes.»
