Script- and cluster-based UCT for StarCraft

Niels Justesen, Balint Tillman, Julian Togelius, Sebastian Risi

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

    Abstract

    Controlling units in real-time strategy (RTS) games is a challenging problem in Artificial Intelligence (AI) as these games are fast-paced with simultaneous moves and massive branching factors. This paper presents two extensions to the algorithm UCT Considering Durations (UCTCD) for finding optimal sequences of actions to units engaged in combat using the RTS game StarCraft as a test bed. The first extension uses a script-based approach inspired by Portfolio Greedy Search and searches for sequences of scripts instead of actions. The second extension uses a cluster-based approach as it assigns scripts to clusters of units based on their type and position. Our results show that both our script-based and cluster-based UCTCD extensions outperform the original UCTCD with a winning percentage of 100% with 32 units or more. Additionally, our results show that unit clustering gives some improvement in large scenarios while it is less effective in small combats. We suggest further research of the behavior and possible variants of the cluster-based approach which can be applied to many other algorithms similarly to UCT. The algorithms were tested in our StarCraft combat simulator called JarCraft, a complete Java translation of the original C++ package SparCraft, made in hopes of making this research area more accessible.

    Original languageEnglish (US)
    Title of host publicationIEEE Conference on Computatonal Intelligence and Games, CIG
    PublisherIEEE Computer Society
    ISBN (Electronic)9781479935468
    DOIs
    StatePublished - Oct 21 2014
    Event2014 IEEE Conference on Computational Intelligence and Games, CIG 2014 - Dortmund, Germany
    Duration: Aug 26 2014Aug 29 2014

    Publication series

    NameIEEE Conference on Computatonal Intelligence and Games, CIG
    ISSN (Print)2325-4270
    ISSN (Electronic)2325-4289

    Other

    Other2014 IEEE Conference on Computational Intelligence and Games, CIG 2014
    CountryGermany
    CityDortmund
    Period8/26/148/29/14

    ASJC Scopus subject areas

    • Artificial Intelligence
    • Computer Graphics and Computer-Aided Design
    • Computer Vision and Pattern Recognition
    • Human-Computer Interaction
    • Software

    Fingerprint Dive into the research topics of 'Script- and cluster-based UCT for StarCraft'. Together they form a unique fingerprint.

  • Cite this

    Justesen, N., Tillman, B., Togelius, J., & Risi, S. (2014). Script- and cluster-based UCT for StarCraft. In IEEE Conference on Computatonal Intelligence and Games, CIG [6932900] (IEEE Conference on Computatonal Intelligence and Games, CIG). IEEE Computer Society. https://doi.org/10.1109/CIG.2014.6932900