Combinatorial Game Theory

For the past week, I have been working on a computer science research project. For this project, I have crated an application of combinatorial game theory. Combinatorial game theory involves using perfect moves on sequential games. Sequential games are those in which players take turns playing in an equal fashion, such as tic-tac-toe, chess, or checkers. For my project, I have created an algorithm to help calculate the winner of a game of Gobblet, a 4X4 variant of tic-tac-toe. Upon entering a board of the game, the program calculates the winner of the game, based on each player playing perfectly.

The algorithm itself is relatively simple. It first stores the user inputted board in a struct array. With the initial board made, the algorithm then creates a tree data structure of nodes. Each node contains a board, its parent node, and the wins for each player—keep note of this, this is the main issue we experienced later on. With the tree created and initialized, we then check the board for wins, otherwise we move a random piece, store the new board in the next child, and check the board once again, adding to the corresponding player’s win on a win. This process continues until it has traveled through each node, reaching the end of the tree. Then the branch that has the most wins overall is the one with a highest win chance. Then, we implement a perfect AI, one that plays with an optimal strategy of prioritizing wins, and blocking the opposing player.

However, my partner and I experienced many issues with the project, for instance, because of the way we set up the tree, each node contains a 2 dimensional array of a user created type, resulting in massive memory usage with more empty boards. As such, it takes an immeasurable amount of time to calculate the winner of a board with 5 or more cells empty. The sheer amount of memory needed means that while the program will work eventually, it takes an immeasurable amount of time to do so. In hindsight, after the project’s end today, my partner and I agree: were we to do this specific project again, we would definitely store the board configurations in a less taxing fashion. Whether that means storing boards as text files, or storing only the changes made, our project would take much less time, going from O(n^1176) to complete an empty board to a much more manageable time. Furthermore, because this project took a week roughly, our code’s structure is incredibly limited. With the large amount of code needed, we ended with 7 classes. This resulted in the fact that as someone coded in a certain file, the other person was almost likely to be halted in their code as they couldn’t touch the file, because it would create GitHub merge issue. As a result, whenever I or my partner modified either the main class or the tree, the other could not do the same. This meant that since my partner always had something to do in the tree, this meant that rather than coding in the same file, I was forced to essentially be a backseat programmer, giving him feedback and advice without touching the keyboard.

Regardless, our project works quite well, even if empty boards take massive amounts of time. Check out our GitHub repository here!