Project 3: Adversarial Search

Executive Summary

This project will take 10-12 hours to complete.  Note, as with the last project, graduate students have additional requirements.

By the end of this project, you will have accomplished the following objectives.

  • Created an agent that can play games optimally using minimax (and alpha-beta pruning if you are a graduate student) 
  • Reused your code from the previous projects to allow the agent to effectively navigate around the environment and choose a gaming asteroid
  • Compete on the class-wide competition ladder

Project summary

Watch the video to see what we are doing in this project!  Basic idea: we are adjusting the project to play adversarial games.

Class-wide ladders – Extra credit

The extra credit ladders remain the same type as the previous projects (e.g. coop and compete).  You are welcome to choose a different ladder path than you chose for either of the previous projects.  To encourage a focus on the asteroids, we will change the scoring to be:

  • Coop ladder will use the scoring Resources which is just the total amount of resources collected and brought back to base.  This encourages you to get gaming asteroids since they are worth a LOT more.
  • Compete ladder will use the scoring ResourcesAndCores which is the total amount of resources collected and brought back to base plus 100 times the number of cores brought back to base.  This encourages both seeking out gaming asteroids and continuing to seek out the opponents (since this is the competitive ladder).

The class-wide ladders will start on Oct 9 2023.

New heuristic agents

There are two new heuristic agents for this project.

  • PacifistHeuristicGameAsteroidCollectorTeamClient
  • AggressiveHeuristicGameAsteroidCollectorTeamClient 

These are both extensions of the Passive or Aggressive Asteroid Collector client.  The difference is that each goes for the nearest gaming asteroid, if it is available, and then tries to beat it to collect the larger amount of resources.  You should look at these agents to see the interface to playing against the gaming asteroids and how you can create a minimax search agent.  There is an example heuristic (model-based reflex really) agent called HeuristicTicTacToe3DGameAgent and another called HeuristicTicTacToe2DGameAgent in the spacesettlers.game package.  I cannot release an agent with minimax code in it or you would have the solution!  So my agents that you compete against will be some form of a heuristic agent.  You will be able to see all of what that agent is doing in the code.

Implementation details

This project requires looking at code in a whole new package – look at spacesettlers.game for details but I give an overview of the critical parts in the video below.  Watch to help get your project started!

Minimax search

All students (CS 4013 and CS 5013) need to implement minimax search inside their agent and use it in some strategic way to obtain the gaming asteroids.  You can still maintain your agent on the competitive or cooperative ladder but that agent should have minimax implemented and be able to play the game of 3x3x3 3D Tic Tac Toe intelligently.  If you never got a working search for projects 1 & 2, you could start with one of the heuristic agents and just modify them to do MiniMax and ignore the intelligent navigation part.

CS 5013 students need to implement alpha-beta pruning on top of minimax search.

For extra credit, both CS 4013 and 5013 can implement rollouts and use them to improve search efficiency (this is a large space for full minimax search).  

Available games

I have implemented TWO games that will be chosen for you randomly this year.  When you touch a gaming asteroid, the game factory will randomly choose one of the two games for you to play.  The two games are:

  • 2D Tic Tac Toe.  This is your standard Tic Tac Toe or Noughts and Crosses game as described here.
  • 3D Tic Tac Toe.  There is a description of the 3x3x3 and the 4x4x4 game on Wikipedia here.  We have only given you 3x3x3 if you get handed the 3D game board!

Extra credit

The extra credit opportunities for being creative and finding bugs remain the same as in previous projects. I want to add a bit of extra encouragement to find bugs for this project specifically.  The idea of having two searches is new this year and 2D TTT is specifically new.  It is much more likely that bugs are in the new code than in the general simulator which has been used for many years!  Please report them if you find them!

In addition to bug finding, both CS 4013 and 5013 can receive extra credit for implementing rollouts and using them to improve search efficiency.  Remember you have to document it in your writeup to get the extra credit!  

How to download and turn in your project

