Artificial Intelligence ( Computer Science, Python) assignment Help

Homework 2 (10% of total course weight) – Multiagent Search

California State University San Bernardino, School of Computer Science and Engineering (CSE)

Date of Issue: February 24, 2020, Date of submission: March 10, 2021 – 11:59 pm (PST)

Module: CSE 5120 Introduction to Artificial Intelligence

Assessment brief: The code and resources provided in this homework are drawn from UC Berkeley which are part of their recent offering. Thanks, and credit to the authors (particularly Dan Klein, Pieter Abbeel, John DeNero, and others) at UC Berkeley for making these projects available to the public.

Pacman lives in a shiny blue world of twisting corridors and tasty round treats. Navigating this world efficiently will be Pacman’s first step in mastering his domain.

The code for this project consists of several Python files, some of which you will need to read and understand in order to complete the assignment, and some of which you can ignore. You can download all the code and supporting files as a zip folder from homework 2 link given on Blackboard (multiagent.zip).

Your homework is based on two parts as given below:

1. Code implemented for multiagent algorithms in given multiAgents.py file (in specific sections as indicated in detail below)

2. A brief report on what you did for each algorithm (i.e., how you implemented with screenshots from autograder script given in the folder)

File Name	Description
multiAgents.py	Where all of your multi-agent search agents will reside.
pacman.py	The main file that runs Pacman games. This file describes a Pacman GameState type, which you use in this project.
game.py	The logic behind how the Pacman world works. This file describes several supporting types like AgentState, Agent, Direction, and Grid.
util.py	Useful data structures for implementing search algorithms.

After downloading the code, unzipping it, and changing to the directory, you should be able to play a game of Pacman by running the following command.

python pacman.py

pacman.py supports a number of options (e.g. –layout or -l). You can see the list of all options and their default values via python pacman.py -h.

You can use Spyder (installed through Anaconda from week 1 Thursday’s lecture) or other IDE for this work.

Files to Edit and Submit: You will need to edit and submit (multiAgents.py) file to implement your algorithms. Once you have completed the homework, you are welcome to run automated tests using an autograder.py given in the folder before you submit them for accuracy. You do not need to submit autograder.py file in your code submission but will need to test your algorithms with autograder.py to copy screenshots in your report. Please do not change the other files in this distribution or submit any of the original files other than these files.

Academic Dishonesty: Your code will be checked against other submissions in the class for logical redundancy. If you copy someone else’s code and submit it with minor changes, they will be detected easily, so please do not try that and submit your own work only. In case of cheating, the University’s academic policies on cheating and dishonesty will strictly apply which may result from the deduction in your grade to expulsion.

Getting Help: If you are having difficulty in implementing the algorithms from the pseudocodes provided in this homework, contact the course staff for help. Office hours and Slack are there for your support. If you are not able to attend office hours, then please inform your instructor to arrange for additional time. The intent is to make these projects rewarding and instructional, not frustrating and demoralizing. You can either complete this homework on your own or discuss the problem and collaborate with another member of the class (or different section). Please clearly acknowledge and mention your group member in your homework report submission who you will collaborate with in this homework. Your report and program (search.py file) will be separately submitted by yourself on Blackboard irrespective of your collaboration with your group member. Group discussions are encouraged but copying of programs is NOT recommended. Programming based on your own skills is encouraged.

Tasks for homework 2

1. Minimax search (3%)

Write an adversarial agent in the provided MinimaxAgent class in multiAgents.py. Your minimax agent should work with any number of ghosts, so your algorithm should be a more generalized version of the standard Minimax algorithm that we have studied in the class. Your minimax tree will have multiple min layers (one for each ghost) for each max layer. Your code should also be able to expand the tree to an arbitrary depth which can be accessed from self.depth and score your nodes with the supplied self.evaluationFunction. Make sure your Minimax program refers to these variables since these are populated in response to the command line options.

Important: A single search ply is considered to be one Pacman move and all the ghosts’ responses, so depth 2 search will involve Pacman and each ghost moving two times. For further reading and understanding of Minimax (including alpha-beta pruning), please see this short video tutorial with pseudo code.

Hints and Observations

· Hint: Implement the algorithm recursively using helper function(s).

