Description
You are going to do the 8 programming questions about search given in the website. You are only required to change search.py and searchAgents.py. If you have any issues with other parts of the code let your instructor or TA know ASAP, even if you manage to solve your problem. Use the data structures in util.py for the autograder to work properly. If the you think you have the right answer but the autograder is not giving you any points, try to run it on individual questions (look at P0 for details on how to use the autograder.py).
1
Hints
• We understand that having too many files to go through might be troublesome, however keep in mind that you do not need to go over all the files. Read the P1:Search documentation in the Berkeley Website and the comment sections of the relevant files/functions that you are going to work on. If you start worrying about implementation details of Pacman, you will get lost and lose track of how to handle the assignment requirements.
• Always read the comment sections of the given code before starting your implementation. These comments are very useful and they will save you precious time later on.
Part 2: Report
This part includes answering the following questions based on your programs’ output on the given pacman tests. Look specfically at bigMaze and the openMaze for stark comparisons.
You are expected to answer the questions concisely. Five sentences is more than enough for most of them. Limit yourself to 200 words. It is okay if you over-generalize, as long as your direction is clear and correct. Note that some answers are already in the provided link to the Berkeley site.
Create a PDF file named report.pdf containing your answers for submission. Write your name and your number on the report as well!
Written Q1:
What are some differences between DFS and BFS in terms of path cost and number of expanded nodes? When and why would you prefer BFS over DFS? When and why would you prefer DFS over BFS?
Written Q2:
What are some differences between UCS and A* in terms of path cost and number of expanded nodes? When and why would you prefer UCS over A*? When and why would you prefer A* over UCS?
Written Q3:
Comment on your choice of state in the finding all the corners problem. Why does it allow you to solve the problem?
Written Q4:
Comment on your choice of heuristic in the finding all the corners problem.. Why did you settle on that heuristic? Why is it admissible and consistent?
Written Q5:
Comment on your choice of heuristic in the eating all the dots problem. Why did you settle on that heuristic? Why is it admissible and consistent?
Written Q6:
What are some practical differences between a consistent and an inadmissible heuristic, in terms of path cost and number of expanded nodes? When and why would you prefer an inadmissible heuristic over a consistent one? When and why would you prefer a consistent heuristic over an inadmissible one?
