Tree Search versus Optimization Approaches for Map Generation
Debosmita Bhaumik, Ahmed Khalifa, Michael Green, Julian Togelius · Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment · 2020
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 performs similarly to optimization algorithms, and in one particular problem, we see surprisingly strong results from MCTS.