Genetic Programming applied to a real time game domain
Authors
Holm, Jørn ; Nielsen, Jens Dalgaard
Term
4. term
Education
Publication year
2002
Abstract
Genetisk programmering (GP) er en metode, der automatisk udvikler computerprogrammer ved at kombinere og ændre kode for at løse en opgave bedre. Et kendt problem i GP er bloat: programmerne vokser i størrelse uden tilsvarende forbedringer, hvilket mindsker diversiteten i populationen og kan give for tidlig konvergens. Når løsningerne bliver store, mister standardoperatorer som subtræ-crossover og subtræ-mutation—som normalt står for udforskning og udnyttelse—meget af deres virkning, og yderligere forbedringer ses sjældent. I denne afhandling bruger vi GP til at udvikle nærkampsstrategier for agenter i spillet Unreal Tournament, med Holm og Nielsen (2002) som ramme. Vi foreslår fire udvidelser af den grundlæggende GP-algoritme med to mål: (1) at kontrollere den gennemsnitlige størrelsesvækst af løsninger og (2) at bevare diversitet ved at forbedre de genetiske operatorer. Vores resultater viser, at det giver god performance at styre de genetiske operatorer, så de ændrer effektiv kode (de dele, der faktisk påvirker agentens adfærd). Vi finder også, at et direkte pres, som belønner unikke løsninger og straffer almindelige, fungerer godt og giver en ubetydelig grad af bloat.
Genetic Programming (GP) automatically evolves computer programs by combining and modifying pieces of code to perform a task better. A well-known issue in GP is bloat: programs grow larger without equivalent gains, which reduces population diversity and can cause premature convergence. As solutions become larger, standard operators such as sub-tree crossover and sub-tree mutation—responsible for exploration and exploitation—lose much of their effect, and further improvements become rare. In this thesis, we use GP to evolve close-combat strategies for agents in the game Unreal Tournament, using Holm and Nielsen (2002) as the framework. We propose four extensions to the basic GP algorithm aimed at (1) controlling the average size of solutions and (2) maintaining diversity by improving the genetic operators. Our results show that guiding genetic operators to act within effective code (the parts that actually influence the agent’s behavior) yields good performance. We also find that applying direct pressure that rewards unique solutions and penalizes common ones performs well and keeps bloat minimal.
[This abstract was generated with the help of AI]
Documents