CS 440: Artificial Intelligence

Lab 4

Due: Friday 11/01/2024 @ 11:59pm EST

The purpose of labs is to practice the concepts that we learn in class. To that end you will be writing java code that uses a game engine called Sepia to develop agents that solve specific problems. In this lab we will be playing a zombie survival game called Zombayes, where we have to classify between human units (pretending to be zombies so they don’t get eaten) and actual zombies. Zombies will attack you given the chance, but humans will not. Your job will be to use a decision tree to learn how to distinguish between zombies and humans: you want to attack the zombies but not the humans!

1. Copy Files

Please, copy the files from the downloaded lab directory to your cs440 directory.  You can just drag and drop them in your file explorer.

•  Copy Downloads/lab4/lib/zomtree.jar to cs440/lib/zomtree.jar. This file is the custom jarfile that I created for you.

•  Copy Downloads/lab4/data/labs/zomtree to cs440/data/labs/zomtree. This directory contains a game configuration and map files.

•  Copy Downloads/lab4/src/labs to cs440/src/labs. This directory contains our source code  .java files.

• Copy Downloads/lab4/zomtree .srcs to cs440/zomtree .srcs.

This file contains the paths to the  .java files we are working with in this lab.  Just like last lab, files like these are used to speed up the compilation process by preventing you from listing all source files you want to compile manually.

•  Copy Downloads/lab4/doc/labs to cs440/doc/labs.   This is the documentation generated from  zomtree.jar  and  will  be  extremely  useful  in  this  assignment.   After  copying,  if  you double-click on cs440/doc/labs/zomtree/index.html, the documentation should open in your browser.

2. Test run

If your setup is correct, you should be able to compile and execute the given template code.  You should see the Sepia window appear.

#  Mac,  Linux .  Run  from  the  cs440  directory .

javac  -cp  " ./lib/*: . "  @zomtree .srcs

java  -cp  " ./lib/*: . "  edu .cwru .sepia.Main2  data/labs/zomtree/easy/tunnel .xml

#  Windows .  Run  from  the  cs440  directory .

javac  -cp  " ./lib/*; . "  @zomtree .srcs

java  -cp  " ./lib/*; . "  edu .cwru .sepia.Main2  data/labs/zomtree/easy/tunnel .xml

3. Survival Rules & Information

Our game has two phases.  Initially, you and a partner must go and collect some gold.  However, the gold is guarded by a horde of zombies with humans pretending to be zombies (so they don’t get eaten) mixed in. There is also a special zombie unit who will continuously spawn new units whenever another unit is killed (this special zombie can spawn other zombies and also other humans, dont ask why). Because of this scenario, you will lose this game.  However, we are interested in how long you last; how many zombies you can take down with you before you are killed, and also how many humans you choose to kill.

The game will start off with your partner going to collect gold.  Once your partner is adjacent to the gold, all units in the horde will rush them. Humans, who bear no ill will to you or your partner, will take advantage of the confusion and flee to the bottom-right of the map.  The zombies however will seek to kill your partner. Your partner has a lot of health but isn’t very smart (or capable with their weapon), so will eventually succumb to the horde.

You have been paying attention this whole time, and will be supplied at the moment of your partner’s death with a record of which units attacked them (and therefore are known to be zombies), and which units did not (and therefore are known to be humans).  Each unit has a feature description which you cannot see on the game rendering.  So, to make it easier to view, human units in the horde have a  “h” character, and zombie units have a “z” character.  The “S” character is the zombie spawning unit, and there is only one of them in the game.

Your agent however does not get to view the characters of the units in order to make its decisions. Instead, your agent is supplied with four features:  2 continuous and 2 discrete.  The distribution of the features is controlled by the difficulty of the game:  humans and zombies look very different in the EASY game mode and look much more similar in the HARD game mode. You are to implement and train a decision tree model to classify whether or not a unit (represented with its feature vector) is a human or not.  Any unit your decision tree classifies as a zombie (i.e.  class 1) will be attacked by your agent. So be careful! Any time you waste shooting humans is time that you aren’t shooting zombies!

Task 1: Decision Tree Agent (100 points)

In this task,I want you to fill in the empty methods and classes in src .labs .zomtree .DecisionTreeAgent. You will need to finish the implementation for a DecisionTree type.  Our Decision Tree implemen-

tation will be a standard tree implementation, using Node objects and children/parent relationships. I have provided an abstract Node datatype, and have begun the implementation for two subtypes: InteriorNode and LeafNode.  You will need to finish these two classes in order to begin assembling a Decision Tree.

To build a Decision Tree, I have begun a recursive dfs-style. implementation for you called dfsBuild. This implementation should build a Node from the provided data (only looking at the provided columns within that data), and should recurse to build all children of the Node before returning.

I have provided the implementation for fit and predict for you as a courtesy.  Most notably is the predict method which will walk your tree until it encounters a LeafNode, at which point it will make a prediction. I have hidden most of the Sepia-ness from you, so please focus entirely on making a good Decision Tree model!

Suggestion:  This game will take a long time to run, so to save time, please complete the following:

1.  Modify the DecisionTree .fit method to save the training data to disk.  The Matrix class has serialization/deserialization methods, but you will need to open/close and read/write to the files. Once your training data is saved to disk, you don’t have to run the game again (and wait for the training data to generate from your partner) until the very end.  Once your data is saved to disk, you can remove your modification(s) from the fit method.

2. Write a separate Java file with its own main method. The name of this file, where it goes, etc. are not important.  What is important is that your main method loads the training data from disk, instantiates your DecisionTree class, and tries to fit the decision tree to the training data. Use this to debug your implementation.

3. When you have your implementation working, run the game again and see how well it does!  Use this pipeline to iterate and begin changing the difficulty of the game as you see fit.

Task 2: Extra Credit (50 points)

In this task I will ask you to tune your decision tree model.  There are many ways of doing this (for instance going through the ROC curve of your model, etc) however the most effective strategy for this is to prune your tree. The reason for doing so is that the consequences for a misclassification are not symmetric: if you misclassify a human as a zombie you will kill the human (and presumably feel bad). If you misclassify a zombie as a human, you won’t kill the zombie and the zombie will stand there attacking you until you die. Since our model predicts zombies as class 1 (i.e. the class corresponding to the boolean value true), misclassifying a zombie as a human is a false  negative.  The first false negative your model predicts is your death sentence.

To avoid making these mistakes, you should implement some of the pruning algorithms we discussed in lecture. Some will work better than others, its up to you to identify them.  Extra credit points will be awarded by running on the HARD difficulty.  Your implementation will earn credit proportional to the number of zombies that you kill, and will lose credit for every human that you kill.  For full extra credit, you must kill at least 40 zombies and not kill any humans.

Task 3:  Submitting your lab

Please submit your unpruned DecisionTreeAgent.java to the “normal-credit” entry on gradescope (just  drag  and  drop  in  the  file).    If  you  complete  the  extra  credit,  please  submit  your  pruned DecisionTreeAgent.java on the “ec” entry on gradescope.