· The correct implementation of minimax will lead to Pacman losing the game in some tests. This is not a problem: as it is correct behavior, it will pass the tests.

· The evaluation function for the Pacman test in this part is implemented for you (self.evaluationFunction). You should not change this function but recognize that now we are evaluating states rather than actions, as compared to the reflex agent. Look-ahead agents evaluate future states whereas reflex agents evaluate actions from the current state.

· Pacman is always agent 0, and the agents move (take turns) in order of increasing agent index.

· All states in minimax should be GameStates, either passed in to getAction or generated via GameState.generateSuccessor. In this project, you will not be abstracting to simplified states.

Evaluation: Your code will be checked to determine whether it explores the correct number of game states. This is the only reliable way to detect some very subtle bugs in implementations of minimax. As a result, the autograder will be very picky about how many times you call GameState.generateSuccessor. If you call it any more or less than necessary, the autograder will complain. Please note that q1 relates to ReflexAgent which is not a part of this homework and can be skipped. We will start with q2 in this homework. To test and debug your code, run

python autograder.py -q q2

This will show what your algorithm does on a number of small trees, as well as a pacman game. To run it without graphics, use:

python autograder.py -q q2 –no-graphics

Figure 1: Pseudo-code for the implementation of Minimax algorithm. Please use this as a guide only. You will still need to carefully read multiAgents.py file for helper functions given in the comments and think/reason about the implementation of Minimax in Pacman scenario.

Figure 2: Pseudo-code for general-purpose implementation of Minimax algorithm. Please use this as a guide only. You will still need to carefully read multiAgents.py file for helper functions given in the comments and think/reason about the implementation of Minimax in Pacman scenario.

2. Alpha-beta pruning (2%)

write an adversarial agent in the provided AlphaBetaAgent class in multiAgents.py to more efficiently explore the minimax tree. Your agent should work with any number of ghosts, so your algorithm should be a generalized version of the standard Alpha-Beta Pruning algorithm. The AlphaBetaAgent minimax values should be identical to the MinimaxAgent minimax values, although the actions it selects can vary because of different tie-breaking behavior.

Note: The correct implementation of alpha-beta pruning will lead to Pacman losing some of the tests. This is not a problem: as it is correct behavior, it will pass the tests.

Evaluation: Your code will be checked to determine whether it explores the correct number of game states. Therefore, it is important that you perform alpha-beta pruning without reordering children. In other words, successor states should always be processed in the order returned by GameState.getLegalActions. Again, do not call GameState.generateSuccessor more than necessary. Additionally, in order to match the set of states explored by the autograder, you must not prune on equality: that is, stop generating children for a max (min) node only if a child’s value is strictly greater than (less than) β (α). To test and debug your code, run

python autograder.py -q q3

This will show what your algorithm does on a number of small trees, as well as a pacman game. To run it without graphics, use:

python autograder.py -q q3 –no-graphics

Figure 3: Pseudo-code for the implementation of the algorithm you should implement for this question. Please use this as a guide only. You will still need to carefully read multiAgents.py file for helper functions given in the comments and think/reason about the implementation of Minimax in Pacman scenario.

3. Expectimax Search (2%)

Implement the ExpectimaxAgent, which is useful for modeling probabilistic behavior of agents who may make suboptimal choices. As with the search and constraint satisfaction problems covered in CSE 5120, the impressive feature of this algorithm is its general applicability.

Note: The correct implementation of expectimax will lead to Pacman losing some of the tests. This is not a problem: as it is correct behavior, it will pass the tests.

Evaluation: You can debug your implementation on small the game trees using the command:

python autograder.py -q q4

Debugging on these small and manageable test cases is recommended and will help you to find bugs quickly. Once your algorithm is working on small trees, you can observe its success in Pacman. Random ghosts are not optimal minimax agents, and so modeling them with minimax search may not be appropriate. ExpectimaxAgent, does not take the min over all ghost actions, but the expectation according to the agent’s model of how the ghosts act. To simplify your code, assume you will only be running against an adversary which chooses amongst their getLegalActions uniformly at random (read about uniform distribution for further understanding). To see how the ExpectimaxAgent behaves in Pacman, run:

python pacman.py -p ExpectimaxAgent -l minimaxClassic -a depth=3

