Tree Search vs Optimization Approaches for Map Generation
  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.
