can anyone answer task 6.. if yes message +919852719784

EECS492F18PS1-Revision2.pdf

Home >Computer Science homework help >can anyone answer task 6.. if yes message +919852719784

EECS 492 - FALL 2018 PROBLEM SET 1

DUE: MONDAY 10/1, 11:59PM

GENERAL INFORMATION ● For the written questions, put your answers in a pdf (with your name in the pdf) and submit to the corresponding

assignment on Gradescope. ● For the coding questions, rename and submit your code file to the corresponding assignment on canvas, and also

append the code to the end of your pdf. The renaming of the files are as follows: Task 4: Pac-Man:

search.py → <firstname>_<lastname>_search.py (i.e. john_doe_search.py) searchAgents.py → <firstname>_<lastname>_searchAgents.py (i.e.

john_doe_searchAgents.py) Task 6: Line Labeling

<firstname>_<lastname>_diagram.py (i.e. john_doe_diagram.py) ● Late homework will be penalized 10% per day (each day starts at 12:01AM the day after the due date). ● Homework turned in after three days will not be accepted.

Reminder: All solutions must be your own. For any solutions that require programming, comment and format your code to make it readable. You should code your solutions in Python 2, and your code should be able to run on CAEN.

Updates from Revision 1:

● Expected statistics for Pac-Man have changed to reflect the goal testing presented in Figure 3.7 in the book. ● A paragraph for the above has been added on page 7. ● A sentence on page 6 detailing where to look for Windows setup guidelines.

Updates from Revision 2:

● Fix depth-first search expected output (also on Piazza)

TASK 1: GAMBLING AGENTS For reasons that baffle much of the population, televising poker tournaments, such as the World Series of Poker, has mysteriously become a staple of sports network programming. It seems unlikely that athletic grace and prowess are the main attractions of this “sport,” so perhaps there is something about the nature of the competitive task, and the complexity of the environment in which the task is conducted, that rivets the attention of the adoring public.

In part to see if you can discover whether this is the case, this problem set consists of questions about the World Series of Poker and about the design of artificial agents to make decisions in this context. The version of poker played is known as “Texas Hold 'em.” Full rules for the game can be found at https://www.partypoker.com/how-to-play/texas-holdem.html , and you should be familiar with how the game works before attempting this assignment (initial hand being dealt, a hand vs. a game, betting rules for staying in game). A quick google search for “how to play texas holdem” turns up many resources.

Just to be clear about terminology in this assignment, a hand is assumed to involve the dealing of cards to the players, followed by rounds of betting and revelation of other cards until one of the players wins the money that has been bet. A fresh deck of cards is used for each hand, and the dealer has no possibility of cheating to benefit any player.

We will assume that a full game consists of a table of players who repeatedly play hands until one of them has won all of the money from the others.

Games take place in the context of a tournament. In the larger tournament, winners from different tables then play in games against each other; for the purposes of this assignment, assume that each game brings together a group of players that are unfamiliar with each other. This continues until there is one tournament winner. Assume that winnings are not carried over between games; every player in every game in every round of the tournament starts with the same amount of money.

1. Specify a game of poker in terms of each element of the PEAS description. Assume that the agent just plays poker, it does not need to move between tables, socialize, order drinks, etc.

2. A characterization of one poker environment has been presented in the book on page 45. Using this as a starting point, characterize a poker game environment as described in this assignment. For each dimension of the characterization, write a few sentences justifying your choice.

3. While in Vegas, you observe your very drunk friend play poker at a table. You notice that they sometimes seem to make the wrong decision. For example, your friend folded on a [2♣, 4♣] but the communal cards turned out to be [3♣, 9♦ ,J♠ ,5♣ ,6♣], which would have given them a straight flush and would’ve won them that hand! What can we say about the rationality of your friend (when it comes to playing poker, not drinking or making life decisions in Vegas)? Explain your answer.

4. Consider a hypothetical agent that decides whether to fold or call based solely on the value of the largest card in its pair. Is this agent rational? Why or why not?

