I have been researching the Game of Thrones. You might ask yourself "how do you research a game?" Well there is an entire field of mathematics devoted to studying games, it is called Game Theory . There are two things a research is attempting to discover when researching a game, those two things are: A winning strategy, and a losing position. A winning strategy is exactly what it sounds like, a strategy that will win the game. Ideally a researcher wants to discover a strategy that will guarantee a win regardless of the opponents strategy, but this is not always possible. A losing position is a position in the game that a player cannot win from regardless of strategy. Often times the winning strategy is to make sure your opponent is in the losing position.
Dr. Larry Langley visited Utah State University in Spring 2013, while he was here he presented a game he had invented that he called the Game of Thrones. I attended the presentation and became fascinated with the game. It seemed so simple, but every time I attempted to find a winning strategy I was stumped. By the end of the Spring semester I had given up discovering a winning strategy, but could never quite forget the game. When the fall semester began Dr. David Brown informed me of a grant that Utah State was awarding to students for various research projects. He suggested that I develop a project and apply. I immediately thought of the Game of Thrones and another graph theory game called Graph Nim. I wrote a proposal to study both the Game of Thrones and Graph Nim, but my proposal was rejected because my budget did not meet the criteria. I was informed of another grant that I would qualify for and developed another proposal . I was awarded the grant and began my research.
Now that I had been awarded grant money I was obligated to produce some results, there was only one problem, I didn't know how to. I decided that the first thing I needed to do was find a way to actually play the game. Dr. Brown had a former student that developed a program called GraphShop. I obtained the program and began playing around with it. GraphShop would allow me to construct graphs, and digraphs. It would create an adjacency matrix for the graph and show other useful information. After playing with the program I realized that to use it to it's fullest extent I would need to use it's capability of interpreting javascript code. I had ran into my second great hurdle, I didn't know javascript, or any other programming language. I found recording of lecutres from an intro to programming course that MIT had published. I also found valuable javascript tutorials online. Within weeks I was using javascript within GraphShop to play the game of thrones.
Now that I could actually play the Game of Thrones I began an in depth analysis of the game. I was constantly playing, or thinking about the game. Before long I noticed a pattern, any tournament that had a vertex with score n-2 could be won in a single move. I told Dr. Brown about the pattern I had noticed and he showed me a paper by one of his former students that developed a function to determine the maximum number of vertices with a given score that could exist in a tournament of a given size (Mousley, 2013). Using this function I determined that there could be at most three vertices with score n-2. Then I was able to prove that any tournament with at least one vertex of score n-2 was a winning position for the Game of Thrones.
With my first result I was ready to find a winning strategy. I tried. I failed. I tried again. I failed again. At one point I was convinced that I had found a winning strategy. My cousin was visiting and I was explaining the strategy to him. In the middle of my explanation I realized that it was not a winning strategy after all. I still have yet to find and prove a winning strategy, but I have developed an algorithm that may be the winning strategy I'm after. The algorithm is:
I have yet to prove a winning strategy, but that is still on the to do list. I have looked into using a theorem called the Sprauge-Grundy Theorem (Sprague, 1935-36)(Grundy, 1939). The Sprauge-Grundy Theorem states that any impartial combinatorial game is equivalent to a position of the game Nim . The game of Nim is at least centuries old, possibly originating in China, but noted in the 16th century in European countries. It consists of several stacks of tokens, and two players alternate taking one or more tokens from one of the stacks, and the player who cannot make a move loses. This video show a winning strategy for one version of Nim:
Since the Game of Thrones is an impartial combinatorial game the Sprauge-Grunday Theorem should apply. In order to use the Sprauge-Grundy theorem I need to determine how each position of the game relates to a position of Nim. I also have not found how heirs relate to the winning strategy of the game, but it would only make sense for them to.
I have loved researching the game of thrones and getting first hand experience of real math. I have been able to participate in multiple conferences , and will hopefully participate in more.