Introduction to AI

Project 3: Adversarial search

Summary

This project will take 6-10 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 summarize what we are doing in this project!  It is fun to adjust the project to play adversarial games!

Class-wide ladders – Extra credit

The extra credit ladders remain the same as with Project 1.  You are welcome to choose a different ladder path than you chose for either of the previous projects.  Remember, even though we rank you the same as we did in the earlier projects, the new “gaming asteroids” will enable you to collect a LOT more resources!  

The class-wide ladders will start on Sep 29, 2021.

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 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 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 and likely it will be updated to be more intelligent than it is right now.

Implementation details

This project requires 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.  

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).  

3D Tic Tac Toe

To make the project doable, I have implemented a 3x3x3 3D Tic Tac Toe game.  There is a description of the 3x3x3 and the 4x4x4 game on Wikipedia here.  Although the 4x4x4 game is more complicated, for this year I chose the 3x3x3 game to implement.  In future years, the asteroids may offer you a choice of games!  

 

extra credit

The extra credit opportunities for being creative and finding bugs remain the same as in Project 1. I want to add a bit of extra encouragement to find bugs for this project specifically.  Last year (2021) was the first time I implemented adversarial search inside spacesettlers.  Although we found a few bugs last year, it is much more likely that bugs remain 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 eclipse or using ant on the command line if you are not using eclipse (we highly recommend eclipse or another IDE!). 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.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
    • Copy your code from your laptop to spacesettlers.cs.ou.edu using the account that was created for you for this class (your username is your 4×4 and the password that you chose in project 0). You can copy using scp or winscp or pscp.
    • ssh into spacesettlers.cs.ou.edu
    • Make sure your working directory contains all the files you want to turn in. All files should live in the package 4×4. Note: The spacesettlersinit.xml file is required to run your client!
    • 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 probably 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 3D Tic Tac Toe. A correct player will win the game against the game asteroids if it is the first player (since 3x3x3 3D Tic Tac Toe is solved for the first player win) 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.

 

AI course home

Project Module home