Tree Search vs Optimization Approaches for Map Generation
This work addresses the problem of efficient procedural content generation for game developers, though it is incremental as it compares existing methods rather than introducing fundamentally new ones.
The paper compared tree search and optimization algorithms for generating game levels across three problems (Binary, Zelda, Sokoban), finding that optimization algorithms generally outperformed tree search, but with appropriate representations, some tree search methods performed similarly, and MCTS showed surprisingly strong results in one case.
Search-based procedural content generation uses stochastic global optimization algorithms to search for game content. However, standard tree search algorithms can be competitive with evolution on some optimization problems. We investigate the applicability of several tree search methods to level generation and compare them systematically with several optimization algorithms, including evolutionary algorithms. We compare them on three different game level generation problems: Binary, Zelda, and Sokoban. We introduce two new representations that can help tree search algorithms deal with the large branching factor of the generation problem. We find that in general, optimization algorithms clearly outperform tree search algorithms, but given the right problem representation certain tree search algorithms perform similarly to optimization algorithms, and in one particular problem, we see surprisingly strong results from MCTS.