Crédit :Ecole Polytechnique Fédérale de Lausanne
Mathématicien David Strütt, un collaborateur scientifique à l'EPFL, travaillé pendant quatre mois pour développer Matheminecraft, un jeu vidéo de maths dans Minecraft, où le joueur doit trouver un cycle eulérien dans un graphe. Minecraft est un jeu vidéo sandbox sorti en 2011, où le joueur peut construire presque n'importe quoi, des maisons simples aux calculatrices complexes, en utilisant uniquement des cubes et des liquides. Ces innombrables possibilités sont ce qui a attiré David Strütt dans l'univers de Minecraft :« le jeu était peut-être d'abord destiné aux enfants mais j'étudiais mon baccalauréat en mathématiques quand je l'ai découvert. Je suis tombé amoureux du jeu quand j'ai réalisé qu'il y avait tout blocs nécessaires pour construire une machine de Turing à l'intérieur du jeu. C'était il y a longtemps, j'ai donc oublié ce qu'est une machine de Turing. Mais l'essentiel est que tout est possible à l'intérieur du jeu."
Mathématique, désormais accessible gratuitement à tous, est un jeu vidéo autour des graphes eulériens avec un tutoriel et quatre niveaux. Le projet a été réalisé pour l'équipe Maths Outreach avec l'idée qu'il devrait être prêt pour les Open Days de l'EPFL en septembre 2019. Après le succès rencontré lors des Open Days, il a été décidé que le jeu serait proposé aux classes de la région sous la forme d'une série d'ateliers organisés par l'équipe Maths Outreach et le Science Outreach Departement (SPS). Pendant 4 semaines, 36 classes d'enfants de 8 à 10 ans se sont inscrites pour visiter l'EPFL et ont participé à une matinée de deux heures où ils ont joué à Matheminecraft et ont fait diverses expériences de chimie. Minecraft est un jeu très populaire et a été décrit comme l'un des plus grands jeux de tous les temps. Les enfants reconnaissent immédiatement le jeu et un rugissement croissant de "allons-nous jouer à Minecraft" remplit l'air lorsqu'ils entrent dans la pièce. "Je pense que Minecraft joue numériquement le même rôle que LEGO a joué dans mon enfance. Il plaît à tous ceux qui prennent un peu de leur temps pour s'y plonger, " spécule David.
L'idée derrière le projet est la suivante. Considérons un graphe :c'est un dessin sur une planche fait de points appelés sommets qui sont reliés par des lignes appelées arêtes. La question qui se pose à propos des graphes est :« est-il possible de franchir chaque arête exactement une fois, passer par chaque sommet au moins une fois, et se retrouver au sommet de départ?". Le premier mathématicien à poser cette question est le Suisse Leonhard Euler en 1736. Non seulement il s'est interrogé à ce sujet, mais il a fourni la réponse, donnant une description exhaustive des graphes qui admettent un tel chemin et de ceux qui ne le font pas.
Dans l'atelier Matheminecraft, nous essayons de répondre à la question de Leonhard Euler. Une manière simple de faire découvrir les cycles eulériens aux écoliers est de leur poser des questions sur des figures ou des dessins qui peuvent être réalisés sans lever la plume et en allant deux fois sur la même ligne. Triangle, carré, Star, une pléthore d'exemples leur vient à l'esprit. Dans Matheminecraft, chaque niveau consiste en un graphique qui admet un cycle eulérien. Le jeu utilise des graphiques assez simples, dans le sens suivant :un cycle eulérien sera trouvé si les joueurs font en sorte qu'ils ne restent pas bloqués. De tels graphiques sont assez faciles à travailler, rendre le jeu adapté aux élèves du primaire.
Dans le jeu, chaque sommet est représenté par un gros point de couleur et chaque arête par un pont. Pour garder l'esprit du jeu vidéo, et pour s'assurer qu'un pont n'est franchi qu'une seule fois, David Strütt a ajouté une "condition de lave, " ce qui signifie que les ponts, une fois franchi, se transformera en lave. Cela les rend impossibles à croiser à nouveau. Une carte du graphique est là pour aider les enfants. Des animaux Minecraft célèbres ont été ajoutés pour décorer les niveaux, comme les chevaux squelettes et les Mooshrooms.
Crédit :Ecole Polytechnique Fédérale de Lausanne
L'histoire de Matheminecraft ne s'arrêtera pas là, car des niveaux supplémentaires sont en préparation et de nouvelles séries d'ateliers - organisés avec le SPS - auront lieu en 2020 et 2021. un Matheminecraft 2.0 verra le jour. Il comprendra des sentiers eulériens, où le joueur devra choisir le point de départ de son cycle. Cela rendrait le jeu plus difficile et conviendrait aux élèves plus âgés.
La liberté offerte par Minecraft a donné lieu à d'autres projets au sein de l'équipe Maths Outreach, as a Summer School est actuellement en préparation en association avec le département Education Outreach. "Bien sûr, à un moment de mon enfance, j'ai voulu devenir développeur de jeux. Ce n'est que plus tard dans mon adolescence que j'ai pensé que je pouvais devenir mathématicien. En quelque sorte, Je suis devenu les deux" conclut David.
La théorie des graphes
La théorie mathématique derrière le jeu est vaste et bien connue. C'est la théorie des graphes et a été mentionnée pour la première fois en tant que telle en 1736 par Leonhard Euler. Euler a jeté les bases de la théorie des graphes dans son article sur les sept ponts de Königsberg (aujourd'hui Kaliningrad en Russie). C'est un problème célèbre lié à la géographie urbaine de la ville :peut-on trouver une promenade à travers la ville qui traverserait chaque pont une et une seule fois.
Euler a prouvé qu'il n'y avait pas de solution à ce problème. La théorie des graphes nous donne des outils pour répondre à notre question initiale :étant donné un graphe, pouvons-nous visiter chaque sommet, passer une fois par chaque bord et se retrouver au point de départ ? Limitons-nous au non dirigé, connecté, graphiques, ce qui simplifie la réponse.
Crédit :Ecole Polytechnique Fédérale de Lausanne
Si nous pouvons répondre "oui, " le but est atteint et le graphe admet un cycle eulérien. De plus, le point de départ et d'arrivée n'a pas d'importance.
Si la réponse est " non, " alors certaines exigences ne sont pas vérifiées. C'est le cas des ponts de Königsberg. Mais il existe des graphes où l'on peut visiter chaque sommet, passer par chaque bord une fois mais se retrouver à un sommet différent. Dans ces cas, le graphe admet une piste ou un chemin eulérien.
Si les preuves mathématiques ne conviennent pas aux écoliers, tester si un graphe non orienté est eulérien (avec un cycle ou une traînée) est facile, en fonction bien sûr du graphe à portée de main et de sa capacité à compter. Pour savoir si un graphe est eulérien, nous devons définir la notion simple de degré ou de valence d'un sommet d'un graphe. Le degré d'un sommet est le nombre d'arêtes incidentes au sommet, en termes simples, c'est le nombre d'arêtes arrivant (ou partant) d'un sommet.
Si chaque sommet a un degré pair alors le graphe admet un cycle eulérien. S'il y a exactement deux sommets de degré impair alors le graphe admet une traînée eulérienne. Dans le dernier cas, les points de départ et d'arrivée sont les sommets de degré impair.
Si Matheminecraft ne couvre pas les sentiers eulériens, la théorie est néanmoins expliquée de manière très mathématique, sur un tableau noir ou sur un tableau blanc faute de meilleures options.