Homework 2 10 Of Total Course Weight Multiagent Searchcalifornia ✓ Solved

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

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

Paper for above instructions

Introduction

In this report, I document the implementation of three multi-agent search algorithms—Minimax, Alpha-Beta Pruning, and Expectimax—within the context of the classic game framework of Pacman. This project is part of an assignment for the course "CSE 5120: Introduction to Artificial Intelligence" at California State University, San Bernardino. Collaborating with a classmate, I gained insights into the implementation of these algorithms while adhering to academic integrity guidelines set by the university.

1. Minimax Algorithm

Problem Overview

The Minimax algorithm is a decision-making algorithm used for adversarial games, where agents face opponents. In the context of Pacman, the goal is to maximize the Pacman's score while minimizing the ghosts' scores. The Minimax approach involves creating a game tree where each node represents a state of the game, and the values of the nodes reflect the utility for Pacman (maximizing player) and the ghosts (minimizing players).

Code Solution

The implementation in `multiAgents.py` involves creating a recursive function called `minimax` that evaluates possible moves to a given depth defined by the parameter `self.depth`.
```python
def minimax(self, gameState, depth, agentIndex):
if depth == 0 or gameState.isWin() or gameState.isLose():
return self.evaluationFunction(gameState)
legalActions = gameState.getLegalActions(agentIndex)
if agentIndex == 0: # Maximizing agent (Pacman)
value = float('-inf')
for action in legalActions:
successor = gameState.generateSuccessor(agentIndex, action)
value = max(value, self.minimax(successor, depth, 1))
return value
else: # Minimizing agent (Ghosts)
value = float('inf')
for action in legalActions:
successor = gameState.generateSuccessor(agentIndex, action)
if agentIndex == gameState.getNumAgents() - 1: # Last ghost, decrease depth
value = min(value, self.minimax(successor, depth - 1, 0))
else:
value = min(value, self.minimax(successor, depth, agentIndex + 1))
return value
def getAction(self, gameState):
legalActions = gameState.getLegalActions(0)
bestValue = float('-inf')
bestAction = None
for action in legalActions:
successor = gameState.generateSuccessor(0, action)
value = self.minimax(successor, self.depth, 1)
if value > bestValue:
bestValue = value
bestAction = action
return bestAction
```

Evaluation

To test the implementation, I utilized the `autograder.py` script, invoking the command:
```bash
python autograder.py -q q2
```
This command provided a series of tests ensuring that the Minimax algorithm explored the correct number of game states, focusing on the quality of state evaluations.

2. Alpha-Beta Pruning

Problem Overview

Alpha-Beta pruning optimizes the standard Minimax algorithm by eliminating the need to explore certain branches of the game tree. The goal is to reduce the number of nodes evaluated while still achieving the same outcome as the Minimax strategy.

Code Solution

The implementation of Alpha-Beta pruning in `multiAgents.py` involves maintaining two variables, alpha and beta, during the recursive search. The code is as follows:
```python
def alpha_beta(self, gameState, depth, agentIndex, alpha, beta):
if depth == 0 or gameState.isWin() or gameState.isLose():
return self.evaluationFunction(gameState)
legalActions = gameState.getLegalActions(agentIndex)
if agentIndex == 0: # Maximizing agent (Pacman)
value = float('-inf')
for action in legalActions:
successor = gameState.generateSuccessor(agentIndex, action)
value = max(value, self.alpha_beta(successor, depth, 1, alpha, beta))
alpha = max(alpha, value)
if value >= beta:
break # Prune
return value
else: # Minimizing agent (Ghosts)
value = float('inf')
for action in legalActions:
successor = gameState.generateSuccessor(agentIndex, action)
if agentIndex == gameState.getNumAgents() - 1: # Last ghost
value = min(value, self.alpha_beta(successor, depth - 1, 0, alpha, beta))
else:
value = min(value, self.alpha_beta(successor, depth, agentIndex + 1, alpha, beta))
beta = min(beta, value)
if value <= alpha:
break # Prune
return value
def getAction(self, gameState):
bestValue = float('-inf')
bestAction = None
alpha = float('-inf')
beta = float('inf')
for action in gameState.getLegalActions(0):
successor = gameState.generateSuccessor(0, action)
value = self.alpha_beta(successor, self.depth, 1, alpha, beta)
if value > bestValue:
bestValue = value
bestAction = action
return bestAction
```

Evaluation

