Artificial intelligence for real-time strategic games

Název práce: Umělá inteligence pro real-time strategické počítačové hry Autor: Ondřej Sýkora Katedra (ústav): Katedra teoretické informatiky a matematické logiky Vedoucí diplomové práce: Mgr. Cyril Brom e-mail vedoucího: brom@ksvi.mff.cuni.cz Abstrakt: Real-time strategické hry (RTS) jsou mezi hráči počítačových her jedním z něj- oblíbenějších žánrů. Přesto existuje jen málo prací, které by se tímto žánrem zabývaly. V této práci se zabýváme problémem výběru akcí pro jednotky v real-time strategických hrách za použití teoretických nástrojů pro řešení markovovských rozhodovacích problémů. V úvodních kapitolách představujeme real-time strategické hry jako herní žánr i jako vý- zkumný problém v oboru umělé inteligence. Následně se věnujeme markovovským rozho- dovacím procesům a metodám pro jejich řešení. Navrhujeme řešení problému výběru akcí pro real-time strategickou hru jako řešení markovovského rozhodovacího problému za po- mocí zjednodušeného diskrétního simulátoru real-time strategické hry. Na experimentech ověřujeme možnost takového výběru akcí a jeho vlastnosti. Klíčová slova: real-time strategická hra, markovovský rozhodovací proces, Expected Out- come, bandit-based plánování, diskrétní simulace 6Title: Artificial intelligence for real-time strategic games Author: Ondřej Sýkora Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor: Mgr. Cyril Brom Supervisor's e-mail address: brom@ksvi.mff.cuni.cz Abstract: Among the computer game players, real-time strategy games (RTS) are one of the most popular genres. Despite of this fact, there is a very low number of publicati- ons concerning this genre. In this thesis we study the problem of an action selection in the real-time strategy games using methods based on Markov decision processes. In the first chapters we introduce the genre of real-time strategy games from the game designer's perspective as well as from the view of an artificial intelligence researcher. We give an introduction to the Markov decision processes and to methods designed to solve them. We propose a solution of the problem of an action selection based on Markov decision problem solving using a discrete-event simulation of the real-time strategy game. We test the clarity of the proposed method and its properties. Keywords: real-time strategy game, Markov decision process, Expected Outcome, bandit- based planning, discrete-event-simulation 6Katedra teoretické informatiky a matematické logikyDepartment of Theoretical Computer Science and Mathematical LogicFaculty of Mathematics and PhysicsMatematicko-fyzikální fakult