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.