5. We’ve completely forgotten one factor of the game and the whole reason why people gamble: the bets. Betting different amounts is an important part of playing poker and can be advantageous for a player. Regardless of what type of agent it is (table lookup, simple reflex, etc.), the agent we implement doesn’t have actuators that allow it to do things like go “all-in” on a bluff to scare the other players into folding. With this in mind, is it still possible for this agent still be considered rational? Explain your answer.

6. Now let’s consider a learning agent. The agent watches an expert who is playing poker, and observes the expert’s initial (pre-flop) hand. The agent watches the expert’s decision as to whether to check, bet, or fold based on only these two cards. The agent uses this information to update its performance element to match the behavior of the expert.

http://www.texasholdem-poker.com/beginnersintro

https://www.partypoker.com/how-to-play/texas-holdem.html

If the agent’s performance element does table lookup, the agent will find the appropriate entry in the table (corresponding to the pair held by the expert) and record the expert’s decision for that particular pair of cards.

If the agent’s performance element uses a reflex-threshold architecture, it instead does the following. It uses statistical information to rank all of the possible pairs in terms of likelihood of ultimately winning. Given this ranking, what it needs to learn are thresholds for classifying the pairs into different actions. For example, if a pair is in the top-third then bet, middle third then check, and bottom third then fold. By watching the expert, though, the agent can improve these thresholds - if the expert folds on the pair ranked in the center of the ranking, for example, the agent might adjust its thresholds to fold on the bottom half rather than the bottom third.

For each of these two types of performance elements, describe how well the agent will do when it has finished learning and must play on its own. In particular, how good will its decisions be when it is dealt pairs that it never saw the expert receive, and how will the quality of the decisions depend on how many different observations of the expert it got?

TASK 2: SEARCH FORMULATION

Situation: You are in charge of delivering water to families who are currently being affected by a drought. Unfortunately, on your way to the first family, the truck’s water meter breaks, so you cannot easily measure out specific amounts of water. After some searching, you manage to find three different sized containers that hold 7, 11, and 20 gallons.

Problem: A family is entitled to x gallons of water, where 0 < x < 20. Your job is to provide each family with water by filling one of the containers with exactly x gallons of water and then transferring the water to the family’s storage tank. When transferring water, the following restrictions must be obeyed:

● When pouring from one container into another, you can only stop when the source container is empty, or when the destination container is full.

● When pouring from the truck into a container, you can only stop when the container you’re pouring into is full.

Since the families are currently experiencing a drought, wasting water is frowned upon (not allowed). Also adding water to the truck takes a great deal of time and effort, so once water is removed from the truck, it cannot be put back until the current family has been given their water (having extra water in the containers when you’ve finished measuring is acceptable, but you cannot pour water back into the truck, or worse yet dump it on the ground, during the measuring process). Formulate the problem as a well-defined search problem, providing a detailed description of the following:

1. A specific state representation. 2. The total number of possible states in the state space. 3. A list of possible actions. Explicitly say, for each action, what state(s) (in your representation) the action can

be taken in, and give a specification of the state (in your representation) before the action, and the specification of the state (in your representation) after the action.

4. The initial state expressed in your state representation. 5. The goal test (you can assume x is known) expressed in your state representation (you may represent this

algebraically if it’s more convenient for you). 6. A reasonable path cost function. Be sure to justify your choice, specify your inputs and outputs, and make

sure that your function is actually a function.

TASK 3: SYSTEMATIC SEARCH IN A SMALL GRAPH This task will refer to the graph below, where each vertex represents a state, and each arrow corresponds to a possible action transition. The cost of a transition is 1 unless there is a different number written for an edge. State A is the initial state and state I is the only state that satisfies the goal test. The number given in parentheses after the name of a state is a heuristic estimate of the cost to the goal.

1. Give the path, if one exists, that is found using the below uninformed search techniques within the general tree search algorithm to get from A to I. When generating the successors of a node, assume their insertion into the queue has them appear in alphabetical order and that the nodes are added in batches (e.g., successors of A are in the queue ordered (AB AC) as a tuple). If the goal is found give the node (specified in terms of its path i.e. ABDH) that first passes the goal test, the total number of nodes generated (including the initial node), and how many nodes are in the fringe at its largest point. Otherwise explain what prevents the search from finding the goal. (Note: for all the searches use the convention from class and the tree-search pseudocode on page 77 where a node is checked for the goal state when it is removed from the frontier.)

