The Game of Cycles

The Game of Cycles

Zandee, Jonathan (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Applied Probability)

Fokkink, R.J. (mentor)
Bishnoi, A. (graduation committee)

Delft University of Technology

Applied Mathematics

2022-07-08

The Game of Cycles, invented by Francis Su (2020, p.51) is an impartial game played on a graph, where players take turns marking an edge according to a set of rules. Together with the game, there also came a conjecture that gives a condition for whether a specific position is winning or losing. Proving or disproving this conjecture is the main focus of this research, which we end up succeeding in by giving a counter-example, thus disproving the conjecture. We do this by first showcasing some relevant background knowledge from game theory in chapter 1. In chapter 2 we then introduce the Game of Cycles and its rules, as well as some of the previous results others have found. We continue in chapter 3 by creating a python script to brute-force the game for us and it is here that we find a counter-example to the main conjecture, of which we prove that it is indeed a counter-example. We close off with chapter 4 by looking at a simplification of the game, where it is played on trees instead of any graph. Here we prove that the main conjecture does hold for a special family of trees and state a conjecture for the solution of any tree.

Game Theory
Graph theory
Brute-force

http://resolver.tudelft.nl/uuid:6c61bdb6-58c2-4a76-9712-448a882e044b

Student theses

bachelor thesis

© 2022 Jonathan Zandee