CS 205 AI Project - Winter 2024
Pac-Man Automated Search
Summary
Learning Goals/Objective
In this project, your goals are to learn how to implement some of the searches we have learned in
class in a fun game. You will be implementing Depth First Search, Breadth First Search, A* search,
Uniform Cost Search, a greedy search, and various heuristics. You will be able to see firsthand
what each search is good at and better understand where they would be used.
You MUST work in a group of 3 people (not up to 3 people, exactly 3 people) - Only 1 group
would have an issue finding a third member due to the size of the class and they will have an
exemption. All submissions for your group will be group-based. So appoint a person who will be
responsible for maintaining the deliverables.
Due dates
Deliverables are due each week, final report is due in Week 7.
Implementation
Where to begin
Visit the main website for this project (http://ai.berkeley.edu/search.html) and download the main
zip file (Berkeley Pac-Man zip). After downloading, unzip the file in the directory of your choice.
You can play the game manually by using the command python pacman.py from your terminal
(if your computer is set up to use Python 3 as default, you must type python2 pacman.py
instead).
After unzipping you will notice a lot of files, but there are only two main files you will be modifying
throughout the entire project: search.py and searchAgents.py. The website has a list of files you
might want to look into and a list of files you can ignore.
1
Procedure
01. Week 5 (Due Thursday, February 8, by midnight)
a. Run through the tutorial and familiarize yourself with the game
i. After downloading and playing around with Pac-Man, run through the short
tutorial section (the Welcome to Pacman section) on the UCB website. You
will see how the AI can automatically make Pac-Man move and go towards
his targets.
b. Implement Questions **2
i. For the first week, you will be implementing DFS and BFS to help Pac-Man
find a fixed piece of food. All of the search algorithms you will implement
after this will be similar to DFS and BFS, so make sure to implement them
correctly and the rest will come easily!
ii. Make sure your code returns a solution for the examples in question 1 and
question 2 on the website.
iii. Run python autograder.py --q q1 and python autograder.py
--q q2
c. Implement Questions 3-4
i.
ii. Make sure your code returns a solution for questions 3 and 4 on the
website.
iii. Run python autograder.py --q q3 and python autograder.py
--q q4
d. Answer the auxiliary questions from Question 1 on the UCB
website
i. Does Pacman visit all the explored nodes?
ii. Is DFS a least-cost solution? Explain your answer.
02.Week 6 (Due Thursday, February 15, by midnight)
a. Implement Question 5
i. Use BFS search to find all the corners of the map
ii. Make sure your code runs for tinyCorners and mediumCorners in question
5 on the website
iii. Run python autograder.py --q q5
b. Implement Question 6
i. Implement a non-trivial heuristic for your A* search to find the corners of
the map
2
ii. Make sure your code runs for mediumCorners instructions in question 6 on
the website
iii. Run python autograder.py --q q6
03.Week 7 (Due Thursday, February 22, by midnight)
a. Implement Questions 7-8
i. Use A* search to eat all the dots on the map, and implement a suboptimal
greedy search to eat all the dots
ii. Make sure your code runs for the searches in questions 7 and 8 on the
website
iii. Run python autograder.py --q q7 and python autograder.py
--q q8
b. Write the final report
i. In your report, describe.
ii. Your final report must be a maximum of 2 pages. Any more than 2 pages
and you will lose points!
Deliverables
Upload deliverables via Google Drive. You will be graded on a mix of three things: the README
file, if your code runs on all the instructions for the questions, and the autograder grade for that
question. Think of your README as a research log — nice documentation of your work and
efforts for each week, but in a way that will be easy for us to scan and interpret. That is, make it
concise, informative, detailed, and organized. Keep it concise, which means short yet dense and
informative.
Follow these instructions carefully! You will lose points if your Google Drive does not have the
correct format:
● Create a Google Drive folder for PacMan.
● Add a README with only your team members' names in the root folder.
● Create 3 sub-folders in PacMan called "Week 5" ... up to "Week 7."
● Fill the project sign-up sheet with the names of group members and add the link to your
project Google Drive (Link here)
● Upload the necessary files below in the sub-folder.
○ search.py
○ searchAgents.py
● Summarize your progress and learnings in a README in a paragraph or two for each
folder (separate README files for each week).
3
● Add screenshots as appropriate (nicely, don't make the file too long).
● Give full read/write access on your directory to dadje001@ucr.edu to allow for automated
downloads for grading.
● Make sure to submit your files to Google Drive by 11:59 p.m. on each due date.
Recap
1. Due Week 5
a. Upload search.py (with your DFS and BFS code implemented)
b. Create/upload screenshots of your successful runs on the commands on the
website for questions 1 and 2, add to README
c. Answer the questions in "Question 1" (label it clearly as such) in your README for
that week.
d. Upload search.py (with your UCS and A* code implemented)
e. Upload screenshots of your successful runs on the commands on the website for
questions 3 and 4, add to README
3. Due Week 6
a. Upload searchAgents.py with the CornersProblem implemented
b. Upload screenshots of your successful runs on the commands on the website in
question 5, add to README
c. Upload searchAgents.py with your cornersHeuristic implemented
d. Upload screenshots of your successful runs on the commands on the website in
question 6, add to README
5. Due Week 7
a. Upload search.py file.
b. Upload searchAgents.py with your foodHeuristic and findPathToClosestDot
implemented
c. Upload screenshots of your successful runs on the commands on the website in
questions 7 and 8, add to README
d. Upload your maximum 2-page final report in the ROOT ("PacMan") folder.
4
Materials & Resources
The base project will be run in Python 2. If you choose to run it with Python 3 you are responsible
for changing the project files to make it work with Python 3. Let us know at the top of the readme
if you’re using Python 3. You are more than welcome to do so.
a. Project Materials:
a. Main Project Website: http://ai.berkeley.edu/search.html
b. Resources:
a. Slides (Student Resources on Google Drive)
b. Book (AI a Modern Approach)
c. Python 2 documentation: https://docs.python.org/2.7
Assessment
You are responsible for uploading the required materials to the Google Drive folder.
The Final Report: Summarize in a single report all you have accomplished and learned as a
team. Highlight in the report the activities you found most challenging and why, the activities you
found most interesting and why, or the activities you simply hated and why. Tell us what you
thought! Discuss the team dynamic, were there challenges you had to overcome? Take a moment
to describe what you are most proud of accomplishing (and why). Show off to us! You only have
two pages, so use them wisely. We don't want to read fluff and platitudes or pandering. We want
a serious analysis and debriefing of your project work.
Not sure how to write a good project report? Google it! Ten times. You can figure it out.
Extra points for creativity. For example: Maybe you want to make a video? Maybe you want to
create a newspaper print, showcasing your work. You could create a new game that makes us
search for the answers to your project. Who knows! Impress us—extra points for creativity.
5
What your Google Drive should look like:
Root of your PacMan Directory:
Week 5 sub-folder:
6
Week 6 sub-folder:
Week 7 sub-folder:
如有需要，請加QQ：99515681 或WX：codehelp