Humanoids

Final Project: Mario AI

Here's a link to my project code. My controllers can be found under "src/MyAgents".

Project Description

The Mario AI Competition was held from 2009 - 2012. The focus of the competition was on developing controllers that could play a version of Super Mario Bros as well as possible. The competition used a modified version of Super Mario Bros developed by Markus Persson called Infinite Mario. My project goal was to design and implement as many controllers as I could think of in the time that I had. I was originally inspired by this viedo I had watched years ago, showing someone's implementation of a controller that used A* search.

My Controllers

Due to issues that I will discuss later, I was only able to implement 3, pretty simple, controllers. The three of them are:

  • Button Masher
  • Shooter
  • Finite State Machine

Button Masher
This was my first and most basic controller. It shoots and jump as often as possible while moving right, making it's movement similar to a human player who justpresses buttons as often as possible while playing. Surprisingly, this controller can make it through the first level of gameplay. This, of course, doesn't last beyond that level; once flying monsters are introduced into gameplay on the second level, Mario dies almost immediately. This is a result of button mashing leading to Mario being in the air almost constantly.
Shooter
This was my second controller. It builds off the first one by still shooting continuously but it tries to make "smart" decisions about when to jump. In deciding whether to jump, it takes into account whether Mario is in danger from enemies, whether Mario is close to a hole, and whether it is safe for Mario to jump (for example, would jumping cause Mario to collide with a flying enemy). Like the Button Masher, the Shooter makes it throught the first level. It also gets pretty far into the second level (much farther than the Button Masher) but Mario dies before reaching the castle at the end of the level. The Shooter makes it pretty far on most levels it's presented with but can't quite successfully finish these levels.
Finite State Machine
A finite state machine is a computational model that can be used to model a large variety of problems (such as language parsing). It can be thought of as an abstract machine that can be in one of a finite muber of states. The machine is in only one state at a time and changes from one state to another when initiated by a triggering event or condition. For this controller, I defined four states: Jump, Jump Hole, Walk Forward, Walk Backward (I encountered a few cases where Mario gets trapped by bricks and walls and needs to back up a few steps. The transitions are determined by whether there is an enemy close to Mario, whether there is a hole in Mario's path, and whether there is an obstacle in Mario's path. The Finite State Machine most resembles a human player out of the three; it's the "calmest" and least controller. However, while I expected it to be at least on par with the shooter agent, it doesn't make it past the first level of play. While I originally thought this was because of a bug in my code, I haven't been able to find it and I'm now considering the possibility that a finite state machine is just not an effective controller for playing Mario.

Project Challenges

At the outset of the project, I had intended to also implement a controller using A* search and a controller that implemented more advanced AI techniques such as Reinforcement Learning. However, I ran into two problems that led to these two goals becoming something to consider for future work on the project:

  1. No source code documentation -- I couldn't find much documentation for the Mario AI source code online and the code is largely uncommented meaning I spent the main chunk of this project just trying to understand the underlying code. While I got far enough to write my three basic controllers, I didn't get far enoughto figuring out how I would go about implementing a controller that used things like reinforcement learning or neural networks
  2. After some research, I found that every existing controller that uses A* search was only able to do so by replicating the game's physics and then simulating the state of the game for some seconds into the future depending on the action taken. Due to problem #1, this approach seemed beyond the scope of something I could do in the timespan of my project

Future Work

  1. Implement a controller that uses Reinforcement Learning
  2. Implement a A* controller

Final Thoughts

While I expected a more "sophisticated" controller like the Finite State Machine to be the best out of the basic controllers, it seems the simpler strategy behind the Shooter controller is actually the best option.