Reinforcement Learning in RTS Games
Authors
Toftgaard Andersen, Kresten ; Buch, Anders ; Dahl Christensen, Dennis ; Tran, Dung
Term
4. term
Education
Publication year
2008
Pages
126
Abstract
Denne afhandling undersøger, om forstærkningslæring (RL)—en metode, hvor en AI lærer ved forsøg og fejl gennem belønninger—kan bruges effektivt i strategispil i realtid (RTS) mod menneskelige modstandere. Vi ser på, hvordan man kan overvåge modstanderens strategi og modgå den ved at skifte mellem foruddefinerede belønninger og beslutningspolitikker, som løbende opdateres med RL. Vi foreslår tre udvidelser, der tilsammen danner et rammeværk for RL i RTS-spil: 1) en enkel, effektiv struktur med flere lag, der organiserer beslutninger på forskellige niveauer og gør det let at udskifte belønninger og politikker; 2) en spiller-modelleringsmetode kaldet profiler, som hjælper med at vælge passende belønninger og politikker baseret på modstanderens adfærd; og 3) en ændring af opdateringsfunktionen kaldet backtracking, hvor læringen opdateres flere skridt tilbage i tiden i stedet for kun ét skridt som i TD(0)-metoder. For at teste rammeværket anvender vi det i RTS-spillet Tank General, som hovedsageligt blev udviklet i forberedelsessemesteret. Resultaterne viser, at backtracking ikke giver en ydelsesforbedring, mens multilagsstrukturen og profiler fungerer meget godt: de reducerer tilstandsrummet (antallet af mulige spilsituationer) markant og forkorter den tid, det tager for RL at konvergere (finde en stabil, effektiv strategi). Vores konklusion er, at det er muligt og praktisk at bruge det foreslåede rammeværk i et RTS-spil.
This thesis examines whether reinforcement learning (RL)—a method where an AI learns through trial and error using rewards—can be used effectively in real-time strategy (RTS) games against human opponents. We explore monitoring an opponent’s strategy and countering it by switching predefined reward signals and decision policies that are updated by RL. We propose three extensions that together form a framework for RL in RTS games: 1) a simple, effective multi-layered structure that organizes decisions at different levels and makes it easy to swap rewards and policies; 2) a player modeling technique called profiler, which helps select suitable rewards and policies based on opponent behavior; and 3) a modification to the update function called backtracking, where learning updates several steps back in time instead of only one step as in TD(0) methods. To test the framework, we apply it to the RTS game Tank General, which was mainly developed during the preparation semester. The results show that backtracking does not improve performance, while the multi-layered structure and profiler perform very well: they drastically reduce the state space (the number of possible game situations) and shorten the time it takes for RL to converge (settle on a stable, effective strategy). We conclude that it is feasible and practical to use the proposed framework in an RTS game.
[This abstract was generated with the help of AI]
Keywords
Documents