Tree Search versus Optimization Approaches for Map Generation


  • Debosmita Bhaumik New York University
  • Ahmed Khalifa New York University
  • Michael Cerny Green New York University
  • Julian Togelius New York University



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.




How to Cite

Bhaumik, D., Khalifa, A., Green, M., & Togelius, J. (2020). Tree Search versus Optimization Approaches for Map Generation. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 16(1), 24-30.