CIS667 Semester Project Guidelines and Proposals
Overview
You will implement an AI system that combines some tree search and machine learning algorithms to
play a game with some form of non-determinism (such as partial observability, randomness, or
opponent players). You can work individually or in groups with at most 4 members. You will not be
graded based on the performance of the AI (it doesn’t have to beat a human). But you will be required
to implement and report several experiments that quantify your AI’s performance. You will also need to
specify which team member is responsible for which part of your report and that will factor in to your
individual grades. Before the main project you will need to write a proposal and get approval from the
instructor (potentially after a revision).
Game selection
You will need to choose and implement a game for your AI. The implementation can be all text-based
(no need for a graphical user interface). You must implement the game in such a way that it can be run
with larger or smaller instances. For example, in tic-tac-toe, you should be able to adjust the size of the
game board, and the number of symbols in a row needed to win. Your implementation should include
an interactive mode which lets a human user play the game, by providing all the actions available to
them, letting them choose one of those actions, printing the new state of the game environment, and
repeating. Your game must include some form of non-determinism: for a given percept/action that your
agent sees/performs, there must be more than one possible new state (for example, if the opponent
chooses one response vs another).
Model selection
You will need to choose two AI models to combine for your project. The first “model” must use a tree-
search-based algorithm, including but not limited to what we covered in class (e.g. minimax or monte-
carlo tree search). The second “model” should be a machine learning model with some parameters that
can be trained by gradient descent or reinforcement learning methods (e.g. a neural network). Your
second model should be used to by your first model to prioritize child nodes during the search
algorithm.
Performance Evaluation
To evaluate performance, you must try a range of instance sizes (e.g., smaller or larger tic-tac-toe
boards) and a range of machine learning model configurations (e.g., different sizes/types/number of
neural network layers). You can implement the game as a team, but each individual is responsible for
evaluating a different machine learning model configuration.
You must evaluate your configuration using 5 different problem instance sizes. For each problem
instance size, you must use at least 25 game repetitions for training at every parameter update, and you
must use at least 100 updates during learning. You must plot the “learning curve” of training on each
problem instance size, which shows performance on the y-axis and update iteration on the x-axis. So
there will be 5 learning curves in your results.
After training is done, you must compare the performance of your search both with and without the
machine learning component, again on each of 5 problem instance sizes. To evaluate performance in
this case, you should measure both win rate and efficiency. Win rate should be how often your AI wins,
compared against a uniform random baseline (e.g., an opponent that chooses randomly or environment
with random changes in a one-player game). Efficiency should be measured by the number of nodes
checked during the tree search. You should use at least 100 games at each problem instance size to
measure win rate and efficiency. These results should be shown with the appropriate plots (such as
histograms).
Implementation requirements
You can use generic libraries like NumPy and PyTorch or TensorFlow. You can also use a language other
than Python. However, libraries that already implement your game or specific model is not allowed,
unless there is a sufficient amount of work left for you to do, which will be assessed based on your
project proposal.
You will be required to post your project code on GitHub and include a readme that lists all of the
software dependencies and all of the steps needed to run your code and reproduce your results.
Project proposals
You must submit a project proposal ahead of time that will be reviewed by the instructor. You may
receive feedback about necessary revisions to your project idea before moving forward. Your proposal
will be worth 10% of the overall project grade, and should specify:
• All of the team members, including full name and NetID
• Which game you will implement
• Which tree search algorithm you will use
• Which machine learning algorithm you will use
• Which software libraries, if any, you want to use in your project.
Points will be deducted for lateness and for not addressing the foregoing after revisions.