Kooperativna koevolucija strategije za igru za više igrača

master's thesis

• Title (english): Cooperative coevolution of strategies for multiplayer games
• Author: Jakov Ivković
• Mentor: Domagoj Jakobović (mentor)
• Committee member: Domagoj Jakobović (predsjednik povjerenstva)
• Committee member: Marin Golub (član povjerenstva)
• Committee member: Leonardo Jelenković (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2024-02-22, Croatia

Abstract

Rad se bavi podržanim učenjem kroz korištenje kooperativne koevolucije za pronalazak što bolje strategije za igru Halite. Problem igranja igre je podijeljen na razvoj dvije strategije --- svaka strategija upravlja jednim od dva tipa entiteta u igri, čime je problem pretvoren u više-agentni optimizacijski problem. Implementirana su dva evolucijska algoritma (evolucijska strategija i genetski algoritam) te tri prikaza jedinki (prikaz stablima, kartezijsko genetsko programiranje i umjetna neuronska mreža). Implementirano je i učenje po kurikulumu, odnosno učenje u tri faze protiv, postepeno, sve težih i težih strategija. Isprobano je nekoliko kombinacija prikaza jedinki, evolucijskih algoritama te pripadnih hiperparametara. Najveći ograničavajući faktor ovog optimizacijskog problema je vrlo skupa evaluacija, koja, u određenim slučajevima, može trajati i preko 100 sekundi po jedinki.

Abstract (english)

This paper explores using cooperative coevolution in reinforced learning environment in order to find a good strategy for playing a game of Halite. The problem of playing the game is decomposed into two strategies --- each strategy controls one out of two types of entities in the game. With that decomposition the problem is transformed into multi-agent optimization problem. Two evolutionary algorithms (evolutionary strategy and genetic algorithm) and three individual representations are implemented (multiple tree representation, cartesian genetic programming and artificial neural network). Curriculum learning is implemented for learning in three phases against, progressively, harder opponents. Several combinations of evolutionary algorithms and individual representations were tested. The biggest limiting factor of this optimization problem is the very expensive evaluation, which, in some cases, can last over 100 seconds per individual.

• Keywords: podržano učenje; genetski algoritam; evolucijska strategija; kartezijsko genetsko programiranje; umjetna neuronska mreža; prikaz jedinke stablima; učenje po kurikulumu; metaheuristika; evolucijski algoritam
• Keywords (english): reinforcement learning; genetic algorithm; evolutionary strategy; cartesian genetic programming; artificial neural network; multiple tree representation; curriculum learning; metaheuristic; evolutionary algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:168:181399
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2024-03-28 07:47:47