Using the famous computer game Minecraft, Mathematicians at EPFL have developed a video game around Eulerian Cycles. It is now freely available online to everyone.
Mathematician David Strütt, a scientific collaborator at EPFL, worked for four months to develop Matheminecraft, a math video game in Minecraft, where the gamer has to find a Eulerian cycle in a graph. Minecraft is a sandbox video game released in 2011, where the gamer can build almost anything, from simple houses to complex calculators, using only cubes and fluids. These countless possibilities are what lured David Strütt into Minecraft's universe: "the game might be first intended for kids but I was studying for my Bachelor's degree in mathematics when I discovered it. I fell in love with the game when I realized there is all the necessary blocks to build a Turing machine inside the game. It was a long time ago, so I have since forgotten what a Turing machine is. But the gist of it is: anything is possible inside the game".
Matheminecraft, now freely available to everyone, is a video game around Eulerian graphs with a tutorial and four levels. The project was made for the Maths Outreach team with the idea that it should be ready for the EPFL Open days in September 2019. After the success encountered at the Open Days, it was decided that the game will be proposed to classes of the region as a series of ateliers organized by the Maths Outreach Team and the Science Outreach Departement (SPS). During 4 weeks, 36 classes of children - 8 to 10 years old- registered to visit EPFL and took part in a two hours matinée where they played Matheminecraft and did various chemistry experiments. Minecraft is a very popular game and has been described as one of the greatest games of all time. Children immediately recognize the game and a growing roar of "are we going to play Minecraft" fills the air as they enter the room. "I think Minecraft digitally plays the same role LEGOs did in my childhood. It appeals to anyone who takes a bit of their time to dive into it" speculates David.
The idea behind the project is the following. Consider a graph: that is a drawing on a board made of dots called vertices which are linked by lines called edges. The question that is asked about graphs is: "is it possible to cross each edge exactly once, pass by each vertex at least once, and end up at the starting vertex?". The first mathematician to ask that question is the Swiss Leonhard Euler in 1736. Not only did he wonder about that, but he provided the answer, giving an exhaustive description of which graphs admit such a path and which don't.
In the Matheminecraft atelier, we try to answer Leonhard Euler's question. An easy way to introduce Eulerian cycles to schoolchildren is to ask them about figures or drawings that can be done without lifting the pen and going twice on the same line. Triangle, square, star, a plethora of examples comes to their minds. In Matheminecraft each level consists of a graph that admits an Eulerian cycle. The game uses graphs that are easy enough, in the following sense: an Eulerian cycle will be found if the gamers make sure they don't get stuck. Such graphs are quite easy to work with, making the game suited to grade-schoolers.
In the game, each vertex is represented as a large color dot and each edge as a bridge. To keep the video game spirit, and to ensure that one bridge is only crossed once, David Strütt added a "lava condition", meaning that bridges, once crossed, will turn into lava. That makes them unable to be crossed again. A map of the graph is there to help the children. Famous Minecraft animals were added to decorate the levels, such as skeleton horses and Mooshrooms.
The story of Matheminecraft will not end there, as additional levels are in preparation and new series of ateliers - organized with the SPS - will take place in 2020 and 2021 Furthermore, a Matheminecraft 2.0 will see the day. It will include Eulerian trails, where the gamer will have to choose the starting point of his cycle. This would make the game harder and suitable for older grade-schoolers.
The freedom offered by Minecraft gave rise to other projects in the Maths Outreach Team, as a Summer School is currently in preparation in association with the Education Outreach Department. "Of course, at some point in my childhood I wanted to become a game developer. Only later in my teens did I think I could become a mathematician. Somehow, I became both" concludes David.
Graph theory
The mathematical theory behind the game is vast and well known. It's graph theory and was first mentioned as such in 1736 by Leonhard Euler. Euler laid the foundations of graph theory in his paper about the Seven Bridges of Königsberg (now Kaliningrad in Russia). This is a famous problem related to the urban geography of the city: can we found a walk through the city that would cross each bridge once and only once.
Euler proved that there was no solution to that problem. The graph theory gives us tools to answer our initial question: given a graph, can we visit each vertex, pass by each edge once and end up at the starting point? Let us restrict ourselves to undirected, connected, graphs, which simplifies the answer.
If we can answer "yes", the goal is reached and the graph admits an Eulerian cycle. Furthermore, the starting and ending point does not matter.
If the answer is "no", then some of the requirements are not verified. That is the case with the Königsberg bridges. But there exist graphs where we can visit each vertex, pass by each edge once but end up at a different vertex. In such cases, the graph admits an Eulerian trail or path.
If the mathematical proofs might not be suitable for schoolchildren, testing whether an undirected graph is Eulerian (with a cycle or a trail) is easy - depending of course on the graph at hand and one's ability at counting. To know if a graph is Eulerian, we need to define the simple notion of degree or valency of a vertex of a graph. The degree of a vertex is the number of edges that are incident to the vertex - in layman's terms that is the number of edges arriving (or leaving) a vertex.
If each vertex has an even degree then the graph admits an Eulerian cycle. If there are exactly two vertices with an odd degree then the graph admits an Eulerian trail. In the latter case, the starting and ending points are the vertices with odd degree.
If Matheminecraft does not cover Eulerian trails, the theory is nevertheless explained in a very mathematical way, on a blackboard - or on a whiteboard for a lack of better options.
