Optimizing Super Mario game tree search
Optimalizace prohledávání herního stromu v počítačové hře Super Mario
diplomová práce (OBHÁJENO)
![Náhled dokumentu](/bitstream/handle/20.500.11956/184179/thumbnail.png?sequence=7&isAllowed=y)
Zobrazit/ otevřít
Trvalý odkaz
http://hdl.handle.net/20.500.11956/184179Identifikátory
SIS: 256963
Kolekce
- Kvalifikační práce [10925]
Autor
Vedoucí práce
Oponent práce
Dvořák, Tomáš
Fakulta / součást
Matematicko-fyzikální fakulta
Obor
Informatika - Vizuální výpočty a vývoj počítačových her
Katedra / ústav / klinika
Katedra softwaru a výuky informatiky
Datum obhajoby
6. 9. 2023
Nakladatel
Univerzita Karlova, Matematicko-fyzikální fakultaJazyk
Angličtina
Známka
Výborně
Klíčová slova (česky)
umělá inteligence|herní strom|doménově závislé heuristiky|Super MarioKlíčová slova (anglicky)
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.