Jouer à Super Mario Bros., c’est comme résoudre un problème de maths très complexe

Super Mario Bros.

Les jeux vidéo peuvent servir des desseins. Certains ont justement pour objectif d'aider à résoudre de grandes énigmes. Mais saviez-vous que lorsque vous terminez un niveau de Super Mario Bros., vous résolvez en vérité un problème de mathématiques très complexe, parmi les plus difficiles de l'informatique ?

Les problèmes de complexité NP (« non-déterministe polynomial »), par opposition aux problèmes de complexité P, sont extrêmement difficiles à résoudre. L’un des exemples les plus connus est celui du représentant de commerce qui doit trouver le trajet le plus court pour visiter 100 villes. Selon l’ingénieur Erik Demaine, du MIT, évoluer dans des niveaux de Super Mario Bros. créés avec Super Mario Maker peut être équivalent à résoudre l’un de ces problèmes mathématiques très complexes.

Larry Hardesty, du MIT lui aussi, expliquait il y a quelques années :

L’informatique est très concerné par cette seule question : combien de temps faut-il pour exécuter un certain algorithme ? Mais les spécialistes ne répondent pas en terme de minutes ou de millisecondes, ils donnent une réponse relative au nombre d’éléments que l’algorithme a à manipuler.

Imaginez par exemple que vous avez une liste non ordonnée de nombres et que vous souhaitez écrire un algorithme pour trouver le plus grand. L’algorithme doit alors regarder tous les nombres de cette liste : impossible de faire autrement. Mais s’il garde simplement un enregistrement du plus grand nombre qu’il rencontre, il n’a alors qu’à regarder chaque nombre une seule fois. La durée d’exécution de l’algorithme est alors directement proportionnelle au nombre d’éléments qu’il traite – nombre que les informaticiens désignent par N -.

Mais les choses se compliquent si votre algorithme doit, par exemple, trouver les distances entre un certain nombre d’aéroports (N) sur une carte. Cela prendra davantage de temps parce que pour chaque aéroport sur la carte, l’algorithme devra calculer la distance avec tous les autres. Et le problème est pire avec des algorithmes exponentiels – pour factoriser un nombre à 1 000 chiffres, par exemple -. Cependant, si on donne la réponse à un ordinateur, celui-ci peut vérifier très rapidement que celle-ci est correcte…

Quel rapport alors avec Super Mario Bros. ? Erik Demaine et ses collègues avaient examiné il y a quelques années une version générique d’un jeu de type « porte fermée ». Chaque chemin pouvait être, au choix, sécurisé ou non – comme les 0 et les 1 de l’informatique -. Les chercheurs ont démontré que n’importe quel problème informatique pouvait être représenté par des portes de ce genre dans la bonne configuration. Si un problème est exponentiellement complexe, réussir à terminer le niveau de ce jeu le sera tout autant.

Avec les éléments disponibles dans le jeu, l’équipe est parvenue à construire des portes de ce genre dans Donkey Kong Country, mais pas dans Super Mario Bros.. Ils en ont conclu que le jeu était au moins aussi difficile que le plus difficile des problèmes NP. Il y a cependant un moyen de construire ce genre de porte, en exploitant un monstre appelé « piquant ». Celui-ci peut évoluer entre deux barrières dans le jeu, sans pouvoir sauter par-dessus, sans l’aide de Mario tout du moins. Si Mario saute alors que le piquant approche la barrière, il passe juste derrière. S’il est d’un côté, le chemin est ouvert, s’il est de l’autre, le chemin est fermé. Et plusieurs chemins peuvent permettre à Mario de faire passer le piquant d’un côté à l’autre.

Et cette question des problèmes de complexité P ou NP revient très souvent chez les mathématiciens et informaticiens. Si P n’est pas égal à NP, alors il n’y a aucun moyen rapide et générique de résoudre des problèmes NP. À l’inverse, si P est égal à NP, cela signifie que même les problèmes qui semblent les plus difficiles pourraient avoir des solutions très simples et rapides à trouver. Cela pourrait avoir des conséquences plus que fâcheuses notamment en matière de cryptographie… Et pour information, la plupart des mathématiciens s’accordent à penser qu’il y a davantage de chances que P ne soit pas égal à NP !

Tags :Via :Gizmodo
Dernières Questions sur UberGizmo Help
  1. « Si P n’est pas égal à NP, alors il n’y a aucun moyen rapide et générique de résoudre des problèmes NP. À l’inverse, si P n’est pas égal à NP,… »

    Bonjour, j’aimerais me plaindre quand à la qualité dégradante du site depuis la fusion avec Gizmodo.

    Tout les articles sont bâclés à l’exception de ceux de Noredine et René.
    Vous faites une traduction mot pour mot (et je ne suis pas sur que vous avez le droit de le faire même en citant la source) d’articles provenant d’autres sites tout en bloquant des vidéos (qui ne vous appartiennent pas pour le coup) pour les utilisateurs d’adblock qui on en marre de vos publicité extrêmement nombreuses et ennuyantes.

    Non seulement la qualité de traduction est souvent à la plaque, mais en plus vous simplifiez l’information originale. Il y’a donc une forte baisse de qualité depuis la source à la lecture sur votre site.

    Je ne vais pas m’attarder sur les procédés douteux de titres à clics, de liens contextuels dans l’article qui ont l’air de renvoyer vers une source intéressante alors que non, c’est juste une recherche vers un tag, ou bien de vouloir ouvrir un article et d’avoir une pop up qui force l’ouverture d’une page de votre partenaire ( au pire faites vous un bot qui s’amuse à ouvrir la page tout seul, niveau malhonnêteté vous avez déjà dépassé ce stade de toute facon)

    Franchement si la majorité de vos lecteurs se plaignent de ce qu’est devenu le site, écoutez les, car sans les lecteurs, vous n’avez pas de travail. Donc respectez nous un petit peu au lieu de nous balancer 15 000 articles dégueulasses et mal rédigés par jour pour faire du clic, au lieu de nous faire QUE quelques articles bien rédigés.

    Vous avez au moins le mérite de m’avoir fait découvrir quelques blogs intéressants que je préfère visiter plutôt que de venir ici.

    1. Et encore j’ai parfaitement conscience que là je dis ça dans un article plutôt au dessus de la moyenne par rapport au reste du site.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Publicité