Tree search versus optimization approaches for map generation

Debosmita Bhaumik, Ahmed Khalifa, Michael Cerny Green, Julian Togelius

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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 performs similarly to optimization algorithms, and in one particular problem, we see surprisingly strong results from MCTS.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 16th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2020
    EditorsLevi Lelis, David Thue
    PublisherThe AAAI Press
    Pages24-30
    Number of pages7
    ISBN (Electronic)9781577358497
    StatePublished - 2020
    Event16th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2020 - Virtual, Online
    Duration: Oct 19 2020Oct 23 2020

    Publication series

    NameProceedings of the 16th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2020

    Conference

    Conference16th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2020
    CityVirtual, Online
    Period10/19/2010/23/20

    ASJC Scopus subject areas

    • Visual Arts and Performing Arts
    • Artificial Intelligence

    Fingerprint Dive into the research topics of 'Tree search versus optimization approaches for map generation'. Together they form a unique fingerprint.

    Cite this