You should now observe a more cavalier approach in close quarters with ghosts. In particular, if Pacman perceives that he could be trapped but might escape to grab a few more pieces of food, he will at least try. Investigate the results of these two scenarios:

python pacman.py -p AlphaBetaAgent -l trappedClassic -a depth=3 -q -n 10

python pacman.py -p ExpectimaxAgent -l trappedClassic -a depth=3 -q -n 10

You should find that your ExpectimaxAgent wins about half the time, while your AlphaBetaAgent always loses. Make sure you understand why the behavior here differs from the minimax case.

4. Constraint satisfaction problems (3%)

1. (1.5%) Consider the problem of placing k knights on an n×n chess board such that no two knights are attacking each other, where k is given and k ≤ n2.

· Choose a CSP formulation. What are the variables in your formulation?

· What are the possible values of each variable in your formulation?

· What sets of variables are constrained, and how?

2. (1.5%) Class scheduling (items to answer are at the end in green font)

You are given a problem of class scheduling for the computer science department at CSUSB. The class timings are Tuesdays, Thursdays, and Fridays. There are 5 different classes on these given days and 3 professors who are qualified for teaching these classes.

Problem constraint: Each professor can teach only one class at a time.

Classes:

C1 – CSE 5120 Introduction to Artificial Intelligence: Time: 1:00 – 2:15pm

C2 – CSE 4600 Operating Systems: Time: 9:00 – 10:15am

C3 – CSE 4550 Software Engineering: Time: 10:30-11:45am

C4 – CSE 5720 Database Systems: Time: 10:30 – 11:45am

C5 – CSE 5160 Machine Learning: Time: 2:30 – 3:45pm

Professors:

Professor A: Qualified to teach Classes 1, 2, and 5.

Professor B: Qualified to teach Classes 3, 4, and 5.

Professor C: Qualified to teach Classes 1, 3, and 4.

1. Formulate this problem as a CSP where there is one variable per class, reporting the domains and constraints (e.g., for each class, the entry in the table should be <class number (e.g., C1)> <Domains (unary constraints)>). Also, list binary constraints on the classes . Your constraints should be specified formally which can be implicit rather than explicit

2. Draw the constraint graph for your problem in item 1

3. Make sure your CSP looks nearly tree-structure. Provide a one paragraph description of why the solution to CSP via tree structured CSPs is preferred. Review lecture slides and videos for help.

Homework 2 (10%)

CSE 5120 (Section ##) – Introduction to Artificial Intelligence – Spring 2021

Submitted to

Department of Computer Science and Engineering California State University, San Bernardino, California

Student name (CSUSB ID)

(Your collaborator in this homework (if any))

Date: Month Day, Year

Email:

· Your email

· Your collaborator’s email (if you collaborated with any)

Report

Brief description of your work here acknowledging your collaboration with your class fellow (or a friend from other CSE 5120 section), and the capacity at which he/she collaborated with you, followed by the algorithms you implemented.

1. Minimax algorithm

Your brief explanation of the problem, your code solution, and any documentation with screenshots of your code Evaluation (results from autograder.py)

2. Alpha-beta pruning

Your brief explanation of the problem, your code solution, and any documentation with screenshots of your code Evaluation (results from autograder.py)

3. Expectimax Search

Your brief explanation of the problem, your code solution, and any documentation with screenshots of your code Evaluation (results from autograder.py)

4. Constraint satisfaction problems

Your explanation and drawings, wherever necessary, numbered according to how the questions are defined in the questions.

α-βImplementationdef min-value(state, α, β):initialize v = +∞for each successor of state:v = min(v, value(successor, α, β))if v ≤ αreturn vβ = min(β, v)return vdef max-value(state, α, β):initialize v = -∞for each successor of state:v = max(v, value(successor, α, β))ifv ≥ βreturn vα= max(α, v)return vα: MAX’s best option on path to rootβ:MIN’s best option on path to root

Minimax Implementationdef value(state):if the state is a terminal state: return the state’s utilityif the next agent is MAX: return max-value(state)if the next agent is MIN: return min-value(state)def min-value(state):initialize v = +∞for each successor of state:v = min(v, value(successor))return vdef max-value(state):initialize v = -∞for each successor of state:v = max(v, value(successor))return v

Artificial Intelligence ( Computer Science, Python) assignment Help