Game Playing

Homework Assignment 2600.335/435 Artificial Intelligence
Game PlayingIn the past weeks, we discussed intelligent agents and how they can use tree searchingtechniques to solve abstracted problems. In this assignment, modeled after the BerkeleyAI course’s search assignment, we will use a variety of searching techniques to finda route for pacman to take to reach the pellet. For this assignment you are allowedto work in pairs. Note that grad students will be expected to complete some additionaltasks (if a pair of students has one undergrad student and one grad student, weexpected all grad student-specific tasks to be completed).First, download the code from the Berkeley website (search.zip). Follow the instructionsin order to be sure your system can properly run python and start the game.Please take a look through search.py and searchAgents.py to see which functions youwill need to implement, as well as pacman.py, game.py, and util.py. Please fulfill all ofthe following items and provide all performance-relevant output information (in casewe aren’t able to get your code to run properly):• Complete question 1, the depth-first search. Provide your solution for tinyMaze,mediumMaze, and bigMaze.• Complete question 2, the breadth-first search. Provide your solution for tiny-Maze, mediumMaze, and bigMaze.• Grad Students: In addition to the two previously-mentioned search algorithms,please implement an iterative deepening search. Provide your solution for tiny-Maze, mediumMaze, and bigMaze.• Complete question 3, which varies the cost function of your breadth-first search.Provide your solution for mediumMaze with the UCS agent, mediumDotted-Maze with StayEastSearchAgent, and mediumScaryMaze with StayWestSearchAgent.Grad Students: Create a new cost function and provide the solution it generateswith mediumMaze, mediumDottedMaze, and mediumScaryMaze. Why did youchoose this cost function and how did it alter the results you see for these environments?• Complete question 4, the A* search using manhattanHeuristic. Provide your solutionfor tinyMaze, mediumMaze, and bigMaze.1• Complete question 5, which solves the corners problem with a BFS agent. Provideyour solution for tinyCorners and mediumCorners.• Grad Students: Complete question 6, which creates a new heuristic for the cornersproblem. Provide your solution for tinyCorners and mediumCorners. Howdid you choose this heuristic and how well did it perform?• Complete question 7, which solves the eating all the dots problem with A* witha null heuristic. Provide your solution for testSearch and trickySearch.Grad Students: Implement foodHeuristic and provide your solutions using thisnew heuristic for testSearch and trickySearch. How did you choose this heuristicand how well does it perform?Submission RequirementsYou should email Paul (pwilken3@gmail.com) a zip file containing:• A README that provides all necessary instructions for running your programto verify the results you provide, as well as an explanation for any parts of theassignment that aren’t functioning properly. If you are able to figure out the natureof the problem you’re experiencing, this will be looked upon more favorablythan a non-functioning program with no explanation. You also need to includethe names of the students who worked on the assignment (limited to 2!) and abreakdown of the division of labor between the students. If your group has anundergrad student and a grad student, this section is important as it determinesour grading policy for the undergrad student.• The search.py and searchAgents.py files with all functions implemented as instructed.Please be sure to include informative comments!• A text document (pdf or word format preferred) that answers any prompts inthe above questions. Note that for this assignment the questions asked by theBerkeley professor can be thought of as simply thought exercises, but questionsasked in this document should be explicitly answered.