Remember there are help videos for this in Project 0 also!

  1. Update your code from the last project. You can update your code at the command line with “git pull”. If you did not get the code checked out for project 0, follow the instructions to check out the code in Project 0.
  2. Change the SpaceSettlersConfig.xml file in spacesettlers/config/heuristicCooperative or heuristicCompetitive to point to your agent in src/4×4. The detailed instructions for this are in project 0. Make sure to copy over a spacesettlersinit.xml in the src/4×4 directory so your agent knows how to start. In spacesettlersinit.xml change the line <ladderName>Random Client</ ladderName> to the team name you chose in Canvas.
  3. Write your minimax code as described above
  4. Build and test your code using the ant compilation system within intelliJ or using ant on the command line. Make sure you use the spacesettlers.graphics system to draw your graph on the screen as well as the path your ship chose using your search method. You can write your own graphics as well but the provided classes should enable you to draw the graph quickly.
  5. Submit your project on spacesettlers.cs.nor.ou.edu using the submit script as described below.  You can submit as many times as you want and we will only grade the last submission.
    • Submit ONLY the writeup to the correct Project 3 on canvas: Project 3 for CS 4013 and Project 3 for CS 5013
    • Instructions to login to the machine are given in Project 0.
    • Submit your file using one of the following commands (be sure your java files come last). You can submit to only ONE ladder. If you submit to both, small green monsters will track you down and deal with you appropriately.
/home/spacewar/bin/submit --config_file spacesettlersinit.xml \
--project project3_coop \
--java_files *.java
/home/spacewar/bin/submit --config_file spacesettlersinit.xml \
--project project3_compete \
--java_files *.java
    • After the project deadline, the above command will not accept submissions. If you want to turn in your project late, use:
/home/spacewar/bin/submit --config_file spacesettlersinit.xml \
--project project3_coop_late \
--java_files *.java
/home/spacewar/bin/submit --config_file spacesettlersinit.xml \
--project project3_compete_late \
--java_files *.java

Rubric

Remember, just as with the other projects, graphics (or in the case of this project, printouts can work fine) are required in order to be graded.

  • CS 4013/5013: Minimax printouts or graphics
    • 10 points for correctly drawing (or printing) graphics that enable you to debug your Minimax search and that help us to grade it. Since minimax happens entirely inside one time step, it is easiest to use printouts.
    • 7 points for drawing/printing something useful for debugging and grading but with bugs in it
    • 3 points for major graphical/printing bugs
  • Minimax
    • 30 points for correctly implementing Minimax search for BOTH 2D and 3D Tic Tac Toe. This means it is a GENERIC minimax search.  A correct player will win the game against the game asteroids if it is the first player in 3x3x3 3D Tic Tac Toe or tie in 2D Tic Tac Toe and will do so using Minimax search.  A correct player will also ensure it goes to the gaming asteroids to play against them.  Full credit requires FULL code documentation explaining what each function does. The top of each java file should also contain a 2-3 sentence description of everything that java file does.
    • 25 points if there is only one minor mistake. You can also lose 5 points for not documenting your code well (but at least somewhat).
    • 20 points if there are several minor mistakes or if your code is missing a lot of documentation.
    • 15 points if you have one major mistake. 
    • 5 if there are several major mistakes or if you implement a search other than Minimax that at least tries to play the game intelligently and is not just a re-use of the provided heuristic agent.
  • CS 5013 students only: You must also implement alpha-beta search 
    • 20 points for a fully implemented and correct alpha-beta search
    • 15 points for implementing the search but it is lacking documentation or has minor errors
    • 10 points for a major error or several minor ones
    • 5 points for major errors
  • Good coding practices: We will randomly choose from one of the following good coding practices to grade for these 10 points. Note that this will be included on every project. Are your files well commented? Are your variable names descriptive (or are they all i, j, and k)? Do you make good use of classes and methods or is the entire project in one big flat file? This will be graded as follows:
    • 10 points for well commented code, descriptive variables names or making good use of classes and methods
    • 5 points if you have partially commented code, semi-descriptive variable names, or partial use of classes and methods
    • 0 points if you have no comments in your code, variables are obscurely named, or all your code is in a single flat method
  • Writeup: Your writeup is limited to 2 pages maximum. Any writeup over 2 pages will be automatically given a 0. Turn your writeup in to canvas and your code into spacesettlers.
    • 8 points: Describe how you implemented minimax
    • 2 points: Why did you choose the cooperative or competitive path? A sentence or two is sufficient here.

MODULE MENU