COMP3270 Assignment 2 Solution

Introduction

• Download the code for this assignment and then unzip the archive.
• This assignment uses Python 3. Do not use python 2.
o We have tested the assignment with Python 3.11.4.
• You can work on the assignment using your favourite python editor. We recommend VSCode.
• Post any questions or issues with this assignment to our discussion forum.


Important: Ensure that your code does not run too long. More than 5 min per test case (assuming at most 10 trials for each testcase) on our grading machine (M1 Mac) would be considered too long. For Problems 5 and 6 in particular it is required to search to reasonable depth which is only possible with a state representation that enables O(1) time queries. Problems 2, 4, 5 and 6 have a verbose option which is passed as a parameter into the search function. Only perform output computations when verbose is True to save valuable compute.

Problem 1: Random Pacman vs. Single Random Ghost (Weight: 20%)

In this part of the assignment you are going to implement
- a parser to read a pacman layout file in the file parse.py, and
- a game of Pacman where Pacman and ghost select moves randomly in the file p1.py.

Both these python files have already been created for. Do not change anything that has already been implemented. Our auto grader relies on the existing code.

Start by implementing the read_layout_problem() in the file parse.py.
def read_layout_problem(file_path):
#Your p1 code here problem = '' return problem

You can ‘test’ your code with the first layout as follows. This will simple output whatever you return from the read_layout_problem() function.

python parse.py 1 1

This will supply the test_cases/p1/1.prob file as an argument to the function. The file has the following Pacman layout.

seed: 8
%%%%
% W%
% %
% %
% .%
%P.%
%%%%

The first line is a random seed which will be used to initialize python’s random number generator via the random.seed() function. This ensures that python generates a fixed sequence of random values. A seed value of -1 will result in no seed being set. More on this later. The rest of the file is the Pacman layout that you will have to parse. You can expect the following characters in the file.

'%': Wall
'W': Ghost
'P': Pacman
'.': Food
' ': empty Square


As in assignment 1, you can choose any data structure and return it from your read_layout_problem function. We recommend to design the data structure such that a location query of various entities in the world can be done in O(1) time, i.e., in constant time independent of world size.

Once you are done with the parsing you can move on to the second part of this problem and implement the random_play_single_ghost() function in the file p1.py.

A correct implementation will return the following string for the first test case.

seed: 8 0
%%%%
% W%
% %
% %
% .%
%P.%
%%%%
1: P moving E
%%%%
% W%

% %
% %
% .%
% P% %%%% score: 9 2: W moving W
%%%%
%W %
% %
% %
% .%
% P% %%%% score: 9 3: P moving W
%%%%
%W %
% %
% %
% .%
%P % %%%% score: 8 4: W moving E
%%%%
% W%
% %
% %
% .%
%P % %%%% score: 8 5: P moving E
%%%%
% W%
% %
% %
% .%
% P% %%%% score: 7 6: W moving S
%%%%
% %
% W%
% %
% .%
% P% %%%% score: 7 7: P moving N
%%%%
% %
% W%
% %
% P%
% % %%%% score: 516 WIN: Pacman

As you can see, Pacman and the Ghost make moves alternatively. Pacman starts by making a move east. This is determined using the random.choice() function on the available moves to Pacman. In this case for the start state Pacman can move East (E) for the food or North(N) for the empty square. Pacman (P) moves east. Let’s reproduce that decision to understand the sequence of moves generated here.

(base) scdirk@Dirks-Air a2 % python
>>> import random
>>> random.seed(8, version=1)
>>> random.choice(('E', 'N')) 'E'

Next, the Ghost (W) moves West (W). The available actions to the ghost are W and S.

(base) scdirk@Dirks-Air a2 % python
>>> import random
>>> random.seed(8, version=1)
>>> random.choice(('E', 'N'))
'E'
>>> random.choice(('S', 'W')) 'W'

