1 Introduction The purpose of this assignment is to become more familiar with bit-level representations of integers. You’ll do this by solving a series of programming “puzzles.” Many of these puzzles are quite artificial, but you’ll find yourself thinking much more about bits in working your way through them. 2 Handout Instructions Download the datalab-handout.tar from PLMS. Upload the file to a programming server, move it to the directory you want to work on. Then give the command unix> tar xvf datalab-handout.tar. This will cause a number of files to be unpacked in the directory. The only file you will be modifying and turning in is bits.c. The bits.c file contains a skeleton for each of the 5 programming puzzles. Your assignment is to complete each function skeleton using only straightline code for the integer puzzles (i.e., no loops or conditionals) and a limited number of C arithmetic and logical operators. Specifically, you are only allowed to use the following eight operators: ! ˜ & ˆ | + > A few of the functions further restrict this list. Also, you are not allowed to use any constants longer than 8 bits. See the comments in bits.c for detailed rules and a discussion of the desired coding style. 3 Problems Name Description Rating Max Ops bitNor(x,y) Compute ˜(x | y) using only ˜ and & 1 8 isZero(x,n) Return 0 if x is non-zero, else 1 1 2 addOk(x,y) Determine if can compute x+y without overflow 3 20 absVal(x) Return absolute value of x 4 10 logicalShift(x,n) Perform logical right shift to x by n 3 20 Table 1: Bit-Level Manipulation Functions. 4 Evaluation Your score will be computed out of a maximum of 12 points. We will evaluate your functions using the btest program, which is described in the next section. You will get full credit for a problem if it passes all of the tests, and no credit otherwise. Autograding your work We have included some autograding tools in the handout directory — btest, dlc, and driver.pl — to help you check the correctness of your work. • btest: This program checks the functional correctness of the functions in bits.c. To build and use it, type the following two commands: unix> make unix> ./btest Notice that you must rebuild btest each time you modify your bits.c file. You’ll find it helpful to work through the functions one at a time, testing each one as you go. You can use the -f flag to instruct btest to test only a single function: unix> ./btest -f bitAnd You can feed it specific function argument using the option flags -1, -2, and -3: unix> ./btest -f bitAnd -1 7 -2 0xf Check the file README for documentation on running the btest program. • dlc: This is a modified version of an ANSI C compiler from the MIT CILK group that you can use to check for compliance with the programming rules for each problem. The typical usage is: unix> ./dlc bits.c The program runs silently unless it detects a problem, such as an illegal operator, too many operators, or non-straightline code in the integer puzzles. Running with the -e switch: unix> ./dlc -e bits.c causes dlc to print counts of the number of operators used by each function. Type ./dlc -help for a list of command line options. • driver.pl: This is a driver program that uses btest and dlc to compute the correctness and performance points for your solution. It takes no arguments: unix> ./driver.pl 5 Handin Instructions Upload your bits.c file and report in PLMS with the following format: • Rename your bits.c file as: [student id].c (e.g., 20231234.c) • Submit your report with pdf format: [student id].pdf (e.g., 20231234.pdf) Submissions with incorrect format will not be graded, no exception (i.e., you will get 0 points for this entire lab). 6 Advice • The dlc program enforces a stricter form of C declarations than is the case for C++ or that is enforced by gcc. In particular, any declaration must appear in a block (what you enclose in curly braces) before any statement that is not a declaration. For example, it will complain about the following code: int foo(int x) { int a = x; a *= 3; /* Statement that is not a declaration */ int b = a; /* ERROR: Declaration not allowed here */ }
CSED342 – Artificial Intelligence General Instructions This assignment has been developed in Python 3.8, so please use Python 3.8 to implement your code. we recommend using Conda environment. You should modify the code in submission.py between # BEGIN_YOUR_ANSWER and # END_YOUR_ANSWER You can add other helper functions outside the answer block if you want, but do not import other libraries and do not make changes to files other than submission.py. Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run all the tests, type python grader.py This will tell you only whether you passed the basic tests. The script will alert you if your code takes too long or crashes on the hidden tests, but does not say whether you got the correct output. You can also run a single test (e.g., 2a-1-basic) by typing python grader.py 2a-1-basic We strongly encourage you to read and understand the test cases, create your own test cases, and not just blindly run grader.py. Problems Here, we are going to solve two problems, Text reconstruction and Maze search. Both are search problems, which are defined by state, action, cost, and successor. The object is to find the minimum cost path from a starting state to the goal. Problem 1. Text reconstruction In this problem, we consider two tasks: word segmentation and vowel insertion. Word segmentation often comes up in processing many non-English languages, in which words might not be flanked by spaces on either end, such as in written Chinese or in long compound German words. Vowel insertion is relevant in languages such as Arabic or Hebrew, for example, where modern script eschews notations for vowel sounds and the human reader infers them from context. More generally, it is an instance of a reconstruction problem given lossy encoding and some context. We already know how to optimally solve any particular search problem with graph search algorithms such as uniform cost search or A*. Our goal here is modeling — that is, converting real-world tasks into state-space search problems. Setup: n-gram language models and uniform-cost search Our algorithm will base its segmentation and insertion decisions on the cost of processed text according to a language model. A language model is some function of the processed text that captures its fluency by estimating the likelihood of text, N p(w1,w2,…,wN−1,wN) = Xp(wi|w1,…,wi−1). i=1 A very common language model in NLP is an n-gram sequence model, which assumes p(wi|w1,…,wi−1) = p(wi|wi−(n−1),…,wi−1). We’ll use the ngram model’s negative log-likelihood (−log p(wi|wi−(n−1),…,wi−1)) as a cost function c(wi−(n−1),…,wi−1,wi). The cost will always be positive, and lower costs indicate better fluency. As a simple example: in a case where n = 2 and c is our n-gram cost function, c(big, fish) would be low, but c(fish, fish) would be fairly high. Word segmentation In word segmentation, you are given as input a string of alphabetical characters ([a-z]) without whitespace, and your goal is to insert spaces into this string such that the result is the most fluent according to the language model. Problem 1.a [10 points] Implement an algorithm that finds the optimal word segmentation of an input character sequence. Your algorithm will consider costs based simply on a unigram cost function. Before jumping into code, you should think about how to frame this problem as a state-space search problem. How would you represent a state? What are the successors of a state? What are the state transition costs? Uniform cost search (UCS) is implemented for you in util.py, and you should make use of it here. Fill in the member functions of the WordSegmentationProblem class and the segmentWords function. The argument unigramCost is a function that takes in a single string representing a word and outputs its unigram cost. You can assume that all the inputs would be in lowercase. The function segmentWords should return the segmented sentence with spaces as delimiters, i.e. ‘ ’.join(words). For convenience, you can run python submission.py to enter a console in which you can type character sequences that will be segmented by your implementation of segmentWords. To request a segmentation, type seg mystring into the prompt. For example: >> seg thisisnotmybeautifulhouse Query (seg): thisisnotmybeautifulhouse this is not my beautiful house Console commands other than seg – namely ins and both – will be used for the upcoming parts of the assignment. Other commands that might help with debugging can be found by typing help at the prompt. Vowel insertion Now you are given a sequence of English words with their vowels missing (A, E, I, O, and U; never Y). Your task is to place vowels back into these words in a way that maximizes sentence fluency (i.e., that minimizes sentence cost). For this task, you will use a bigram cost function. You are also given a mapping possibleFills that maps any vowel-free word to a set of possible reconstructions (complete words). For example, possibleFills(‘fg’) returns set([‘fugue’, ‘fog’]). Problem 1.b [10 points] Implement an algorithm that finds optimal vowel insertions. Use the UCS subroutines. When you’ve completed your implementation, the function insertVowels should return the reconstructed word sequence as a string with space delimiters, i.e. ‘ ’.join(filledWords). Assume that you have a list of strings as the input, i.e. the sentence has already been split into words for you. Note that an empty string is a valid element of the list. Note: If some vowel-free word w has no reconstructions according to possibleFills, your implementation should consider w itself as the sole possible reconstruction. Putting it together We’ll now see that it’s possible to solve both of these tasks at once. This time, you are given a whitespace- and vowel-free string of alphabetical characters. Your goal is to insert spaces and vowels into this string such that the result is the most fluent possible one. As in the previous task, costs are based on a bigram cost function. Problem 1.c [15 points] Implement an algorithm that finds the optimal space and vowel insertions. Use the UCS subroutines. When you’ve completed your implementation, the function segmentAndInsert should return a segmented and reconstructed word sequence as a string with space delimiters, i.e. ‘ ’.join(filledWords). The argument query is the input string of space- and vowel-free words. The argument bigramCost is a function that takes two strings representing two sequential words and provides their bigram score. The special out-ofvocabulary beginning-of-sentence word -BEGIN- is given by wordsegUtil.SENTENCE_BEGIN. The argument possibleFills is a function; it takes a word as string and returns a set of reconstructions. Note: Unlike in problem 1.b, where a vowel-free word could (under certain circumstances) be considered a valid reconstruction of itself, here you should only include in your output words that are the reconstruction of some vowel-free word according to possibleFills. Additionally, you should not include words containing only vowels such as “a” or “I”; all words should include at least one consonant from the input string. Use the command both in the program console to try your implementation. Similar to ins command, vowels are striped and spaces are also ignored. For example: >> both imagine all the people Query (both): mgnllthppl imagine all the people Problem 2. Maze search In this problem, we consider searching a 2D grid maze. It’s a common task to find an exit path with the minimum cost. Starting from the first state, the agent can take any action from possibleMoves. To see how action corresponds to the actual move, please check util.directions. If a valid action is chosen, the agent moves toward the direction with predefined cost. However, every maze has a wall that the agent can pass but at a high cost. Also, the size of a maze is finite, which limits its state space. Problem 2.a [3 points] Implement an algorithm that finds the minimum cost of a path from the starting point to the goal. Fill in the member functions of the MazeProblem and the UCSMazeSearch function. When you’ve completed your implementation, the function UCSMazeSearch should return a cost of the shortest path. The arguments start and goal are the coordinates of the starting point and the goal in a maze. As we are going to explore a 2D maze, each coordinate is represented as a tuple of two integer numbers. The argument moveCost is a function that takes in two coordinates and outputs a cost from the first coordinate to the second coordinate. The argument possibleMoves is a function that takes in a single coordinate and outputs a set of possible moves and their costs. Maze search with A* search algorithm Until now, maze search is not that different from text reconstruction. However, with uniform cost search used in text reconstruction, the agent has to search a lot of states that might be meaningless in a high-level perception. Consider the following figure showing a grid maze, where A and G represent the current positions of the agent and the goal.With a given figure, humans can notice that going straight to the goal is the shortest path. However, with uniform cost search, the agent does not know about such a strategy. Instead, it will move around all the nearby cells. To prevent such explorations, we can use A* search with a heuristic cost function, instead of uniform cost search. If heuristic cost is consistent, A* search always finds the shortest path with less exploration compared to uniform cost search. As the term ’heuristic’ implies, depending on a heuristic cost function, A* search differs in time to find the shortest path. With a na¨ıve heuristic, finding the shortest path can be non-optimal. Still, it will find the shortest path if the given heuristic cost function is consistent.up: with UCS, down: with A* search. Green tiles represent visited states.Heuristic used for A* search can be non-optimal. Still, it will find the shortest path if it is consistent. Problem 2.b [12 points] Implement a heuristic cost function that is consistent with the maze search problem. Fill in the function consistentHeuristic. It is used as a heuristic cost function for this problem, which is an input argument of util.UniformCostSearch.solve. When you’ve completed your implementation, the function AStarMazeSearch should return a cost of the shortest path. Note that if your heuristic cost function is well-defined, A* search should be faster than UCS.
CS 39006: Networks Lab Assignment 1: Using Wireshark, UDP socketsPART A: Exploring Packet Sniffer and Packet AnalyzerThe objective of this part of the assignment is to understand the network packet structures and different fields present at the packet headers corresponding to different layers of the protocol stack. For this assignment, you need to install Wireshark on your machine and keep your machine connected with the Internet.To start with, execute the following steps. 1) Ensure that no browsing activity is going on in your machine. Close all the browser tabs. 2) Download and run Wireshark. 3) Start capturing packets over your default (active) network interface. 4) Open a browser tab and open the website http://iitkgp.ac.in/. 5) Wait for 1 minutes. 6) Now on the same browser tab, open the website https://www.cornell.edu/. 7) Close the browser tabs. 8) Stop packet capture. 9) Save the pcap file from Wireshark.Now answer the following questions by analyzing the packet traces. Do not use any other tools other than wireshark, use its features to answer the questions to learn them better.1. How many packets do you see for the following protocols? a. TCP and UDP together b. IPv4 and IPv6? 2. What is the total amount of data being received for the following two cases? a. When you access http://iitkgp.ac.in b. When you access https://www.cornell.edu 3. How many DNS packets have you observed in total? a. Create a table by exploring the queries and the answers in those DNS packets. The Domain Name will be the domain for which you see a query, and the IP address will be the address that is being returned against the corresponding query. b. Can you find out the IP of the DNS servers by exploring the DNS packets? 4. Answer the following when you access the site http://iitkgp.ac.in. a. How many HTTP GET requests do you observe? List down the GET requests. b. For each of the HTTP GET requests you see above, find out (ii) the total number of TCP segments being received, and (ii) the total amount of data being received in the corresponding HTTP Response message.Submission Instructions:Upload the pcap file that you have used in a password-less shareable Google drive folder (do not upload the file directly in moodle). Create a doc file named _Assignment1_A.doc (replace with your roll number) with your answers. The header of the doc file should be as follows.===================================== Assignment 1 (Part A) Submission Name: Roll number: Link of the pcap file: =====================================PART B: Simple Datagram Socket using POSIX CThe objective of this assignment is to get familiar with datagram sockets using POSIX C programming. The target is to establish a communication between two computers (processes) using a datagram socket. A datagram socket uses a simple communication paradigm to transfer short messages between two computers (processes) without ensuring any reliability.Your task will be to write two programs – one program corresponding to the server process and another program corresponding to the client process. The client process requests for the content of a file (by providing the file name) and the server process sends the contents of that file to the client.For simplicity, we assume that the file is a simple text file that contains a set of words, with the first work being HELLO and the last word being END. We assume that HELLO and END are two special keywords that do not come anywhere except at the first line (HELLO) and at the last line (END). The content of a sample file looks as follows.HELLO SOCKET PROGRAMMING COMPUTER NETWORK TCP UDP ENDThe transfer of the contents of the file works using a communication protocol as follows. 1. The client first sends the file name to the server (assume the name has les than 100 characters). 2. The server looks for the file in the local directory, if the file is not there it sends back with a message NOTFOUND , where is the name of the file requested by the client. By receiving this message, the client prints an error message “File Not Found” and exits. 3. If the file is present, the server reads the first line of the file, which contains HELLO, and sends this message to the client. 4. After receiving HELLO, the client creates a local file (a different file name from the requested one) and sends a message WORD1 to the server. This message indicates that the client is requesting for the first word. 5. After receiving the message WORD1, the server sends the first word (after HELLO) to the client. The client writes this word to the local file after receiving it and sends the message WORD2 to request for the next word. This procedure continues for each word. 6. On receiving WORDi, the server sends the i-th word to the client. This process continues until the client receives the keyword END. 7. Once the client receives the keyword END, it closes the local file after writing the last word to the file. Is this a good file transfer protocol?Submission Instruction:You should write two C programs – wordserver.c (contains the server program) and wordclient.c (contains the client program). Keep these two files in a single compressed folder (zip or tar.gz) having the name _Assignment1_B.zip or _Assignment1_B.tar.gz.
Instructions: • This assignment is meant to help you grok certain concepts we will use in the course. Please don’t copy solutions from any sources. • Avoid verbosity. • The assignment needs to be written in latex using the attached tex file. The solution for each question should be written in the solution block in space already provided in the tex file. Handwritten assignments will not be accepted. 1. Partial Derivatives (a) Find the derivative of g(ρ) with respect to ρ where g(ρ) is given by,(You can consider ˆρ as constant) Solution: (b) Consider the following computation , by definition : and The value L is given by, L = −y log(f(x)) Here, x and y are constants and w and b are parameters that can be modified. In other words, L is a function of w and b. Derive the partial derivatives, and . Solution: 2. Chain Rule: (a) Consider the evaluation of E as given below, E = h(u,v,w,x) = 2 ∗ f(au + bv) − g(cw + dx)) Represented as graph: Here u,v,w,x are inputs (constants) and a,b,c,d are parameters (variables). f and g are the activation functions (with z as input) defined as below: f(z) = sigm(z) g(z) = tanh(z) Note that here E is a function of parameters a,b,c,d. Compute the partial derivatives of E with respect to the parameters a, b, c and d i.e. ∂E∂a , ∂E∂b , ∂E∂c and . Solution: (b) Assume that z = f(x,y), where x = uv and . We use fx to denote the partial derivative . Using the chain rule, express and in terms of u, v, fx and fy. Solution: (c) Given the change of variables as mentioned in the previous part: x = uv and , calculate the Jacobian of this transformation. Solution: (d) Calculate the Jacobian of the transformation for rectangular coordinates; i.e., the Jacobian of x = rsinθ, y = rcosθ, z = z, (hint: using the relevant partial derivatives) Solution: 3. Visit Taylor Series The first order derivative of a function f is defined by the following limit, (1) On observing the above definition we see that the derivative of a function is the ratio of change in the function value to the change in the function input, when we change the input by a small quantity (infinitesimally small). A first degree approximation based on eq. 1 would be the following. (2) Consider f(x) = ln(x + 5). (a) Estimate the value of f(1),f(1.1) and f(2.5) using the above formula. Solution: (b) Compare these estimates to the actual values of function f(1),f(1.1) and f(2.5). Explain the discrepancy as we increase the value. Solution: (c) Can we get a better estimate of f(1),f(1.1) and f(2.5) ? How? Solution: (d) Consider g(x) = a + bex + c ∗ cos(x). Find a, b, c ∈ R such that g approximates f at x = 0. (i.e. by matching the (i) direct values (ii) first derivative and (iii) second derivative at x = 0). Solution: 4. Differentiation of function of multiple variables s1 = tan(w1x) s2 = sec(w2x + s1) s3 = sin(w3s1 + w4s2) s4 = cos(w5s3 + w6) y = tanh(w7s4 + w8) An alternative representation of the function y is given in the figure below.Compute the derivatives and (show all the steps). Solution: 5. Differentiation of vectors/matrices Consider vectors u,b ∈Rd, and matrix A ∈Rn×n. The derivative of a scalar f w.r.t. a vector u is a vector by itself, given by( Hint: The derivative of a scalar f w.r.t. a matrix X, is a matrix whose (i,j) component is , where Xij is the (i,j) component of the matrix X.) (a) Derive the expression for the derivative: ∇uTAu + bTu. Solution: (b) Compare your results with derivatives for the scalar equivalents of the above expressions au2 + bu. Solution: (c) Derive the Hessian: given that f = uTAu + bTu Solution:(a) One way to encode this sequence is to use fixed length code with each code word long enough to encode ten different symbols. How many bits would be needed for this 33-character phrase using such a fixed-length code? Solution: (b) What are the minimum number of bits needed (theoretically) to encode the entire phrase , assuming that each character is independent of the surrounding character? Hint: We can calculate the average information (in other words, bits needed) of a symbol using entropy information. Solution: 7. Plotting Functions for Great Good (a) Consider the variable x and functions h11(x), h12(x) and h21(x) such thatThe above set of functions are summarized in the graph below.Plot the following functions: h11(x), h12(x) and h21(x) for x ∈ (−1,1) Solution: (b) Now consider the variables x1,x2 and the functions h11(x1,x2),h12(x1,x2),h13(x1,x2),h14(x1,x2), h21(x1,x2),h22(x1,x2),h31(x1,x2) and f(x1,x2) such thatThe above set of functions are summarized in the graph below.Plot the following functions: h11(x1,x2),h12(x1,x2),h13(x1,x2),h14(x1,x2),h21(x1,x2), h22(x1,x2),h31(x1,x2) and f(x1,x2) for x1 ∈ (−5,5) and x2 ∈ (−5,5) Solution:
Objective: Problem Statement: In Assignment 2 on SQL, you have created a number of tables and populated them using sample data. You have also written ten SQL queries. In this assignment you have a to write a menu driven Java/C/python program, where the user will give a choice of query number and the program should print a formatted output of the query results on the screen. Also write a 11th query which is same as query number 1 in Assignment 2 but the name of the “event” should be input by the user. Submissions: You have to submit the java and C and python program (properly commented) which connects to either/both postgresql/mysql databases.. We will also ask you to demo the programs in your screen during next weeks lab hours. 1. JDBC: https://docs.oracle.com/javase/tutorial/jdbc/basics/index.html 2. ODBC: https://learn.microsoft.com/en-us/sql/odbc/reference/introduction-to-odbc?view=sql-serverver16 3. Python: https://www.postgresqltutorial.com/postgresql-python/connect/ https://dev.mysql.com/doc/connector-python/en/
Assignment 2: Database Design – SQL———————————————————————————–1. Define a relational schema to capture the above information. The schema should include table definitions, attribute definitions, and attribute data types.2. Create tables in SQL for the above schema.3. Insert sample records in the tables. At least 5 records should be inserted in each table.4. Write SQL and Relational Algebra Queries for the following:(i) Roll number and name of all the students who are managing the “Megaevent” (ii) Roll number and name of all the students who are managing “Megevent” as an “Secretary”. (iv) Name of all the colleges who have at least one participant in “Megaevent” (v) Name of all the events which is managed by a “Secretary” (vi) Name of all the “CSE” department student volunteers of “Megaevent” (vii) Name of all the events which has at least one volunteer from “CSE” (ix) Name of the department with the largest number of volunteers in all the events which has at least one participant from “IITB”Deliverable: (a) Write a report listing all the SQL commands, records inserted and output of queries. (b) A single script file with the commands (in sequence) – table create, record insert, sql queries in listed order. The file extension should be .sqlSubmission Details: The SQL queries will have to be executed from pgsql in your terminal in the next lab.
CSED342 – Artificial Intelligence General Instructions This (and every) assignment has a written part and a programming part. You should write both types of answers in submission.py between # BEGIN_YOUR_ANSWER and # END_YOUR_ANSWER Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided to you, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run all the tests, type python grader.py This will tell you only whether you passed the basic tests. On the hidden tests, the script will alert you if your code takes too long or crashes, but does not say whether you got the correct output. You can also run a single test (e.g., 3a-0-basic) by typing python grader.py 3a-0-basic We strongly encourage you to read and understand the test cases, create your test cases, not just blindly run grader.py. IntroductionFigure 1: Pac-Man, now with ghosts. For those of you not familiar with Pac-Man, it’s a game where Pac-Man (the yellow circle with a mouth in the above figure) moves around in a maze and tries to eat as many food pellets (the small white dots) as possible while avoiding the ghosts (the other two agents with eyes in the above figure). If Pac-Man eats all the food in a maze, it wins. The big white dots at the top-left and bottom-right corner are capsules, which give Pac-Man power to eat ghosts in a limited time window (but you won’t be worrying about them for the required part of the assignment). You can get familiar with the setting by playing a few games of classic Pac-Man, which we come to just after this introduction. In this project, you will design agents for the classic version of Pac-Man, including ghosts. Along the way, you will implement various search strategies. Files • submission.py : Where all of your multi-agent search agents will reside and the only file you need to concern yourself with for this assignment. • pacman.py : The main file that runs Pac-Man games. This file also describes a Pac-Man GameState type, which you will use extensively in this project • game.py : The logic behind how the Pac-Man world works. This file describes several supporting types like AgentState, Agent, Direction, and Grid. • util.py : Useful data structures for implementing search algorithms. • graphicsDisplay.py : Graphics for Pac-Man • graphicsUtils.py : Support for Pac-Man graphics • textDisplay.py : ASCII graphics for Pac-Man • ghostAgents.py : Agents to control ghosts • keyboardAgents.py : Keyboard interfaces to control Pac-Man • layout.py : Code for reading layout files and storing their contents Warmup First, play a game of classic Pac-Man to get a feel for the assignment: python pacman.py You can always add –frameTime 1 to the command line to run in ”demo mode” where the game pauses after every frame. Now, run the provided ReflexAgent in submission.py: python pacman.py -p ReflexAgent Note that it plays quite poorly even on simple layouts: python pacman.py -p ReflexAgent -l testClassic You can also try out the reflex agent on the default mediumClassic layout with one ghost or two. python pacman.py -p ReflexAgent -k 1 python pacman.py -p ReflexAgent -k 2 Note: you can never have more ghosts than the layout permits. Options: Default ghosts are random; you can also play for fun with slightly smarter directional ghosts using -g DirectionalGhost. You can also play multiple games in a row with -n. Turn off graphics with -q to run lots of games quickly. So, now that you are familiar enough with the interface, inspect the ReflexAgent code carefully (in submission.py) and make sure you understand what it’s doing. The reflex agent code provides some helpful examples of methods that query the GameState (a GameState specifies the full game state, including the food, capsules, agent configurations, and score changes: see submission.py for further information and helper methods) for information, which you will be using in the actual coding part. We are giving an exhaustive and very detailed description below, for the sake of completeness and to save you from digging deeper into the starter code. The actual coding part is very small – so please be patient if you think there is too much writing. Note: if you wish to run Pac-Man in the terminal using a text-based interface, check out the terminal directory. Problems Problem 1: Minimax Before you code up Pac-Man as a minimax agent, notice that instead of just one adversary, Pac-Man could have multiple ghosts as adversaries. So we will extend the minimax algorithm from class (which had only one min stage for a single adversary) to the more general case of multiple adversaries. In particular, your minimax tree will have multiple min layers (one for each ghost) for every max layer. Specifically, consider the limited depth tree minimax search with evaluation functions taught in class. Suppose there are n + 1 agents on the board, a0,…,an, where a0 is PacMan and the rest are ghosts. Pac-Man acts as a max agent and the ghosts act as min agents. A single depth consists of all n+1 agents making a move, so the depth 2 search will involve Pac-Man and each ghost moving two times. In other words, a depth of 2 corresponds to a height of 2(n + 1) in the minimax game tree. Problem 1a [2 points] Now fill out MinimaxAgent class in submission.py using the recurrence you designed. Remember that your minimax agent should work with any number of ghosts, and your minimax tree should have multiple min layers (one for each ghost) for every max layer. Your code should also expand the game tree to an arbitrary depth. Score the leaves of your minimax tree with the supplied self.evaluationFunction, which defaults to scoreEvaluationFunction. The class MinimaxAgent extends MultiAgentSearchAgent, which gives access to self.depth and self.evaluationFunction. Make sure your minimax code makes reference to these two variables where appropriate as these variables are populated from the command line options. Other functions that you might use in the code: GameState.getLegalActions() which returns all the possible legal moves, where each move is Directions.X for some X in the set NORTH, SOUTH, WEST, EAST, STOP. Go through ReflexAgent code as suggested before to see how the above is used and also for other important methods like GameState.getPacmanState(), GameState.getGhostStates(), GameState.getScore() etc. These are further documented inside the MinimaxAgent class. Hints and Observations • The evaluation function in this part is already written (self.evaluationFunction). You shouldn’t change this function but recognize that now we’re evaluating states rather than actions, as we were for the reflex agent. Look-ahead agents evaluate future states whereas reflex agents evaluate actions from the current state. Use self.evaluationFunction in your definition of Vmax,min wherever you used Eval(s) in part 1a. • The minimax values of the initial state in the minimaxClassic layout are 9, 8, 7, -492 for depths 1, 2, 3, and 4 respectively. You can use these numbers to verify if your implementation is correct. Note that your minimax agent will often win (just under 50% of the time for us–be sure to test on a large number of games using the -n and -q flags) despite the dire prediction of depth 4 minimax. python pacman.py -p MinimaxAgent -l minimaxClassic -a depth=4 • Pac-Man is always agent 0, and the agents move in order of increasing agent index. Use self.index in your minimax implementation, but only Pac-Man will actually be running your MinimaxAgent. • Functions are provided to get legal moves for Pac-Man or the ghosts and to execute a move by any agent. See GameState in pacman.py for details. • 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. • getAction should use Vmax,min to determine the best action for Pac-Man. • On larger boards such as openClassic and mediumClassic (the default), you’ll find Pac-Man to be good at not dying, but quite bad at winning. He’ll often thrash around without making progress. Don’t worry if you see this behavior. • Consider the following run: python pacman.py -p MinimaxAgent -l trappedClassic -a depth=3 Why do you think Pac-Man rushes the closest ghost in minimax search on trappedClassic? • You can assume that you will always have at least one action from which to choose in getAction. • getQ should return Qmax,min for the current state given action. Problem 2: Expectimax Random ghosts are of course not optimal minimax agents, so modeling them with minimax search is not optimal. Let’s assume that ghosts follow the uniform policy, therefore ghosts take legal actions uniformly in any state. Before implementing it, first extend Expectimax recurrence, so the algorithm considers multiple ghosts as opponents.Your recurrence should resemble that of Problem 1a Problem 2a [2 points] Fill in ExpectimaxAgent, where your agent will no longer take the min over all ghost actions, but the expectation according to your agent’s model of how the ghosts act. Assume Pac-Man is playing against RandomGhosts, which each choose getLegalActions uniformly at random. You should now observe a more cavalier approach to close quarters with ghosts. In particular, if Pac-Man perceives that he could be trapped but might escape to grab a few more pieces of food, he’ll at least try: python pacman.py -p ExpectimaxAgent -l trappedClassic -a depth=3 Problem 3: BiasedExpectimax Now assume that policy ghosts follow is biased to select to stop (i.e. Directions.STOP). Specifically, ghosts decide their next action according to the following distribution: for a = Directions.STOP elsewhere, where A is a set of legal actions of a player from the current state. Problem 3a [6 points] Fill in BiasedExpectimaxAgent. This time, your agent should take the expectation over ghosts’ biased action policy. Assume Pac-Man is playing against RandomGhosts which are likely to choose to stop in place. Your agent now would show some foolish actions. In particular, Pac-Man sometimes rushes to the very-close ghost even though there are no benefits for the game score (i.e. food pellets): python pacman.py -p BiasedExpectimaxAgent -l trappedClassic -a depth=3 Compared to the expectimax, the winning rate would still be half. The final score, however, would change when Pac-Man loses: you will get -503 not -502. In case the game loses, Pac-Man will stop to move between the two approaching ghosts before it dies. Do you know why? Problem 4: Expectiminimax In the real world, it is not the best prediction that treating (if playing with multiple opponents) all adversaries follow the same policy. From now on, you assume that ghosts are divided into two groups of following either min policy or random policy. Specifically, the ghosts with odd-number select the action for the minimum value and the ghosts with evennumber select the action randomly according to a certain distribution. For the simplicity of your implementation, suppose the action chosen by even-numbered ghosts is from uniform distribution. Problem 4a [4 points] Fill in ExpectiminimaxAgent, where your agent will take the min over half of the ghosts and the expectation over others. Assume Pac-Man is playing against RandomGhosts, some choosing the worst action for Pac-Man and others uniformly randomly choosing the action: python pacman.py -p ExpectiminimaxAgent -l minimaxClassic -a depth=4 The expectiminimax values of the initial state in the minimaxClassic layout are almost similar to the minimax values. They would be 9.0, 8.0, 7.0, and 263.75 for depths 1, 2, 3, and 4 respectively. Why the values for the expectiminimax and minimax are same for depths 1, 2, and 3 but differ for depth 4? Problem 5: Alpha-beta pruning Problem 5a [8 points] Make a new agent that uses alpha-beta pruning to more efficiently explore the expectiminimax tree, in AlphaBetaAgent. Again, your algorithm will be slightly more general than the pseudo-code in the slides, so part of the challenge is to extend the alpha-beta pruning logic appropriately to multiple expectiminimizer agents. You should see a speed-up. Ideally, depth 3 on mediumClassic should run in just a few seconds per move or faster. python pacman.py -p AlphaBetaAgent -a depth=3 The AlphaBetaAgent expectiminimax values should be identical to the ExpectiminimaxAgent expectiminimax values, although the actions it selects can vary because of different tiebreaking behavior. Again, the expectiminimax values of the initial state in the minimaxClassic layout are 9.0, 8.0, 7.0, and 263.75 for depths 1, 2, 3, and 4, respectively. Running the command given above this paragraph, the expectiminimax values of the initial state should be 9.0, 18.0, 27.0, and 36.0 for depths 1, 2, 3, and 4, respectively. Problem 6: Evaluation function Problem 6a [8 points] After implementing it, choose the Pac-Man agent model to be used for the test. You can choose among the agents you’ve implemented in Problem 1-5 or design your own agent model. You can test your code with: python pacman.py -l smallClassic -p ExpectimaxAgent -a evalFn=better -q -n 20 python pacman.py -l smallClassic -p MyOwnAgent -a evalFn=better -q -n 20 We will run your Pac-Man agent 20 times, and calculate the average score you obtained. If your average score is less than 1000, you’ll get no points. If your average score is more than 1500, you’ll get 8 points. Check the grader.py to see how the scores are calculated. Hints and Observations • Having gone through the rest of the assignment, you should play Pac-Man again yourself and think about what kinds of features you want to add to the evaluation function. How can you add multiple features to your evaluation function? • For your information, our solution code gets more than 1600 scores on average with various random seeds.
CSED342 – Artificial Intelligence General Instructions This assignment has only a programming part. ¥This icon means you should write code. You can add other helper functions outside the answer block if you want. Do not make changes to files other than submission.py. You should modify the code in submission.py between # BEGIN_YOUR_ANSWER and # END_YOUR_ANSWER Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided to you, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run all the tests, type python grader.py This will tell you only whether you passed the basic tests. On the hidden tests, the script will alert you if your code takes too long or crashes, but does not say whether you got the correct output. You can also run a single test (e.g., 3a-0-basic) by typing python grader.py 3a-0-basic We strongly encourage you to read and understand the test cases, create your own test cases, and not just blindly run grader.py.The search algorithms explored in the previous assignment work great when you know exactly the results of your actions. Unfortunately, the real world is not so predictable. One of the key aspects of an effective AI is the ability to reason in the face of uncertainty. Markov decision processes (MDPs) can be used to formalize uncertain situations. In this homework, you will implement algorithms to find the optimal policy in these situations. You will then formalize a modified version of Blackjack as an MDP, and apply your algorithm to find the optimal policy. Problem 1. Value Iteration (Volcano Crossing)Figure 1: The example image of Volcano Crossing introduced during the class. In this problem, you will handle an algorithm that performs value iterations for the Volcano Crossing case. There is a grid-world modeled as an M by N grid of states (where M and N are positive integers). The grid world contains at least one volcano grid and one island grid. If the agent moves to any volcano cell, it receives a negative integer reward. If the agent moves to an island cell, it receives a reward of a positive integer. Whenever the agent reaches any island or volcano cell, the travel ends. To simplify the discussion, we assume that the transition probability is 1 (There is no slip, so the agent will go exactly to the cell it intends to). We only consider the discount factor (which is greater than 0 and less than or equal to 1) and the reward per move (moveReward, which is less than or equal to 0). The agent can move in four directions: east, south, west, and north. If the agent tries to move off the grid, it remains in the same cell. Problem 1a [5 points] ¥ VolcanoCrossing initializes with environment information regarding the grid world (provided as a numpy.ndarray), the discount rate, and the moveReward. When executing VolcanoCrossing.value_iteration(n), the algorithm performs n iterations for the given environment and return the value table containing the value Vn(s) for each state s. To ensure that the value iteration operates correctly, implement VolcanoCrossing.value_update to appropriately update the value table. Problem 2. BlackjackYou will be creating a MDP to describe a modified version of Blackjack. (Before reading the description of the task, first check how util.ValueIteration.solve finds the optimal policy of a given MDP such as util.NumberLineMDP.) For our version of Blackjack, the deck can contain an arbitrary collection of cards with different values, each with a given multiplicity. For example, a standard deck would have card values [1,2,…,13] and multiplicity 4. You could also have a deck with card values [1,5,20]. The deck is shuffled (each permutation of the cards is equally likely). The game occurs in a sequence of rounds. Each round, the player either (i) takes the next card from the top of the deck (costing nothing), (ii) peeks at the top card (costing peekCost, in which case the card will be drawn in the next round), or (iii) quits the game. (Note: it is not possible to peek twice in a row; if the player peeks twice in a row, then succAndProbReward() should return [].) The game continues until one of the following conditions becomes true: • The player quits, in which case her reward is the sum of the cards in her hand. • The player takes a card, and this leaves her with a sum that is strictly greater than the threshold, in which case her reward is 0. • The deck runs out of cards, in which case it is as if she quits, and she gets a reward which is the sum of the cards in her hand. In this problem, your state s will be represented as a triple: (totalCardValueInHand, nextCardIndexIfPeeked, deckCardCounts) As an example, assume the deck has card values [1,2,3] with multiplicity 1, and the threshold is 4. Initially, the player has no cards, so her total is 0; this corresponds to state (0, None, (1, 1, 1)). At this point, she can take, peek, or quit. • If she takes, the three possible successor states (each has 1/3 probability) are (1, None, (0, 1, 1)) (2, None, (1, 0, 1)) (3, None, (1, 1, 0)) She will receive reward 0 for reaching any of these states. • If she instead peeks, the three possible successor states are (0, 0, (1, 1, 1)) (0, 1, (1, 1, 1)) (0, 2, (1, 1, 1)) She will receive reward -peekCost to reach these states. From (0, 0, (1, 1, 1)), taking yields (1, None, (0, 1, 1)) deterministically. • If she quits, then the resulting state will be (0, None, None) (note setting the deck to None signifies the end of the game). As another example, let’s say her current state is (3, None, (1, 1, 0)). • If she quits, the successor state will be (3, None, None). • If she takes, the successor states are (3 + 1, None, (0, 1, 0)) or (3 + 2, None, None). Note that in the second successor state, the deck is set to None to signify the game ended with a bust. You should also set the deck to None if the deck runs out of cards. Problem 2a [5 points] ¥ Your task is to implement the game of Blackjack as a MDP by filling out the succAndProbReward() function of class BlackjackMDP. Problem 3: Learning to Play Blackjack So far, we’ve seen how MDP algorithms can take an MDP which describes the full dynamics of the game and return an optimal policy. But suppose you go into a casino, and no one tells you the rewards or the transitions. We will see how reinforcement learning can allow you to play the game and learn the rules at the same time! Problem 3a [5 points] ¥ We are using Q-learning with function approximation, which means Qˆopt(s,a) = w · ϕ(s,a), where in code, w is self.weights, ϕ is the featureExtractor function, and Qˆopt is self.getQ. We have implemented Qlearning.getAction as a simple ϵ-greedy policy. Your job is to implement Qlearning.incorporateFeedback, which should take an (s,a,r,s′) tuple and update self.weights according to the standard Q-learning update. Problem 3b [5 points] ¥ Now, you’ll implement SARSA, which can be considered as a variation of Q-learning. Your task is to fill in incorporateFeedback of SARSA, which is same with Qlearning except the update equation. Problem 3c [5 points] ¥ Now, we’ll incorporate domain knowledge to improve the generalization of RL algorithms for BlackjackMDP. Your task is to implement blackjackFeatureExtractor as described in the code comments in submission.py. This way, the RL algorithm can use what it learned about some states to improve its prediction performance on other states. Using the feature extractor, you should be able to get pretty close to the optimum on some large instances of BlackjackMDP.
CSED342 – Artificial Intelligence General Instructions You should write answers in submission.py between # BEGIN_YOUR_ANSWER and # END_YOUR_ANSWER In Problem 1 you just need to provide your answers. In Problem 2 and Problem 3 you have to implement some functions. You can add other helper functions outside the answer block if you want. Do not make changes to files other than submission.py. Please use Python 3.7 and NumPy to develop your code. You can refer to the official documentation of Numpy to install it. We recommend you use Conda to set up the environment. You have to write answers in the same format as provided in submission.py. Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided to you, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run all the tests, type python grader.py This will tell you only whether you passed the basic tests. On the hidden tests, the script will alert you if your code takes too long or crashes, but does not say whether you got the correct output. You can also run a single test (e.g., 3a-0-basic) by typing python grader.py 3a-0-basic We strongly encourage you to read and understand the test cases, create your own test cases, and not just blindly run grader.py.Advice for this homework: • Words are simply strings separated by whitespace. Don’t normalize the capitalization of words (treat great and Great as different words). • You might find some useful functions in util.py. Have a look around in there before you start coding. Problems Problem 1. Hinge Loss Here are two reviews of “Frozen,” courtesy of Rotten Tomatoes (no spoilers!):Rotten Tomatoes has classified these reviews as “positive” and “negative,” respectively, as indicated by the in-tact tomato on the left and the splattered tomato on the right. In this assignment, you will create a simple text classification system that can perform this task automatically. Problem 1a [2 points] We’ll warm up with the following set of four mini-reviews, each labeled positive (+1) or negative (−1): • (+1) so interesting • (+1) great plot • (−1) so bored • (−1) not interesting Each review x is mapped onto a feature vector ϕ(x), which maps each word to the number of occurrences of that word in the review. For example, the first review maps to the (sparse) feature vector ϕ(x) = {so : 1,interesting : 1}. Recall the definition of the hinge loss: Losshinge(x,y,w) = max{0,1 − w · ϕ(x)y}, where y is the correct label. Suppose we run stochastic gradient descent, updating the weights according to w ← w − η∇wLosshinge(x,y,w), once for each of the four examples in order. After the classifier is trained on the given four data points, what are the weights of the six words (‘so’, ‘interesting’, ‘great’, ‘plot’,‘bored’, ‘not’) that appear in the above reviews? Use η = 1 as the step size and initialize w = [0,…,0]. Assume that ∇wLosshinge(x,y,w) = 0 when the margin is exactly 1. Problem 2: Sentiment ClassificationIn this problem, we will build a binary linear classifier that reads movie reviews and guesses whether they are “positive” or “negative.” Problem 2a [2 points] Implement the function extractWordFeatures, which takes a review (string) as input and returns a feature vector ϕ(x) (you should represent the vector ϕ(x) as a dict in Python). Problem 2b [8 points] We’re going to train a linear predictor, which can be represented by a logistic regression model. Here is the definition of linear predict: if w · ϕ(x) > 0 if w · ϕ(x) < 0where σ is a logistic(or sigmoid) function. Your task is to implement the function learnPredictor using stochastic gradient descent, minimizing the negative log-likelihood loss (NLL) defined as: LossNLL(x,y,w) = − log(pw(y | x))You should first derive ∇wLossNLL(x,y,w), then exploit the formula to update weights for each example. Initialize the weights w as 0. Also, you can print the training error and test error after each iteration through the data, so it’s easy to see if your code is working. Problem 2c [3 points] The previous features include unigram(single) words only, which cannot consider the context of a word in an utterance. In this task, we’ll incorporate n-gram words into features. In other words, the feature vector will count the number of occurrences of consecutive words of length n. Implement extractNgramFeatures which extracts n-gram word features. Problem 3: Multi-Layer Perceptron & Backpropagation In this problem, we will build a binary non-linear classifier with Multi-Layer Perceptron (MLP) and train the classifier with the NLL loss using stochastic gradient descent. Note that you are not allowed to use Python libraries that support automatic differentiation (e.g., PyTorch, TensorFlow). Use Numpy to implement your codes. Suppose we have a feature extractor ϕ that produces 2-dimensional feature vectors, and a training dataset Dtrain = {(x1,y1),(x2,y2),(x3,y3),(x4,y4)} (a.k.a XOR problem) with 1. ϕ(x1) = [0,0], y1 = 0 2. ϕ(x2) = [0,1], y2 = 1 3. ϕ(x3) = [1,0], y3 = 1 4. ϕ(x4) = [1,1], y4 = 0. Problem 3a [4 points] Implement the forward function in MLPBinaryClassifier to predict the likelihood of y = 1 using 2-dimensional features with sigmoid activation. Do not modify the init function of MLPBinaryClassifier provided. Note that you need to save intermediate activations within the forward function for backpropagation (Problem 3b). Problem 3b [8 points] Implement the loss and backward functions in MLPBinaryClassifier to backpropagate the negative log-likelihood (NLL) loss to network parameters: W1, b1, W2, and b2. Utilize the saved activations from the forward process to compute the gradient for each parameter. Problem 3c [2 points]
CSED342 – Artificial Intelligence General Instructions Assignment 1 has four problems – problem 0, 1, 2, and 3. You only need to submit problem 1, 2, and 3. Problem 0 is not be graded, but must be solved by yourself before participating in this course. This assignment has been developed in Python 3.8, so please use Python 3.8 to implement your code. we recommend using Conda environment. You should modify the code in submission.py between # BEGIN_YOUR_ANSWER and # END_YOUR_ANSWER You can add other helper functions outside the answer block if you want, but do not import other libraries and do not make changes to files other than submission.py. You can solve all the problems without any libraries other than collections and math. Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run all the tests, type python grader.py This will tell you only whether you passed the basic tests. The script will alert you if your code takes too long or crashes on the hidden tests, but does not say whether you got the correct output. You can also run a single test (e.g., 2a-0-basic) by typing python grader.py 2a-0-basic We strongly encourage you to read and understand the test cases, create your own test cases, and not just blindly run grader.py. Problems Problem 0. Optimization and probability In this class, we will cast AI problems as optimization problems, that is, finding the best solution in a rigorous mathematical sense. At the same time, we must be adept at coping with uncertainty in the world, and for that, we appeal to tools from probability. The three problems below will not be scored, but please solve them because they are basic concepts. Problem 0a [0 points] Suppose you repeatedly roll a fair six-sided dice until you roll a 6 (and then you stop). Every time you roll a 3, you win 2 points, and every time you roll a 1 or a 2, you lose 1 points. You do not win or lose any points if you roll a 4 or a 5. What is the expected number of points you will have when you stop? Problem 0b [0 points] Suppose the probability of a coin turning up heads is 0 < p < 1, and that we flip it 5 times and get {H,T,H,H,T}. We know the probability (likelihood) of obtaining this sequence is L(p) = p(1 − p)pp(1 − p) = p3(1 − p)2. Now let’s go backward and ask the question: what is the value of p that maximizes L(p)? Hint: Consider taking the derivative of logL(p). Taking the derivative of L(p) works too, but it is cleaner and more natural to differentiate logL(p). You can verify for yourself that the value of p which minimizes logL(p) must also minimize L(p). Problem 0c [0 points] Let’s practice taking gradients, which is a key operation for being able to optimize continuous functions. For w ∈Rd and constants ai,bj ∈Rd and λ ∈R, define the scalar-valued function , where w, ai and bj are column vectors (e.g. w = (w1,…,wd)⊤) and is known as the L2 norm. Compute the gradient ∇wf(w). Recall: the gradient is a d-dimensional vector of the partial derivatives with respect to each wi: . If you’re not comfortable with vector calculus, first warm up by working out this problem using scalars in place of vectors and derivatives in place of gradients. Not everything for scalars goes through for vectors, but the two should at least be consistent with each other (when d = 1). Do not write out summation over dimensions, because that gets tedious. Problem 1. Implementing string functions In this problem, you will implement short functions that handle Python strings. The main purpose of this exercise is to familiarize yourself with Python and strings. If you’re new to Python, the following articles provide pointers to various tutorials and examples for the language: • Python for Programmers: https://wiki.python.org/moin/BeginnersGuide/Programmers • Example programs of increasing complexity: https://wiki.python.org/moin/SimplePrograms Hint: You can use the .split() method to split a string into a list. Problem 1a [4 points] Implement find alphabetically first word in submission.py. Problem 1b [4 points] Implement find frequent words in submission.py. Problem 1c [4 points] Implement find non singleton words in submission.py. Problem 2. Implementing vector operations In this problem, you will implement a bunch of short functions related to vector representations. The main purpose of this exercise is to understand vector representations and operations in programming. Problem 2a [4 points] Implement dense vector dot product in submission.py. Problem 2b [4 points] Implement increment dense vector in submission.py. Problem 2c [4 points] Implement dense to sparse vector in submission.py. Problem 2d [4 points] Implement sparse vector dot product in submission.py. Problem 2e [4 points] Implement increment sparse vector in submission.py. Problem 2f [4 points] Implement euclidean distance in submission.py. Problem 3. Advanced Programming Problem 3a [4 points] Implement mutate sentence in submission.py. Hint: You can consider Depth First Search (DFS) to solve this problem.
CSED342 – Artificial Intelligence General Instructions You should write both types of answers in submission.py between # BEGIN_YOUR_ANSWER and # END_YOUR_ANSWER You can implement other helper functions outside the answer block if you want, but must not add other libraries. Do not make changes to files other than submission.py. Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided to you, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run all the tests, type python grader.py This will tell you only whether you passed the basic tests. On the hidden tests, the script will alert you if your code takes too long or crashes, but does not say whether you got the correct output. You can also run a single test (e.g., 2a-0-basic) by typing python grader.py 3a-0-basic We strongly encourage you to read and understand the test cases, create your own test cases, and not just blindly run grader.py. $ conda create -n assn7 python=3.9 $ conda activate assn7 Introduction This assignment is a modified version of the Driverless Car assignment written by Chris Piech. A study by the World Health Organisation found that road accidents kill a shocking 1.24 million people a year worldwide. In response, there has been great interest in developing autonomous driving technology that can drive with calculated precision and reduce this death toll. Building an autonomous driving system is an incredibly complex endeavor. In this assignment, you will focus on the sensing system, which allows us to track other cars based on noisy sensor readings. Getting started. Let’s start by trying to drive manually: python drive.py -l lombard -i none You can steer by either using the arrow keys (↑, ←, →) or ’w’, ’a’, and ’d, and quit drive.py by using ’q’. Note that you cannot reverse the car or turn in place. Your goal is to drive from the start to finish (the green box) without getting in an accident. How well can you do on crooked Lombard street without knowing the location of other cars? Don’t worry if you aren’t very good; the staff was only able to get to the finish line 4/10 times. This 60% accident rate is pretty abysmal, which is why we’re going to build an AI to do this. Flags for python drive.py: • -a: Enable autonomous driving (as opposed to manual). • -i : Use none, exactInference, particleFilter to (approximately) compute the belief distributions. • -l: Use this map (e.g. small or lombard). Defaults to small. • -d: Debug by showing all the cars on the map. • -p: All other cars remain parked (so that they don’t move). Modeling car locations. We assume that the world is a two-dimensional rectangular grid on which your car and K other cars reside. At each time step t, your car gets a noisy estimate of the distance to each of the cars. As a simplifying assumption, we assume that each of the K other cars moves independently and that the noise in sensor readings for each car is also independent. Therefore, in the following, we will reason about each car independently (notationally, we will assume there is just one other car). At each time step t, let Ct ∈ R2 be a pair of coordinates representing the actual location of the single other car (which is unobserved). We assume there is a local conditional distribution p(ct | ct−1) which governs the car’s movement. Let at ∈ R2 be your car’s position, which you observe and also control. To minimize costs, we use a simple sensing system based on a microphone. The microphone provides us with Dt, which is a Gaussian random variable with mean equal to the distance between your car and the other car and variance σ2 (in the code, σ is Const.SONAR_STD, which is about two-thirds the length of a car). In symbols, Dt ∼ N(∥at − Ct∥,σ2). (1) For example, if your car is at at = (1,3) and the other car is at Ct = (4,7), then the actual distance is 5 and Dt might be 4.6 or 5.2, etc. Use util.pdf(mean, std, value) to compute the probability density function (PDF) of a Gaussian with given mean and standard deviation, evaluated at value. Note that the PDF does not return a probability (densities can exceed 1), but for the purposes of this assignment, you can get away with treating it like a probability. The Gaussian probability density function for the noisy distance observation Dt, which is centered around your distance to the car µ = ∥at − Ct∥:The figure below shows another example where one black car and our (orange) car are located in the 2D grid and the sensor estimates the distances of the black car from our car. Note that we can access the information of distances (Dt) measured by the sensor, but we’re not provided with the exact locations (Ct) of the black car. Theory. Here’s what the Bayesian network (it’s an HMM, in fact) for car tracking looks like:p(ct | d1:t) = p(ct | d1:t−1,dt) ∝ p(dt | d1:t−1,ct)p(ct | d1:t−1) (∵ Bayes rule) = p(dt | ct)p(ct | d1:t−1), (∵ Markov model/independence) and p(ct | d1:t−1) = Xp(ct,ct−1 | d1:t−1) ct−1 = Xp(ct | ct−1,d1:t−1)p(ct−1 | d1:t−1) (∵ Conditional prob.) ct−1 = Xp(ct | ct−1)p(ct−1 | d1:t−1), (∵ Markov model/independence) ct−1 where d1:t is also the observations from 1 to t time steps. We can see that p(ct | d1:t) is defined recursively over time. The following problems can be solved with this idea. Your job is to implement a car tracker that (approximately) computes the posterior distribution P(Ct | D1:t = d1:t) (your beliefs of where the other car is) and update it for each t = 1,2,…. We will take care of using this information to actual drive the car (i.e., set at as to avoid collision with ct), so you don’t have to worry about that part. To simplify things, we will discretize the world into tiles represented by (row, col) pairs, where 0 ≤ row < numRows and 0 ≤ col < numCols. For each tile, we store a probability distribution whose values can be accessed by self.belief.getProb(row, col). To convert from a tile to a location, use util.rowToY(row) and util.colToX(col). In Problem 1, you will warm up to a more simplified problem. In Problems 2 and 3, you will implement ExactInference, which computes a full distribution over tiles (row, col). In Problem 4, you will implement ParticleFilter, which works with particle-based representation of this distribution. Problem 1: Simplification Before we start implementing car tracking, let us look at a simplified version of the car tracking problem. Problem 1a [4 points] For this problem only, let Ct ∈ {0,1} be the actual location of the car, and Dt ∈ {0,1} be a sensor reading for the location of that car measured at time t. The distribution over the initial car position c1 ∈ {0,1} is defined as: . The following local conditional distribution governs the movement of the car (with probability ϵ, the car moves). For each t, . The following local conditional distribution governs the noise in the sensor reading (with probability η, the sensor reports the wrong position). For each t, ( p(dt | ct) = η if dt ̸= ct 1 − η if dt = ct. We have obtained sensor readings by time t, D1:t = d1:t, (D1 = d1,D2 = d2,…,Dt = dt). Implement all necessary methods for ConditionalProb class in submission.py to compute the posterior distribution P(Ct = ct | D1:t). Problem 2: Emission Probabilities In this problem, we assume that the other car is stationary (e.g., Ct = Ct−1 for all time steps t). You will implement a function observe that upon observing a new distance measurement Dt = dt updates the current posterior probability from P(Ct | D1 = d1,…,Dt−1 = dt−1) to P(Ct | D1 = d1,…,Dt = dt) ∝ P(Ct | D1 = d1,…,Dt−1 = dt−1)p(dt | ct), where we have multiplied in the emission probabilities p(dt | ct) described earlier. The current posterior probability is stored as self.belief in ExactInference, which you should update self.belief in place. Problem 2a [4 points] Fill in the observe method in the ExactInference class of submission.py. This method should update the posterior probability of each tile given the observed noisy distance. After you’re done, you should be able to find the stationary car by driving around it (-p means cars don’t move): Notes: • You can start driving with exact inference now. python drive.py -a -p -d -k 1 -i exactInference You can also turn off -a to drive manually. • Remember to normalize the updated posterior probability (see useful functions provided in util.py). • On the small map, the autonomous driver will sometimes drive in circles around the middle block before heading for the target area. In general, don’t worry too much about driving the car. Instead, focus on if your car tracker correctly infers the location of other cars. • Don’t worry if your car crashes once in a while! Accidents do happen, whether you are human or AI. However, even if there was an accident, your driver should have been aware that there was a high probability that another car was in the area. Problem 3: Transition Probabilities Now, let’s consider the case where the other car is moving according to transition probabilities p(ct+1 | ct). We have provided the transition probabilities for you in self.transProb. Specifically, self.transProb[(oldTile, newTile)] is the probability of the other car being in newTile at time step t + 1 given that it was in oldTile at time step t. In this part, you will implement a function elapseTime that updates the posterior probability about the location of the car at a current time t P(Ct = ct | D1 = d1,…,Dt = dt) to the next time step t + 1 conditioned on the same evidence, via the recurrence: . Again, the posterior probability is stored as self.belief in ExactInference. Problem 3a [4 points] Finish ExactInference by implementing the elapseTime method. When you are all done, you should be able to track a moving car well enough to drive autonomously: python drive.py -a -d -k 1 -i exactInference Notes: • You can also drive autonomously in the presence of more than one car: python drive.py -a -d -k 3 -i exactInference • You can also drive down Lombard: python drive.py -a -d -k 3 -i exactInference -l lombard Problem 4: Particle Filtering Though exact inference works well for the small maps, it wastes a lot of effort computing probabilities for cars being on unlikely tiles. We can solve this problem using a particle filter which has complexity linear in the number of particles rather than linear in the number of tiles. Implement all necessary methods for the ParticleFilter class in submission.py. When complete, you should be able to track cars nearly as effectively as with exact inference. Problem 4a [6 points] Some of the code has been provided for you. For example, the particles have already been initialized randomly. You need to fill in the observe and elapseTime functions. These should modify self.particles, which is a map from tiles (row, col) to the number of times that particle occurs, and self.belief, which needs to be updated after you resample the particles. You should use the same transition probabilities as in exact inference. The belief distribution generated by a particle filter is expected to look noisier compared to the one obtained by exact inference. python drive.py -a -i particleFilter -l lombard To debug, you might want to start with the parked car flag (-p) and the display car flag (-d).
CSED342 – Artificial Intelligence General Instructions ¥This icon means you should write code. You can add other helper functions outside the answer block if you want. Do not make changes to files other than submission.py. Please use Python 3.9 to develop your code. You have to write answers in the same format as provided in submission.py. You should modify the code in submission.py between # BEGIN_YOUR_ANSWER and # END_YOUR_ANSWER Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided to you, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run all the tests, type python grader.py This will tell you only whether you passed the basic tests. On the hidden tests, the script will alert you if your code takes too long or crashes, but does not say whether you got the correct output. You can also run a single test (e.g., 3a-0-basic) by typing python grader.py 3a-0-basic We strongly encourage you to read and understand the test cases, create your own test cases, and not just blindly run grader.py.In this assignment, you will formulate some problems as constraint satisfaction problems (CSPs) which consist of variables and unary or binary factors between the variables. Once you defined CSPs, you can find the solutions by backtracking search. However, its run-time increases exponentially with the number of variables and factors. Therefore, you will also implement some heuristics which reduce the required time for backtracking. Problem 0. Warm-up Problem 0a [3 points] ¥ Let’s consider a CSP with n variables X1,…,Xn and n − 1 binary factors t1,…,tn−1 where Xi ∈ {0,1} and ti(X) = xi Lxi+1. Note that the CSP has a chain structure. The figure below illustrates an example of the factor graph with 3 variables.Implement create_chain_csp() by creating a generic chain CSP with XOR as factors. Note: We’ve provided you with a CSP implementation in util.py which supports unary and binary factors. For now, you don’t need to understand the implementation, but please read the comments and get yourself familiar with the CSP interface. For this problem, you’ll need to use CSP.add_variable() and CSP.add_binary_factor(). Problem 1: CSP solving So far, we’ve only worked with unweighted CSPs, where fj(x) ∈{0,1}. In this problem, we will work with weighted CSPs, which associates a weight for each assignment x based on the product of m factor functions f1,…,fm: m Weight(x) = Yfj(x) j=1 where each factor fj(x) ≥ 0. Our goal is to find the assignment(s) x with the highest weight. As in problem 0, we will assume that each factor is either a unary factor (depends on exactly one variable) or a binary factor (depends on exactly two variables). For weighted CSP construction, you can refer to the CSP examples we provided in util.py for guidance (create_map_coloring_csp(), create_weighted_csp() and create_or_csp()). You can try these examples out by running python run_p1.py Take a look at BacktrackingSearch.reset_results() to see the other fields which are set as a result of solving the weighted CSP. You should read submission.BacktrackingSearch carefully to make sure that you understand how the backtracking search is working on the CSP. Problem 1a [4 points] ¥ Let’s create a CSP to solve the n-queens problem: Given an n × n board, we’d like to place n queens on this board such that no two queens are on the same row, column, or diagonal. Implement create_nqueens_csp() by adding n variables and some number of binary factors. Note that the solver collects some basic statistics on the performance of the algorithm. You should take advantage of these statistics for debugging and analysis. You should get 92 (optimal) assignments for n = 8 with exactly 2057 operations (number of calls to backtrack()). Hint: If you get a larger number of operations, make sure your CSP is minimal. Try to define the variables such that the size of domain is O(n). Problem 1b [4 points] ¥ You might notice that our search algorithm explores quite a large number of states even for the 8 × 8 board. Let’s see if we can do better. One heuristic we discussed in class is using most constrained variable (MCV): To choose an unassigned variable, pick the Xj that has the fewest number of values a which are consistent with the current partial assignment (a for which get_delta_weight() on Xj = a returns a non-zero value). Implement this heuristic in get_unassigned_variable() under the condition self.mcv = True. It should take you exactly 1361 operations to find all optimal assignments for 8 queens CSP — that’s 30% fewer! Some useful fields: • csp.unaryFactors[var][val] gives the unary factor value. • csp.binaryFactors[var1][var2][val1][val2] gives the binary factor value. Here, var1 and var2 are variables and val1 and val2 are their corresponding values. Hint: you can simply use get_delta_weight() rather than csp.unaryFactors and csp.binaryFactors. Problem 1c [5 points] ¥ You should make sure that your existing MCV implementation is compatible with your AC-3 algorithm as we will be using all three heuristics together during grading. With AC-3 enabled, it should take you 769 operations only to find all optimal assignments to 8 queens CSP — That is almost 45% fewer even compared with MCV! Hint 1: documentation for CSP.add_unary_factor() and CSP.add_binary_factor() can be helpful. Problem 2: Handling n-ary factors So far, our CSP solver only handles unary and binary factors, but for any non-trivial application, we would like to define factors that involve more than two variables. It would be nice if we could have a general way of reducing n-ary constraint to unary and binary constraints. In this problem, we will do exactly that for two types of n-ary constraints. The second type of n-ary factors is constraints on the sum over n variables. You are going to implement reduction of this type. Problem 2a [5 points] ¥ Let’s implement get_sum_variable(), which takes in a sequence of non-negative integervalued variables and returns a variable whose value is constrained to equal the sum of the variables. You will need to access the domains of the variables passed in, which you can assume contain only non-negative integers. The parameter maxSum is the maximum sum possible of all the variables. You can use this information to decide the proper domains for your auxiliary variables. How can this function be useful? Suppose we wanted to enforce the constraint [X1+X2+X3 ≤ K]. We would call get_sum_variable() on (X1,X2,X3) to get some auxiliary variable Y , and then add the constraint [Y ≤ K]. Note: You don’t have to implement the ≤ constraint for this part. Problem 2b [4 points] ¥ Let’s create a CSP. Suppose you have n light bulbs, where each light bulb i = 0,…,n − 1 is initially off. You also have m buttons which control the lights. For each light bulb i = 0,…,n − 1, we know the subset Li ⊆{0,…,m − 1} of buttons that control it. When button j is pressed, it toggles the state of light bulbs whose corresponding L includes j (If buttons B0 and B1 are pressed in the example shown in the figure, light bulbs L0, L2, and L3 will turn on, while L1 will remain off.). In code, Li corresponds to buttonSets[i]. Your goal is to turn on all the light bulbs by pressing a subset of the buttons. Implement create_lightbulb_csp to solve this problem.
CSED342 – Artificial Intelligence General Instructions This (and every) assignment has a written part and a programming part. You should write both types of answers in submission.py between # BEGIN_YOUR_ANSWER and # END_YOUR_ANSWER ÒThis icon means a written answer is expected. Some of these problems are multiple choice questions that impose negative scores if the answers are incorrect. So, don’t write answers unless you are confident. ¥This icon means you should write code. you can add other helper functions outside the answer block if you want. Do not make changes to files other than submission.py. Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided to you, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run all the tests, type python grader.py This will tell you only whether you passed the basic tests. On the hidden tests, the script will alert you if your code takes too long or crashes, but does not say whether you got the correct output. You can also run a single test (e.g., 3a-0-basic) by typing python grader.py 3a-0-basic We strongly encourage you to read and understand the test cases, create your own test cases, and not just blindly run grader.py. IntroductionFigure 1: Pac-Man, now with ghosts. For those of you not familiar with Pac-Man, it’s a game where Pac-Man (the yellow circle with a mouth in the above figure) moves around in a maze and tries to eat as many food pellets (the small white dots) as possible, while avoiding the ghosts (the other two agents with eyes in the above figure). If Pac-Man eats all the food in a maze, it wins. The big white dots at the top-left and bottom-right corner are capsules, which give Pac-Man power to eat ghosts in a limited time window (but you won’t be worrying about them for the required part of the assignment). You can get familiar with the setting by playing a few games of classic Pac-Man, which we come to just after this introduction. In this project, you will design agents for the classic version of Pac-Man, including ghosts. Along the way, you will implement various search strategies. Files • submission.py : Where all of your multi-agent search agents will reside and the only file you need to concern yourself with for this assignment. • pacman.py : The main file that runs Pac-Man games. This file also describes a Pac-Man GameState type, which you will use extensively in this project • game.py : The logic behind how the Pac-Man world works. This file describes several supporting types like AgentState, Agent, Direction, and Grid. • util.py : Useful data structures for implementing search algorithms. • graphicsDisplay.py : Graphics for Pac-Man • graphicsUtils.py : Support for Pac-Man graphics • textDisplay.py : ASCII graphics for Pac-Man • ghostAgents.py : Agents to control ghosts • keyboardAgents.py : Keyboard interfaces to control Pac-Man • layout.py : Code for reading layout files and storing their contents Warmup First, play a game of classic Pac-Man to get a feel for the assignment: python pacman.py You can always add –frameTime 1 to the command line to run in ”demo mode” where the game pauses after every frame. Now, run the provided ReflexAgent in submission.py: python pacman.py -p ReflexAgent Note that it plays quite poorly even on simple layouts: python pacman.py -p ReflexAgent -l testClassic You can also try out the reflex agent on the default mediumClassic layout with one ghost or two. python pacman.py -p ReflexAgent -k 1 python pacman.py -p ReflexAgent -k 2 Note: you can never have more ghosts than the layout permits. Options: Default ghosts are random; you can also play for fun with slightly smarter directional ghosts using -g DirectionalGhost. You can also play multiple games in a row with -n. Turn off graphics with -q to run lots of games quickly. So, now that you are familiar enough with the interface, inspect the ReflexAgent code carefully (in submission.py) and make sure you understand what it’s doing. The reflex agent code provides some helpful examples of methods that query the GameState (a GameState specifies the full game state, including the food, capsules, agent configurations and score changes: see submission.py for further information and helper methods) for information, which you will be using in the actual coding part. We are giving an exhaustive and very detailed description below, for the sake of completeness and to save you from digging deeper into the starter code. The actual coding part is very small – so please be patient if you think there is too much writing. Note: if you wish to run Pac-Man in the terminal using a text-based interface, check out the terminal directory. Problems Problem 1: Minimax Before you code up Pac-Man as a minimax agent, notice that instead of just one adversary, Pac-Man could have multiple ghosts as adversaries. So we will extend the minimax algorithm from class (which had only one min stage for a single adversary) to the more general case of multiple adversaries. In particular, your minimax tree will have multiple min layers (one for each ghost) for every max layer. Specifically, consider the limited depth tree minimax search with evaluation functions taught in class. Suppose there are n + 1 agents on the board, a0,…,an, where a0 is PacMan and the rest are ghosts. Pac-Man acts as a max agent, and the ghosts act as min agents. A single depth consists of all n + 1 agents making a move, so depth 2 search will involve Pac-Man and each ghost moving two times. In other words, a depth of 2 corresponds to a height of 2(n + 1) in the minimax game tree. Problem 1a [2 points] ¥ Now fill out MinimaxAgent class in submission.py using the recurrence you designed. Remember that your minimax agent should work with any number of ghosts, and your minimax tree should have multiple min layers (one for each ghost) for every max layer. Your code should also expand the game tree to an arbitrary depth. Score the leaves of your minimax tree with the supplied self.evaluationFunction, which defaults to scoreEvaluationFunction. The class MinimaxAgent extends MultiAgentSearchAgent, which gives access to self.depth and self.evaluationFunction. Make sure your minimax code makes reference to these two variables where appropriate as these variables are populated from the command line options. Other functions that you might use in the code: GameState.getLegalActions() which returns all the possible legal moves, where each move is Directions.X for some X in the set NORTH, SOUTH, WEST, EAST, STOP. Go through ReflexAgent code as suggested before to see how the above are used and also for other important methods like GameState.getPacmanState(), GameState.getGhostStates(), GameState.getScore() etc. These are further documented inside the MinimaxAgent class. Hints and Observations • The evaluation function in this part is already written (self.evaluationFunction). You shouldn’t change this function, but recognize that now we’re evaluating states rather than actions, as we were for the reflex agent. Look-ahead agents evaluate future states whereas reflex agents evaluate actions from the current state. Use self.evaluationFunction in your definition of Vmax,min wherever you used Eval(s) in part 1a. • The minimax values of the initial state in the minimaxClassic layout are 9, 8, 7, -492 for depths 1, 2, 3 and 4 respectively. You can use these numbers to verify if your implementation is correct. Note that your minimax agent will often win (just under 50% of the time for us–be sure to test on a large number of games using the -n and -q flags) despite the dire prediction of depth 4 minimax. python pacman.py -p MinimaxAgent -l minimaxClassic -a depth=4 • Pac-Man is always agent 0, and the agents move in order of increasing agent index. Use self.index in your minimax implementation, but only Pac-Man will actually be running your MinimaxAgent. • Functions are provided to get legal moves for Pac-Man or the ghosts and to execute a move by any agent. See GameState in pacman.py for details. • 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. • getAction should use Vmax,min to determine the best action for Pac-Man. • On larger boards such as openClassic and mediumClassic (the default), you’ll find Pac-Man to be good at not dying, but quite bad at winning. He’ll often thrash around without making progress. Don’t worry if you see this behavior. • Consider the following run: python pacman.py -p MinimaxAgent -l trappedClassic -a depth=3 Why do you think Pac-Man rushes the closest ghost in minimax search on trappedClassic? • You can assume that you will always have at least one action from which to choose in getAction. • getQ should return Qmax,min for the current state given action. Problem 2: Expectimax Random ghosts are of course not optimal minimax agents, so modeling them with minimax search is not optimal. Let’s assume that ghosts follow the uniform policy, therefore ghosts take legal actions uniformly in any state. Before implementing it, first extend Expectimax recurrence, so the algorithm considers multiple ghosts as opponents.Your recurrence should resemble that of Problem 1a Problem 2a [2 points] ¥ Fill in ExpectimaxAgent, where your agent will no longer take the min over all ghost actions, but the expectation according to your agent’s model of how the ghosts act. Assume Pac-Man is playing against RandomGhosts, which each choose getLegalActions uniformly at random. You should now observe a more cavalier approach to close quarters with ghosts. In particular, if Pac-Man perceives that he could be trapped but might escape to grab a few more pieces of food, he’ll at least try: python pacman.py -p ExpectimaxAgent -l trappedClassic -a depth=3 Problem 3: BiasedExpectimax Now assume that policy ghosts follow is biased to select to stop (i.e. Directions.STOP). Specifically, ghosts decide their next action according to the following distribution: for a = Directions.STOP elsewhere, where A is a set of legal actions of a player from the current state. Problem 3a [6 points] ¥ Fill in BiasedExpectimaxAgent. This time, your agent should take the expectation over ghosts’ biased action policy. Assume Pac-Man is playing against RandomGhosts which are likely to choose to stop in place. Your agent now would show some foolish actions. In particular, Pac-Man sometimes rush to the very-close ghost even though there are no benefits for the game score (i.e. food pellets): python pacman.py -p BiasedExpectimaxAgent -l trappedClassic -a depth=3 Compared to the expectimax, the winning rate would still be half. The final score, however, would change when Pac-Man loses: you will get -503 not -502. In case the game loses, Pac-Man will stop to move between the two approaching ghosts before it dies. Do you know why? Problem 4: Expectiminimax In real world, it is not the best prediction that treating (if playing with multiple opponents) all adversaries follow the same policy. From now on, you assume that ghosts are divided into two groups of following either min policy or random policy. Specifically, the ghosts with odd-number select the action for the minimum value and the ghosts with even-number select the action randomly according to a certain distribution. For the simplicity of your implementation, suppose the action chosen by even-numbered ghosts are from uniform distribution. Problem 4a [4 points] ¥ Fill in ExpectiminimaxAgent, where your agent will take the min over half of the ghosts and the expectation over others. Assume Pac-Man is playing against RandomGhosts, some choosing the worst action for Pac-Man and others uniformly randomly choosing the action: python pacman.py -p ExpectiminimaxAgent -l minimaxClassic -a depth=4 The expectiminimax values of the initial state in the minimaxClassic layout are almost similar to the minimax values. They would be 9.0, 8.0, 7.0 and 263.75 for depths 1, 2, 3 and 4 respectively. Why the values for the expectiminimax and minimax are same for depths 1, 2 and 3 but differ for depth 4? Problem 5: Alpha-beta pruning Problem 5a [8 points] ¥ Make a new agent that uses alpha-beta pruning to more efficiently explore the expectiminimax tree, in AlphaBetaAgent. Again, your algorithm will be slightly more general than the pseudo-code in the slides, so part of the challenge is to extend the alpha-beta pruning logic appropriately to multiple expectiminimizer agents. You should see a speed-up. Ideally, depth 3 on mediumClassic should run in just a few seconds per move or faster. python pacman.py -p AlphaBetaAgent -a depth=3 The AlphaBetaAgent expectiminimax values should be identical to the ExpectiminimaxAgent expectiminimax values, although the actions it selects can vary because of different tiebreaking behavior. Again, the expectiminimax values of the initial state in the minimaxClassic layout are 9.0, 8.0, 7.0, and 263.75 for depths 1, 2, 3, and 4, respectively. Running the command given above this paragraph, the expectiminimax values of the initial state should be 9.0, 18.0, 27.0, and 36.0 for depths 1, 2, 3, and 4, respectively. Problem 6: Evaluation function Problem 6a [8 points] ¥ After implementing it, choose the Pac-Man agent model to be used for the test. You can choose among the agents you’ve implemented in Problem 1-5 or design your own agent model. You can test your code with: python pacman.py -l smallClassic -p ExpectimaxAgent -a evalFn=better -q -n 20 python pacman.py -l smallClassic -p MyOwnAgent -a evalFn=better -q -n 20 We will run your Pac-Man agent 20 times, and calculate the average score you obtained. If your average score is less than 1000, you’ll get no point. If your average score is more than 1500, you’ll get 8 points. Check the grader.py to see how the scores are calculated. Hints and Observations • Having gone through the rest of the assignment, you should play Pac-Man again yourself and think about what kinds of features you want to add to the evaluation function. How can you add multiple features to your evaluation function? • For your information, our solution code gets more than 1600 scores in average with various random seeds.
CSED342 – Artificial Intelligence General Instructions This assignment has a written part and a programming part. ¥This icon means you should write code. You can add other helper functions outside the answer block if you want. Do not make changes to files other than submission.py. Please use Python 3.9 to develop your code. You have to write answers in the same format as provided in submission.py. You should modify the code in submission.py between # BEGIN_YOUR_ANSWER and # END_YOUR_ANSWER Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided to you, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run all the tests, type python grader.py This will tell you only whether you passed the basic tests. On the hidden tests, the script will alert you if your code takes too long or crashes, but does not say whether you got the correct output. You can also run a single test (e.g., 3a-0-basic) by typing python grader.py 3a-0-basic We strongly encourage you to read and understand the test cases, create your own test cases, and not just blindly run grader.py.The search algorithms explored in the previous assignment work great when you know exactly the results of your actions. Unfortunately, the real world is not so predictable. One of the key aspects of an effective AI is the ability to reason in the face of uncertainty. Markov decision processes (MDPs) can be used to formalize uncertain situations. In this homework, you will implement algorithms to find the optimal policy in these situations. You will then formalize a modified version of Blackjack as an MDP, and apply your algorithm to find the optimal policy. Problem 1: MDP Warm-up Consider an MDP problem. There are four states {SA,SB,SC,SD}, at each of which two actions {+,−} are available, and the state transition and reward have no randomness. All the (action, reward) pairs are described in Figure 1. Assume all the episodes have length 3 (e.g. SA −→+ SB −→− SA −→− SA).Figure 1: MDP problem with (action, reward) pairs. Problem 1a [2 points] Ò Find the optimal policy at the initial state SA with discount factor γ = 0.001. Justify your answer. Problem 1b [2 points] Ò Find the optimal policy at the initial state SA with discount factor γ = 0.999. Justify your answer. Problem 1c [2 points] Ò What is the optimal policy at the initial state SB? Explain your answer in terms of discount factor γ ∈ (0,1). Problem 2. Blackjack You will be creating a MDP to describe a modified version of Blackjack. (Before reading the description of the task, first check how util.ValueIteration.solve finds the optimal policy of a given MDP such as util.NumberLineMDP.) For our version of Blackjack, the deck can contain an arbitrary collection of cards with different values, each with a given multiplicity. For example, a standard deck would have card values [1,2,…,13] and multiplicity 4. You could also have a deck with card values [1,5,20]. The deck is shuffled (each permutation of the cards is equally likely). The game occurs in a sequence of rounds. Each round, the player either (i) takes the next card from the top of the deck (costing nothing), (ii) peeks at the top card (costing peekCost, in which case the card will be drawn in the next round), or (iii) quits the game. (Note: it is not possible to peek twice in a row; if the player peeks twice in a row, then succAndProbReward() should return [].) The game continues until one of the following conditions becomes true: • The player quits, in which case her reward is the sum of the cards in her hand. • The player takes a card, and this leaves her with a sum that is strictly greater than the threshold, in which case her reward is 0. • The deck runs out of cards, in which case it is as if she quits, and she gets a reward which is the sum of the cards in her hand. In this problem, your state s will be represented as a triple: (totalCardValueInHand, nextCardIndexIfPeeked, deckCardCounts) As an example, assume the deck has card values [1,2,3] with multiplicity 1, and the threshold is 4. Initially, the player has no cards, so her total is 0; this corresponds to state (0, None, (1, 1, 1)). At this point, she can take, peek, or quit. • If she takes, the three possible successor states (each has 1/3 probability) are (1, None, (0, 1, 1)) (2, None, (1, 0, 1)) (3, None, (1, 1, 0)) She will receive reward 0 for reaching any of these states. • If she instead peeks, the three possible successor states are (0, 0, (1, 1, 1)) (0, 1, (1, 1, 1)) (0, 2, (1, 1, 1)) She will receive reward -peekCost to reach these states. From (0, 0, (1, 1, 1)), taking yields (1, None, (0, 1, 1)) deterministically. • If she quits, then the resulting state will be (0, None, None) (note setting the deck to None signifies the end of the game). As another example, let’s say her current state is (3, None, (1, 1, 0)). • If she quits, the successor state will be (3, None, None). • If she takes, the successor states are (3 + 1, None, (0, 1, 0)) or (3 + 2, None, None). Note that in the second successor state, the deck is set to None to signify the game ended with a bust. You should also set the deck to None if the deck runs out of cards. Problem 2a [5 points] ¥ Your task is to implement the game of Blackjack as a MDP by filling out the succAndProbReward() function of class BlackjackMDP. Problem 3: Learning to Play Blackjack So far, we’ve seen how MDP algorithms can take an MDP which describes the full dynamics of the game and return an optimal policy. But suppose you go into a casino, and no one tells you the rewards or the transitions. We will see how reinforcement learning can allow you to play the game and learn the rules at the same time! Problem 3a [5 points] ¥ We are using Q-learning with function approximation, which means Qˆopt(s,a) = w · ϕ(s,a), where in code, w is self.weights, ϕ is the featureExtractor function, and Qˆopt is self.getQ. We have implemented Qlearning.getAction as a simple ϵ-greedy policy. Your job is to implement Qlearning.incorporateFeedback(), which should take an (s,a,r,s′) tuple and update self.weights according to the standard Q-learning update. Problem 3b [5 points] ¥ Now, you’ll implement SARSA, which can be considered as a variation of Q-learning. Your task is fill in incorporateFeedback of SARSA, which is same with Qlearning except the update equation. Problem 3c [5 points] ¥ Now, we’ll incorporate domain knowledge to improve generalization of RL algorithms for BlackjackMDP. Your task is to implement blackjackFeatureExtractor as described in the code comments in submission.py. This way, the RL algorithm can use what it learned about some states to improve its prediction performance on other states. Using the feature extractor, you should be able to get pretty close to the optimum on some large instances of BlackjackMDP.
CSED342 – Artificial Intelligence General Instructions This (and every) assignment has a written part and a programming part. ÒThis icon means a written answer is expected in writeup.pdf. Refer to writeup.tex for pdf file generation. ¥This icon means you should write code in submission.py. You should modify the code in submission.py between # BEGIN_YOUR_CODE and # END_YOUR_CODE but you can add other helper functions outside this block if you want. Do not make changes to files other than submission.py. Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided to you, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run all the tests, type python grader.py This will tell you only whether you passed the basic tests. On the hidden tests, the script will alert you if your code takes too long or crashes, but does not say whether you got the correct output. You can also run a single test (e.g., 3a-0-basic) by typing python grader.py 3a-0-basic We strongly encourage you to read and understand the test cases, create your own test cases, and not just blindly run grader.py.Problems In this homework, we consider two tasks: word segmentation and vowel insertion. Word segmentation often comes up in processing many non-English languages, in which words might not be flanked by spaces on either end, such as in written Chinese or in long compound German words. Vowel insertion is relevant in languages such as Arabic or Hebrew, for example, where modern script eschews notations for vowel sounds and the human reader infers them from context. More generally, it is an instance of a reconstruction problem given lossy encoding and some context. We already know how to optimally solve any particular search problem with graph search algorithms such as uniform cost search or A*. Our goal here is modeling — that is, converting real-world tasks into state-space search problems. Setup: n-gram language models and uniform-cost search Our algorithm will base segmentation and insertion decisions based on the cost of produced text according to a language model. A language model is some function of the processed text that captures its fluency by estimating the likelihood of text p(w1,w2,…,wN−1,wN) = A very common language model in NLP is an n-gram sequence model, which assumes p(wi|w1,…,wi−1) = p(wi|wi−(n−1),…,wi−1). We’ll use the n-gram model’s negative loglikelihood −logp(wi|wi−(n−1),…,wi−1) as a cost function c(wi−(n−1),wi−1,…,wi). The cost will always be positive, and lower costs indicate better fluency. As a simple example: in a case where n = 2 and c is our n-gram cost function, c(big, fish) would be low, but c(fish, fish) would be fairly high. u(w1) + u(w2) + u(w3) + u(w4). For a bigram model b (n = 2), the cost is b(w0,w1) + b(w1,w2) + b(w2,w3) + b(w3,w4), Problem 1. Word Segmentation In word segmentation, you are given as input a string of alphabetical characters ([a-z]) without whitespace, and your goal is to insert spaces into this string such that the result is the most fluent according to the language model. Problem 1a [4 points] ¥ Implement an algorithm that finds the optimal word segmentation of an input character sequence. Your algorithm will consider costs based simply on a unigram cost function. Before jumping into code, you should think about how to frame this problem as a statespace search problem. How would you represent a state? What are the successors of a state? What are the state transition costs? Uniform cost search (UCS) is implemented for you, and you should make use of it here. Fill in the member functions of the WordSegmentationProblem class and the segmentWords function. The argument unigramCost is a function that takes in a single string representing a word and outputs its unigram cost. You can assume that all the inputs would be in lower case. The function segmentWords should return the segmented sentence with spaces as delimiters, i.e. ‘ ’.join(words). For convenience, you can actually run python submission.py to enter a console in which you can type character sequences that will be segmented by your implementation of segmentWords. To request a segmentation, type seg mystring into the prompt. For example: >> seg thisisnotmybeautifulhouse Query (seg): thisisnotmybeautifulhouse this is not my beautiful house Console commands other than seg – namely ins and both – will be used for the upcoming parts of the assignment. Other commands that might help with debugging can be found by typing help at the prompt. You are encouraged to refer to NumberLineSearchProblem and GridSearchProblem implemented in util.py for reference. They don’t contribute to testing your submitted code but only serve as a guideline to how your code should look like. Problem 1b [6 points] ¥ Implement an algorithm that finds the optimal word segmentation for a given input character sequence, with the constraint that it can only have at most k words. This is called k-word segmentation. For example, if the input sequence is ‘pepperonimage’ and k is 2, it should be segmented into ‘pepperoni mage’ instead of ‘pepper on image’, even though the latter is more fluent. When you’ve completed your implementation, the function segmentKWords should return the k-segmented sentence with spaces as delimiters, i.e., ‘ ’.join(words). You can assume that k ranges from 1 to the length of the input sequence (or the number of characters in the sequence). The argument unigramCost is the same as in problem 1a. To test your implementation, use the k-seg command in the program console followed by the value of k. For example: >> k-seg 4 thisisnotmybeautifulhouse Query (k-seg) (k = 4): thisisnotmybeautifulhouse this isnotmy beautiful house Problem 2. Vowel Insertion Now you are given a sequence of English words with their vowels missing (A, E, I, O, and U; never Y). Your task is to place vowels back into these words in a way that maximizes sentence fluency (i.e., that minimizes sentence cost). For this task, you will use a bigram cost function. You are also given a mapping possibleFills that maps any vowel-free word to a set of possible reconstructions (complete words). For example, possibleFills(‘fg’) returns set([‘fugue’, ‘fog’]). Problem 2a [4 points] ¥ Implement an algorithm that finds optimal vowel insertions. Use the UCS subroutines. When you’ve completed your implementation, the function insertVowels should return the reconstructed word sequence as a string with space delimiters, i.e. ‘ ’.join(filledWords). Assume that you have a list of strings as the input, i.e. the sentence has already been split into words for you. Note that empty string is a valid element of the list. The argument queryWords is the input sequence of vowel-free words. Note well that the empty string is a valid such word. The argument bigramCost is a function that takes two strings representing two sequential words and provides their bigram score. The special out-ofvocabulary beginning-of-sentence word -BEGIN- is given by wordsegUtil.SENTENCE_BEGIN. The argument possibleFills is a function; it takes a word as string and returns a set of reconstructions. Note: If some vowel-free word w has no reconstructions according to possibleFills, your implementation should consider w itself as the sole possible reconstruction. Use the ins command in the program console to try your implementation. For example: >> ins thts m n th crnr Query (ins): thts m n th crnr thats me in the corner The console strips away any vowels you do insert, so you can actually type in plain English and the vowel-free query will be issued to your program. This also means that you can use a single vowel letter as a means to place an empty string in the sequence. For example: >> ins its a beautiful day in the neighborhood Query (ins): ts btfl dy n th nghbrhd its a beautiful day in the neighborhood Problem 2b [6 points] ¥ This time, you are given a sequence of English words with missing vowels and a set of specific vowels. Implement an algorithm for the limited vowel insertion problem that inserts vowels into the words without using the provided set of restricted vowels. Use the UCS subroutines. When you’ve completed your implementation, the function insertLimitedVowels should return the reconstructed word sequence containing only the allowed vowels as a string with space delimiters, i.e., ‘ ’.join(filledWords). The input set of restricted vowels is assumed to be given as a string (e.g., ‘a’, ‘iou’). The other assumptions and arguments queryWords, bigramCost, and possibleFills are the same as in problem 2a. To test your implementation, use the limited-ins command in the program console, followed by the string of restricted vowels. The query is preprocessed in the same way as the ins command. For example: >> limited-ins i thats me in the corner Query (limited-ins) (limited_vowels = ‘i’): thts m n th crnr thats me on the corner Problem 3: Putting It Together We’ll now see that it’s possible to solve both of these tasks at once. This time, you are given a whitespace- and vowel-free string of alphabetical characters. Your goal is to insert spaces and vowels into this string such that the result is the most fluent possible one. As in the previous task, costs are based on a bigram cost function. Problem 3a [6 points] ¥ Implement an algorithm that finds the optimal space and vowel insertions. Use the UCS subroutines. When you’ve completed your implementation, the function segmentAndInsert should return a segmented and reconstructed word sequence as a string with space delimiters, i.e. ‘ ’.join(filledWords). The argument query is the input string of space- and vowel-free words. The argument bigramCost is a function that takes two strings representing two sequential words and provides their bigram score. The special out-of-vocabulary beginning-of-sentence word -BEGINis given by wordsegUtil.SENTENCE_BEGIN. The argument possibleFills is a function; it takes a word as string and returns a set of reconstructions. Note: Unlike in problem 2, where a vowel-free word could (under certain circumstances) be considered a valid reconstruction of itself, here you should only include in your output words that are the reconstruction of some vowel-free word according to possibleFills. Additionally, you should not include words containing only vowels such as “a” or “I”; all words should include at least one consonant from the input string. Use the command both in the program console to try your implementation. Similar to ins command, vowels are striped and spaces are also ignored. For example: >> both imagine all the people Query (both): mgnllthppl imagine all the people Problem 4: A* search Now, we’ll apply A* search to accelerate search speed. First, you exercise by making a simple problem and a heuristic function to be familiar with A* search. Then, you make a heuristic function for the text reconstruction task. Problem 4a [4 points] ¥ In this problem, you should define your own simple search problem SimpleProblem anda heuristic function admissibleButInconsistentHeuristic. As the name suggests, the heuristic function should be admissible but not consistent, so A* cannot find the minimumcost path with the heuristic function. Also, we assume the heuristic returns 0 when givenan end state. Before implementing them, check UniformCostSearch and its parameter heuristic to examine how A* works. Problem 4b [6 points] ¥ We’re going to speed up the joint space and vowel insertion problem with A*. Recall that score an output using a bigram model b(w′,w) is more expensive than using a unigram model u(w) because we have to remember the previous word w′ in the state. Now let’s tackle the task by following the guideline below: Note: Don’t confuse ub defined here with the unigram cost function u used in Problem 1. 2. Implement RelaxedProblem which is a relaxed problem of JointSegmentationInsertionProblem. The relaxed problem calculate action’s cost based on wordCost. 3. Implement makeHeuristic which returns a consistent heuristic function for the given query. You can exploit RelaxedProblem and util.DynamicProgramming. 4. Finally implement fastSegmentAndInsert which should be faster than segmentAndInsert. You should use UniformCostSearch.solve with a proper heuristic argument.
CSED342 – Artificial Intelligence General Instructions You should write answers in submission.py between # BEGIN_YOUR_ANSWER and # END_YOUR_ANSWER In Problem 1 and Problem 3a you just need to provide your answers. In Problem 2 and Problem 3b you have to implement some functions. You can add other helper functions outside the answer block if you want. Do not make changes to files other than submission.py. Please use Python 3.9 to develop your code. You have to write answers in the same format as provided in submission.py. Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided to you, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run all the tests, type python grader.py This will tell you only whether you passed the basic tests. On the hidden tests, the script will alert you if your code takes too long or crashes, but does not say whether you got the correct output. You can also run a single test (e.g., 3a-0-basic) by typing python grader.py 3a-0-basic We strongly encourage you to read and understand the test cases, create your own test cases, and not just blindly run grader.py.Advice for this homework: • Words are simply strings separated by whitespace. Don’t normalize the capitalization of words (treat great and Great as different words). • You might find some useful functions in util.py. Have a look around in there before you start coding. Problems Problem 1. Hinge Loss Here are two reviews of “Frozen,” courtesy of Rotten Tomatoes (no spoilers!):Rotten Tomatoes has classified these reviews as “positive” and “negative,” respectively, as indicated by the in-tact tomato on the left and the splattered tomato on the right. In this assignment, you will create a simple text classification system that can perform this task automatically. Problem 1a [2 points] We’ll warm up with the following set of four mini-reviews, each labeled positive (+1) or negative (−1): • (+1) so touching • (+1) quite impressive • (−1) not impressive • (−1) quite boring Each review x is mapped onto a feature vector ϕ(x), which maps each word to the number of occurrences of that word in the review. For example, the first review maps to the (sparse) feature vector ϕ(x) = {so : 1,touching : 1}. Recall the definition of the hinge loss: Losshinge(x,y,w) = max{0,1 − w · ϕ(x)y}, where y is the correct label. Suppose we run stochastic gradient descent, updating the weights according to w ← w − η∇wLosshinge(x,y,w), once for each of the four examples in order. After the classifier is trained on the given four data points, what are the weights of the six words (‘so’, ‘touching’, ‘quite’, ‘impressive’,‘not’, ‘boring’) that appear in the above reviews? Use η = 1 as the step size and initialize w = [0,…,0]. Assume that ∇wLosshinge(x,y,w) = 0 when the margin is exactly 1. Problem 2: Sentiment ClassificationIn this problem, we will build a binary linear classifier that reads movie reviews and guesses whether they are “positive” or “negative.” Problem 2a [2 points] Implement the function extractWordFeatures, which takes a review (string) as input and returns a feature vector ϕ(x) (you should represent the vector ϕ(x) as a dict in Python). Problem 2b [8 points] We’re going to train a linear predictor, which can be represented by a logistic regression model. Here is the definition of linear predict: if w · ϕ(x) > 0 if w · ϕ(x) < 0where σ is a logistic(or sigmoid) function. Your task is to implement the function learnPredictor using stochastic gradient descent, minimizing the negative log-likelihood loss (NLL) defined as: LossNLL(x,y,w) = − log(pw(y | x))You should first derive ∇wLossNLL(x,y,w), then exploit the formula to update weights for each example. Also, you can print the training error and test error after each iteration through the data, so it’s easy to see if your code is working. Problem 2c [3 points] The previous features include unigram(single) words only, which cannot consider the context of a word in an utterance. In this task, we’ll incorporate n-gram words into features. In other words, feature vector will counts number of occurrences of consecutive words of length n. Implement extractNgramFeatures which extract n-gram word features. Problem 3: K-means Clustering Problem 3a [2 points] Suppose we have a feature extractor ϕ that produces 2-dimensional feature vectors, and a toy dataset Dtrain = {x1,x2,x3,x4} with 1. ϕ(x1) = [−1,0] 2. ϕ(x2) = [2,0] 3. ϕ(x3) = [0,3] 4. ϕ(x4) = [4,3] Run 2-means on this dataset. What are the final cluster centers µ? Run this algorithm until it converges, with initial centers: 1. µ1 = [−2,0] and µ2 = [3,0] 2. µ1 = [−1,−1] and µ2 = [2,3] Problem 3b [6 points] Implement the kmeans function. You should initialize your k cluster centers to random elements of examples.
CSED342 – Artificial Intelligence General Instructions Assignment 1 has three problems – problem 0, 1, 2. You only need to submit problem 1 and 2. Problem 0 is not graded, but must be solved by yourself before participating in this course. This assignment has been developed in Python 3.9, so please use Python 3.9 to implement your code. we recommend using Conda environment. You should modify the code in submission.py between # BEGIN_YOUR_ANSWER and # END_YOUR_ANSWER You can add other helper functions outside the answer block if you want, but do not import other libraries and do not make changes to files other than submission.py. Your code will be evaluated on two types of test cases, basic and hidden, which you can see in grader.py. Basic tests, which are fully provided to you, do not stress your code with large inputs or tricky corner cases. Hidden tests are more complex and do stress your code. The inputs of hidden tests are provided in grader.py, but the correct outputs are not. To run all the tests, type python grader.py This will tell you only whether you passed the basic tests. On the hidden tests, the script will alert you if your code takes too long or crashes, but does not say whether you got the correct output. You can also run a single test (e.g., 2a-0-basic) by typing python grader.py 2a-0-basic We strongly encourage you to read and understand the test cases, create your own test cases, and not just blindly run grader.py. Problems Problem 0. Optimization and probability In this class, we will cast AI problems as optimization problems, that is, finding the best solution in a rigorous mathematical sense. At the same time, we must be adroit at coping with uncertainty in the world, and for that, we appeal to tools from probability. The three problems below will not be scored, but please solve them because they are basic concepts. Problem 0a [0 points] Suppose you repeatedly roll a fair six-sided dice until you roll a 1 or a 2 (and then you stop). Every time you roll a 3, you lose 1 points, and every time you roll a 4, you win 2 points. You do not win or lose any points if you roll a 5 or a 6. What is the expected number of points you will have when you stop? Problem 0b [0 points] Suppose the probability of a coin turning up heads is 0 < p < 1, and that we flip it 5 times and get {H,T,H,T,T}. We know the probability (likelihood) of obtaining this sequence is L(p) = p(1 − p)p(1 − p)(1 − p) = p2(1 − p)3. Now let’s go backwards and ask the question: what is the value of p that maximizes L(p)? Hint: Consider taking the derivative of logL(p). Taking the derivative of L(p) works too, but it is cleaner and more natural to differentiate logL(p). You can verify for yourself that the value of p which minimizes logL(p) must also minimize L(p). Problem 0c [0 points] Let’s practice taking gradients, which is a key operation for being able to optimize continuous functions. For w ∈Rd and constants ai,bj ∈Rd and λ ∈R, define the scalar-valued function m n f(w) = XX(a⊤i w − b⊤j w)2 + λ∥w∥22, i=1 j=1 where w, ai and bj are column vectors (e.g. w = (w1,…,wd)⊤) and is known as the L2 norm. Compute the gradient ∇wf(w). Recall: the gradient is a d-dimensional vector of the partial derivatives with respect to each wi: . If you’re not comfortable with vector calculus, first warm up by working out this problem using scalars in place of vectors and derivatives in place of gradients. Not everything for scalars goes through for vectors, but the two should at least be consistent with each other (when d = 1). Do not write out summation over dimensions, because that gets tedious. Problem 1. Programming 1 In this problem, you will implement a bunch of short functions related vector representations. The main purpose of this exercise is to familiarize yourself with Python, and to understand vector representations in programming. If you’re new to Python, the following provide pointers to various tutorials and examples for the language: • Python for Programmers: https://wiki.python.org/moin/BeginnersGuide/Programmers • Example programs of increasing complexity: https://wiki.python.org/moin/SimplePrograms Problem 1a [2 points] Implement denseVectorDotProduct in submission.py. Problem 1b [2 points] Implement incrementDenseVector in submission.py. Problem 1c [2 points] Implement dense2sparseVector in submission.py. Problem 1d [2 points] Implement sparseVectorDotProduct in submission.py. Problem 1e [2 points] Implement incrementSparseVector in submission.py. Problem 2. Programming 2 In this problem, you will implement short functions more, and the main purpose of this exercise is also to familiarize yourself with Python. Problem 2a [2 points] Implement minkowskiDistance in submission.py. Problem 2b [2 points] Implement getLongestWord in submission.py. Problem 2c [2 points] Implement getFrequentWords in submission.py.
**** PLEASE READ THIS GRAY BOX CAREFULLY BEFORE STARTING THE ASSIGNMENT ****Evaluation policy: ■ 100% penalty is applied for that submission. ● Your code will be automatically tested using an evaluation program. ○ Each problem has the maximum score. ● We won’t accept any submission via email – it will be ignored.**** PLEASE READ THIS GRAY BOX CAREFULLY BEFORE STARTING THE ASSIGNMENT ****Coding: ● Please do not use the containers in C++ standard template library (STL). ○ Such as , , , and . ○ Any submission using the above headers will be disregarded.Submission: ● Compile your file(s) using C++ 11 compiler on ‘Replit’ or ‘Clion’ and check your program before the submission● All characters in submit.txt should be in uppercase letters, e.g., ‘TRUE’, ‘FALSE’, (except for [Task 1], [Task 2], …)● Files you need to submit. (Do not change the filename.) ○ pa4.cpp ○ graph.cpp and graph.hAny questions? ● Please use PLMS – Q&A board. (Questions should be written in English and uploaded publicly)1. Undirected Graph – Cycle (1 pts) a. Implement a function that returns whether the given undirected graph forms a cycle or not. The given graph is a simple graph, which does not have more than one edge between any two vertices and self-loop. A cycle is a path of length 3 or more that starts and ends at the same vertices. You can modify graph.cpp and graph.h files for this problem.b. Input & Output Input: Pairs of nodes with integer labels that indicate edges. – (A,B): an edge between node A and node B. The names of the nodes are restricted to uppercase alphabetic characters. Output: – TRUE if the graph forms a cycle, FALSE otherwise. Note that they must be printed in uppercase.c. Example Input & Output Input Output “[(‘A’,’B’), (‘B’,’C’), (‘A’,’C’)]” TRUE “[(‘A’,’B’), (‘A’,’C’), (‘C’,’D’)]” FALSEd. Example execution2. Undirected Graph – Furthest node (2 pts) a. Implement a function that returns nodes which are the furthest distance from the given source node in the given undirected graph, and their distance. The distance is defined as the number of edges in the shortest path from the source node. Also, the given graph is a simple graph. You can modify graph.cpp and graph.h files for this problem.b. Input & output Input: Pairs of node labels that indicate edges, and the source node. – (‘A’,’B’): an edge between node A and node B. The names of the nodes are restricted to uppercase alphabetic characters. – (‘A’,NULL): the source node. You should find a node that is furthest from this source node. Output: – The furthest node. If there are some nodes that has the same distance with the found furthest node, print them all in lexicographic order. – Distancec. Example Input & Output Input Output “[(‘A’,’B’), (‘B’,’C’), (‘D’,’C’), D (‘A’,NULL)]” 3 “[(‘A’,’B’), (‘B’,’C’), (‘A’,’C’), B (‘A’,NULL)]” C 1 “[(‘A’,’B’), (‘A’,’C’), (‘C’,’D’), (‘C’,’E’), D (‘B’,’D’), (‘D’,’E’), (‘A’,NULL)]” E 2 “[(‘A’,’B’), (‘B’,’C’), (‘D’,’C’), (‘E’,’F’), D (‘A’,NULL)]” 3d. Example execution >> ./pa4.exe 2 “[(‘A’,’B’), (‘B’,’C’), (‘D’,’C’), (‘A’, NULL)]” [Task 2]3. Directed Graph – Topological Sort (2 pts) a. Implement a function that performs a topological sort using the given directed graph. If there exists more than one result, print the topological sort that comes first in the ascending order. To take an example below, acceptable topological sorts are ‘A B C D F E’, ‘A C B F E D’, ‘A C D B F E’, etc. Among these, the desirable output is ‘A B C D F E’. Also, print ‘ERROR’ if the topological sort could not be performed. You can modify graph.cpp and graph.h files for this problem. * You do not have to think about self-loop cases. We will not put such case in our test case.b. Input & output Input: Pairs of node labels that indicate edges. – (‘A’,’B’): an edge from node A to node B. – If the input edge already exists in the graph, ignore the input and continue the program. Output: – Result of topological sort or ‘ERROR’ messagec. Example Input & Output Input Output “[(‘A’,’B’),(‘A’,’C’),(‘B’,’F’),(‘F’,’ A B C D F E E’),(‘C’,’E’),(‘C’,’D’)]” “[(‘A’,’B’), (‘A’,’D’), (‘B’,’C’), (‘C’,’E’), A B C D E F (‘D’,’E’), (‘E’,’F’)]” “[(‘B’,’C’), (‘C’,’D’), (‘D’,’B’)]” ERRORd. Example execution >> ./pa4.exe 3 “[(‘A’,’B’),(‘A’,’C’),(‘B’,’F’),(‘F’,’ E’),(‘C’,’E’),(‘C’,’D’)]” [Task 3] A B C D F E4. Directed Graph – Strongly & Weakly Connected Components (2 pts) a. Implement a function that returns the strongly connected components and weakly connected components in the given directed graph. Print the strongly and weakly connected components in the ascending order. We show an example below. You can modify graph.cpp and graph.h and pa4.cpp files for this problem.b. Input & output Input: Pairs of node labels that indicate edges. – (‘A’,’B’): an edge from node A to node B – If the input edge already exists in the graph, ignore the input and continue the program. Output: – Strongly and Weakly connected components in ascending order. Each strongly and Weakly connected components are separated with Enter as shown in Output examples. Please first print all the strongly connected components then start to print the weakly connected components.c. Example Input & OutputThe input and output of such graph is written in the first row.Input Output “[(‘A’,’B’),(‘C’,’A’),(‘B’,’C’),(‘D’,’B’),(‘D A B C ‘,’E’),(‘E’,’G’),(‘G’,’F’),(‘F’,’E’)]” D E F G A B C D E F G “[(‘A’,’B’), (‘B’,’C’), (‘A’,’C’)]” A B C A B C “[(‘A’,’B’), (‘B’,’C’), (‘C’,’A’)]” A B C A B C “[(‘A’,’B’), (‘B’,’C’), (‘A’,’C’), (‘D’,’E’), A (‘E’,’F’), (‘F’,’D’)]” B C D E F A B C D E Fd. Example execution5. Single Source Shortest Path – Dijkstra’s Algorithm (4 pts)a. Implement a function that performs the following steps: i. Find all paths from the source node to other nodes such that the total cost of the path is lower than the given budget. Return pairs of reachable destinations nodes and the total cost (sum of the weights of the edges) of the paths. ii. From the found paths, identify and print the path that includes the most nodes and its total cost within the budget.b. We assume that the given graph is a directed, weighted, and weakly-connected graph. All weights of edges are positive (i.e. larger than 0). If the path from the source node to the destination node doesn’t exist, return an empty line.c. The maximum number of nodes in the graph is 26 (A to Z), without considering duplicate nodes.d. You can modify graph.cpp and graph.h files for this problem.e. Input & Output Input: A sequence of commands – (‘A-B’, integer): an edge from node ‘A’ to node ‘B’ with a weight value {integer}. – (‘A’, integer) : The first element indicates the source node and the second integer indicates the allowed budget.Output: – Pairs of the destination node and the total cost of the path (the sequence of pairs should be in lexicographical order). Node and cost separated with space. – Print the path that includes the most nodes within the budget at the end. – An empty line if the path does not exist. It should include ‘ ’, a newlinecharacter.Input “[(‘A-B’,10),(‘A-C’,3),(‘B-D’,5),(‘C-B’,2), (‘C-E’,15),(‘A-D’,20),(‘D-E’,11),(‘A’,11)]”“[(‘A-B’,10),(‘A-C’,3),(‘B-D’,5),(‘C-B’,2), (‘C-E’,15),(‘A-D’,20),(‘D-E’,11),(‘A’,1)]” “[(‘A-B’,10),(‘A-C’,3),(‘B-D’,5),(‘C-B’,2), (‘C-E’,15),(‘A-D’,20),(‘D-E’,11),(‘A’,20)]” “[(‘A-B’,10),(‘A-C’,3),(‘B-D’,5),(‘C-B’,2), (‘C-E’,15),(‘A-D’,20),(‘D-E’,11),(‘D’,12)]” f. Example input & outputg. Example execution Output B 5 C 3 D 10 A C B D 10B 5 C 3 D 10 E 18 A C B D 10E 11 D E 11>> ./pa4.exe 5 “[(‘A-B’,10),(‘A-C’,3),(‘B-D’,5),(‘C-B’,2), (‘C-E’,15),(‘A-D’,20),(‘D-E’,11),(‘A’,11)]” [Task 5] B 5 C 36. Advanced Kruskal’s Algorithm (4 pts)a. Implement a function that finds the Minimum-cost Spanning Tree (MST) of the given weighted undirected graph using Kruskal’s algorithm, with the option to include or exclude specific edges. The MST should include/exclude specific edges as indicated by input values of 0 or -1 (please refer to the input & output section for clarity). The function should print each added edge and its weight as the MST grows. The edge weights will be within the range of 1 to 100. When printing an edge, the labels must be in lexicographical order. If multiple edges have the same weight, the function should select edges in lexicographical order by comparing the first node of each edge, and if they are the same, then comparing the second node. The function returns the total cost of the MST (i.e., the sum of the edge weights). You can assume that the given graph is connected. You are allowed to modify graph.cpp and graph.h files for this problem.b. Input & Output Input: A sequence of commands – (‘A-B’, integer): an edge between node A and node B with a weight value of {integer}. – (‘A-B’, -1): an edge that should be excluded in MST – (‘A-B’, 0): an edge that should be included in MST – (‘MST’, NULL): find MST using Kruskal’s algorithm. Output: – For each time the tree grows, print the labels of the nodes indicating the added edges in lexicographical order and the weight of the edge as a string separated with a white space. – Print the cost of MST.c. Example Input & Output Input Output “[(‘A-B’, 3), (‘C-A’, 1), (‘C-B’, 4), (‘B-D’, 1), A C 1 (‘C-D’, 2), (‘D-E’, 5), (‘MST’, NULL)]” B D 1 C D 2 D E 5 9 “[(‘D-B’, 1), (‘D-C’, 2), (‘E-D’, 5), (‘B-A’, 3), A C 1 (‘C-A’, 1), (‘C-B’, 4), (‘B-D’, -1), (‘MST’, NULL)]” C D 2 A B 3 D E 5 11 “[(‘A-B’, 1), (‘B-C’, 1), (‘C-D’, 1), (‘D-A’, 1), A B 1 (‘A-C’, 1), (‘B-D’, 1), (‘MST’, NULL)]” A C 1 A D 1 3 “[(‘D-B’, 1), (‘D-C’, 2), (‘E-D’, 5), (‘B-A’, 3), A C 1 (‘C-A’, 1), (‘C-B’, 4), (‘A-B’, 0), (‘MST’, NULL)]” B D 1 A B 3 D E 5 10d. Example execution
