Apprendre les mathématiques grâce à Matheminecraft

Utilisant le célèbre jeu Minecraft, un nouveau jeu vidéo présente le concept des cycles eulériens. Conçu par des mathématiciennes et des mathématiciens de l’EPFL, il est disponible en téléchargement en ligne.

Mathématicien et collaborateur scientifique à l’EPFL, David Strütt a travaillé pendant quatre mois au développement de Matheminecraft. Il s’agit d’un jeu vidéo mathématique dans Minecraft — pour les connaisseurs, il s'agit d'une carte aventure — où le joueur doit trouver un cycle eulérien dans un graphe. Publié en 2011, Minecraft est un jeu de type bac à sable — ou sandbox, en anglais — où le joueur peut construire presque n’importe quoi, d’une simple maison à des calculatrices complexes, en utilisant exclusivement des cubes ou des fluides. Ce sont ces possibilités infinies qui ont attiré David Strütt dans l’univers de ce jeu : « Il a beau avoir été conçu pour les enfants, j’étudiais pour mon bachelor en maths quand je l’ai découvert. Ça a été le coup de foudre quand j’ai réalisé qu’il comportait tous les blocs de construction nécessaires pour concevoir une machine de Turing. C’était il y a longtemps, et depuis j’ai oublié ce qu’est une machine de Turing. Mais l’essentiel, c’est que rien n'est impossible».

Disponible pour tous en ligne, Matheminecraft est conçu autour des graphes eulériens. Il comprend un tutoriel et quatre niveaux. L'idée a germé dans l'équipe de promotion des mathématiques, dans le but de le présenter aux journées portes ouvertes de l’EPFL en septembre 2019. Suite à son succès, il a été décidé de le proposer aux classes de la région, dans le cadre d’ateliers scolaires organisés par le Groupe de promotion des mathématiques et le Service de promotion des sciences de l'EPFL. Pendant quatre semaines, des élèves de 36 classes d'enfants de 8 à 10 ans se sont rendus à l’EPFL où ils ont pris part à une visite matinale de deux heures durant laquelle ils ont joué à Minecraft et réalisé diverses expériences chimiques. Minecraft est un jeu très populaire, décrit comme l’un des plus influents de tous les temps. Les enfants le reconnaissent immédiatement. Une clameur croissante envahit la salle quand ils entrent — « On va jouer à Minecraft! ». David Strütt spécule que «Minecraft joue le même rôle que les legos de mon enfance mais au format numérique. Le jeu parle à toutes celles et ceux qui prennent le temps de s’y plonger. »

L’idée qui sous-tend le projet est la suivante. Imaginez un graphe : un dessin sur une surface plane, composé de points — des « sommets » — reliés par des lignes — des « arêtes ». On se pose la question suivante : « est-il possible de parcourir chaque arête exactement une fois, chaque sommet au moins une fois et de finir au sommet de départ? ». Le mathématicien suisse Leonhard Euler est le premier à s'être posé cette question. C'est en 1736 qu'il a publié le résultat de sa réflexion et qu'il a donné une réponse mathématique au problème. Il a donné un critère exhaustif pour décrire complètement les graphes qui admettent un tel parcours.

Pour introduire facilement les cycles eulériens aux écoliers, on leur demande quelles figures ou dessins il est possible de tracer, sans soulever le crayon et sans revenir sur la même ligne. Triangles, carrés, étoiles, de nombreux exemples leur viennent à l’esprit. Dans Matheminecraft, chaque niveau consiste en un graphe qui admet un cycle eulérien. Le jeu utilise des graphes suffisamment simples, dans le sens suivant : les joueurs trouveront un cycle eulérien s’ils s’assurent de ne pas rester coincés. La difficulté de tels graphes est alors adaptée aux écoliers.

