Optimizing Super Mario game tree search

Abstract

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.

Hra 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.