The objective was to implement the Learning Track for Mario bros, that is, to implement a Machine Learning technique for Mario Bros. For this project I chose Decision Tree Learning (ID3). A Decision Tree is a series of decisions that generate an action based on a set of observations.
This project was implemented over the existent IEEE Super Mario Bros infrastructure that can be found at this URL: http://www.marioai.org/ .
The objective was to implement the Learning Track for Mario bros, that is, to implement a Machine Learning technique for Mario Bros. For this project I chose Decision Tree Learning (ID3). A Decision Tree is a series of decisions that generate an action based on a set of observations. At each node in the Tree, some aspect of the game world is taken into consideration and a different branch is taken according to the decision. In the ID3 algorithm, the Decision Tree is self-generated according to a set of Training Data which is also called Examples. These examples look like a table, where columns are attributes with their values, and each row is an Example, and the last column is a decision or action. The objectives in this project are:
The ID3 implementation was successfully accomplished in this project. It compromises the Data Structure for the Decision Tree, a Data Parser to read the Training data, and the core ID3 algorithm which builds the Tree based on the Training data. This module was tested with independent data, and it accomplished to build the correct Trees.
Getting the Training Data (Examples) was the most challenging part in this project. There are three main challenges: Where to get the data from, How to get good data and how to encode the data. In order to have a robust ID3 Tree, I had to tackle those main three areas which unfortunately were not accomplished successfully.
I implemented an Agent which records the examples from human game play. Every second a few set of Examples were recorded while somebody played MarioBros. Recording this Training data had its own set of challenges:
The agent in charge of executing the ID3 Tree has the following tasks:
My main objective was to create a learner agent that will traverse the game level in an efficient manner; that is with the least collisions with enemies and obstacles by using a Decision Tree generated from a Training data which was a log of examples from my own game play. Although the implementation of the ID3 structure was successful, the Training data has many flaws: noise data, few examples, and not enough attributes; and that cause that the Agent performed very poorly.
I chose ID3 because at the moment it seemed to be the most straightforward and logical choice for a game that require a lot of decisions; moreover, my inexperience in Machine Learning made me decide to use this technique over others such as Neural Networks. Unfortunately, the challenges and issues progressively started to emerge while I was making small progress in the project, and given the time constraints, there was not going back. ID3 for this type of game requires a lot of training data with too many attributes and that has been the greatest challenge and obstacle in this project.
This agent could have been improved by using a much larger set of high quality Training Data perhaps coming from an almost perfect Mario Agent, along with an increased set of Attributes for the Examples.