\documentclass[10pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\newcommand{\astar}{A$^*$}
\begin{document}
\title{Decision Trees for RISK: \\ Learning winning states}
\author{}
\date{}
\maketitle

\vspace{8pt}
\hrule
\vspace{8pt}

This assignment involves learning a classifier for the game of RISK that will return a probability of a player winning given the territory assignments at the end of the territory selection phase at the beginning of the game.  
Naturally, such a classifier could be used by an AI for the game to decide which territories to select. 
We will do this by implementing a decision tree to do the classification.  
You should first download the \texttt{RISK-AI.zip} file from Blackboard and unzip in on your computer.  
The provided code has been tested with Python 2.7.

The folder you are provided contains (in addition to files for the final RISK AI assignment, which are described in that handout): 
\begin{itemize}
\item \textbf{\texttt{RISK\_Decision\_Tree\_Handout.pdf}} - This file that you are reading
\item \textbf{\texttt{generate\_dt\_data.py}} - This file is used to generate labeled data instances that we will feed into our decision tree algorithm.  
This has already been run for the attacker AI, and data is provided, but if you want to generate your own data from your own AI, you can do this.  
It generates data by playing games between the specified AIs and saving the state at the end of the assignment phase, as well as who wins the game at the end. It can be run by typing: 

\begin{center}
\texttt{python generate\_dt\_data.py ai\_1.py ai\_1\_name ai\_2.py ai\_2\_name number\_of\_games} 
\end{center}

from the command line.

\item \textbf{\texttt{learn\_d\_tree.py}} - This is the file you will be editing for this assignment.  It learns a decision tree, given a data file.  
It then saves the learned decision tree to a file.  

It can be run by typing: 

\begin{center}
\texttt{python learn\_d\_tree.py datafile.dat depth\_of\_decision\_tree} 
\end{center}

from the command line.

\item \textbf{\texttt{evaluate\_d\_tree.py}} - This is the script that you will run to evaluate your decision tree accuracy. 

It can be run by typing: 

\begin{center}
\texttt{python evaluate\_d\_tree.py decision\_tree.tree datafile.dat} 
\end{center}

from the command line.

\item \textbf{decision\_trees, dt\_data} - these are folders where the scripts save the decision trees and dataset for this programming assignment, respectively. The dataset folder already contains the datasets you will use, which are:
\begin{itemize}
\item \textbf{\texttt{dt\_10.dat}}
\item \textbf{\texttt{dt\_1000.dat}}
\item \textbf{\texttt{dt\_10000.dat}}
\item \textbf{\texttt{dt\_100000.dat}}
\item \textbf{\texttt{dt\_test.dat}}
\end{itemize}

These datasets differ in size, and each contains the results from as many games as the name implies. 
(There are, however, twice this many examples, because each single game provides us a winning example and a losing example.)  
You will use them to see how extra data effects the quality of the decision tree, using the dataset labeled ``test'' for evaluation. 

\end{itemize}

\section*{Part 1 [60 points]} 
The first part of this assignment is to complete the code so that you can learn a decision tree from data.
In this task, you will be required to implement two functions to learn decision trees.  
Starter code has been provided with the assignment 

\begin{itemize}
\item \textbf{Task 1 [10 points]} This task requires you to look over the provided code and implement the \texttt{compute\_entropy} function within the \newline \texttt{learn\_d\_tree.py} file.  This function should return the entropy value for a given probability $p$. Look for the place in the code marked ``BEGIN TASK 1''. 
\item \textbf{Task 2 [50 points]} This task requires you to implement the \newline \texttt{determine\_info\_gain} function within the \texttt{learn\_d\_tree.py} file. 
This function should return the information gain that would occur if the decision tree node were to split on the given feature. 
This code should use the \texttt{compute\_entropy} function that you completed earlier. 

You can learn a decision tree on the \texttt{dt\_10.dat} dataset to make sure this works right.  The printed screen output that you should get after learning a depth 3 tree is stored in ``example\_tree.txt''.  If your output does not match this is exactly, that is ok.  
Apparently some systems have some floating point differences with the entropy calculation that impact the tiebreaking.  
If your output splits the data into similarly sized and labeled subsets at each level (same entropy gains), then your implementation is correct.  

\end{itemize}

\section*{Part 2 [40 points]} 
Now that you have the decision tree learning code working, you will experimentally see how well the tree compares with varying depth and input dataset size.  
For each depth = \{1,3,5,7,10\} and each supplied dataset (mentioned above), report the accuracy of the resulting decision tree on the testset provided.  

Comment on how well you think the decision tree performed.

You are required to hand in the following for this assignment:
\begin{enumerate}
\item Your code with the required parts implemented or changed.
\item Your evaluation of the different decision trees, learned to different depths and on different datasets.
\item At least one substantial paragraph describing what you learned from these experiments.
\end{enumerate}

\section{Extra credit [20 points]}

Modify the \texttt{attacker\_ai.py} RISK AI to use the best decision tree you learned to help it select countries at the beginning.  
Turn in your code and a report of how well this new AI performs against the original attacker ai, with random initial country selection.


\end{document}