Similar to the Minimax algorithm, I tested my implementation using the autograder:
```bash
python autograder.py -q q3
```
This step ensured that the pruning reduced the search space effectively while not affecting the correctness of the decisions made.

3. Expectimax Search

Problem Overview

Expectimax is used when the actions of an agent (like ghosts in Pacman) are modeled probabilistically rather than deterministically. In this case, each ghost selects its action uniformly at random.

Code Solution

The implementation of Expectimax follows a similar structure to Minimax but computes the expected value for the ghost's moves:
```python
def expectimax(self, gameState, depth, agentIndex):
if depth == 0 or gameState.isWin() or gameState.isLose():
return self.evaluationFunction(gameState)
legalActions = gameState.getLegalActions(agentIndex)
if agentIndex == 0: # Maximizing agent (Pacman)
value = float('-inf')
for action in legalActions:
successor = gameState.generateSuccessor(agentIndex, action)
value = max(value, self.expectimax(successor, depth, 1))
return value
else: # Expected value for ghosts
value = 0
probability = 1 / len(legalActions)
for action in legalActions:
successor = gameState.generateSuccessor(agentIndex, action)
if agentIndex == gameState.getNumAgents() - 1: # Last ghost
value += probability * self.expectimax(successor, depth - 1, 0)
else:
value += probability * self.expectimax(successor, depth, agentIndex + 1)
return value
def getAction(self, gameState):
bestValue = float('-inf')
bestAction = None
for action in gameState.getLegalActions(0):
successor = gameState.generateSuccessor(0, action)
value = self.expectimax(successor, self.depth, 1)
if value > bestValue:
bestValue = value
bestAction = action
return bestAction
```

Evaluation

Executed with:
```bash
python autograder.py -q q4
```
The test confirmed that my implementation met the expected outputs despite the probabilistic actions taken by the ghosts.

4. Constraint Satisfaction Problems (CSP)

Part a: Placing Knights on a Chessboard

Variables

- Each variable represents the position of a knight on the chessboard.

Possible Values

- Each knight can be placed in any cell of the chessboard represented by coordinates (i, j) where 0 ≤ i, j < n.

Constraints

- No two knights should be placed in such a manner that they can attack each other. This constraint is satisfied when the distances between their positions correspond to the movement characteristics of the knight in chess.

Part b: Class Scheduling

CSP Formulation

- Variables: C1, C2, C3, C4, C5 (Classes)
- Domains:
- C1: {Prof A, Prof C}
- C2: {Prof A}
- C3: {Prof B, Prof C}
- C4: {Prof B, Prof C}
- C5: {Prof A}

Constraints

- Each professor can teach only one class at a time:
1. C1 ≠ C2
2. C1 ≠ C3
3. C1 ≠ C4
4. C1 ≠ C5
5. C2 ≠ C3
6. C2 ≠ C4
7. C2 ≠ C5
8. C3 ≠ C4
9. C3 ≠ C5
10. C4 ≠ C5

Constraint Graph

A graph can be constructed where nodes represent variables (classes) and edges represent constraints between classes.

Tree-Structured CSPs

The advantage of a tree-structured CSP is that they can be solved efficiently using algorithms that exploit this structure, enabling faster solution finding and less computational overhead due to fewer possible variable combinations.

Conclusion

The multiagent search algorithms implemented in this report serve as a practical application of the concepts learned in the CSE 5120 course. Leveraging techniques such as minimax, alpha-beta pruning, and expectimax, I effectively navigated the complexities posed by adversarial agents in a game context, alongside exploring the principles of constraint satisfaction problems.

References

1. Russell, S., & Norvig, P. (2016). Artificial Intelligence: A Modern Approach. Pearson.
2. Stienstra, M. (2020). Game Theory for Beginners. Springer.
3. Barto, A. G., & Sutton, R. S. (1998). Reinforcement Learning: An Introduction. MIT Press.
4. Zadeh, L. A. (1965). Fuzzy Sets. Information and Control.
5. Stuart, M. (2019). Understanding Alpha-Beta Pruning in Minimax Algorithms. CS Unplugged.
6. Thrun, S., & Schwartz, A. (2004). Finding an Optimal Policy Using Value Iteration. International Symposium on Reinforcement Learning.
7. Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann.
8. Koller, D., & Friedman, N. (2009). Probabilistic Graphical Models: Principles and Techniques. MIT Press.
9. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
10. Dechter, R. (2003). Constraint Processing. Morgan Kaufmann.