Automatic generation of state space graphs

Abstract

This project presents the research process, design and implementation of a software tool capable of synthesizing a wide variety of state-space graphs through parametrization. State-space graphs play a central role in the analysis and benchmarking of heuristic search algorithms, especially in domains such as two-player, zero-sum, deterministic, perfect information games. Traditional approaches to studying search algorithms often rely on hard-coded game environments, which can be time-consuming and computationally expensive.To address this, we developed a parameterized framework that allows researchers to simulate abstract yet realistic game-state graphs with features such as transpositions, branching factor, terminal distributions, heuristic value modeling, among others. The tool generates graphs implicitly in a memory-efficient and deterministic manner, enabling reproducibility across runs. It supports both simple use cases via default parameters and advanced experimentation through user-defined behavioral functions.The resulting tool can effectively replicate important structural properties of real-world graphs. By enabling controlled exploration of how algorithmic performance varies across different types of search spaces, it offers a valuable foundation for future research in heuristic search, algorithm evaluation and synthetic state-space generation.