Important: You must ensure that the parameter to the random.choice() function is sorted alphabetically. Otherwise you will not be able to reproduce the exact result and you won’t be able to pass the auto grader.


seed: 42

0
%%%%
%.W%
% %
% %
% .%
%P.%
%%%%
1: P moving E
%%%%
%.W%
% %
% %
% .%
% P% %%%% score: 9 2: W moving S
%%%%
%. %
% W%
% %
% .%
% P% %%%% score: 9 3: P moving W
%%%%
%. %
% W%
% %
% .%
%P % %%%% score: 8 4: W moving N
%%%%
%.W%
% %
% %
% .%
%P % %%%% score: 8 5: P moving E
%%%%
%.W%
% %

% %
% .%
% P% %%%% score: 7 6: W moving S
%%%%
%. %
% W%
% %
% .%
% P% %%%% score: 7 7: P moving N
%%%%
%. %
% W%
% %
% P%
% % %%%% score: 16 8: W moving W
%%%%
%. %
%W %
% %
% P%
% % %%%% score: 16 9: P moving W
%%%%
%. %
%W %
% %
%P %
% % %%%% score: 15 10: W moving S
%%%%
%. %
% %
%W %
%P %
% %

%%%% score: 15 11: P moving E
%%%%
%. %
% %
%W %
% P%
% % %%%% score: 14 12: W moving S
%%%%
%. %
% %
% %
%WP%
% % %%%% score: 14 13: P moving S
%%%%
%. %
% %
% %
%W %
% P% %%%% score: 13 14: W moving E
%%%%
%. %
% %
% %
% W%
% P% %%%% score: 13 15: P moving N
%%%%
%. %
% %
% %
% W%
% % %%%% score: -488 WIN: Ghost

Scoring is done as follows.

EAT_FOOD_SCORE = 10
PACMAN_EATEN_SCORE = -500
PACMAN_WIN_SCORE = 500
PACMAN_MOVING_SCORE = -1

Once you are done you can check if you pass all the test cases for Problem 1.

(base) scdirk@Dirks-Air a2 % python p1.py
Grading Problem 1 :
----------> Test case 1 PASSED <----------
----------> Test case 2 PASSED <----------
----------> Test case 3 PASSED <----------
----------> Test case 4 PASSED <----------
----------> Test case 5 PASSED <----------
----------> Test case 6 PASSED <----------


Problem 2: Reflex Pacman vs. Single Random Ghost (Weight: 20%)


In our implementation we simply evaluating the distance to the closest ghost and combine with the distance to the closest food to rank the best move. Do not run minimax/expectimax or any other more advanced algorithms here. In this problem you are supposed to implement a simple reflex agent.




(base) scdirk@Dirks-Air a2 % python p2.py 1 10 0
test_case_id: 1 num_trials: 10 verbose: False time: ?
win % 100.0

The three parameters control the test case id, number of trials and a verbose option that will output the actual gameplay if it is set to 1 instead of 0.

base) scdirk@Dirks-Air a2 % python p2.py 1 1 1
test_case_id: 1 num_trials: 1 verbose: True seed: -1 0
%%%%%
% . %
%.W.%
% . %
%. .%
% %
% .%
% %
%P .%
%%%%%
…
123: P moving W
%%%%%
% %
% %
% %
%P %
% %
% %
% %
%W % %%%%% score: 518 WIN: Pacman time: ?
win % 100.0

With a reasonable evaluation function you should be able to win some of the games. It is not necessary to achieve a high win rate for this question. You will implement expectimax soon and play better games.

For your reference, here is the performance (= win rate in % after playing 100 games) of a random agent, the min acceptable win rate of your agent and our reflex agent. You will have to check this manually because there is no auto grader for this question.

Testcase Random Agent Min acceptable Reflex Agent Our Reflex Agent
1.prob 2 > 50 100
2.prob 66 > 80 100
3.prob 20 > 60 97
4.prob 0 > 50 100
5.prob 0 > 50 100