a. Breadth-first search b. Depth-first search c. Depth-limited search with limit 2 (the root is depth = 0) d. Iterative Deepening Depth-Limited search

2. Consider an A* graph-search on this graph from state A to I. For each iteration of A*, write out the contents of the fringe, in prioritized order, and the contents of the closed/explored list. When writing out the list of nodes at a particular step, you should specify a node in terms of its path and its f() value (i.e AB(4)), as was done in class. When prioritizing the fringe, break ties putting first whichever node was in the fringe longer; if there is still a tie use alphabetical ordering based on the node’s state. When the search is finished, what solution was found, how many nodes were generated, and how many nodes were in the fringe at its largest point? Also, answer the following: Is the heuristic admissible? Is it consistent?

TASK 4: PAC-MAN IS HUNGRY! Pac-Man is on the loose and is hungry! Sadly, he is currently in a maze and has a hard time finding where the edible Pac-Dots are. To aid Pac-Man in finding Pac-Dots in the maze, you will implement a few search functions in search.py as well as a couple of heuristics in searchAgents.py (these are the only two files you should be editing for this task!). Remember to rename these two files as stated in the General Information section at the beginning of this homework.

FIGURE 1: EXAMPLE PAC-MAN MAZE

For this portion of the homework, you will implement the following graph search algorithms in search.py:

● Depth-First Search (fn=dfs) ● Breadth-First Search (fn=bfs) ● Iterative Deepening Depth-Limited Search (fn=ids) ● Uniform Cost Search (fn=ucs) ● A* Search (fn=astar)

You will also implement the following tree search algorithms in search.py:

● Depth-First Tree Search (fn=dfts) ● Breadth-First Tree Search (fn=bfts)

You will also implement the following two heuristics in searchAgents.py:

● Manhattan Distance ● Euclidean Distance

In order to begin, please download the file pacman.zip and unzip it to your working directory. Before starting this portion, try playing a game of Pac-Man via the following command: python pacman.py

If you are using CAEN Linux, please run module load python on machine startup. If you receive issues with Tkinter (capital T in Python 2) locally, please install it using pip, the python package manager. Tkinter shouldn’t be an issue on CAEN Linux. If you are on Windows and the command fails to launch, be sure to checkout the suggested instructions on Piazza (Cygwin, WSL, and PuTTY). At the end of the game, you will receive some statistics on the terminal regardless of if you win or lose:

Pacman emerges victorious! Score: 503 Average Score: 503.0 Scores: 503.0 Win Rate: 1/1 (1.00) Record: Win

Pacman died! Score: 39 Average Score: 39.0 Scores: 39.0 Win Rate: 0/1 (0.00) Record: Loss

You will be submitting these statistics for a certain set of mazes and search algorithms. Currently, a trivial search agent, GoWestAgent, has already been implemented for you. This search agent only moves west. In some mazes, it may help Pac-Man find food, but it may not in others. Try out these 2 commands: python pacman.py --layout testMaze --pacman GoWestAgent

python pacman.py --layout tinyMaze --pacman GoWestAgent

Now, your job is to write the search algorithms and the needed heuristic functions! In lecture, you have learned that you need certain data structures to implement these search functions (stack, queue, priority queue). Before you begin coding, please take a look at util.py and make sure to use the Stack, Queue, and PriorityQueue data structures there. Also, please read the comments in the depthFirstTreeSearch function in search.py for instructions on how to use the internal methods. A note on the order of processing the successors of each state: they should be processed in batch order (like what was done in lecture and in Task 3). However, do not push batches into the data structures (so don’t push an entire tuple of successors into the frontier). Rather, push them one-by-one, but make sure that they are processed as if they were pushed on as a whole batch. A note on when you run the commands below: each tile has a different shade of red when run with a search algorithm. The redder the tile, the earlier it has been explored by your agent. A note on testing on expansion vs. generation: please follow Figure 3.7 in the textbook. If you use PriorityQueue, you may need to read carefully in the source code in util.py to find which method you should be using (of course, the same goes for Stack and Queue). If you feel like Pac-Man moves too slowly, feel free to add --frameTime 0 to the end of the command you’re running. The frameTime argument is the time to pause between rendering successive states, so making this 0 would make your search algorithm finish immediately instead of waiting for the animation to finish. Here are the commands we will be testing for and the ones you should submit statistics for.:

