Tree Search vs Optimization Approaches for Map Generation

Debosmita Bhaumik, Ahmed Khalifa, Michael Cerny Green, Julian Togelius
3/27/2019
cs.AI

Official code: amidos2006/gym-pcgrl (134 stars, MIT, last commit 2024-12-13).

Abstract

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.

View on arXivView PDF

Code Implementations(1)

amidos2006/gym-pcgrlOfficial100%
MIT

A package for "Procedural Content Generation via Reinforcement Learning" OpenAI Gym interface.

13432Python, DockerfileOct 28, 20191 years agoMIT

Similar Papers

Tools for Landscape Analysis of Optimisation Problems in Procedural Content Generation for Games

88% match2023

Evolutionary Wave Function Collapse

83% match2026

Computational and Exploratory Landscape Analysis of the GKLS Generator

82% match2023

Benchmarking Algorithms for Submodular Optimization Problems Using IOHProfiler

81% match1 repo112023

An Evolutionary Framework for Connect-4 as Test-Bed for Comparison of Advanced Minimax, Q-Learning and MCTS

80% match2024

The Procedural Content Generation Benchmark: An Open-source Testbed for Generative Challenges in Games

80% match2 repos282025

Cite this paper

@article{bhaumik2019tree,
  title  = {Tree Search vs Optimization Approaches for Map Generation},
  author = {Debosmita Bhaumik and Ahmed Khalifa and Michael Cerny Green and Julian Togelius},
  year   = {2019},
  eprint = {1903.11678},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/1903.11678}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/1903.11678.svg)](https://codeofpaper.com/paper/1903.11678)

Discussion