Dans le jeu, chaque sommet est représenté par un gros rond de couleur et chaque arête, par un pont en pierre. Pour conserver l’esprit jeu vidéo et faire en sorte que chaque pont ne soit traversé qu’une seule fois, David Strütt a implémenté la condition suivante : une fois parcourus, les ponts se muent en rivières de lave. On ne peut donc pas les traverser à nouveau sans mourir. À chaque niveau du jeu, le joueur reçoit une carte du graphe lui permettant de s'orienter. Pour rendre Matheminecraft plus attractif, les niveaux sont décorés d’animaux typiques de Minecraft. Chevaux-squelettes et champimeuh — des vaches couvertes d'amanites tue-mouches — sont au rendez-vous.

L’histoire de Matheminecraft ne s’arrête pas là. Des niveaux additionnels sont en développement et de nouvelles séries d'ateliers, organisées en partenariat avec le SPS, sont prévues en 2020 et 2021. De plus, une version 2.0 devrait voir le jour. Elle inclura des graphes qui n'admettent que des chemins eulériens et non plus des cycles. Face à de tels graphes, les joueurs devront choisir le point de départ de leur cycle. De quoi corser le jeu et l’adapter à des élèves plus âgés.

La liberté qu’offre Minecraft a donné naissance à d’autres projets dans le Groupe de promotion des maths. Une summer school, en partenariat avec le Service de promotion de l'éducation de l'EPFL, est en préparation. « A un certain moment de mon enfance, bien sûr, j’ai voulu être développeur de jeux vidéo. Plus tard seulement, dans l’adolescence, j’ai pensé à la carrière de mathématicien. Mais en quelque sorte, je suis devenu les deux », sourit David Strütt.

Un jeu pour apprendre la théorie des graphes

Derrière le jeu se cache une théorie vaste et bien connue. Il s’agit de la théorie des graphes, mentionnée comme telle pour la première fois en 1736 par le mathématicien suisse Leonhard Euler. Ce dernier a créé les fondations avec sa publication concernant le problème des sept ponts de Königsberg (maintenant Kaliningrad, Russie). Ce problème célèbre est lié à la géographie urbaine de la ville : peut-on trouver une promenade qui traverse tous les ponts de la ville une fois, et une fois seulement ? Leonhard Euler a prouvé qu'un tel itinéraire n'existe pas. Sa théorie des graphes nous donne les outils à même de répondre à la question de départ : sur un graphe donné, peut-on parcourir chaque arête exactement une fois et passer par chaque sommet au moins une fois, en revenant à son point de départ? Limitons-nous à des graphes non dirigés et connectés, pour simplifier la réponse.

Si la réponse est affirmative, le but est atteint et le graphe admet un cycle eulérien. En outre, le point de départ et d’arrivée n’a aucune importance, et il existera un cycle partant de chaque sommet.

Si la réponse est négative, cela veut dire que certains prérequis ne sont pas vérifiés. C’est le cas avec les ponts de Königsberg où il n'est pas possible de passer une seule fois par chaque arête. Cependant, il existe d’autres graphes où il est possible de visiter chaque sommet et passer exactement une fois par chaque arête, mais où le tracé se terminera à un sommet différent de celui de départ. Dans de tels cas, le but est atteint dans une moindre mesure et le graphe admet un parcours eulérien.

Si la preuve mathématique n’est pas des plus accessibles pour des écoliers, il est facile de tester si un graphe non dirigé est eulérien (s’il comprend un cycle ou un parcours). Cela dépend du graphe et de la capacité à compter. Pour savoir si un graphe est eulérien, nous devons définir la simple notion de degré (ou valence) du sommet d’un graphe. Le degré d’un sommet correspond au nombre d’arêtes qui lui sont incidentes — dit simplement il s’agit du nombre d’arêtes qui arrivent au sommet (ou qui en partent).

Si chaque sommet présente un degré de nombre pair, alors le graphe admet un cycle eulérien. S’il y a exactement deux sommets avec des degrés de nombre impair, le graphe admet un parcours eulérien. Dans ce dernier cas, les points de départ et d’arrivée doivent être les sommets au degré impair.

Si le jeu Matheminecraft ne couvre pas les parcours eulériens, les animateurs de l’atelier expliquent la théorie d’une manière très mathématique, sur un tableau noir — ou plus précisément sur un tableau blanc, faute de mieux.


Auteur: Orane Jecker