Search Algorithm Commands

Depth-First Search python pacman.py -l tinyMaze -p SearchAgent

python pacman.py -l mediumMaze -p

SearchAgent

python pacman.py -l bigMaze -z .5 -p

SearchAgent

Breadth-First Search python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs

python pacman.py -l bigMaze -p

SearchAgent -a fn=bfs -z .5

Iterative Deepening Depth-Limited Search (with max depth = 5)

python pacman.py -l tinyMaze -p

SearchAgent -a fn=ids

Iterative Deepening Depth-Limited Search (with max depth = 10)

python pacman.py -l tinyMaze -p

SearchAgent -a fn=ids

Uniform Cost Search python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs

python pacman.py -l mediumDottedMaze -p

StayEastSearchAgent

python pacman.py -l mediumScaryMaze -p

StayWestSearchAgent

A* Search python pacman.py -l bigMaze -z .5 -p SearchAgent -a

fn=astar,heuristic=manhattanHeuristic

python pacman.py -l bigMaze -z .5 -p

SearchAgent -a

fn=astar,heuristic=euclideanHeuristic

The table below is a list of expected statistics run on different commands. Note that you will receive more credit the closer your results are to the expected values (that is, point deductions for close answers will be small). If you can’t get all of them to be completely correct, your time may be better spent to make all of the numbers relatively close to the expected results and for you to make sure that your algorithm is generally correct:

Search Algorithm Sample Command Statistics for Sample Commands

Depth-First Search python pacman.py -l openMaze -p SearchAgent

--frameTime 0

Path found with total cost of 226 in 0.0 seconds Search nodes expanded: 333 Pacman emerges victorious! Score: 284 Average Score: 284.0 Scores: 284.0 Win Rate: 1/1 (1.00) Record: Win

Breadth-First Search python pacman.py -l tinyMaze -p SearchAgent -a

fn=bfs --frameTime 0

Path found with total cost of 8 in 0.0 seconds Search nodes expanded: 15 Pacman emerges victorious! Score: 502 Average Score: 502.0 Scores: 502.0 Win Rate: 1/1 (1.00) Record: Win

Iterative-Deepening Depth-Limited Search (max depth = 1000)

python pacman.py -l

idsTest -p SearchAgent -a

fn=ids --frameTime 0

Path found with total cost of 8 in 0.0 seconds Search nodes expanded: 4667 Pacman emerges victorious! Score: 502 Average Score: 502.0 Scores: 502.0 Win Rate: 1/1 (1.00) Record: Win

Uniform Cost Search python pacman.py -l tinyMaze -p SearchAgent -a

fn=ucs --frameTime 0

Path found with total cost of 8 in 0.0 seconds Search nodes expanded: 15 Pacman emerges victorious! Score: 502 Average Score: 502.0 Scores: 502.0 Win Rate: 1/1 (1.00) Record: Win

A* Search python pacman.py -l openMaze -p SearchAgent -a

fn=astar,heuristic=manhatt

anHeuristic --frameTime 0

Path found with total cost of 54 in 0.0 seconds Search nodes expanded: 535 Pacman emerges victorious! Score: 456 Average Score: 456.0 Scores: 456.0 Win Rate: 1/1 (1.00) Record: Win

Questions:

1. Paste your <firstname>_<lastname>_search.py code here, and submit it to Canvas.

2. Paste your <firstname>_<lastname>_searchAgents.py code here, and submit it to Canvas.

3. Please submit a table of statistics for the 11 following commands (run bash commands.txt to run all the commands below in order. Note that you will have to run fn=ids again after changing the depth limit). Each statistic should look like the following:

