Graphs, Games and Groups #maths

This is a first video about a Math 91r project from this spring. The scope was to describe solitaire and two player games graph theoretically. The frame work is simple in such a way that the formulation of Zermelo's theorem from 1918 follows directly from the definitions. Our main focus had been to compute God numbers. These are maximin values of a functional in the case of solitaire games (the graph diameter) or a minimax value of a function in the case of a two player games: minimize the maximal path length of game events (subgraphs are strategies) when minimizing over all strategies. Pictures were shot on wednesday with an avata 360. Added May 3rd: In the presentation, I mentioned smaller nxn sliding puzzles. For the 8 = 3x3-1 puzzle the computation of the god number is actually quite easy. It is 31. Mathematica struggle with the 3*4-1=11 puzzle, C or python can do it. For the 15 puzzle, one would need special computers. The god number is 80. For the 24 =5x5-1 puzzle it is unknown, in general it is NP complete (a classical result from 1986, when complexity theory was "hip".). When I was an undergraduate in college, I talked during two Specker seminars in such areas, one about the complexity of graph isomorphism, an an other about the god number of the rubik cube (which was at that time not yet known). I had chosen that topic on my own even so Specker did not like it. He found the problem "too special", which actually is true as it is just a number, 20 is just a number. But the general god number problem is interesting because it is an NP complete problem already for specific games. And NP problems are nice even so we are 40 years after the hype. What of course has helped is that the P-NP problem was picked to be one of the Millenium problems. Otherwise, it might be fallen into obscurity. The scientific community tends to follow hypes and fashion much more than what is actually interesting.