Optimizing Super Mario game tree search
Optimalizace prohledávání herního stromu v počítačové hře Super Mario
diploma thesis (DEFENDED)
![Document thumbnail](/bitstream/handle/20.500.11956/184179/thumbnail.png?sequence=7&isAllowed=y)
View/ Open
Permanent link
http://hdl.handle.net/20.500.11956/184179Identifiers
Study Information System: 256963
Collections
- Kvalifikační práce [10925]
Author
Advisor
Referee
Dvořák, Tomáš
Faculty / Institute
Faculty of Mathematics and Physics
Discipline
Computer Science - Visual Computing and Game Development
Department
Department of Software and Computer Science Education
Date of defense
6. 9. 2023
Publisher
Univerzita Karlova, Matematicko-fyzikální fakultaLanguage
English
Grade
Excellent
Keywords (Czech)
umělá inteligence|herní strom|doménově závislé heuristiky|Super MarioKeywords (English)
artificial intelligence|game tree|domain-dependent heuristics|Super MarioHra Super Mario Bros. je stále aktivně využívána jako modelová hra pro výzkum generování herních úrovní. Každý rok jsou zkoušeny nejnovější techniky, což v poslední době zahrnuje obzvláště hluboké a zpětnovazební učení. Velká část generátorů využívá umělé agenty pro testování hratelnosti úrovní nebo ke sbírání herních metrik. Proto je výkon generátorů úzce spjat s výkonem umělých agentů, jak ve validaci herních úrovní, tak v potřebném výpočetním čase. V naší předchozí práci jsme vytvořili nového nejlepšího agenta pro tuto hru jakožto ověření funkčnosti nové implementace simulace světa hry. V této práci na toto navazu- jeme a zaměřujeme se na optimalizování toho, jak agenti prohledávají herní strom. Pro tento účel jsme vytvořili několik doménově specifických heuristik a provedli jsme rozsáhlé experimenty hledající optimální parametry, abychom agenty co nejvíce vylepšili. Díky těmto vylepšením se nám podařilo vytvořit nového nejlepšího agenta pro hru Super Mario Bros. Tento agent by měl být schopný porazil libovolnou standardní úroveň hry a zvládá tak učinit mnohem rychleji než předchozí nejlepší agent. Také představíme koncept agenta, který dokáže řešit labyrinty, což je něco, co žádný předchozí agent nedo- kázal.
Super Mario Bros. is still actively used as a model game for research in level genera- tion. Every year, the most recent techniques are applied and tested. This lately includes various deep learning and reinforcement learning methods. Many of the level generators use an artificial agent to test levels' playability or to gather playthrough metrics. There- fore, the performance of the level generators is undeniably tied to the performance of the artificial agent used, both in level validation and the computing time needed. In our previous work, we created a new state-of-the-art agent for Super Mario Bros. as a proof of concept when we implemented a more efficient forward model (world simu- lation) for the Mario AI framework. In this work, we continue in that work and focus on optimising how the agents explore the game tree by devising domain-specific heuristics and running extensive parameter searches to tune the agents as much as possible. Thanks to these improvements, a new state-of-the-art agent was created. This new agent should be capable of beating every standard Super Mario Bros. level and it requires less time to solve levels than previous agents. We also present a proof of concept agent that is capable of solving maze-like levels, which is something none of the previous agents was capable of.