Path found with total cost of 1024 in 0.0 seconds Search nodes expanded: 222 Pacman emerges victorious! Score: 500 Average Score: 500.0 Scores: 500.0 Win Rate: 1/1 (1.00) Record: Win

Command Statistic (fill in)

1 python pacman.py -l tinyMaze -p SearchAgent

2 python pacman.py -l mediumMaze -p SearchAgent

3 python pacman.py -l bigMaze -z .5 -p SearchAgent

4 python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs

5 python pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5

6 (max depth = 5) python pacman.py -l tinyMaze -p SearchAgent -a fn=ids

7 (max depth = 10) python pacman.py -l tinyMaze -p SearchAgent -a fn=ids

8 python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs

9 python pacman.py -l mediumDottedMaze -p StayEastSearchAgent

10 python pacman.py -l mediumScaryMaze -p StayWestSearchAgent

11 python pacman.py -l bigMaze -z .5 -p SearchAgent -a

fn=astar,heuristic=manhattanHeuristic

12 python pacman.py -l bigMaze -z .5 -p SearchAgent -a

fn=astar,heuristic=euclideanHeuristic

4. Why do you think that depth-first tree search fails on the smallest maze? (Try running python pacman.py -l tinyMaze -p SearchAgent -a fn=dfts ).

5. Execute python pacman.py -l tinyMaze -p SearchAgent -a fn=bfts. How many search nodes were expanded? Why was a path found for breadth-first tree search, and why is the number of search nodes expanded greater than/less than/equal to that of breadth-first graph search?

6. Why is Iterative-Deepening Search a Tree search instead of a graph search? Hint: try tracing out on paper a graph version of Iterative-Deepening Search on tinyMaze. What happens?

7. Observe the movement of Pac-Man in a maze. When Pac-Man moves, the score drops. Why shouldn’t the utility of every Pac-Man step be zero instead?

8. While running all the commands, your dear friend Bobby Tables decided that the computation for A* search on a humongous map was too slow. To combat this, Bobby decided to come up with a heuristic called fastHeuristic that returns the straight-line distance from the origin (0, 0). Surely, this will make Pac-Man take a shorter route, right? What is the problem with Bobby’s fastHeuristic? Hint: look at the goal state of one of the Pac-Man maps, and see which coordinates it lies in.

9. Being the adventurous student you are, you try running your Pac-Man A* graph search algorithm on a 3-D Pac-Man world. However, the search seems to be taking forever and you realize that the main bottleneck is the branching factor. Describe, in 1~2 sentences, how you would modify your algorithm to cope with this and what the expected big-O runtime would be.

TASK 5: LOCAL SEARCH This task explores local search on the 8-puzzle domain, which was introduced both in lecture and in the book. The game consists of eight tiles, each of which occupies one of nine board positions. For the purposes of this assignment, we label the board positions in the same manner as English text, from top left to bottom right. The state representation to be used is a listing of the tile at each position, and use an e (empty) for the position with no tile. So, the goal state

will be represented as (1,2,3,4,e,5,6,7,8).

1. Perform a greedy hill-climbing search, starting from state

or (1,e,3,6,2,5,7,4,8). Use a heuristic cost defined by the Manhattan distance (found in the book) of the tiles (do not count the distance of the empty space). For each iteration, show the current state being expanded and its value, and a list of its possible successor states and their values.

2. Consider the following partial description of a state, showing locations of only some of the tiles:

or (5,-,-,-,-,-,6,7,8). Give a complete state description that matches this partial assignment such that the resulting state is a local minimum, but is not the global minimum.

TASK 6: LINE-LABELING BY CONSTRAINT SATISFACTION

Among the many applications of the constraint satisfaction problem (CSP) paradigm, one of the first was to perform a process called line-labeling to attempt to use a 2-dimensional image of a “blocks-world” environment to infer its 3-dimensional structure so that a robot can reconfigure the blocks to achieve a goal. In this task, you will utilize code that we provide to you, and extend it with code that you write, to develop a deeper understanding of the CSP paradigm and its application to line labeling.

As an introduction to the line-labeling problem, see the separate document provided that summarizes it.

Part of the line labeling code has been written for you (Python 2.7). Parts a to i will provide more instruction on finishing the code.