Win rates are quite high because a reflex that is very careful and plays long games will be able to win most of the time. In our implementation we don’t look at scores. To avoid long games and obtain a high score it would be desirable to win as fast as possible.

Problem 3: Random Pacman vs. 4 Random Ghost (Weight: 10%)

In this problem, Pacman is up against up to 4 ghosts . This problem is similar to problem 1 except that you will implement a game against multiple ghosts.

Ghosts cannot move on top of each other. If a Ghost is stuck no move will be done. Pacman will start followed by W, X, Y, Z. Note that the last three ghosts are optional. So the following combinations are possible:
● 1 Ghost: W
● 2 Ghosts: W, X
● 3 Ghosts: W, X, Y
● 4 Ghosts: W, X, Y, Z

Here is a game with 2 ghosts.

seed: 42 0
%%%%
%.X%
%W %
%P %
%%%%
1: P moving E
%%%%
%.X%
%W %
% P% %%%% score: -1 2: W moving E
%%%%
%.X%
% W%
% P% %%%% score: -1 3: X moving W
%%%%
%X %
% W%
% P% %%%% score: -1 4: P moving N
%%%%
%X %
% W%
% % %%%% score: -502 WIN: Ghost

Note that ghosts move in alphabetical order, i.e., W first followed by X etc.

Problem 4: Reflex Pacman vs. 4 Random Ghost (Weight: 20%)


(base) scdirk@Dirks-Air a2 % python p4.py 1 100 0 test_case_id: 1 num_trials: 100 verbose: False time: ? win % ?

Don’t worry too much if the performance of your agent is worse compared to P2. This is to be expected considering the problem difficulty has increased with multiple ghosts.

For your reference, here is the performance (= win rate in % after playing 100 games) of a random agent, the min acceptable win rate of your agent and our reflex agent. You will have to check this manually because there is no auto grader for this question.

Testcase Random Agent Min acceptable Reflex Agent Our Reflex Agent
1.prob 0 > 30 49
2.prob 22 > 50 69
3.prob 1 > 10 27
4.prob 0 > 70 98
5.prob 2 > 10 24
6.prob 1 > 20 42
7.prob 5 > 10 28
8.prob 0 > 60 82
9.prob 0 > 50 74

As expected, the win rates are much lower compared to P2.

Problem 5: Expectimax Pacman vs. Single Random Ghost (Weight: 15%)

In this problem, you will implement an Expectimax agent. Hopefully, Pacman will be able to outsmart a single random Ghost on any map. To make this happen you will have to carefully design your model with an evaluation function and an appropriate depth limit. So your Expectimax search will search until a ply depth k (i.e., k moves by everyone) and then use an evaluation function to determine the value of the state at that depth.


For this assignment, we only care about win rate and not the score. Therefore, you can change how games are scored internally or modify your evaluation function to max the win rate.

The parameter k is provided as an argument to the function. You can test the performance of your game playing agent as follows.

(base) scdirk@Dirks-Air a2 % python p5.py 1 3 10 0
test_case_id: 1 k: 3 num_trials: 10 verbose: False time: ? win % ?

Problem 6: Expectimax Pacman vs. 4 Random Ghost (Weight: 15%)

In this problem, you will implement an Expectimax agent again. This time against up to 4 random ghosts. Test cases are the same as in P4. Are you able to perform better?

A good performance will strongly depend on your evaluation function and the efficiency (time and space) of your state representation. You should describe your design choices and the performance of your agent in detail in the short written report. More details below.

Congratulations you have completed this assignment.

Short Written Report


In the report, you should explain the various design choices that you have made regarding state representation and evaluation functions etc. What was the impact of your design choices?

Finally, write down the approximate number of hours you have spent per questions for this assignment.

Submission

To submit your assignment to Moodle, *.zip the following files ONLY:

- p1.py
- p2.py
- p3.py
- p4.py
- p5.py
- p6.py
- parse.py
- report.pdf