Graph-Based Search for Game Design

Daniel Ashlock and Cameron McGuinness
Submitted to Game and Puzzle Design

Abstract PDF eprint

This article is the second in a tutorial series on the relationship between games, puzzles, and combinatorial graphs. It introduces classical and modern algorithms for permitting a computer to play a game and for designing games and puzzles by search. This latter activity is called searched based procedural content generation. The article introduces the foundational minimax search algorithm and its more efficient variation, $\alpha-\beta$-pruning. Monte Carlo tree search, a modern alternative to $\alpha-\beta$-pruning is described and used to design a polyomino puzzle. Dijkstra's algorithm for finding shortest paths on a graph is described as well as $A^*$-search, a family of heuristic improvements on Dijkstra's algorithm. These algorithms are applied in the evolutionary design of level maps.