Many of the utility functions written in diagram.py will be helpful. The class Vertex is used extensively in diagram.py and is defined in vertex.py .

You will use main.py to run the code. Example commands:

python main.py examples/cube.txt propagation -p ac_3 # only run AC3 on cube.txt

python main.py examples/cube.txt backtracking -p ac_3 -o mrv # find all solutions of AC3 and

MRV

python main.py examples/cube.txt backtracking -s -p ac_3 -o mrv # find ONE solution using

backtracking with AC3 and MRV

python main.py examples/cube.txt backtracking -p forward_checking -o first_unassigned # find

ONE solution using backtracking with forward checking and the first unassigned heuristic

Run python main.py -h for detailed usage instructions.

row# #solns propagation ordering # assignments TOWER

# assignments POIUYT

1 all No-prop First-unassigned 2 all Forward-checking First-unassigned 3 all Arc-consistency First-unassigned 4 all No-prop MRV 5 all Forward-checking MRV 6 all Arc-consistency MRV 7 one No-prop First-unassigned 8 one Forward-checking First-unassigned 9 one Arc-consistency First-unassigned 10 one No-prop MRV 11 one Forward-checking MRV 12 one Arc-consistency MRV 13 all Arc-consistency** MRV

a. The method for backtracking, search_solutions in diagram.py was left unfinished. Finish the code to fill in the first 2 rows of the table.

b. Implement arc consistency and fill in the 3rd row of the table. Fill in the ac_3 method of the Diagram class in diagram.py.

For each of the diagrams, briefly explain the extent to which it did (or did not) affect the number of variable assignments compared to forward-checking, and why.

c. In class, we will have talked about how the order in which variables are assigned can make a difference to the search effort. In the current code the first_unassigned method chooses based on alphabetical order. As a first step at considering this, modify first_unassigned to return a random unassigned vertex instead. Test out the new random heuristic and record the number of variable assignments for 10 trials for both diagrams and each of the 3 propagation methods.

What do your results tell you about the impact of variable ordering on the search effort for each of these diagrams?

d. One way of ordering vertices that heuristically can decrease the number of (tentative) assignments needed to find solutions, as discussed in class, is to assign the variable next that has the fewest number of possible values to assign - the Minimum Remaining Values (MRV) heuristic.

Implement this heuristic and add it to your code in the method mrv. Break ties based alphabetical ordering (as was done in first_unassigned). With your new code, fill in rows 4-6 of the Table.

e. Use observation(s) from the answer to part c to explain the impact of the MRV heuristic in rows 4-6 you just filled in. Particularly address the fourth row performance on the TOWER diagram. What do the results tell you about the mrv heuristic?

f. As you did in part d, experiment with a “random” MRV heuristic (break ties randomly). Comment on whether the variance in the number of tentative assignments differs from part c, and briefly (in a sentence or two) explain why or why not.

g. In most applications of constraint satisfaction where there might be multiple solutions, the user only cares about getting one legal solution (for example, for scheduling a conference room, packing a box, the n-queens problem in class). Fill in rows 7-12 using the -s command line argument in main.py (see examples).

For each of the TOWER and POIUYT diagrams, briefly explain how searching for just one solution (rows 7-12) impacts the number of variable assignments performed compared to the first 6 rows where all solutions were found.

h. Finally, create a version where you modify the search_solutions method to apply arc-consistency (ac_3) to every vertex before any search is done. Fill in row 13 of the table, and briefly explain any difference(s) with row 6.

RULES FOR PROGRAMMING AND SUBMISSION Name your source files by appending firstname and lastname to the beginning, chained by underscores. i.e. if your name is John Doe, change task.py to john_doe_task.py. Your programs must compile and run from a command line on CAEN computers. Use good style and layout. Comment your code well.

CREDITS AND ATTRIBUTION We would like to thank UC Berkeley’s CS188 for the amazing interface used in the Pac-Man search. For more information, visit http://ai.berkeley.edu.

The line-labeling problem was adapted from Paradigms of AI Programming by Peter Norvig (yes our text’s coauthor), and the figures given with the problem description are from that source.