代做program、Python语言编程代写

日期：2024-03-18 09:17

Assignment 2

Introduction

This assignment includes two parts, programming assignment and writing assignment. The

deadline of this assignment is 16 Mar (11:59 PM), 2024.

Part 1: Programming assignment

Download the code for this assignment here and then unzip the archive.

As in assignment 1, this assignment uses python 3. Do not use python 2. 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. Alternatively you

may also contact your TA directly.

This assignment uses auto grading for Problems 1 and 3. For the other problems no auto

grader is provided. The auto grader is provided for your own convenience and we won’t use

it to mark your submission. Instead, all submissions will be hand graded by our TA. Make

sure that your code is readable and add appropriate comments, if necessary.

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 play against a single random Ghost (15 points)

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 autograder 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.

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. 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

You may assume the layout is always surrounded by walls and that there is at least one ghost.

For problem 1 there will be a single ghost only. Later Pacman we will have to deal with more

ghosts (‘X’, ‘Y’, ‘Z’). There will always be at least one food and there will always be

exactly one pacman.

As in assignment 1, you can choose any data structure and return it from your

read_layout_problem function. 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.

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

You may define any number of your own functions to solve the problem.

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

(base) AICourse@AICourse a2 % python p1.py -6

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 <----------

You may import anything from the Python Standard Library. Do not import packages that are

not included in Python such as numpy.

Make sure that you pass all provided test cases before moving on to the next question. Note

that we may use novel test cases for marking. You can also design your own new test cases

for testing.

Problem 2: Pacman play against a single random Ghost (10 points)

Next you will write a simple reflex agent that does not move randomly. Instead it will move

to a better position based on a simple evaluation function, designed by you, that takes a stateaction pair and returns the best action. Hint: You may consider evaluating the distance to the

closest ghost and combine somehow with the distance to the closest food.

You may reuse some of the code that you wrote in Problem 1 and implement just the

evaluation function and action selection by completing the code in the function

better_play_single_ghosts(). This function should return two values, the gameplay

as usual and the winner which should be ‘Pacman’ if Pacman wins. You can see how the

better_play_single_ghosts() is used in the main function of the script p2.py.

This time, we will have no autograder and ghosts should move randomly without a seed. You

may inspect the test cases and note that the seed is -1, which indicates that there will be no

seed. This allows us to conduct multiple trials.

(base) AICourse@AICourse a2 % python p2.py 1 10 0

test_case_id: 1

num_trials: 10

verbose: False

time: 0.09921669960021973

win % 90.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) AICourse@AICourse 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: 0.008844137191772461

win % 100.0

With a reasonable evaluation function you should be able to win half of the games easily. No

need to spend too much time on this question. You will implement expectimax soon and play

better games.

Problem 3: Random Pacman play against up to 4 random Ghost (10 points)

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: Pacman play against up to 4 random Ghost (15 points)

This problem is similar to P2 except that we have multiple ghosts as in P3. Again, no

autograding is provided and you may check the performance of your agent as follows.

(base) AICourse@AICourse a2 % python p4.py 1 100 0

test_case_id: 1

num_trials: 100

verbose: False

time: 0.3293917179107666

win % 80.0

Don’t worry too much if the performance of your agent is much worse compared to P2. This

is to be expected considering the problem difficulty has increased with multiple ghosts.

Problem 5: Minimax Pacman play against up to 4 minimax Ghosts (15 points)

In this problem, you will implement a minimax agent and minimax ghosts. Your minimax

should 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. The depth is provided as a parameter to the

function. You can test the performance of your game playing agent as follows.

(base) AICourse@AICourse a2 % python p5.py 1 3 1 0

test_case_id: 1

k: 3

num_trials: 1

verbose: False

time: 0.93696603775024414

win % 0.0

With minimax pacman and agent moves could be deterministic, depending on your

evaluation function. So a single trial would be sufficient then. However, you may add

randomness to this problem by selecting the best move randomly among equally good best

moves.

Problem 6: Expectimax Pacman play against up to 4 random Ghosts (10 points)

Finally, you will implement an expectimax agent against random ghosts. Your expectimax

should search until a depth k and then use an evaluation function to determine the value of

the state. The depth is provided as a parameter to the function. You can test the performance

of your game playing agent as follows.

(base) AICourse@AICourse a2 % python p6.py 1 2 10 0

test_case_id: 1

k: 2

num_trials: 10

verbose: False

time: 0.2952871322631836

win % 90.0

Part 2: Writing assignment

Answer the questions below and save your answers as “report.pdf”.

1. (11 points) You are in charge of scheduling for computer science classes that meet on the

same day. There are 6 classes that meet on these days and 4 professors who will be

teaching these classes. You are constrained by the fact that each professor can only teach

one class at a time.

The classes are:

⚫ Class 1 - Intro to Programming: meets from 8:00-9:00am

⚫ Class 2 - Intro to Artificial Intelligence: meets from 8:30-9:30am

⚫ Class 3 - Natural Language Processing: meets from 9:00-10:00am

⚫ Class 4 - Computer Vision: meets from 9:00-10:00am

⚫ Class 5 - Machine Learning: meets from 9:30-10:30am

⚫ Class 6 - Computer Graphics: meets from 9:30-10:30am

The professors are:

⚫ Professor A, who is available to teach Classes 3 and 6

⚫ Professor B, who is available to teach Classes 2, 3, 4, and 5

⚫ Professor C, who is available to teach Classes 3, 4, and 5

⚫ Professor D, who is available to teach Classes 1, 2, 3, and 6

(1) Formulate this problem as a CSP problem in which there is one variable per class, stating

the domains, and constraints. Constraints should be specified formally and precisely, but

may be implicit rather than explicit. (3 points)

(2) Draw the constraint graph associated with your CSP. (3 points)

(3) Show the domains of the variables after running arc-consistency on this initial graph

(after having already enforced any unary constraints). (3 points)

(4) Give all solutions to this CSP. (2 points)

2. (7 points) Consider the general less-than chain CSP below. Each of the 𝑁 variables 𝑋𝑖

has the domain {1 . . . 𝑀}. The constraints between adjacent variables 𝑋𝑖 and 𝑋𝑖+1

require

that 𝑋𝑖 < 𝑋𝑖+1

.

For now, assume 𝑁 = 𝑀 = 6.

(1) How many solutions does the CSP have? (1 point)

(2) What will the domain of 𝑋1 be after enforcing the consistency of only the arc 𝑋1 → 𝑋2?

(1 point)

(3) What will the domain of 𝑋1 be after enforcing the consistency of only the arcs 𝑋3 → 𝑋4

then 𝑋2 → 𝑋3 and then 𝑋1 → 𝑋2? (2 points)

(4) What will the domain of 𝑋1 be after fully enforcing arc consistency? (1 point)

Now consider the general case for arbitrary 𝑁 and 𝑀.

(5) What is the minimum number of arcs (big-O is ok) which must be processed by AC-3

(the algorithm which enforces arc consistency) on this graph before arc consistency is

established? (2 points)

3. (7 points) Consider the following minimax tree.

(1) What is the minimax value for the root? (2 points)

(2) Draw an “X” through any nodes which will not be visited by alpha-beta pruning,

assuming children are visited in left-to-right order. (3 points)

(3) Is there another ordering for the children of the root for which more pruning would

result? If so, state the order. (2 points)

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

Do not zip any other files. Use the *.zip file format. Name the file UID.zip, where UID is

your university number, like 3030661123.zip. Make sure that you have submitted the correct

files and named all files correctly. We will deduct up to 5% for files with incorrectly file

names.