CS7IS2: Artificial Intelligence Assignment 1
In this assignment you will implement a number of search and reinforcement learning algorithms.
This assignment is worth 20% of your overall CS7IS2 mark. Please note this is an individual
assignment. You are allowed discuss the ideas with your colleagues but not share code.
The assignment heavily relies on the Pacman project developed by UC Berkley, specified at
https://inst.eecs.berkeley.edu/~cs188/sp20/projects/, with skeleton code available for download
from individual project pages in that link.
Submissions are via Blackboard, and due by Friday March 11th 5pm.
You have an option to penalty-free submit assignment until Sunday evening (midnight) but please
note there will be no blackboard/email/TA/lecturer support for assignment or any other technical
issues past the official deadline.
Assignments submitted later than Sunday will be deducted 20% of the overall mark per day.
Assignment specification and mark breakdown
1. Part 1 – Search algorithms implementation - 25 points
2. Part 2 – MDP and RL implementation - 50 points
3. Part 3 – MDP and RL analysis - 25 points

Total = 100 points

Part 1

In this part you will implement, DFS, BFS, UCS, and A* search. Please follow the instructions on
https://inst.eecs.berkeley.edu/~cs188/sp20/project1/

You are only required to answer questions Q1 to Q4 (but feel free to do others for fun!).

You only have to edit and submit 2 files: search.py and searchAgents.py

Important: For each function you add, please in the comment in specify which problem/sub-problem
it is addressing.

Part 2

In this part you will implement MDP and Reinforcement Learning algorithms. Please follow the
instructions on https://inst.eecs.berkeley.edu/~cs188/sp20/project3/

You are only required to answer questions Q1 to Q9 (but feel free to Q10 for fun too!).

You only have to edit and submit 3 files: valueIterationAgents.py, qlearningAgents.py, analysis.py

Important: For each function you add, please in the comment in specify which problem/sub-problem
is it addressing.





Part 3

This part consists of analysing performance of variations of value-iteration and RL algorithms from
part 2. Please answer the following questions, including screenshots of your code execution and
explanations:

1. Part 2-Q1 - Run value iteration on default BookGrid for 5, 10, 15, 20, 30, 50 iterations. Show
screenshots and comment at which point did the values of states and actions converge

2. Part 2-Q1 - Run value iteration on BridgeGrid for 10 iterations and show the result. Modify
discount rate from the default 0.9 to 0.1, and run again for 10 iterations. Comment if/why
results differ.

3. Part 2 – Q4 - Run value iteration on MazeGrid for 100 iterations. Show final screenshot. Then
run asynchronous value iteration you just implemented on the same grid for 100 iterations.
Show screenshot. Explain the difference. Run it again for 1000 iterations and compare the
results.

4. Part 2 – Q6 and Q7 - Run qQlearning agent for 100 iterations on default BookGrid and
compare the Q-values to those obtained when running value iteration. Run Q-learning with a
few variations of noise, epsilon, and discount parameters. Show screenshots and explain the
behavior/influence of parameters.

5. Part 2- Q9 - Run Q-learning in Pacman, as specified in Q9 from the Pacman RL project, using
the parameters specified in the question (2000 iterations, small grid). Show screenshots of
your results (average reward, and win/loses). Now run it for 2000 iterations in the
mediumGrid in Pacman and show the results. What do you observe? Increase the number of
training iterations (and if needed modify epsilon) to achieve desired Pacman performance in
medium grid. Show screenshots of results and list which parameters/number of iterations
did you have to use.


To submit:
Please submit a single zip file named NAME_SURNAME_STUDENTID_assignment1.zip containing:
1. Modified .py files from parts 1 and 2
2. Pdf of a self-assessment marking sheet for parts 1 and 2 (instructions below)
3. Pdf of your answers to part 3

Self-assessment instructions
You are also asked to perform self-assessment of your implementation. Autograding scripts are
provided alongside each of the sections.
Run the autograder.py on your submission files for both parts, and for each sub-question report the
marks achieved and observe where did you lose the marks from the full marks available.
Autograder marks
Question Mark Reason marks lost, if any
1
2
3
4
Total marks part 1

Question Mark Reason marks lost, if any
1
2
3
4
5
6
7
8
9
Total marks part 2

The discussion board on blackboard is open if you’d like to discuss the assignment approaches
with your classmates, or ask me or the course TA a question. Again a reminder, that discussing is
fine but sharing code is not. Please refer to college plagiarism policy for the definitions and
consequences of plagiarism.