C | Combinatorial Game Theory

GamesCrafters Website | Github | Writeup | Presentation

Gamescrafters is a research group at UC Berkeley headed by Professor Garcia which explores combinatorial game theory.

9 Men’s Morris is an ancient game that was (partially) implemented by GamesCrafters in previous semesters. However, it was unable to be solved fully because it consumed too much time and memory.

We worked to increase the efficiency of the retrograde solver.

In order to decrease the time complexity, we implemented symmetries (symmetrcal game positions that are collapsed into a single position). This cut the time to solve by a factor of 16.

We also implemented the functions GenerateUndoMoves and UndoMove, which takes a position and generates the possible preceding positions. The standard retrograde solver stores a stack of every move taken; by implementing this method, we can cut down the storage space and compute the backwards stack when it’s needed.