GitHub: https://classroom.github.com/a/v-VpEy-O General Instructions For this assignment, we provided starter code. Your task is to complete and submit the following files: – Deck.java – SolitaireCipher.java You will see these files when you successfully clone the assignment from GitHub. • Do not change any of the starter code that is given to you. Add code only where instructed, namely in the “ADD YOUR CODE HERE” block. This includes: – If you found that you have to change the folder structure to make it work in IntelliJ, there are probably problems with you IntelliJ setup for the “root of the source code”. Make sure IntelliJ recognizes the src folder as the root for your source code. You can check for more information at this link: https://www.jetbrains.com/help/idea/ content-roots.html#configure-folders. – Do not change any given code (e.g., names of the classes or methods, return types or parameters, etc). – Do not add any additional import statements. • You are NOT allowed to use any class other than those that have already been imported for you. • Any failure to comply with the above rules will give you an automatic 0. • You will get 0 if your code does not compile. Starting from this assignment, we are not fixing compilation errors for you! Make sure that your code is compilable. Don’t miss any semi-colon! • Do NOT wait until you are done writing the entire assignment to start testing your code. It will be extremely hard to debug your entire program. A good practice is to do unit tests: test each unit (a method) whenever you finish writing one. If you need help with debugging, feel free to reach out to the teaching staff. When doing so, make sure to mention what is the bug you are trying to fix, what have you tried to do to fix it, and where have you isolated the error to be. Submission instructions • All your work must be submitted on GitHub. Similar to the previous assignments, you can begin by accepting the assignment at https://classroom.github.com/a/v-VpEy-O. Subsequently, a repository naming assignment-1-*** will be created for you (*** is your GitHub username). You can then clone the repository, and work on it. If you want to recap the instructions to setup GitHub, clone your repository and submit your code, you can refer to the instructions of weekly assignment 1 (https://classroom.github.com/a/8qHfdL6n). • Don’t worry if you realize that you made a mistake after you submitted: you can git push multiple times but only the latest submission will be graded. Regularly pushing your work with well-documented commits is an encouraging practice to stay on track with your changes. You will be using the following commands. – git add * – git commit –m “update yyyy method in xxxx.java.” – git push • Do not submit any other files, especially .class files and the tester files. You are welcome to share your tester code with other students on Ed. Try to identify tricky cases. Do not hand in your tester code. • If you have any questions related to your grade, you can request a regrade within 7 days after the release of the grade by posting a private post on Ed and including your McGill ID. Learning Objectives There are several learning goals for this assignment. Firstly, this assignment aims to provide exposure to simple cryptography concepts. You will be introduced to the fundamental idea of a one-time pad and tasked with implementing an example of a stream cipher. Secondly, you will gain practical experience working with linked lists. Specifically, you will implement a data structure to represent a deck of cards. This implementation will utilize a circular doubly linked list. Thirdly, the assignment will emphasize the importance of algorithm efficiency. You will learn to evaluate and improve the efficiency of your code, moving beyond mere correctness to consider performance. Lastly, this assignment offers an opportunity for further practice in Java programming. While ECSE 250 primarily focuses on core computer science principles, programming remains an integral aspect. The more practice you engage in, the more proficient you will become. Introduction As the winter chill fades away and students scatter far and wide for the upcoming reading week, your friend – a recent computer science graduate – embarks on a mission: ‘Java.util.RemoteConnect,’ a venture aimed at facilitating secure communication among students, regardless of their physical location. In a stroke of creative genius (or perhaps just delirium from too many late-night coding sessions), they conceive of a plan involving a deck of cards and a sprinkle of cryptographic chaos. Inspired by the intrigue of Neal Stephenson’s ‘Cryptonomicon’, they aim to empower ECSE 250 students with a secret language, a digital code that transcends the ordinary. At the core of their endeavor lies a noble goal: to provide students with a means of communication that fosters trust and confidentiality, whether they’re collaborating on projects or simply catching up with classmates from afar during the break. Recognizing the importance of maintaining privacy in an increasingly digital world, they aim to create a virtual sanctuary where students can connect without fear of surveillance. Taking a cue from the novel’s clandestine communications via playing cards and the Solitaire encryption algorithm (thanks, Bruce Schneier!), your friend enlists your help in bringing their vision of a safer and more connected student community to life. The novel includes the description of the algorithm, but you can also find a revised version on the web . With the countdown to reading week ticking away faster than your friend can say ‘NullPointerException’, the pressure’s on to crack the code before the students disperse. Can you help your friend turn ‘Java.util.RemoteConnect’ into a digital lifeline for reading week, or will it end up being more of a ‘byte’-sized disaster? A bit of Crypto Background In 1917, Vernam patented a cipher now called one-time pad encryption scheme. The point of an encryption scheme is to transform a message so that only those authorized will be able to read it. One-time pad was later (in 1949) proved to be perfectly secret. The idea behind one-time pad is that given a plaintext message of length n, a uniformly random stream of digits of length n (which is the key) is generated and then used to encode the message. The message is concealed by replacing each character in the plaintext, with a character obtained combining the original one with one of the digits in the given key. Of course the message can be retrieved by performing the inverse operation on the characters of the encoded message (the ciphertext). Only those with access to the key can encode and decode a message. One-time pad is perfectly secret, but it has a number of drawbacks: for it to be secure, the key is required to be as long as the message, and it can only be used once! This clearly makes the cipher not a convenient one to use. Unfortunately, it was also proven that the limitations of one-time-pad are inherent to the definition of perfect secrecy. This means that to overcome those limitations the security requirements have to be relaxed. Stream ciphers use the same idea of one-time pad encryption scheme except that a pseudorandom sequence of digits is used as the pad instead of a random one. The idea is to use what are called ‘pseudorandom generators’ which given a smaller key can generate streams of pseudorandom digits. The Solitaire encryption algorithm is an example of a stream cipher. The key in this case is the deck of cards in its initial configuration. If two parties, Alice and Bob, share the same deck, following the Solitaire encryption algorithm they will be able to communicate by encoding and decoding messages. Of course, the deck and its configuration (i.e. the key) has to be kept secret to achieve secrecy. To encode and decode messages, Alice and Bob use the deck to generate a pseudorandom keystream which is then used as the “pad”. Encode/Decode with Solitaire Given a message to encode, we need to first remove all non–letters and convert any lower–case letters to upper–case. We then use the keystream of values and convert each letter to the letter obtained by shifting the original one a certain number of positions to the right on the alphabet. This number is the one found in the keystream in the same position as the character we are encoding. Decryption is just the reverse of encryption. Using the same keystream that was used to generate the ciphertext, convert each letter to the letter obtained by shifting the original one the given number of positions to the left on the alphabet. For example, let’s say that Alice wants to send the following message: Is that you, Bob? Then she will first remove all the non-letters and capitalize all the remaining ones obtaining the following: ISTHATYOUBOB She will then generate a keystream of 12 values. We’ll talk about the keystream generation in the next section, so let’s assume that the keystream is the following: 11 9 23 7 10 25 11 11 7 8 9 3 Finally, she can generate the ciphertext by shifting each letter the appropriate number of positions to the right in the alphabet. For example, the ‘I’ shifted 11 positions to the right, becomes a ‘T’. The ‘S’ shifted 9 positions to the right becomes a ‘B’. And so on! The final ciphertext will be: TBQOKSJZBJXE Bob, upon receiving the message, will need to generate the keystream. If Alice and Bob shared the same key and used it to generate the same number of pseudorandom values, then the keystream generated in this moment by Bob will be equal to that used by Alice to encrypt the message. All there’s left for Bob to do is convert all the letters by shifting them the appropriate number of position to the left. In our assignment, the “key” is a deck of cards in a specific configuration from which we can generate the keystream as explained in the next section. Generating a Keystream Using a Deck of Cards The harder part of the Solitaire encryption algorithm is generating the keystream. The idea is to use a deck of playing cards plus two jokers (a red one and a black one). Each card is associated with a value which depends on its rank and its suit. Cards in order from Ace to King have value 1 to 13 respectively. This value can increase by a multiple of 13 depending on the suit of the card. For this section let’s assume we’ll use the Bridge ranking for suits: clubs (lowest), followed by diamonds, hearts, and spades (highest). So, for instance, the Ace of clubs has value 1, while the 5 of diamonds has value 18, and the Queen of spades has value 51. The jokers have a value that depends on the number of cards in the deck. If the deck has a total of 54 cards (the 52 playing cards plus the two jokers), then the jokers have value 53. If the deck has total of 28 cards, then the jokers have value 27. That is, the jokers have both the same value and this value is equal to the total number of cards in the deck minus one. The keystream values depend solely on the deck’s initial configuration. We will implement the deck as a circular doubly linked list with the cards as nodes. This means that the first card (the one on the top of the deck) is linked to the last card (the one at the bottom of the deck) and the last card is linked to the first one. As an example, let’s consider a deck with 28 cards: the 13 of both clubs and diamonds, plus the two jokers. Let’s also consider the following initial configuration : AC 4C 7C 10C KC 3D 6D 9D QD BJ 3C 6C 9C QC 2D 5D 8D JD RJ 2C 5C 8C JC AD 4D 7D 10D KD The cards are represented with their rank, followed by their suit. For example, 6C denotes the 6 of clubs, JD the Jack of diamonds, and RJ the red joker. The cards are also listed in order from the top of to the bottom of the deck. Here are the steps to take to generate one value of the keystream: 1. Locate the red joker and move it one card below. (That is, swap it with the card beneath it.) If the joker is the bottom card of the deck, move it just below the card on the top of the deck. Note that, there is no way for the joker to become the top card as a result of this operation. After this step, the deck above will look as follows: AC 4C 7C 10C KC 3D 6D 9D QD BJ 3C 6C 9C QC 2D 5D 8D JD 2C RJ 5C 8C JC AD 4D 7D 10D KD 2. Locate the black joker and move it two cards below. If the joker is the bottom card of the deck, move it just below the second card from the top. If the joker is one up from the bottom card, move it just below the top card. As before, there is no way for the joker to become the top card as a result of this operation. After this step, the deck above will look as follows: AC 4C 7C 10C KC 3D 6D 9D QD 3C 6C BJ 9C QC 2D 5D 8D JD 2C RJ 5C 8C JC AD 4D 7D 10D KD 3. Perform a “triple cut”: that is, swap the cards above the first joker with the cards below the second joker. Note that here we use “first” and “second” joker to refer to whatever joker is nearest to, and furthest from, the top of the deck. Their colors do not matter. Note that the jokers and the cards between them do not move! If there are no cards in one of the three sections (either the jokers are adjacent, or one is on top or the bottom of the deck), just treat that section as empty and move it anyway. The deck will now look as follows: 5C 8C JC AD 4D 7D 10D KD BJ 9C QC 2D 5D 8D JD 2C RJ AC 4C 7C 10C KC 3D 6D 9D QD 3C 6C 4. Perform a “count cut”: look at the value of the bottom card. Remove that number of cards from the top of the deck and insert them just above the last card in the deck. The deck will now look as follows: 10D KD BJ 9C QC 2D 5D 8D JD 2C RJ AC 4C 7C 10C KC 3D 6D 9D QD 3C 5C 8C JC AD 4D 7D 6C 5. Finally, look at the value of the card on the top of the deck. Count down that many cards (Count the top card as number one) and look at the next card. If you hit a joker, ignore it and repeat the keystream algorithm (i.e. go back to step 1.). Otherwise, use the value of the card you counted to as the next keystream value. Note that this step does not modify the state of the deck. In our example, the top card is a 10 of diamonds which has value 23. By counting down to the 24th card we find the Jack of clubs which has value 11. Hence, 11 would be the first keystream value generated by our deck. To generate the next keystream value repeat the algorithm from step 1 using the current deck configuration. Instructions and Starter Code As mentioned in the section before we will use a circular doubly linked list to represent a deck of cards. The starter code contains two files with five classes which are as follows: • Deck – This class defines a deck of cards. Most of your work goes into this file. This class contains three nested classes: Card, PlayingCard, and Joker. • SolitaireCipher – This class represents a stream cipher that uses the Solitaire algorithm to generate the keystream and then encode/decode messages. Methods you need to implement For this assignment you need to implement all of the methods listed below. See the starter code for the full method signatures. Your implementations must be efficient. For each method below, we indicate the worst case run time using O() notation. • Deck.Deck(int numOfCardsPerSuit, int numOfSuits) : creates a deck with cards from Ace to numOfCardsPerSuit for the first numOfSuits in the class field suitsInOrder. The cards should be ordered first by suit, and then by rank. In addition to these cards, a red joker and a black joker are added to the bottom of the deck in this order. For example, with input 4 and 3, and suitsInOrder as specified in the file, the deck contains the following cards in this specific order: AC 2C 3C 4C AD 2D 3D 4D AH 2H 3H 4H RJ BJ The constructor should raise an IllegalArgumentException if the first input is not a number between 1 and 13 (both included) or the second input is not a number between 1 and the size of the class field suitsInOrder. Remember that a deck is a circular doubly linked list so make sure to set up all the pointers correctly, as well as the instance fields. • Deck.Deck(Deck d) : creates a deck by making a deep copy of the input deck. Hint: use the method getCopy from the class Card. Disclaimer: this is not the correct way of making a deep copy of objects that contain circular references, but it is a simple one and good enough for our purposes. • Deck.addCard(Card c) : adds the input card to the bottom of the deck. This method runs in O(1). • Deck.shuffle() : shuffles the deck. There are different ways of doing this, but for this assignment you will need to implement an algorithm that uses the Fisher–Yates shuffle algorithm. The algorithm runs in O(n) using O(n) space, where n is the number of cards in the deck. To perform a shuffle of the deck follow the steps: – Copy all the cards inside an array – Shuffle the array using the following algorithm: for i from n-1 to 1 do j
Introduction to Database Systems Project Description (2 pages) (Note: This project is based on the material in textbook Chapter 3 – Chapter 5, and Appendix A sections 2 – 5. All the references on figures, chapters/sections, and pages in this document refer to the corresponding textbook parts.) The database for Wedgewood Pacific (WP) has been discussed extensively in Chapter 3 as well as in the “Working with Microsoft Access†in Chapter 1 and Chapter 2. Complete the following four tasks using MySQL (Community Server 8.0 and the Workbench). Create one document file (Microsoft Word or PDF format) that contains all your SQL scripts (in text format) and clear screenshots (with brief explanation) for all 4 parts. 1. Create the Wedgewood Pacific (WP) database as described in Chapter 3. This will include: a. Creating the WP schema, and setting it as the default schema. b. Creating a folder to hold SQL scripts for the WP schema in the C:/Documents/MySQLWorkbench/Schemas folder. c. Creating and running an SQL script named WP-Create-Tables based on Figure 3-7 (page152) to create the WP table structure. d. Creating and running an SQL script named WP-Insert-Datas based on Figure 3-11 (pages159 – 161) to populate the WP tables. What to turn in?  Provide screenshots (similar to Figure A-19 and Figure A-20) with a brief explanation to demonstrate that you have completed this task. What to turn in?  A copy of your SQL script (in text format, not screenshot image);  A screenshot of the results of running the query. 1. Wedgewood Pacific (WP) has decided to keep track of computers used by the employees. To do so, two new tables are added to the database. The schema for these tables, as related to the existing EMPLOYEE table, along with the referential integrity constraints, are shown in question WA.3.3 (pages 241 – 244). In addition, Figure 3-31, Figure 3-32, Figure 3-33, and Figure 3-34 are the corresponding database column characteristics for the tables and table data. The schema for these tables is (note that we are purposely excluding the recursive relationship in EMPLOYEE at this time): The referential integrity constraints: Write an SQL query to answer the following question: Who is currently using which computer at WP? The result should be sorted first by Department and then by employee LastName, and contain the following information: SerialNumber, Make, Model, EmployeeID, LastName, FirstName, Department, and OfficePhone. What to turn in?  A copy of your SQL script (in text format, not screenshot image);  A screenshot of the results of running the query. 1. Using an IE Crow’s Foot E-R diagram, Figure 5-17 (page 365) and Figure A-67 (page A-73) show the database design for the Wedgewood Pacific database (including the recursive relationship for EMPLOYEE) in MySQL Workbench. See Appendix A section 5 (pages A-56 to A-74) for more details. Use MySQL Workbench to enhance this E-R diagram (Figure 5-17 or Figure A-67) with the COMPUTER and COMPUTER_ASSIGNMENT tables as mentioned in the previous part. What to turn in?  A screenshot of the completed E-R diagram.
1. Overview In this programming assignment, you will develop your own AI agents based on some of the AI techniques for Search, Game Playing, and Reinforcement Learning that you have learnt in class to play a small version of the Go game, called Go-5×5 or Little-Go, that has a reduced board size of 5×5. Your agent will play this Little-Go game against some basic as well as more advanced AI agents. Your agents will be graded based on their performance in these online game “tournaments” on Vocareum.com. Your objective is to develop and train your AI agents to play this Little-Go game as best as possible. 2. Game Description Go is an abstract strategy board game for two players, in which the aim is to surround more territory than the opponent. The basic concepts of Go (Little-Go) are very simple: – Players: Go is played by two players, called Black and White. – Board: The Go board is a grid of horizontal and vertical lines. The standard size of the board is 19×19, but in this homework, the board size will be 5×5. – Point: The lines of the board have intersections wherever they cross or touch each other. Each intersection is called a point. Intersections at the four corners and the edges of the board are also called points. Go is played on the points of the board, not on the squares. – Stones: Black uses black stones. White uses white stones.The basic process of playing the Go (Little-Go) game is also very simple: – It starts with an empty board, – Two players take turns placing stones on the board, one stone at a time, – Once played, a stone can never be moved and can be taken off the board only if it is captured.The entire game of Go (Little-Go) is played based on two simple rules: Liberty (No-Suicide) and KO. The definitions of these rules are outlined as follows: Rule1: The Liberty Rule Every stone remaining on the board must have at least one open point, called a liberty, directly orthogonally adjacent (up, down, left, or right), or must be part of a connected group that has at least one such open point (liberty) next to it. Stones or groups of stones which lose their last liberty are removed from the board (called captured).Based on the rule of liberty, players are NOT allowed to play any “suicide” moves. That is, a player cannot place a stone such that the played stone or its connected group has no liberties, unless doing so immediately deprives an enemy group of its final liberty. In the latter case, the enemy group is captured, leaving the new stone with at least one liberty.Examples of capturing: – Example 1. The white stone is captured after Black plays at position 1, because its directly orthogonally adjacent points are occupied.– Example 2. The 3 white stones are captured as a connected group.– Example 3. The two groups of white stones are captured.– Example 4 (Special example). This example illustrates the rule that a capturing stone need not have a liberty until the captured stones are removed.Rule 2: The “KO” RuleFor the position shown on the left board above, Black can capture the stone by a play at position a. The resulting position is shown on the right board above. Without a KO rule, in this position White could recapture the stone at position b, reverting to the position shown on the left, and then Black could also recapture. If neither player gave way, then we would have Black a, White b, Black a, White b, …, repeated ad infinitum, stalling the progress of the game. This situation is known as KO. The KO rule resolves the situation: If one player captures the KO, the opponent is prohibited from recapturing the KO immediately. – Example. Given the initial status on the left below, white player puts a stone at position 1, which captures a black stone. Black stone cannot be placed at position 2 immediately after it’s captured at this position. Black must play at a different position this turn. Black can play at position 2 the next turn if this position is still not occupied.– More examples. KOs need not occur only in the center of the board. They can also show up at the sides or corners of the board, as shown in the diagram below.Komi Because Black has the advantage of playing the first move, awarding White some compensation is called Komi. This is in the form of giving White a compensation of score at the end of the game. In this homework (a board size of 5×5), Komi for the White player is set to be 5/2 = 2.5. Passing End of Game A game ends when it reaches one of the four conditions: – When a player’s time for a single move exceeds the time limit (See Section 6. Notes and Hints). – When a player makes an invalid move (invalid stone placement, suicide, violation of KO rule). – When both players waive their rights to move. Namely, two consecutive passes end the game. – When the game has reached the maximum number of steps allowed. In this homework (a board size of 5×5), the maximum number of steps allowed is 5*5-1 = 24. Winning Condition There are various scoring rules and winning criteria for Go. But we will adopt the following rules for the scope of this Little-Go project. – “Partial” Area Scoring: A player’s partial area score is the number of stones that the player has occupied on the board. – Final Scoring: The Black player’s final score is the partial area score, while the White player’s final score is the sum of the partial area score plus the score of compensation (Komi). – Winning Criteria: – If a player’s time for a single move exceeds the time limit (See Section 6. Notes and Hints), s/he loses the game. – If a player makes an invalid move (invalid stone placement, suicide, violation of KO rule), s/he loses the game. – If the game reaches the maximum number of steps allowed or if both players waive their rights to move, the winner is the player that has a higher final score at the end of the game. For example, in the following board at the end of a game, White’s partial area score is 10 and Black’s partial area score is 12. White is the winner because 10 + 2.5 = 12.5 > 12 .Clarification of the Game Rules The particular set of rules that have been adopted in this assignment references several popular rule sets around the world, but some changes have been made to best adapt to this project. For example, “Full” Area Scoring is usually used in the 19×19 Go game, which counts the number of stones that the player has on the board plus the number of empty intersections enclosed by that player’s stones, but we do not use this rule in our assignment. Go is a very interesting and sophisticated game. Please do some more research if you’re interested.Do not copy code or written material from another student. Even single lines of code should not be copied. Do not collaborate on this assignment. The assignment is to be solved individually. Do not copy code from past students. We keep copies of past work to check for this. Even though this project differs from those of previous years, do not try to copy from homeworks of previous years. Do not ask on Piazza how to implement some function for this homework, or how to calculate something needed for this homework. Do not post test cases on Piazza asking for what the correct solution should be. 4. Playing against Other Agents In this homework, your agent will play against other agents created by the teaching staff of this course. 4.1 Program Structure Figure 1 shows the basic program structure. There is one game host and two players in each game. The Game Host keeps track of the game process, gets the next moves from the players in turn, judges if the proposed moves are valid, wipes out the dead stones, and finally judges the winner. Each of the two Players must output its next move in an exact given format (in a file called output.txt) with the intended point (row and column) coordinates to the Game Host. The job of a player is very simple: take the previous and current states of the board (in a file called input.txt) from the host, and then output the next move back to the host.Figure 1: The Program Structure for the Little-Go Game. 4.2 Rule Parameters The following parameters have been adopted for this homework project: – In a board, 0 stands for an empty point, 1 stands for a Black stone, and 2 stands for a White stone. – In board visualizations, X represents a Black stone and O represents a White stone. – Black always plays first. – The board size is 5×5. – The maximum number of moves allowed is n * n − 1 , where n is the size of the game. For example, max number of moves allowed for a board of size 5×5 is 5*5-1=24. – Komi for the White player is n/2 . For example, Komi for a board of size 5×5 is 2.5. If White scores 10 and Black scores 12 at the end of the game, then White is the winner ( 10 + 2.5 = 12.5 > 12 ). 4.3 The Game BoardFigure 2: The Format of the Current Board of the Little-Go Game. The host keeps track of the game board while the two players make moves in turn. We will use a zero-based, vertical-first, start at the top-left indexing in the game board. So, location 0,0 is the top-left corner of the board, location 0,4 is the top-right corner, location 4,0 is the bottom-left corner, and location 4,4 is the bottom-right corner. An example of game state is shown in Figure 2, in which “1” denotes black stones, “2” denotes white stones, and 0 denotes empty positions. For manual players, we visualize the board as in the image on the right whereX denotes the black stones and O denotes the white stones. 4.4 Players and Game Host AI Players Different AI Players are available for your agent to play against for the purpose of testing and/or grading. Examples of these existing AI players include: – Random Player: Moves randomly. – Greedy Player: Places the stone that captures the maximum number of enemy stones – Aggressive Player: Looks at the next two possible moves and tries to capture the maximum number of enemy stones. – Alphabeta Player: Uses the Minimax algorithm (Depth=70% 15pts*winRate 15pts*winRate 20pts*winRate 10pts*winRate
1. OverviewFigure 1: 3D Maze Configuration: grids world that contains travelable actionsFigure 2: Definitions of Actions in the MazeAct X+ X- Y+ Y- Z+ Z- X+Y+ X+Y- X-Y+ X-Y- X+Z+ X+Z- X-Z+ X-Z- Y+Z+ Y+Z- Y-Z+ Y-Z- Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18Your programming task is as follows. Given as inputs: (1) a list of grid points with their available actions, (2) an entrance grid location, e.g., (0,0,0) in Figure 1, and (3) an exit grid location, e.g., (100,103,97) , your program must search in the maze configuration and find the optimal shortest path from the entrance to the exit, using a list of actions that are available along the way.Conceptually, the specification of a grid location and its associated actions is given as a grid location with a list of actions. For example (Note: The exact input format will be given in section 5 and 6 below),INPUT LINE: (60 45 97), Y+, Z-, X-Y+ INPUT LINE: (60 46 97), Y-, Y+ INPUT LINE: (60 45 96), Z+, Z-, INPUT LINE: (59 46 97), X+Y-, X-Y+is a specification, for Figure 1, that at the grid location (60,45,97), the available actions are Y+, Z-, and X-Y+. At the grid (60,46,97), the available actions are Y- and Y+, and at the grid (60,45,96), the available actions are Z+ and Z-, and at the grid (59,46,97), the available actions are X+Y- and X-Y+ for moving diagonally on the xy plane.Once your agent finds an optimal path from the entrance to the exit, your agent should output a list of points that have been visited along the path. For example, if the entrance and exit would be changed at (60,103,97) and (64,103,97) respectively, then the correct output path would be:OUTPUT: (60,103,97), (61,103,97), (62,103,97), (63,103,97), (64,103,97).2. GradingYour code will be tested and graded as follows: Your program should not require any command-line argument. It should read a text file called “input.txt” in the current directory that contains a problem definition. It should create and write a file “output.txt” with your solution in the same current directory. Format for input.txt and output.txt are specified as in section 5 below and will be supplemented with some details in section 6. End-of-line character is LF (since vocareum is a Unix system and follows the Unix convention).The grading A.I. script will test your program for 40 test cases for grading as follows:– Create an input.txt file and delete any old output.txt file. – Run your code to create your output.txt file. – Check the correctness of your program’s output.txt file. – If your outputs for all 40 test cases are correct, you get 100 points. – The 40 test cases are divided into four classes: Class1 (easy), 10 cases; Class2 (medium), 10 cases; Class3 (hard), 10 cases; and Class4 (complex), 10 cases. – For Class1, each test is worthy of 1 point. For Class 2, each test is 2 points. For Class 3, each test is 3 points, and for Class 4, each test is 4 points.Note that if your code does not compile, or somehow fails to load and parse input.txt, or writes an incorrectly formatted output.txt, or no output.txt at all, or OuTpUt.TxT, you will get zero points. Anything you write to stdout or stderr will be ignored and is ok to leave in the code you submit (but it will likely slow you down). Please test your program on Vocareum’s terminal window with the provided sample files to avoid any problems.Do not copy code or written material from another student. Even single lines of code should not be copied. Do not copy code from past students. We keep copies of past work to check for this. Even though this problem differs from those of previous years, do not try to copy from homeworks of previous years. Do not ask on piazza how to implement some function for this homework, or how to calculate something needed for this homework.4. Project DescriptionIn this project, we twist the problem of path planning a little bit just to give you the opportunity to deepen your understanding of search algorithms by modifying search techniques to fit the criteria of a more realistic application. To give you a realistic context for expanding your ideas about search algorithms, we invite you to take part in a maze-solving mission in an unknown world. The goal of this mission is to send your sophisticated and intelligent agent from a specific entrance-location and travel as quickly as possible to an exit location. You are invited to develop three algorithms to find the optimal path and navigate through a complex 3D maze configuration based on a particular objective.The input of your program includes three elements: the maze configuration, an entrance location, and an exit location, plus perhaps some other quantities that control the quality of the solution. Each possible 3D maze world can be imagined as a 3D grid of points in a 3-dimensional space. At each point inside the maze, your agent can perform one of the 18 actions, and move to one of the 18 possible neighbor grid points (See Fig. 2). To simplify things, your agent’s actions are assumed to be deterministic and error-free. If your agent’s action is legal, then your agent will always end up at the intended neighbor grid point. If your agent tries to move into a wall or outside a maze world, the result will be nil and your agent will remain in its current point location.5. Search for the Optimal PathsYou will write a program that will take an input file that describes the maze configuration, the initial entrance grid location, the exit grid location, and characteristics of the agent. You should find the optimal path from the initial entrance grid location to that exit grid location. A path is composed of a sequence of legal moves. Each legal move consists of moving the agent from a point to one of its 18 neighbor points, using one of the elementary actions that are available at the current location.Your agent must search through possible paths of movements and find the optimal path to travel from the entrance to the exit, and then output the results.To find the solution you will use the following algorithms: – Breadth-first search (BFS) – Uniform-cost search (UCS) – A* search (A*).To help us distinguish between your three algorithm implementations, you must follow the following conventions for computing operational path length:Breadth-first search (BFS) In BFS, each move from one location to any of its neighbors counts for a unit path cost of 1. You do not need to worry about the fact that moving diagonally actually is a bit longer than moving along the North/South, East/West, and Up/Down directions. So, any allowed move from one location to an adjacent location costs 1.Uniform-cost search (UCS) When running UCS, you should compute unit path costs in any of the 2D plane XY, XZ, YZ, on which you are moving. Let us assume that a grid location’s center coordinates projected to a 2D plane are spaced by a 2D distance of 10 units on X and Z plane respectively. That is, on the XZ plane, move from a grid location to one of its 4-connected straight neighbors incurs a unit path cost of 10, while a diagonal move to a neighbor incurs a unit path cost of 14 as an approximation to 10 when running UCS. √ A* search (A*). When running A*, you should compute an approximate integer unit path cost of each move as in the UCS case (unit cost of 10 when moving straight on a plane, and unit cost of 14 when moving diagonally). Notice for A*, you need to design an admissible heuristic for A* for this problem.Input: The file input.txt in the current directory of your program will be formatted as follows: ● First line: Instruction of which algorithm to use, as a string: BFS, UCS or A* ● Second line: Three strictly positive 32-bit integers separated by one space character, for the size of X, Y, and Z dimensions, respectively. ● Third line: Three non-negative 32-bit integers for the entrance grid location. ● Fourth line: Three non-negative 32-bit integers for the exit grid location. ● Fifth line: A strictly positive 32-bit integer N, indicating the number of grids in the maze where there are actions available. ● Next N lines: Three non-negative 32-bit integers separated by one space character, for the location of the grid, followed by a list of actions that are available at this grid. The grid location is guaranteed to be legal and within the maze.For example:A* 100 200 100 0 0 0 3 3 0 4 0 0 0 7 1 1 0 7 10 2 2 0 7 10 3 3 0 10In this example, the 3D maze is of size 100 x 200 x 100 (specifically, points range from (0,0,0) to (99,199,99)) , the entrance grid location is at (0,0,0), and the exit grid location is at (3,3,0). In this maze, there are 4 grid locations that have actions and they are specified in the next four lines. Namely, the grid (0,0,0) has one action X+Y+ (encoded as 7); the grid (1,1,0) has two actions X+Y+ and X-Y- (encoded as 7 and 10); the grid (2,2,0) has two actions X+Y+ and X-Y- (encoded as 7 and 10); and the grid (3,3,0) has one action X-Y- (encoded as 10). .Output: The file output.txt that your program creates in the current directory should be formatted as follows:● First line: A single integer C, indicating the total cost of your found solution. If no solution was found (the exit grid location is unreachable from the given entrance, then write the word “FAIL” (all capital) without any other lines following. ● Second line: A single integer N, indicating the total number of steps in your solution including the starting position. ● N lines: Report the steps in your solution travelling from the entrance grid location to the exit grid location as were given in the input.txt file. – Write out one line per step with cost. Each line should contain a tuple of four integers: X, Y, Z, Cost, separated by a space character, specifying the grid location with the single step cost to visit that grid location by your agent from its last grid during its traveling from the entrance to the exit.For example, the following is a sample output of the corresponding input above:42 4 0 0 0 0 1 1 0 14 2 2 0 14 3 3 0 14Notes and hints:– Please name your program “homework.xxx ” where ‘xxx’ is the extension for the programming language you choose (“py” for python, “cpp” for C++, and “java” for Java). If you are using C++11, then the name of your file should be “homework11.cpp” and if you are using python3 then the name of your file should be “homework3.py”. Please use the programming languages mentioned above for this homework. – Most likely (but no guarantee) we will create 13 BFS, 13 UCS, and 14 A* grading cases for grading your agents. These cases are called “Grading Cases” because they are reserved for the grading purposes only. During your development, there would be some “test cases” for you to use to test, debug, and improve your agents. But in general, you are responsible for testing your agents thoroughly using any test cases you would like. – Your program will be killed after some time if it appears stuck on a given test case, to allow us to grade the whole class in a reasonable amount of time. We will make sure that the time limit for a given test or grading case (or class) is sufficient and long enough for solving the case for a correct algorithm implementation. These time limits are typically determined by a standard algorithm implementation that has been tested thoroughly in solving the given 3D mazes, and we ensure that these time limits are typically very generous. – The time limit is the total combined CPU time as measured by the Unix time command. This command measures pure computation time used by your program, and discards time taken by the operating system, disk I/O, program loading, etc. Beware that it cumulates time spent in any threads spawned by your agent (so if you run 4 threads and use 400% CPU for 10 seconds, this will count as using 40 seconds of allocated time). – If several optimal solutions exist, then any of them will count as correct. – Please submit your homework code through Vocareum (https://labs.vocareum.com /) under the assignment HW1. Your username is your email address (DEN username). Click “forgot password” for the first-time login. You should have been enrolled in this course on Vocareum. If not, please post a private question with your email address and USC ID on Piazza (under “hw1” folder) so that we will invite you again.6. Sample Inputs and OutputsExample 1 (BFS): =======input.txt============= BFS 10 10 10 1 3 1 5 3 4 12 1 3 1 5 1 3 2 1 11 2 3 3 16 2 4 2 11 2 3 2 5 11 3 3 3 17 18 3 2 2 3 3 3 2 5 3 2 4 7 4 3 4 1 11 5 3 4 2 5 3 5 6 ==================================output.txt============ 6 7 1 3 1 0 1 3 2 1 2 3 2 1 3 3 3 1 3 2 4 1 4 3 4 1 5 3 4 1 ============================Example 2 (UCS): =======input.txt============= UCS 10 10 10 7 0 1 5 2 3 9 5 2 3 1 5 1 3 3 5 2 2 5 17 6 1 2 9 3 6 1 1 5 15 7 1 1 9 6 2 1 4 8 0 1 9 7 0 1 9 1 ==================================output.txt============ 48 5 7 0 1 0 6 1 1 14 6 1 2 10 5 2 2 14 5 2 3 10 ===========================Example 3 (A*): =======input.txt============= A* 5 5 5 1 0 4 3 1 2 8 1 0 1 2 1 0 4 3 16 1 1 4 6 12 2 1 3 2 1 1 3 3 12 16 1 2 3 9 2 1 2 1 12 3 1 1 5 ==================================output.txt============= 38 4 1 0 4 0 1 1 3 14 2 1 2 14 3 1 2 10 ============================Example 4 (BFS with no solution): =======input.txt============= BFS 4 4 4 0 0 0 2 3 1 6 0 0 0 7 11 1 1 0 7 1 0 1 7 2 1 1 15 2 2 0 5 2 2 2 3 ==================================output.txt============= FAIL ============================
In this assignment you will be utilizing Perlin Noise generation and a hierarchical set of generation rules to create complex heightmap terrain. Perlin Noise is a type of gradient noise that is useful as a starting point for procedural content generation (PCG) of textures and terrain. Perlin Noise can be scaled to reflect random details at different frequencies. Noise can be processed and layered to create different effects. For this assignment, you will use the PCG generator to design a terrain with three visually distinct areas (biomes or distinct geographic features). This will involve segmenting your terrain according to boundaries generated by Perlin Noise. For instance, you might make mountains in one, sand dunes in a second, and a canyon in a third. This configuration will be saved in a Unity ScriptableObject. You will submit your designed terrain PCGTerrainData.asset (ScriptableObject), a readme.txt file describing it, and four (4) or more screenshots that best demonstrate what you developed. You can also share your screenshots on Piazza with your classmates. There are more details in the Submission Section. Development Resources A Unity Project (GameAI_PCG) is provided as a starting point. Open the project in Unity and then open scene, PCGTerrain. You will not need to “Play” the game at any point to create your terrain. All the work can be done in the Editor. But playing is good for taking a screenshot. You can also build and run the game to view the terrain (but not edit). Note that if you hit play (or run from build) you can exit by hitting Escape. You can move around with WASD and mouse-look, with mouse1 and mouse2 control elevation.Building a PCG Graph You will use the PCG generator (PCG Terrain component) to design a terrain with three visually distinct areas (or biomes). This will involve segmenting your terrain according to boundaries generated by Perlin Noise. For instance, you might make mountains in one biome, sand dunes in a second, and a canyon in a third. This configuration will be saved in a Unity ScriptableObject. The general steps involve configuring a node, then adding new nodes (via “Add Child PCG Terrain Node”) and then continuing the process of configuring and adding more nodes. Lastly, you need to save/serialize out to disk using the Save button. See below for more details. PCG Configuration Details The Name field is very helpful for keeping track of what layers do what. Be sure to change the name in the PCGTerrain Component and not at the top of the GameObject (PCGTerrain overrides the GameObject name). The X/Y/Z Offsets (available in different levels of power for convenience) allow exploration of the noise space. This is useful for demonstrating how well your rules work if the terrain tiled out indefinitely. You can also use these sliders to find the best screenshots. The MaxValue is used to limit the amplitude of generated noise. The PerlinScalar allows “zooming” in/out on the noise (change the frequency of gradient changes). The GenNoiseType allows for PerlinNoise, PerlinNoiseWithMappingCurve, and None. The mapping curve involves processing the generated noise with GenNoiseCurve (a manually configured function). If None is selected, then no noise is generated and a default value of 1.0 is used (scaled by MaxValue). The ProcessParentType can be passed along unmodified (Passthrough), Inverted, processed/remapped with ProcessParentCurve, or a TrapezoidFunction (a bit like a bandpass and can help with crossfading terrain effects) The latter is especially useful for quickly segmenting noise for the purpose of creating regions/biomes. Note that the ProcessParentVariables is needed to define the bandpass region (4 values; the two outer values [index 0 and 3] define the start of the fade region and the two inner values [index 1 and 2] define the band). Anything outside the bandpass is mapped to 0.0. Anything inside is mapped to 1.0 (or faded from 0.0 to 1.0). You can also use the ProcessParentCurve to do the same thing, but it takes a bit more work to setup and is more expensive computationally to evaluate. It does have potential for smoother transitions though. The CombineType selects how the current node’s generated value is combined with the parent. Most commonly, you will want to either Add, Subtract, or Multiply. But there are a few other options such as NormalizeFromParentToTop that makes it easier to avoid clipping to the max (“top”) elevation allowed by the heightmap (1.0). Complement can be used to flip the final output value around (1.0 – outputVal). Mute can be used to temporarily disable noise generation (value is 0.0). DoNotProcessDescendant can be used to temporarily disable evaluation of children nodes. The buttons at the bottom of the PCGTerrain component are also useful. You will need these for building your graph. Load from ScriptableObject: Be cautious with this button! It will delete all children of the root node and reload/rebuild from the ScriptableObject. The load button is NOT smart. It is NOT aware of unsaved changes. The root and children will then match the ScriptableObject contents. Only available at the root of your graph. Save to ScriptableObject: You must manually click this button to serialize your graph to disk (will be PCGTerrainData.asset with the default assignment). You should also save your scene from the Unity File Menu after saving the graph. Only available at the root of your graph. If you exit Unity without saving the scene (including crash or abrupt loss of power) then the ScriptableObject changes likely won’t be preserved. Add Child PCG Terrain Node: This adds a child node that has PCGTerrain configuration to the current node. This button is available at every node of your graph Delete this Node (and children): Be cautious with this button! There is NO confirmation! This button deletes your selected node and children. It cannot be reversed and also affects your serializableObject too. This button is available at every node of your graph. You DO NOT need to delete nodes before Loading. Let the Load operation handle synchronizing things.Validate: This operation will print “Valid!” to the console if everything is ok with the state of your ScriptableObject as compared to the data in the Hierarchy of your Scene. Otherwise, an error will be printed. Other Considerations Feel free to share techniques for building rules graphs on Piazza with classmates. If you are having performance problems, you can reduce your terrain resolution. Select the Terrain component settings (gear) and scroll to “Heightmap Resolution”. Change to something smaller than currently. You might go higher for screenshots. Grading You will be assessed on whether you create three distinct areas that are isolated from one another within the rules you specify in PCGTerrainData.asset. Key features we are looking for in your terrain graph file: • Each of the three areas/biomes must be distinct, except for some crossfade to create smooth transitions. • Each of the three areas/biomes must be generated from a root noise source by way of TrapezoidFunction or custom MappingCurve. You must either split the root noise source into three separate ranges or split hierarchically (e.g. split root noise source into two parts, and then split one of the parts in two). • Each area/biome should have visually distinct heightmap patterns including multiple octaves of Perlin noise and intermittent features like rocks, stalactites, craters, etc. This will require multiple descendant PCG nodes in your graph under each area/biome. • No area/biome should rely on clipping against minimum or maximum height values. These appear as perfectly flat areas with no details. (If you wish to create a water area such as a lake, you should either create the seabed or a turbulent water surface. If you make a seabed, it’s ok to add a translucent plane to show the waterline in your images if you like.) Additionally, your submission will be checked to confirm that the required items are submitted and are formatted correctly (see below). Submission Submit all files individually (NOT in a ZIP file). It is a good idea to use a text editor to check your PCGTerrain.asset contents (YAML file format) and make sure that it matches what you see in Unity. You can also use the “Validate” option under the PCGTerrain Component in the Inspector Window of Unity. Example submission files: • PCGTerrainData.asset • readme.txt • overview_0.png • overview_1.png • mountains_0.png • mountains_1.png • swamp_0.png • swamp_1.png • hills_0.png • hills_1.png
In this assignment you will be implementing a Fuzzy Logic Agent that can race on a procedurally generated track. Optionally, you can also train a Neural Net agent to race on the same track.Your agents will go as fast as they can without crashing, getting, stuck, turned around, etc.The vehicle is a complex physically simulated truck provided by the Free Unity Asset Store Package: Arcade car physics by saarg. You can try driving it yourself if you open the /scenes/RaceTrackHuman. It is quite challenging with interesting dynamics.Fuzzy LogicA fuzzy logic library is provided for you to use. It was developed by t0chas on Github and is based on Buckland’s Programming Game AI by Example. See https://github.com/t0chas/FuzzyLogicNote that some minor changes have been made to the library such as fixing spelling. Additionally, there is Alternate Fuzzy Rules syntax (see below) that you might find easier for defining human readable rules.Check out the Weapons example that is straight from the Buckland book. It is a good example to refer to designing your Fuzzy Logic driving agent. https://github.com/t0chas/FuzzyLogic/blob/master/UnitTest/WeaponsExample.cs Weapons Example of full evaluation: (Refer to link above for fuzzy set declaration functions)public void TestInference() { var desirability = this.GetDesirabilitySet(); // output fuzzy set var distance = this.GetDistanceToTargetSet(); // input fuzzy set var ammo = this.GetAmmoStatusSet(); // input fuzzy set // rules for interpreting fuzzy inputs and determining fuzzy output var rocketRuleSet = this.GetRocketLauncherRuleSet(desirability); FuzzyValueSet inputs = new FuzzyValueSet(); // stores fuzzy inputs distance.Evaluate(200f, inputs); // store distance fuzzy input based on crisp input ammo.Evaluate(8f, inputs); // store ammo fuzzy input based on crisp input var result = rocketRuleSet.Evaluate(inputs); // evaluate fuzzy rules // crisp value is returned and then tested here: Assert.AreEqual(60.625f, result, 0.25f); }You need to develop metrics related to the vehicle state and the track that can be fuzzified, and interpreted by fuzzy rules and then defuzzified to crisp outputs (Throttle and Steering).Neural Net[NOTE: The Neural Net part of this project is not graded and is not required to be completed.]You will use the ml-agents Unity Package to train a neural net to drive the racing truck.Follow the installation instructions here to set up the tools that you will need: https://docs.unity3d.com/Packages/[email protected]/manual/index.htmlNote that you need the dependencies that match ML-Agents Release 18 Package (see https://github.com/Unity-Technologies/ml-agents/releases). Note that the Unity project should already have com.unity.ml-agents (C#) v2.1.0-exp.1 imported.You will use the ML Agents package and tools to train your agent to drive the truck effectively on the track.Tips for the neural net are provided below, but it is recommended that you read through all the introductory documentation that Unity provides.VehicleYour agent (either FuzzyVehicle.cs or NNVehicle.cs in Scripts/GameAIStudentWork/) extends a controller for the vehicle. For FuzzyVehicle you indirectly set Throttle [-1, 1] (brake through full throttle) and Steering [-1, 1]. This is done by passing FuzzyRuleSets for throttle and steering to ApplyFuzzyRules(). Also, you can access the Speed (km/h), transform position, and other settings. You should not use the hand brake, boost, or other advanced features, or change the default settings.ApplyFuzzyRules( //T – enum type for throttle fuzzy states, //S – enum type for steering fuzzy states, FuzzyRuleSet throttleFRS, //throttle fuzzy rule set FuzzyRuleSet steerFRS, //steering fuzzy rule set FuzzyValueSet fuzzyValueSet, // input fuzzy value set //intermediate values useful for debugging follow out FuzzyValue[] throttleRuleOutput, out FuzzyValue[] steeringRuleOutput, ref FuzzyValueSet mergedThrottle, ref FuzzyValueSet mergedSteering ) – This method evaluates your fuzzy rules according to the input fuzzyValueSet and sets the crisp outputs to Throttle and Steering. This is the only way to assign Throttle and Steering in FuzzyVehicle.cs. (Note that NNVehicle.cs has direct access to Throttle and Steering) HardCodeSteering(f) – For debugging, you can hardcode the steering value. Use of this method causes autograder to fail, so don’t use it in your submission. HardCodeThrottle(f) – For debugging, you can hardcode the throttle value. Use of this method causes autograder to fail, so don’t use it in your submission. Speed – Measured in km/h. Divide by 3.6 for m/s. transform – Access WCS position, forward and up vectors Velocity – Vector3 velocity in m/s AngularVelocityProcedurally Generated TrackThe procedurally generated track is based on SebLague’s Path-Creator, a Bézier curve tool for Unity. https://github.com/SebLague/Path-Creator It has been heavily modified to support real time procedurally generated curves.Your agent (either FuzzyVehicle.cs or NNVehicle.cs in GameAIStudentWork/) can access details about the track with the PathTracker. These are useful for generating crisp input values for the Fuzzy Logic or for Neural Net observations.Useful PathTracker details: pathTracker.halfRoadWidth – Access to constant road half width from center (5m). pathTracker.distanceTravelled – The distance (m) the car is from the beginning of the current partial track (since it is always adding new segments and deleting old segments, this value changes relative to the current partial track) pathTracker.totalDistanceTravelled – The overall distance (m) the car has traveled in the forward track direction since the beginning of the race regardless of the current track path segments pathTracker.closestPointOnPath – The Vector3 world position that is on the path closest to the car (will be on track centerline) pathTracker.closestPointDirectionOnPath – The curve tangent of the closest point on path to car (see above) pathTracker.currentBezierSegmentIndex – The index into the array of Bézier segments that the car is closest to pathTracker.currentClosestPathPointIndex – The index into the array of discretized linear segments that the car is closest to pathTracker.maxPathDistance – The full length of the current segments (m) pathTracker.pathCreator.bezierPath – The curved path. This data is difficult to work with and is discretized in a linear format as “path” (see below) pathTracker.pathCreator.path – This is the discretized linear form of the path representing the Bézier path pathTracker.pathCreator.path.GetPointAtDistance(v) – This method gets the world Vector3 point on the path a certain distance down the path, possibly offset from where the car is pathTracker.pathCreator.path.GetDirectionAtDistance(v) – This method gets the tangent on the path a certain distance down the path, possibly offset from where the car is pathTracker.pathCreator.path. GetPointAndDirAtDistance (v) – Get both point and path tangent at distance at same time pathTracker.pathCreator.path.GetClosestPointOnPath(p) – Get the closest point on path to position p pathTracker.pathCreator.path.GetClosestPointDirectionOnPath(p) – Get the tangent at point on path closest to position p pathTracker.pathCreator.path.GetClosestPointAndDirectionOnPath(p) – Get both closest point on path and tangent at that point, closest to position pNOTE: There are some public methods used in tracking vehicle performance. You cannot make calls to override performance metrics. Static code analysis will be performed on your submitted code to detect calls not allowed. If found, your submission will not be accepted.Alternate Fuzzy RulesPrevious OMSCS student, Bob Kerner, made an extension to the Fuzzy Rules framework. You can write rules in an easier to read form if you like:var eatRules = new List() { If(And(FzTaste.Sweet, FzAmount.Tiny)).Then(FzEat.Chomp), If(Or(FzTaste.Sour, FzAmount.Large)).Then(FzEat.Spit), … };He also implemented: • Added Nand, Nor • Implemented Fairly, Very (not done in the current online framework) • And/Or/Nand/Nor now take up to 4 expressions instead of being limited to 2. (Extensible, too.)These extensions are in: AIVehicle.Ext.csGrading CriteriaFuzzy Logic Implementation Penalties You must control your agent exclusively with Fuzzy Logic Rules. You cannot circumvent the Fuzzy Logic interface in order to assign steering or throttle by some other means. Both throttle and steering must utilize Fuzzy Logic rules that dynamically and smoothly adjust across the [1.0, 1.0] crisp output ranges. You aren’t implementing Fuzzy Logic unless the result is “fuzzy”. This generally means that: • Fuzzy Input States within a Fuzzy Set are associated with Degree of Membership functions that overlap in the x-axis (crisp value) range. • Both Fuzzy Input Sets and Output Sets should almost always have at least three states each (and definitely at least two). • Fuzzy Rule Sets should have more than one rule, and generally at least as many as the Fuzzy Output set (these states show up in rule consequent).Preparing crisp input values for fuzzification should involve minimal conditional logic, if any. For instance, an if statement used to conditionally apply a sign to a vehicle-distance-from-centerline is fine (though multiplying by the result of Mathf.Sign(expr) is better). However, a hardcoded decision tree to create an abstract “steering-intent” crisp value is not. All the decisionmaking logic should reside exclusively in the Fuzzy Rules. In general, the crisp input values should come from relative distances and angles or vehicle state such as speed.You must change the HUD student name as well.Your Neural Net agent will not be submitted but you can participate on Piazza regarding training ideas, performance, etc.Submission:You will submit FuzzyVehicle.cs. Don’t forget to change your HUD name!Machine Learning with ML Agents Tips:What is Proximal Policy Optimization (PPO)?https://openai.com/blog/openai-baselines-ppo/Any guidelines to number of layers/nodes?https://machinelearningmastery.com/how-to-configure-the-number-of-layers-and-nodes-in-aneural-network/Guidance on rewards:https://github.com/Unity-Technologies/ml-agents/blob/main/docs/Learning-EnvironmentDesign-Agents.mdUsing an Environment Executable (faster training) https://github.com/Unity-Technologies/ml-agents/blob/main/docs/Learning-EnvironmentExecutable.md#using-an-environment-executableAlso helps to reduce graphics demands by setting windowed mode with low resolutionMight need to increase buffer size per: https://forum.unity.com/threads/num-envs-n-helpwhat-are-unity-instances.975918/Training Using Concurrent Unity Instances (faster training)https://github.com/Unity-Technologies/ml-agents/blob/main/docs/Training-MLAgents.md#training-using-concurrent-unity-instances
In this assignment you will be implementing a Finite State Machine (FSM) to control each of a team of agents playing a game of Prison Dodgeball (description below). Your FSM must be able to reliably beat the provided demonstration opponent as well as undisclosed opponents to receive full points.Your FSM should result in reasonable behavior for a video game. For instance, agents shouldn’t get stuck standing still in an unresponsive state, glitch back and forth, etc. They can however be a bit goofy (e.g. two teammates going after the same ball, not throwing at what appears to be the best target, etc.).AssessmentGrading will be based on the following aspects of your code:1.) Implement a FSM compatible with the Prison Dodgeball Game that can reliably beat opponent AI, “Glass Joe”, with various team sizes (1-5) and number of balls (1-4). Your team should win at least 2/3rds of the time. (85%) 2.) Reliably beat undisclosed AI opponent(s) 2/3rds of the time. (15%)Also, be aware that your tournament submission must run from a compiled build. So you cannot use the UnityEditor namespace.Ballistic Trajectory PredictionIn HW5, you developed algorithms for ballistic projectile trajectory solving and shot selection. You should utilize that work to improve your AI agent’s effectiveness. You will be submitting ThrowMethods.cs and ShotSelection.cs in addition to your MinionStateMachine.cs. The trajectory related files can be improved from your original HW5 submission. The autograder will not directly call them. Only your MinionStateMachine.cs file will call those methods. So it’s ok to change method signatures and types if you feel you need to.If you are not happy with your implementation in HW5, you can use the default implementation for both, which is the same that Glass Joe uses.Prison DodgeballIf you aren’t familiar with Prison Dodgeball, here is a description.The objective of the game is to throw dodgeballs at opponents to tag them (without a bounce on the playing field or walls). If an opponent is tagged, they must go to the prison behind their opponents playing area. A player in prison must wait for a teammate to throw a ball to them for a rescue. The ball must be caught without bouncing first. Prisoners are free to move back and forth in the prison boundaries but cannot leave until rescued. Also, the prisoner gets to keep the ball. Prisoners are not supposed to interact with a neutral ball, but it’s not uncommon to see kids throwing/kicking a neutral ball back to their non-prisoner teammates.Gameplay progresses until one team has all players in prison. Once that happens, the other team wins. There is an optional time limit. If time runs out there is a tie.Special circumstancesA dodgeball that bounces off an opponent and hits a second opponent without first touching the playing field tags both players out. This chain can go further as well. A dodgeball that hits a held dodgeball of an opponent (and no body part) is considered a deflection. In this case, the opponent does not go to jail.In the normal version of prison dodgeball, a player that catches a throw from the opposing teams causes the thrower to be sent to jail.Potentially, two teams can reach the point where there is one free player on either team. Furthermore, each could throw their ball at each other and simultaneously send each other to jail. If it is clear that one was tagged before the other, then there is clearly a game winning tag. However, if it cannot be determined the result is a tie.Differences in Minion Prison DodgeballIt’s not possible to catch opponents’ throws (unless there is a bug in the code). Minions play with a neutral area. Gutters and prisons have a sloped floor to return the balls. Minions play with a time limit (varies). Game rules block minions from entering an area that they are not allowed, so no penalties are necessary.Rescued minions that refuse to leave the prison or gutter will be returned to prisoner status after 10 seconds without return to the neutral area.Homework ResourcesYou will build upon the Unity project provided to you via git.This project contains scene PrisonBall which you can open and play for a demonstration.The file you will be working with is: Assets/Scripts/GameAIStudentWork/MinionStateMachine.csNote that you will also submit ThrowMethods.cs and ShotSelection.cs (even if you plan to use the default “Glass Joe” implementation)This file includes a demo implementation of a state machine. You should replace the implementation of the states with your own. However, you will likely want to keep most of the MinionStateMachine implementation. This class inherits from FiniteStateMachine and does most of the work of running the individual states. You can instantiate and AddStates() to MinionStateMachine in the method Start().Each State you implement has and Enter(), Exit(), and Update() method that you can implement. When the FSM runs a state, it first calls Enter(). Then it calls Update() until a transition occurs. Lastly Exit() is called after a transition. States can initiate a transition by returning a DeferredStateTransition to another state from Update(). If the state doesn’t want to transition yet it should return null. A DeferredStateTransition is just an object that notifies the FSM what state you want to transition to, passes any parameters the new state needs, and optionally allows the transition to immediately update before the next simulation frame (default is to not immediately update).There is a special global state to handle wildcard transitions. Also, there is a simple “TeamShare” implementation that allows for coordination between your team. It is somewhat like a Blackboard Architecture. It currently provides a way to track teammates and dodgeballs. But it could also be extended by you to track responsibilities, avoid redundant behavior, etc. Be aware that with the TeamShare, you should always check it for null before accessing. Also, check any values you store in TeamShare for null as well before using them. In all cases of a null (or otherwise invalid data), have safe fallback behavior.Here are useful features of these objects:MinionTip: when referring to minion information. All the minions have the same abilities and dimensions. So, a minion can just reference itself for things like ThrowSpeed and Radius/Height. However, transform.position, Velocity, etc., are unique to specific minions.transform.position/rotation – minion pose (centered on capsule collider centroid) Radius – radius of minion (capsule collider) Height – height of minion (capsule collider) MaxPathSpeed – how fast minion can run in a straight line ThrowSpeed – speed in m/s of fastest throw minion can make Velocity – current velocity on the navmesh SpawnIndex – what order of spawning into simulation? Good for an arbitrary id relative to team MaxAllowedOffAngleThrow – how far from directly facing target is allowed in ABS degrees? TurnToFaceSpeedDegPerSec – how fast does FaceTowards() turn? EvadeCoolDownTimeSec – how long (in sec) till another evasive action can be taken HasBall – Does the minion have a ball? DodgeballIndex – If a ball is held, the integer index into the DodgeballInfo of the PrisonDodgeballManager (see GetDodgeballInfo()). The value is -1 if a ball is not held HeldBallPosition – Where is the ball for throwing start position? IsPrisoner – Has minion been tagged and marked a prisoner? TouchingPrison – is touching the prison area? IsFreedPrisoner – Is minion freed but still walking back to playing area? CanCollectBall – Can the minion pick up a ball? CanBeRescued – Can the minion be rescued by throwing a ball to him?DisplayText(string s) – Write text above minion’s head. Helpful for debugging. FaceTowards(Vector3 target) – Turn to face target while standing still FaceTowardsForThrow(Vector3 target) – Turn so that throwing hand is facing towards target. You will generally want to use this in conjunction with ThrowBall(). SignedAngleWith(Vector3 target) – Angle minion forward vec makes with vector to target AbsAngleWith(Vector3 target) – ABS angle minion forward vec makes with vector to target GoTo(Vector3 target) – Navigate to target ReachedTarget() – Did agent reach target from GoTo() call? Stop() – Stop following navmesh path Evade(EvasionDirection ed, float strength) – take an evasive action with varying strengths (normalized scale) ThrowBall(Vector3 unitVDir, float normSpeed) – Throw ball in direction with percentage of ThrowSpeedPrisonDodgeBallManagerTeamSize BallsPerTeam IsGameOver IsTie IsWinner(Team) MatchTimeRemSec bool FindClosestNonPrisonerOpponentIndex(Vector3 myPos, Team myTeam, out int foundIndex) – Find a minion worth throwing at bool GetOpponentInfo(Team myTeam, int index, out OpponentInfo oi) – Get details about opponent public bool GetAllOpponentInfo(Team myTeam, ref OpponentInfo[] oppInfo) public bool GetDodgeballInfo(Team myTeam, int ballIndex, out DodgeballInfo di, bool determineRegion) public bool GetAllDodgeballInfo(Team myTeam, ref DodgeballInfo[] dodgeballInfo, bool determineRegion)It is possible that you can access much more information (e.g., cheat), but please limit yourself to the public properties/methods not labeled INTERNAL_. We will screen for disallowed use of INTERNAL_ methods and also GetComponent(), low level runtime access such as Reflection, and Unity game state managers. If you want to use a particular data source but are unsure, just ask on Ed.ThrowingSee HW5 regarding the logic of throwing. Use the provided default implementations if you did not develop code you are happy with (same as Glass Joe).TestingThere are a few resources to aid with testing.There are MinionTestThrowScenario and AdvancedTestThrowScenario scenes. This can help with debugging throwing with a real minion. It requires working with MinionThrowTester.cs.Unit/Integration TestingYou can find unit/integration tests under Assets/Scripts/GameAIStudentWork/PlayModeTests. There is a test that can pit two agents head-to-head over an arbitrary number of matches in various configurations.Note that you must select either the PlayMode or the EditorMode tab in the Unity Test Runner to access each test group.SubmissionSubmit file MinionStateMachine.cs, ThrowMethods.cs, and ShotSelection.cs• Be sure to change the name string • Remove ALL debug print statements for more efficient code o TEST your code after you remove print statements! • Only submit the specified source filesTournament entry will be a separate submission (probably via Canvas and not via Gradescope!). Final tournament details are TBA.
In this assignment you will be implementing prediction code for calculating the trajectory of a projectile to intercept a moving target.AssessmentGrading will be based on the following aspects of your code:1.) Implement ballistic trajectory prediction for projectiles 2.) Implement shot selection logic (decide when it is appropriate throw a dodgeball)Your ballistic trajectory implementation is important for good results in Prison Dodgeball gameplay. The results of this homework can aid you in your homework 6.Ballistic Trajectory PredictionYou can use any method for prediction including Millington’s static target method coupled with iterative refinement, Law of Cosines (LoC) with 10% Holdback, LoC with iterative refinement, or directly solve with a more advanced method (you will likely need to research quartic solving methods and implement).In terms of difficulty of implementation, Millington’s static targeting and LoC are about equal in difficulty to implement. Adding iterative refinement to static targeting (to adjust for target movement) is only slightly more effort to code than LoC with 10% holdback and it gives better range. LoC iterative is arguably difficult to implement. So, if you are looking for a recommendation you might start with Millington plus iterative refinement.Regarding assessment of your ballistic trajectory implementation, your code will be tested with isolated calls to your ThrowMethods.PredictThrow() method, within the Shooting Range scene checking accuracy and shots per minute, and within the AdvancedMinionTestThrowScenario scene (this also tests your Shot Selection logic).Isolated trajectory test scenarios will include both targets that are static and undergoing constant velocity. You will not be expected to accurately predict intercepts for targets that are accelerating, initially unreachable but become reachable after some time, are moving at extreme speeds, or are at extreme elevation differences. But positions, directions, speeds, gravity (always down in -Y direction, or zero), etc., can all vary. Your implementation is expected to reliably determine whether a target is reachable or not (correct Boolean return value).Shot selection will be tested within AdvancedMinionTestThrowScenario. The Minion AI logic found in MinionThrowTester.cs will call your ShotSelection.SelectThrow() implementation. You will select shots based on the context of the scenario. Is the opponent clearly breaking the constant velocity assumption (or will imminently)? If so, defer throwing. Is the opponent’s intercept position going to be occluded by an obstacle? If so, defer throwing.See the existing source code for parameters and scaffolding (along with hints).Homework ResourcesYou will build upon the Unity project provided to you via git.This project contains scenes relevant to this assignment: ShootingRange, MinionTestThrowScenario (probably more useful for next assignment), and AdvancedMinionTestThrowScenario. There is also Prisonball used in the next assignment.The files you will be working with are within Assets/Scripts/GameAIStudentWork/These are: • ThrowMethods.cs • ShotSelection.csHere are useful features of code you will need to access:MinionYou won’t need much information from the MinionScript for HW5, but you will need to know about a few things. See bolded text for most relevant details.Tip: When referring to minion information, all the minions have the same abilities and dimensions. So, a minion can just reference itself for things like ThrowSpeed and Radius/Height. However, transform.position, Velocity, etc., are unique to specific minions. You can’t directly access opponent minions and must use the OpponentInfo available to you.transform.position/rotation – minion pose (centered on capsule collider centroid) Radius – radius of minion (capsule collider) Height – height of minion (capsule collider) MaxPathSpeed – how fast minion can run in a straight line ThrowSpeed – speed in m/s of fastest throw minion can make Velocity – current velocity on the navmesh SpawnIndex – what order of spawning into simulation? Good for an arbitrary id relative to team MaxAllowedOffAngleThrow – how far from directly facing target is allowed in ABS degrees? TurnToFaceSpeedDegPerSec – how fast does FaceTowards() turn? EvadeCoolDownTimeSec – how long (in sec) till another evasive action can be taken HasBall – Does the minion have a ball? DodgeballIndex – If a ball is held, the integer index into the DodgeballInfo of the PrisonDodgeballManager (see GetDodgeballInfo()). The value is -1 if a ball is not held HeldBallPosition – Where is the ball for throwing start position? IsPrisoner – Has minion been tagged and marked a prisoner? TouchingPrison – is touching the prison area? IsFreedPrisoner – Is minion freed but still walking back to playing area? CanCollectBall – Can the minion pick up a ball? CanBeRescued – Can the minion be rescued by throwing a ball to him?DisplayText(string s) – Write text above minion’s head. Helpful for debugging. FaceTowards(Vector3 target) – Turn to face target while standing still FaceTowardsForThrow(Vector3 target) – Turn so that throwing hand is facing towards target. You will generally want to use this in conjunction with ThrowBall(). SignedAngleWith(Vector3 target) – Angle minion forward vec makes with vector to target AbsAngleWith(Vector3 target) – ABS angle minion forward vec makes with vector to target GoTo(Vector3 target) – Navigate to target ReachedTarget() – Did agent reach target from GoTo() call? Stop() – Stop following navmesh path Evade(EvasionDirection ed, float strength) – take an evasive action with varying strengths (normalized scale) ThrowBall(Vector3 unitVDir, float normSpeed) – Throw ball in direction with percentage of ThrowSpeedOpponentInfoYou only have access to limited info about opponents (especially for the Prison Dodgeball game).float Index – persistent spawn order index (can be used to identify same minion frame to frame) Vector3 Pos – World position Vector3 Vel – Velocity of minion Vector3 Forward – Forward vector of minion Vector3 PrevPos – Position of minion last fame Vector3 PrevVel – Velocity of minion last frame Vector3 PrevForward – Forward vector of minion last frame float Radius – opponent radius float Height – opponent height bool HasBall – Is holding a ball bool IsPrisoner – Is a prisoner bool IsFreedPrisoner – Is a prisoner returning to field of playPrisonDodgeBallManagerMinionThrowTesterYou shouldn’t need to modify this file. It is a limited implementation of AI logic to support testing of your ShotSelection and ThrowMethods. Just leave it as is and it will call the necessary methods. An original version of this file will be present in the autograder. You cannot override it.It is possible that you can access much more information (e.g., cheat), but please limit yourself to the public properties/methods not labeled INTERNAL_. We will screen for disallowed use of INTERNAL_ methods and also GetComponent(), low level runtime access such as Reflection, and some Unity game state managers. If you want to use a particular data source but are unsure if allowed, just ask on Ed.ThrowingYou must implement PredictThrow() in your ThrowMethods without modifying the method signature or changing its namespace. Refer to the lectures on Ballistic Projectile Trajectory solving to determine the method you prefer.ThrowMethods.PredictThrow() cannot call “live” game state. This includes Physics and Navmesh namespace. Analysis of live game state should only be done in ShotSelection.cs. If your PredictThrow() passes EditorMode Test Runner tests then you can be assured that your code isn’t accessing live game state.Tip: You can implement an incremental solver that itself calls a static position solver with the same method signature as below. This can be useful for testing because you can test that your static solver works with a static or very slowly moving target before adding the iterative refinement for a moving target (see Testing section regarding the shooting range).// Returns TRUE if the throw is possible, FALSE otherwise
One of the main uses of artificial intelligence in games is to perform path planning, the search for a sequence of movements through the virtual environment that gets an agent from one location to another without running into any obstacles.One of the most commonly used pathfinding algorithms for computer games is A*. With an admissible heuristic, A* provides nice guarantees about optimality—it will find the shortest path—and keep the amount of unnecessary search to a minimum.To find the closest node to goal, use A*’s estimated cost to goal node found in the search node record metadata of closed set nodes. If more than one node is tied for closest, select the one with the smallest cost from the start node up to that point. If A* is used with a null heuristic (e.g. Dijkstra) then nodes will have an estimated cost to goal of zero. In that case, fall back to a manually computed Euclidean distance.What you need to know Please consult earlier assignments for background on the Unity project. In addition to the information about the game engine provided there, the following are new elements you need to know about. AStarPathSearchImplThis class will provide the implementation for incremental path planning using the A* algorithm. Other algorithms in the Unity project depend on this implementation. Once you have successfully implemented the A* algorithm, GreedyBestFirstSearch and DijkstrasSearch will also become functional. They work by providing alternative G()/H() functions.float CostNull(Vector2 nodeA, Vector2 nodeB) This function provides the null cost (weighted graph edge weight) between two pathNodes. It is already implemented for you and should not be modified. Used for Greedy Best First Search.float HeuristicNull(Vector2 nodeA, Vector2 nodeB) This function provides the default null heuristic estimate of the remaining distance between two pathNodes. It is already implemented for you and should not be modified. Used for Dijkstra’s Algorithm.float Cost(Vector2 nodeA, Vector2 nodeB) This function provides the default cost (weighted graph edge weight) between two pathNodes. You must implement this function. Return must be non-negative. Measure the Euclidean distance between nodes.float HeuristicManhattan(Vector2 nodeA, Vector2 nodeB) This function provides the heuristic estimate of the remaining distance between two pathNodes using Manhattan distance. You must implement this function. Return must be non-negative.float HeuristicEuclidean(Vector2 nodeA, Vector2 nodeB) This function provides the heuristic estimate of the remaining distance between two pathNodes using Euclidean distance. You must implement this function. Return must be non-negative.public static PathSearchResultType FindPathIncremental()Arguments: GetNodeCount getNodeCount – A callback that returns the integer number of graph nodes. E.g. int count = getNodeCount(). GetNode getNode – A callback that returns the node at position i. E.g. Vector2 v = getNode(i) GetNodeAdjacencies getAdjacencies – A callback that returns the adjacency list for node at position i. E.g. List adj = getAdjacencies(i) CostCallback G – Cost function that return a non-negative float, taking two Vector2 arguments. If you aren’t familiar with C#, G can be called like any other function. E.g., G(nodeA, nodeB)CostCallback H – Heuristic estimate function that returns a non-negative float, taking two Vector2 arguments. If you aren’t familiar with C#, H can be called line any other function. E.g., H(nodeA, nodeB) bool doInitialization – true if the method should be initialized as starting a new search from the startNodeIndex, with new currentNodeIndex, searchNodeRecords, openNodes, closedNodes, and returnPath. Future incremental calls will be made with false. Note that initialization can be requested on any call ref int currentNodeIndex – The current node the A* algorithm is working from. Note that this is only used for visualization purposes in the A* search (especially during incremental search). The current node is determined by the open set priority queue. However other search algorithms might use this as an in/out param to track state. ref Dictionary searchNodeRecords – a dictionary that associates a PathNode index with metadata pertaining to the PathNode in question. A Dictionary is built into the .NET/mono framework and provides quick mapping between key/value pairs.PathSearchNodeRecord (struct) The metadata necessary to facilitate A* search (and other search types). See: /Assets/Scripts/Framework/PathSearch/PathSearchNodeRecord.cs Struct Members: NodeIndex – the PathNode index of the node that the PathSearchNodeRecord pertains to FromNodeIndex – the PathNode index that lead to the NodeIndex being added to the openNodes set. CostSoFar – The sum of edge weights (G function) that lead to this node EstimatedTotalCost – The CostSoFar plus the Heuristic estimate to the goal from this node Constructor() – Note that there are constructors for instantiating this structlicense) for SimplePriorityQueue is provided in Assets/3rdParty/FastPriorityQueue/ ref HashSet closedNodes – A HashSet of PathNode indexes. These nodes are considered to be (mostly) closed to further consideration in the A* algorithm. A HashSet is built into the .NET/mono framework and provides quick determination of membership in the set. ref List returnPath – A list of indexes of PathNodes. Upon completion of the A* algorithm. This list will be a path from the startNode to the goalNode. If the goalNode was impossible to reach, the returnPath will lead from the startNode to the node closest to the goalNode. Note that this requires modification to the A* algorithm. If return value is successful and has run to completion (returning Complete, Partial) then the returnPath should not be null and contain the path from startNode to goalNode and include those two nodes. If the path is partial, then the final node is instead the node-closest-to-goal. If the return value is InitializationError or InProgress, then returnPath is considered undefined (it can be anything).Return value: PathSearchResultType – This is an enumeration that details the status of the AStar Incremental Search. The enumeration values are as follows.Complete – The A* algorithm has completed calculation and found the goal. Partial – The A* algorithm has completed calculation and only found a partial path. InProgress – The A* algorithm has not yet found a solution. Further calls must be made to complete the search. InitializationError – The A* algorithm has been called with invalid arguments. This can be returned even if doInitialization is not set to true.Instructions To complete this assignment, you must implement the A* algorithm.Download this project from github. Open the project in Unity. Utilize your previous grid and path network solutions, and open either scene (do eventually test both).If you don’t have a valid solution, then you can use the hard coded solutions by enabling “Use Hard Coded Cases” in the Unity Inspector when viewing the NavigationArea game object of both the GridNavigation and PathNetwork scenes. The option will be in the Game Grid or Path Network component sections.Try left-clicking somewhere on the map that is not an obstacle or waypoint. You should see the agent find a path using BreadthFirstSearch. Hit spacebar to cycle through search algorithms (text in top right of HUD). Note that A*, GreedyBestFirst, and Dijkstra won’t work until you implement A*. Try right-clicking to initiate an incremental search. Observe the metadata visualization that draws little arrows showing open/closed sets and FromNode direction (best observed in the grid scene). You can use Shift Right-Click to manually step with “N” for next step. You can clear the metadata visualization with “C”.In the Unity Inspector view of the AgentSphere, you can change IncrSearchMaxNode to different values for testing step sizes other than 1.Once you are familiar with the interface, implement your A* algorithm in Assets/Scripts/GameAIStudentWork/AStar/AstarPathSearchImpl.csMake sure you change the name string and also implement the three methods. Keep in mind that A* must: 1.) Solve incrementally 2.) Return a path to the closest node to the goal, if the goal cannot be reached 3.) Work correctly when the caller passes different G() and H() functions. This is demonstrated with Dijkstra and GreedyBestFirstSearch methods, which are implemented as variants of the base AStar algorithm.Grading Assessment of this assignment will be based on determining whether your algorithm can successfully find the goal, if reachable, can do so incrementally, only search nodes as necessary for A*, etc.Special considerations: • You must not skip putting the goal node in the searchNodeRecords with correct meta data. If the goal node is not reachable, then instead the node closest to goal must be in the searchNodeRecords with correct meta data. This is for grading purposes. • You must always include the start node, the goal node (or node closest to goal), and all the nodes in-between and in order, in your returned pathYour code will be allowed at least 10 seconds to complete each test.HintsStart with the basic A* and ignore maxNumNodesToExplore. Just return PathSearchResultType.Complete/Partial instead of InProgress.Similarly, you can ignore finding the closest node to goal (if goal cannot be reached) until you get the basics working.Don’t forget to later test with AgentSphere’s IncrSearchMaxNode Inspector property.Check out BasicPathSearchImpl.cs and GreedySimplePathSearchImpl.cs for other working search algorithm code.Make new entries in CustomPresetConfig.cs for further testing (do not submit this file).Create Unit/Integration tests with AStarTest.cs. It’s highly recommended that you create several tests! Passing the provided example test(s) in this file does NOT indicate that you have a correct solution!Submission To submit your solution, upload your modified AStarPathSearchImpl.cs with updated name stringYou should not modify any other files in the game engine. (You can modify CustomPresetConfig.cs but don’t turn that in.) DO NOT upload the entire game engine.See Canvas assignment description for specific submission instructions (most like GradeScope).
In this homework you will be implementing an algorithm for creating NavMeshes.A navigation mesh (or navmesh) is a method of creating a discretized space representation of a navigable area. A navigation mesh is a set of convex polygons overlaid on an environment such that the area within each polygon is guaranteed to be obstacle-free. The variable size and dimensions of navmesh polygons provide efficient representation of space as compared to the uniform structure of a grid lattice. It also captures more usable information about the environment than a path network alone. The convexity of the polygons is important because an agent within the area of a polygon can move to any other point within without crossing a boundary (e.g. colliding).When two navmesh convex polygons are adjacent to each other (i.e., they share an edge), that edge can be thought of as a “portal”—an invisible door—from one safe navigation region to another. Connecting adjacent convex polygons into a network of safe paths results in a path graph through which an agent can travel between connected navigable locations.There are various ways to convert a navmesh into a graph with path locations (e.g. a path network). A robust approach is to the use the midpoint of each portal edge to create each pathNode. These pathNodes are connected to all other portal edge midpoints within the same navmesh polygon.In this assignment, you will write the code to generate a navmesh for an arbitrary environment as well as an accompanying path network from the navmesh.There are three main challenges of the assignment: 1. Form adjacent triangles that cover all the navigable space 2. Merge triangles into larger, more efficient polygons that are also convex 3. Create a path graph from the navmeshWhat you need to know Please consult homework 1 for background on the Game Engine. In addition to the information about the game engine provided there, the following elements will be used.CreateNavMesh This file contains a Create() method that you must implement. Additionally, be sure to change the student name string. Considerable scaffolding and comments are provided, which will aid in development of your solution.Create(): Creates a navmesh and pathNetwork (associated with navmesh) canvasOrigin: bottom left corner of navigable region in world coordinates canvasWidth: width of navigable region in world dimensions canvasHeight: height of navigable region in world dimensions obstacles: a list of CCW Polygons that are obstacles in the scene. These are already expanded and clipped to the canvas. No holes are present in the polygons, but are possibly concave.agentRadius: the radius of the agent origTriangles: out param of the triangles that are used for navmesh generation. These triangles are passed out for validation and visualization navmeshPolygons: out param of the convex polygons of the navmesh (list). These polys are passed out for validation and visualization and should be merged adjPolys: out param of type AdjacentPolygons. This is a dictionary that maps CommonPolygonEdges to CommonPolygons. Used for validation and should be merged pathNodes: out param: a list of graph nodes, centered on each portal edge of the navmesh pathEdges: out param: graph adjacency list for each graph node. corresponding index of pathNodes to match node with its edge list. All nodes must have an edge list (no null list) entries in each edge list are indices into pathNodes. All edges should have a matching edge going opposite direction and no duplicate edges.The scaffolding and inline comments of CreateNavMesh.Create() gives specific guidance and recommendations on other classes and methods to use (including methods at the top of the file).Instructions Download the project from Github and open in Unity. Open the Navmesh scene and the CreateNavMesh.cs file. Follow the comments in CreateNavMesh.Create() to build a working navmesh generator. Don’t forget to set the student name to your name.Note: There is an assignment demonstration video on Canvas, but be aware that it demonstrates different versions of the assignment. Be sure and pay attention to the requirements for this semester, particularly related to node placement in navmesh polygons.Grading We will grade your solution based generally on three criteria:● Coverage: The navmesh should cover the entire navigable area of the map, no more and no less. ● Reachability: The path network should include pathNodes at the midpoint of each portal edge of the navmesh polygons and pathEdges should connect with the pathNodes of other portal edges within the same navmesh polygon. Valid edges must have a corresponding edge in opposite direction and there must not be duplicates of the same edge. Every node must have a non-null edge list. Nodes should not link to self. You should not need test for obstacle distance from edges like in HW2. Instead only use the navmesh polygons to determine node connectivity.● Mesh optimization: Your solution should effectively merge navmesh triangles (or more sided polygons) together resulting in a reduction of pathNetwork complexityYour code will be allowed at least 20 seconds to complete each test.Submission To submit your solution, upload your modified CreateNavMesh.cs (did you remember to change the student name string to your name?). All work should be done within this file. Helper methods within the same file are fine.You should not modify any other files in the game engine. DO NOT upload the entire game engine.Refer to the Canvas assignment description for submission details (most likely GradeScope).
One of the main uses of artificial intelligence in games is to perform path planning, the search for a sequence of movements through the virtual environment that gets an agent from one location to another without running into any obstacles. For now, we will assume static obstacles. In order for an agent to engage in path planning, there must be a topography for the agent to traverse that is represented in a form that can be efficiently reasoned about. Grid topologies discretize the environment and usually assumes an agent can be in one discrete cell or another. However, for many games such as 1st-person shooters, a more continuous model of space is beneficial. Depending on the granularity of the grid, a lot of space around obstacles becomes inaccessible in grid-based approaches. Finally, grids result in unnecessarily large number of cell transitions.A path network is a set of path nodes and edges that facilitates obstacle avoidance. The path network discretizes a continuous space into a small number of points and edges that allow transitions between points. However, unlike a grid topology, a path network does not require the agent to be at one of the path nodes at all times. The agent can be at any point in the terrain. When the agent needs to move to a different location and an obstacle is in the way, the agent can move to the nearest path node accessible by straight-line movement and then find a path through the edges of the path network to another path node near to the desired destination.In this assignment, you will be provided with different terrains with obstacles and hard-coded path nodes. You must write the code to generate the path network, as a set of edges between path nodes. An edge between path nodes exists when (a) there is no obstacle or boundary wall between the two path nodes, (b) there is sufficient space on either side of the edge so that an agent can follow the line without colliding with any obstacles or boundary wall and (c) a path node that is inside the boundary but outside of any obstacles. Nodes that are outside of the boundary or inside of obstacles, should not connect.Furthermore, there should be edges in both directions. If there is an edge from Node A to Node B, then there should be an edge from Node B to Node A. Also, if there should be an edge from Node A to Node B, it should appear exactly once in the edge list for Node A (no duplicates). Also, no nodes should link to self.If two nodes are arbitrarily close together, including possibly located at exactly the same location, they should still be connected.What you need to know Please consult homework 1 for background on the Unity Project. In addition to the information about the game engine provided there, the following applies.CreatePathNetwork This is the only file you will be modifying and submitting for this homework. It provided functionality to create a path network from provided pathNodes.String StudentAuthorName – Please change to your nameCreate()This is the method you will be finishing. You can create helper methods in the same source code file if you like.Parameters: Vector2 canvasOrigin – Bottom left corner of navigable space float canvasWidth – Width of navigable space float canvasHeight – Height of navigable space List obstacles – The polygon obstacles that obstruct candidate pathEdges between nodes. Furthermore, end points cannot be within agentRadius distance (less-than test) of a candidate pathEdges float agentRadius – The radius of the agent (don’t expect to always be the same). The agentRadius will always be greater than zero float minPoVDist – The minimum distance a single point of visibility can be from the vertex or lines of angle that is bisected. Only used when generating PoVs float maxPoVDist – The maximum distance a single point of visibility can be from the vertex or lines of angle that is bisected. Only used when generating PoVs ref List pathNodes – The nodes of the graph. You use them as provided if mode is PathNetworkMode.Predefined. But you generate them if mode is PathNetworkMode.PointsOfVisibility out List pathEdges – A list of valid edges, indexing the pathNodes. This is generated by your code. All valid edges should be generated. pathEdges will be returned empty if there are no nodes to consider. PathNetworkMode mode – enum that is either PathNetworkMode.Predefined. or PathNetworkMode.PointsOfVisibility. The first specifies that path nodes are provided to Create() for connection. The second specifies that path nodes must be generated according to PoV algorithm.PathNetworkPathNetworkTest This file is for unit/integration testing. You are highly encouraged to create your own tests. For instance, you might consider different numbers of nodes present, including edge cases. Passing the provided example test(s) in this file does NOT indicate that you have a correct solution! Miscellaneous utility functions Methods you need for this assignment are provided at the top of CreatePathNetwork.cs Also, you will access Polygon member methods such as getIntegerPoints() and getPoints()In terms of Computational Geometry, the DistanceToLineSegment() works best with floats. You can use the poly.getPoints(), which are unscaled floats. The poly.getIntegerPoints() are the equivalent vectors in scaled integer form (by 1000).Instructions To complete this assignment, you must (1) implement code to generate a path network for a set of given path nodes in a given scene. The path network should guarantee that an agent will not collide with an obstacle between any starting point and any destination point in the world.It is not required, nor graded, but you can consider implementing Points of Visibility support as well. See below for details.To run the project code, use the following commands: > Step 1: Download the project from github. Open the project in Unity. Open scene PathNetwork > Step 2: If you hit play, you should see a list of path nodes and some obstacles not connected to each other. You can click the obstacles and path nodes to drag them around. You can press buttons 1,2,3,… to test some preconfigured obstacle/pathNode positions. Clicking outside of an obstacle initiates path planning. Spacebar changes search strategies. Note that any search that relies on AStar won’t function until you implement it. > Step 3: Create the edges in the path network. Open Assets/Scripts/GameAIStudentWork/PathNetwork/CreatePathNetwork.cs. Update the name string first! Implement the functionality to generate a valid list of PathEdges connecting PathNodes that are not obstructed from each other. Also, obstacles cannot be too close to PathEdges for the agent to fit by while following an edge.Grading We will grade your solution based on the following criterion: ● Reachability: The path network should be such that an agent can navigate from any path node to any other path node along any edge in the network without colliding with an obstacle or canvas/world boundary. No edges that are out of bounds (outside boundary or inside obstacles). ● Graph Characteristics: Valid edges should have a corresponding edge going opposite direction between same two nodes. There should be no duplicate edges in each edge list. Nodes should not have an edge directly back to itself. Edge lists should never be null (empty is allowed). Edge lists should not reference non existent node indexes. PathNodes and pathEdges should be the same length. ● Points of Visibility: You don’t need to respond to the PathNetworkMode mode parameter. But you can optionally implement Points of Visibility support.Your code will be allowed at least 10 seconds to complete each test.Hints Make sure any edge in the path network is traversable by an agent that has physical size. That is, edges in the path network should never come too close to any Obstacle such that an agent blindly following the path edge collides with an Obstacle (or the edges of the map). It doesn’t matter how close two path nodes are to one another. If an agent can be centered at one node and traverse in a straight line (without intersecting any obstacles) to another node then the two nodes should be connected by an edge.Create additional presets by adding more configurations to Assets/Scripts/Config/CustomPresetConfig.cs However, you do not submit this file.Also, create Unit/Integration tests with PathNetworkTest.cs (also do not submit).Submission To submit your solution, upload your modified CreatePathNetwork.cs with your name properly set in the name string. All work should be done within this file.You should not modify any other files in the game engine (other than optionally CustomPresetConfig.cs for your own testing purposes).DO NOT upload the entire game engine.Refer to Canvas assignment description for submission instructions (probably GradeScope).Advanced Method
Setup 1. Clone this repository: git clone (personal repository link).git 2. Navigate to the assignment_6/ directory 3. Activate your AI environment if you’re using Anaconda 4. Run the following command to install all requirements for this assignment: pip install -r requirements.txt Overview Hidden Markov Models are used extensively in Artificial Intelligence, Pattern Recognition, Computer Vision, and many other fields. If a system has unobservable (hidden) states and each state is independent of the prior, then we can create a model of that system using probability distributions over a sequence of observations. The idea is that we can provide this system with a series of observations to use to query what is the most likely sequence of states that generated these observations. The Files Submission All submissions will be via Gradescope. If you’re completing this assignment in Jupyter Notebook, you must run the notebook2script.py file to export your work to a python file. To generate your submission file, run the command python notebook2script.py submission: and your file will be created under the submission directory. Upload the resulting submission.py file to the Assignment 6A assignment on Gradescope for feedback. IMPORTANT: A total of 10 submissions is allowed for this assignment. Please use your submissions carefully and do not submit until you have thoroughly tested your code locally. If you’re at 9 submissions, use your tenth and last submission wisely. The submission marked as ‘Active’ in Gradescope will be the submission counted towards your grade. Resources 1. Canvas Lectures on Pattern Recognition Through Time (Lesson 8) 2. Challenge Questions on Edstem 3. We have provided a copy of the Wikipedia page that has been edited for the benefit of this assignment Local Testing If you are using submission.py to complete the assignment instead of the Jupyter Notebook, you can run the tests using: python hmm_submission_tests.py This will run all unit tests for the assignment, comment out the ones that aren’t related to your part (at the bottom of the file) if going step by step. The Assignment The goal of this assignment is to demonstrate the power of probabilistic models. You will build a word recognizer for American Sign Language (ASL) video sequences. In particular, this project employs hidden Markov models (HMM’s) to analyze a series of measurements taken from videos of isolated American Sign Language (ASL) signs collected for research. (see the Isolated Sign Language Recognition Corpus). In each video, an ASL signer signs a meaningful sentence. In a typical ASL recognition system, you observe the XY coordinates of the speaker’s left hand, right hand, and nose for every frame. The following diagram shows how the positions of the left hand (Red), right hand (Blue), and nose (Green) change over time. Saturation of colors represents time elapsed.In this assignment, for the sake of simplicity, you will only use the Y-coordinates of the right hand and the right thumb to construct your HMM. In Part 1 you will build a one dimensional model, recognizing words based only on a series of right-hand Y coordinates; in Part 2 you will go multidimensional and utilize both the right hand and the right thumb features. At this point, you will have two observed coordinates at each time step (frame) representing right hand & right thumb Y positions. The words you will be recognizing are “ALLIGATORâ€, “NUTS”, and “SLEEP”. These individual signs can be seen in the sign phrases from our dataset:ALLIGATORNUTSSLEEP Part 1a: Encoding the HMM [15 Points] Use the training samples from the table below. Provide the transition and prior probabilities as well as the emission parameters for all three words with accuracy to 3 decimal digits. Round the values to 3 decimal places thoughout entire assignment: – 0.1 stays 0.1 or 0.100 – 0.1234 rounds to 0.123 – 0.2345 rounds to 0.235 – 0.3456 rounds to 0.346 – 0.0123 rounds to 0.012 – 0.0125 rounds to 0.013 Those values can be hardcoded in your program. Don’t use round() from python. Word | Frames | Observed sequence | Initial State1 | Initial State2 | Initial State3 — | — | — | — | — | — ALLIGATOR | 17 | 31, 28, 28, 37, 68, 49, 64, 66, 22, 17, 53, 73, 81, 78, 48, 49, 47 | 31, 28, 28, 37, 68, 49 | 64, 66, 22, 17, 53, 73 | 81, 78, 48, 49, 47 ALLIGATOR | 10 | 25, 62, 75, 80, 75, 36, 74, 33, 27, 34 | 25, 62, 75, 80 | 75, 36, 74, 33 | 27, 34 ALLIGATOR | 16 | -4, 69, 59, 45, 62, 22, 17, 28, 12, 14, 24, 32, 39, 61, 35, 32 | -4, 69, 59, 45, 62, 22 | 17, 28, 12, 14, 24, 32 | 39, 61, 35, 32 NUTS | 11 | 45, 68, 62, 75, 61, 44, 73, 72, 71, 75, 55 | 45, 68, 62, 75 | 61, 44, 73, 72 | 71, 75, 55 NUTS | 18 | 33, 33, 32, 32, 34, 38, 43, 41, 35, 36, 36, 37, 38, 38, 39, 40, 38, 38 | 33, 33, 32, 32, 34, 38 | 43, 41, 35, 36, 36, 37 | 38, 38, 39, 40, 38, 38 NUTS | 19 | 33, 31, 29, 28, 25, 24, 25, 28, 28, 38, 37, 40, 37, 36, 36, 38, 44, 48, 48 | 33, 31, 29, 28, 25, 24, 25 | 28, 28, 38, 37, 40, 37, 36 | 36, 38, 44, 48, 48 SLEEP | 8 | 37, 35, 41, 39, 41, 38, 38, 38 | 37, 35, 41 | 39, 41, 38 | 38, 38 SLEEP | 12 | 22, 17, 18, 35, 33, 36, 42, 36, 41, 41, 37, 38 | 22, 17, 18, 35 | 33, 36, 42, 36 | 41, 41, 37, 38 SLEEP | 13 | 38, 37, 35, 32, 35, 13, 36, 41, 41, 31, 32, 34, 34 | 38, 37, 35, 32, 35 | 13, 36, 41, 41, 31 | 32, 34, 34 As shown in the diagram below, each one of the three words (ALLIGATOR, NUTS, and SLEEP) has exactly THREE hidden states in its HMM. All words must start from State 1 and can only transit to the next state or stay in the current one.Training sequences need to have 3 hidden states no matter what! If you follow the HMM training procedure described in Canvas, you might encounter a situation where a hidden state is squeezed out by an adjacent state; that is, a state might have its only observation moved to another state. In that situation, always keep at least one observation for that hidden state. Example: Assume you’ve reached a stage where the following is true: – State 1 has mean=53 & std=6 – State 2 has mean=37 & std=9 – State 3 has mean=70 & std=8 The next training sample has the following observed sequence: 45 45 34 | 30 30 25 36 52 | 62 69 74 and you are trying to adjust the location of state boundary between State 1 & 2. You first move it 1 step to the left since 34 is closer to State 2, and then you realize that 45 is still closer to State 2. If you follow the same routine, you will end up with no obvervation for State 1. In order to prevent this from happening, you have to stop at the last “45” and as a result leave the boundary as 45 | 45 34 30 30 25 36 52 | 62 69 74 Now you meet the ‘3 hidden states per sample’ requirement. Some hints/guidelines for training How should we compare if an observation if closer to one state or another? Check how many standard deviations away is the observation from the mean for each state. Example: Say 46 is the rightmost observation in State 1. If we denote the mean and std of State i as μi,σi, then we should be comparing |46−μ1| / σ1 vs |46−μ2| / σ2 For HMM training, which side of the boundary should we check first while assigning observed sequence values to states? After computing the mean and std for each state, adjust the boundary between the states. Always start from the 1st element at the LEFT side of the boundary. If the LEFT element is closer to the next state, then move the boundary leftward. If the LEFT element should stay at the current state, then check the RIGHT element. This is just done to make sure that everyone gets the same results in the context of the assignment. Functions to complete: 1. part_1_a()Part 1b: Creating the Viterbi Trellis [40 Points] The goal here will be to use the HMM derived from Part 1a (states, prior probabilities, transition probabilities, and parameters of emission distribution) to build a Viterbi trellis. When provided with an evidence vector (list of observed right-hand Y coordinates), the function will return the most likely sequence of states that generated the evidence and the probabilty of that sequence being correct. For example, an evidence vector [38, 37, 35, 32, 35, 13, 36, 41, 41, 31, 32, 34, 34] (last training sequence for “SLEEP”) should output a sequence [‘S1’, … ‘S2’, … ‘S3’] If no sequence can be found, the algorithm should return one of the following tuples: (None, 0) (null), ([], 0) (empty list) or ([‘A1’, ‘A1’, … ‘A1’],0) (Or all being the first state of that letter) “No sequence can be found” means the probability reaches 0 midway. If you find an incomplete sequence with some probability, output that sequence with its probability. Note: DO NOT consult any external sources other than the Wikipedia PDF in the assignment. Failure to abide by this requirement will lead to a 0 on the assignment. Functions to complete: 1. viterbi() Hint: In order to reconstruct your most-likely path after running Viterbi, you’ll need to keep track of a back-pointer at each state, which directs you to that state’s most-likely predecessor. You are asked to use the provided function gaussian_prob to compute emission probabilities. In a typical HMM model you have to convert the probability to log-base in order to prevent numerical underflow, but in this assignemnt we will only test your function against a rather short sequence of observations, so DO NOT convert the probability to logarithmic probability or you will fail on Gradescope. Gradescope: In the autograder, we will also test your code against other evidence_vectors.Part 2a: Multidimensional Output Probabilities [6 Points] In Part 1a, we use only right-hand Y-axis coordinates as our feature, and now we are going to use two features – the same right-hand Y-axis coordinates and the right-thumb Y-axis coordinates. Using observations from both the right hand and the right thumb as features can increase the accuracy of our model when dealing with more complex sentences. Here you are given the transition probabilities and the emission parameters of right-thumb Y-axis locations, following the same procedure conducted in Part 1a.ALLIGATOR | State 1 | State 2 | State 3 — | — | — | — Mean | 53.529 | 40.769 | 51.000 Std | 17.493 | 6.104 | 12.316 NUTS | State 1 | State 2 | State 3 — | — | — | — Mean | 36.318 | 60.000 | 37.476 Std | 7.376 | 15.829 | 8.245 SLEEP | State 1 | State 2 | State 3 — | — | — | — Mean | 35.357 | 31.462 | 38.333 Std | 7.315 | 5.048 | 7.409 Functions to complete: 1. part_2_a()Part 2b: Improving the Viterbi Trellis [39 Points] Modify the Viterbi trellis function to allow multiple observed values (Y locations of the right hand and the right thumb) for a state. The return format should be identical to Part 1b. Note: DO NOT consult any external sources other than the Wikipedia PDF in the assignment. Failure to abide by this requirement will lead to a 0 on the assignment. Functions to complete: 1. multidimensional_viterbi() Gradescope: In the autograder, we will also test your code against other evidence_vectors.CONGRATULATIONS! You have just completed your final assignment for CS6601 Artificial Intelligence.
Expectation Maximization – Assignment 5 – CS6601Setup Clone this repository: Create new conda environment for this assignment. conda env create -f ai_a5_env.yml Activate environment with, conda activate ai_a5_env Jupyter Notebook: You will be using jupyter notebook to complete this assignment. To open the jupyter notebook, navigate to your assignment folder, activate the conda environment conda activate ai_a5_env, and run jupyter notebook. Project description and all of the functions that you will implement are in solution.ipynb file. ATTENTION: You are free to add additional cells for debugging your implementation, however, please don’t write any inline code in the cells with function declarations, only edit the section inside the function, which has comments like: # TODO: finish this function. Grading The grade you receive for the assignment will be distributed as follows: 1. k-Means Clustering (19 points) 2. Gaussian Mixture Model (48 points) 3. Model Performance Improvements (20 points) 4. Bayesian Information Criterion (12 points) 5. Return your name (1 point) Note: For this assignment, we do not have any bonuses. Submission The tests for the assignment are provided in mixture_tests.py. All the tests are already embedded into the respective ipython notebook cells, so they will run automatically whenever you run the cells with your code. Local tests are sufficient for verifying the correctness of your implementation. The tests on Gradescope will be similar to the ones provided here. You’ll need to ensure that your submissions are sufficiently vectorized so that algorithms won’t time out. To get the submission file, make sure to save your notebook and run: python notebook2script.py submit Once the execution is complete, open autogenerated submit/submission.py and verify that it contains all of the imports, functions, and classes you are required to implement. Only then proceed to the Gradescope for submission. In your Gradescope submission history, you can mark certain submissions as Active. Please ensure this is your best submission. Do NOT erase the #export at the top of any cells as it is used by notebook2script.py to extract cells for submission. You will be allowed 3 submissions every 3 hours on gradescope. Make sure you test everything before submitting it. The code will be allowed to run for not more than 40 minutes per submission. In order for the code to run quickly, make sure to VECTORIZE the code (more on this in the notebook itself). Resources 1. Canvas lectures on Unsupervised Learning (Lesson 7) 2. The gaussians.pdf in the read/ folder will introduce you to multivariate normal distributions. 3. A youtube video by Alexander Ihler, on multivariate EM algorithm details: https://www.youtube.com/watch?v=qMTuMa86NzU 4. The em.pdf chapter in the read/ folder. This will be especially useful for Part 2 of the assignment. 5. Numpy and vectorization related Stackexchange discussion Hackernoon article Numpy einsum (highly recommended) Slicing and indexing Copies and views Fancy indexing
Setup Clone this repository: git clone https://github.gatech.edu/CS66012025Spring/assignment4_[YOUR GT GITHUB USER] You will be able to use numpy, math, time and collections.Counter for the assignment You will be able to use the sklearn and graphviz for jupyter notebook visualization only No other external libraries are allowed for solving this problem. We do check. Please use the ai_env environment from previous assignments If you are using an IDE: Ensure that in your preferences, that ai_env is your interpreter and that the assignment_4 directory is in your project structure Else: From your ai_env Terminal: conda activate ai_env The supplementary testing notebooks use jupyter: visualize_tree and unit_testing. From your ai_env Terminal: jupyter notebook The supplementary Helper notebook to visualize Decision tree, requires the graphviz library. From your ai_env Terminal: pip install graphviz==0.17.0 or alternatively pip install -r requirements.txt If you have difficulty or errors on graphviz0.17 From your ai_env Terminal: conda install -c conda-forge python-graphviz which installs version 0.19 (compatible) The previous semester’s FAQ can be found under Files Overview Machine Learning is a subfield of AI, and Decision Trees are a type of Supervised Machine Learning. In supervised learning an agent will observe sample input and output and learn a function that maps the input to output. The function is the hypothesis ”’ y = f(x)”’. To test the hypothesis we give the agent a test set different than the training set. A hypothesis generalizes well if it correctly predicts the y value. If the value is finite, the problem is a classification problem, if it is a real number it is considered a regression problem. When classification problems have exactly two values (+,-) it is Boolean classification. When there are more than two values it is called Multi-class classification. Decision trees are relatively simple but highly successful types of supervised learners. Decision trees take a vector of attribute values as input and return a decision. [Russell, Norvig, AIMA 3rd Ed. Chptr. 18] Decision Trees The deliverable for the assignment is to upload a completed **_submission.py_** to Gradescope. * All functions must be completed in **_submission.py_** for full credit **Important**: Submissions to Gradescope are rate limited for this assignment. **You can submit two submissions every 60 minutes during the duration of the assignment**. Since we want to see you innovate and imagine new ways to do this, we know this can also cause you to fail (spectacularly in my case) For that reason you will be able to select your strongest submission to Gradescope. In your Gradescope submission history, you will be able to mark your best submission as ‘Active’. This is a students responsibility and not faculty. ### The Files You are only required to edit and submit **_submission.py_**, but there are a number of important files: 1. **_submission.py_**: Where you will build your decision tree, confusion matrix, performance metrics, forests, and do the vectorization warm up. 2. **_decision_trees_submission_tests.py_**: Sample tests to validate your trees, learning, and vectorization locally. 3. **_visualize_tree.ipnb_**: Helper Notebook to help you understand decision trees of various sizes and complexity 4. **_unit_testing.ipynb_**: Helper Notebook to run through tests sequentially along with the readme ### Resources * Canvas *Thad’s Videos*: [Lesson 7, Machine Learning] (https://gatech.instructure.com/courses/336814/pages/7-machine-learning?module_item_id=3369476) * Textbook:Artificial Intelligence Modern Approach (3rd Ed. Chapters may have changed for 4th Ed.) * Chapter 18 Learning from Examples * Chapter 20 Learning Probabilistic Models * [Cross-validation](https://en.wikipedia.org/wiki/Cross-validation_(statistics)) * [K-Fold Cross-validation] (https://web.stanford.edu/~lmackey/stats202/content/lec11-condensed.pdf) ### Decision Tree Datasets 1. **_hand_binary.csv_**: 4 features, 8 examples, binary classification (last column) 2. **_hand_multi.csv_**: 4 features, 12 examples, 3 classes, multi-class classification (last column) 3. **_simple_binary.csv_**: 5 features, 100 examples, binary classification (last column) 4. **_simple_multi.csv_**: 6 features, 100 examples, 3 classes, multi-class classification (last column) 5. **_mod_complex_binary.csv_**: 7 features, 1600 examples, binary classification (last column) 6. **_mod_complex_multi.csv_**: 10 features, 2400 examples, 5 classes, multi-class classification (last column) 7. **_complex_binary.csv_**: 10 features, 2800 examples, binary classification (last column) 8. **_complex_multi.csv_**: 16 features, 4800 examples, 9 classes, multi-class classification (last column) 9. **_part23_data.csv_**: 4 features, 1372 example, binary classification (last column) * Not provided, but will have less class separation and more centroids per class. Complex sets given for development * **_challenge_binary.csv_**: 10 features, 5400 examples, binary classification (last column) * **_challenge_multi.csv_**: 16 features, 10800 examples, 9 classes, multi-class classification (last column) #### NOTE: path to the datasets! ‘./data/your_file_name.csv’ #### Warmup Data **_vectorize.csv_**: data used during the vectorization warmup for Assignment 4 #### Imports **NOTE:** We are only allowing four imports: numpy, math, collections.Counter and time. We will be checking to see if any other libraries are used. You are not allowed to use any outside libraries especially for part 4 (challenge). Please remember that you should not change add or change any input parameters other than in part 4. #### Rounding **NOTE:** Although your local tests will have some rounding, it is meant to quickly test your work. Overall this assignment follows the CI 6601 norm of rounding to 6 digits. If in doubt, in use round: ``` x = 0.12345678 round(x, 6) Out[4]: 0.123457 ``` — ### Part 0: Vectorization! _[10 pts]_ * File to use to benchmark tests: **_vectorize.csv_** The vectorization portion of this assignment will teach you how to use matrices to significantly increase the speed and decrease processing complexity of your AI problems. Matrix operations, linear algebra and vector space axioms and operations will be challenging to learn. Learn this, and it will benefit you throughout OMSCS courses and your career. You will not be able to meet time requirements, nor process large datasets without Vectorization Whether one is training a deep neural network on millions of images, building random forests for a U.S. National Insect Collection dataset, or optimizing algorithms, machine learning requires _extensive_ use of vectorization. The NumPy Open Source project provides the **numpy** python scientific computing package using low-level optimizations written in C. If you find the libraries useful, consider contributing to the body of knowledge (e.g. help update and advance numpy) You will not meet the time limits on this assignment without vectorization. This small section will introduce you to vectorization and one of the high-demand technologies in python. We encourage you to use any numpy function to do the functions in the warmup section. You will need to beat the non-vectorized code to get full points. TAs will offer little help on this section. This section was created to help get you ready for this and other assignments; feel free to ask other students on Ed Discussion or use some training resources. (e.g. https://numpy.org/learn/) How grading works: 1. We run your vectorized code against nonvectorized code 500 times, as long as you have the correct answer and your average time is significantly less than the average time of the nonvectorized code, you will get the points. #### Functions to complete in the `Vectorization` class: 1. `vectorized_loops()` 2. `vectorized_slice()` 3. `vectorized_flatten()` 4. `vectorized_glue()` 5. `vectorized_mask()` — ## The Assignment [Creative Commons sourced][cc] E. Thadeus Starner5th is the 5th incarnation of the great innovator and legendary pioneer of Starner Eradicatus Mosquitoes. For centuries the mosquito has imparted only harm on human health, aiding in transmission of malaria, dengue, Zika, chikungunya, CoVid, and countless other diseases impact millions of people and animals every year. The Starner Eradicatus, *Anopheles Stephensi* laser zapper has obtained the highest level of precision, recall, and accuracy in the industry![Creative Commons sourced][cc] The secret is the classification engine which has compiled an unmatched library of classification data collected from 153 countries. Flying insects from the tiny Dicopomorpha echmepterygis (Parasitic Wasp) to the giant titanus giganteus (Titan Beetle) are carefully catalogued in a comprehensive digital record and indexed to support fast and correct classification. This painstaking attention to detail was ordered by A. Thadeus1st to address a tumultuous backlash from the International Pollinators Association to a high mortality among beneficial pollinators.[Creative Commons sourced][cc][Creative Commons sourced][cc] Skeeter explains his idea to E.T. to generalize the Starner Eradicatus zapper to handle a variety of these pests. Wonderful! E.T. exclaims, and becomes wildly excited at the opportunity to bring such an important benefit to the World.[Creative Commons sources below][cc] The wheels of invention lit up the research Scrum that morning as E.T. and Skeeter storyboard the solution. People are calling out all the adjustments, wing acoustics, laser power and duration, going through xyz positioning, angular velocity and acceleration calculations, speed, occlusion noise and tracking errors. You as the lead DT software engineer are taking it all in, when you realize and speak up…, sir… Sir… SIR… and a hush falls. Sir, we are doing Boolean classification and will need to refactor to multi-class classification. E.T. turns to you and with that look in his eye, gives you and your team two weeks to deliver multi-class classification! You will build, train and test decision tree models to perform multi-class classification tasks. You will learn how decision trees and random forests work. This will help you develop an intuition for how and why accuracy differs for training and testing data based on different parameters. ### Assignment Introduction For this assignment we need an explicit way to make structured decisions. The `DecisionNode` class will be used to represent a decision node as some atomic choice in a multi-class decision graph. You must use this implementation for the nodes of the Decision Tree for this assignment to pass the tests and receive credit. An object of type ‘DecisionNode’ can represent a * decision node * *left*: will point to less than or equal values of the split value, type DecisionNode, True evaluations * *right*: will point to greater than values of the split value, type DecisionNode, False evaluations * *decision_function*: evaluates an attribute’s value and maps each vector to a descendant * *class_label*: None * leaf node * *left*: None * *right*: None * *decision_function*: None * *class_label*: A leaf node’s class value * Note that in this representation ‘True’ values for a decision take us to the left. — ### Part 1: Building a Binary Tree by Hand #### Part 1a: Build a Tree _[10 Pts]_ In `build_decision_tree()`, construct a decision tree capable of predicting the class (col y) of each example. Using the columns A0-A3 build the decision tree and nodes in python to classify the data with 100% accuracy. Your tests should use as few attributes as possible, break ties with equal select attributes by selecting the one which classifies the greatest number of examples correctly. For ties in number of attributes and correct classifications use the lower index numbers (e.g. select **A1** over **A2**) | X | A0 | A1 | A2 | A3 | y | | — | ——- | ——- | ——- | ——- | — | | x01 | 1.1125 | -0.0274 | -0.0234 | 1.3081 | 1 | | x02 | 0.0852 | 1.2190 | -0.7848 | -0.7603 | 2 | | x03 | -1.1357 | 0.5843 | -0.3195 | 0.8563 | 0 | | x04 | 0.9767 | 0.8422 | 0.2276 | 0.1197 | 1 | | x05 | 0.8904 | -1.7606 | 0.3619 | -0.8276 | 0 | | x06 | 2.3822 | -0.3122 | -2.0307 | -0.5065 | 2 | | x07 | 0.7194 | -0.4061 | -0.7045 | -0.0731 | 2 | | x08 | -2.9350 | 0.7810 | -2.5421 | 3.0142 | 0 | | x09 | 2.4343 | -1.5380 | -2.7953 | 0.3862 | 2 | | x10 | 0.8096 | -0.2601 | 0.5556 | 0.6288 | 1 | | x11 | 0.8577 | -0.2217 | -0.6973 | -0.1095 | 1 | | x12 | 0.0568 | 0.0696 | 1.1153 | -1.1753 | 0 | #### Requirements: The total number of elements(nodes, leaves) in your tree should be < 10 #### Hints: To get started, it might help to **draw out the tree by hand** with each attribute representing a node. To create a decision function for `DecisionNode`, you are allowed to use python lambda expressions: ``` func = lambda feature : feature[2] = 60% * 25 pts: average test accuracy over 10 rounds should be >= 75% Meanwhile back in the lab… As the size of our flying training set grows, it rapidly becomes impractical to build multiclass trees by hand. We need to add a class with member functions to manage this, it is too much! To do list: * Initialize the class with useful variables and assignments * Fill out the member function that will fit the data to the tree, using build * Fill out the build function * Fill out the classify function For starters, consider these helpful hints for the construction of a decision tree from a given set of examples: 1. Watch your base cases: 1. If all input vectors have the same class, return a leaf node with the appropriate class label. 2. If a specified depth limit is reached, return a leaf labeled with the most frequent class. 3. Splits producing 0, 1 length vectors 4. Splits producing less or equivalent information 5. Division by zero 2. Use the DecisionNode class 3. For each attribute alpha: evaluate the information gained by splitting on the attribute `alpha`. 4. Let `alpha_best` be the attribute value with the highest information gain. 5. As you progress in this assignment this is going to be tested against larger and more complex datasets, think about how it will affect your identification and selection of values to test. 6. Create a decision node that splits on `alpha_best` and split the data and classes by this value. 7. When splitting a dataset and classes, they must stay synchronized, do not orphan or shift the indexes independently 8. Use recursion to build your tree, by using the split lists, remember true goes left using decide 9. Your features and classify should be in numpy arrays where for dataset of size (_m_ x _n_) the features would be (_m_ x _n_-1) and classify would be (_m_ x _1_) 10. The features are real numbers, you will need to split based on a threshold. Consider different approaches for what this threshold might be. First, in the `DecisionTree.__build_tree__()` method implement the above algorithm. Next, in `DecisionTree.classify()`, write a function to produce classifications for a list of features once your decision tree has been built. How grading works: 1. We load **_mod_complex_multi.csv_** and create our cross-validation training and test set with a `k=10` folds. We use our own `generate_k_folds()` method. 2. We fit the (folded) training data onto the tree then classify the (folded) testing data with the tree. 3. We check the accuracy of your results versus the true results and we return the average of this over k=10 iterations. #### Functions to complete in the `DecisionTree` class: 1. `__build_tree__()` 2. `fit()` 3. `classify()` — #### Part 2c: Validation _[7 pts]_ * File to use: **_part23_data.csv_** * Allowed use of numpy, collections.Counter, and math.log * Grading: average test accuracy over 10 rounds should be >= 80% Reserving part of your data as a test set can lead to unpredictable performance as you may not have a complete set or proportionately balanced representation of the class labels. We can overcome this limitation by using k-fold cross validation. There are many benefits to using cross-validation. See book 3rd Ed Evaluating and Choosing the Best Hypothesis 18.4 In `generate_k_folds()`, we’ll split the dataset at random into k equal subsections. Then iterating on each of our k samples, we’ll reserve that sample for testing and use the other k-1 for training. Averaging the results of each fold should give us a more consistent idea of how the classifier is doing across the data as a whole. For those who are not familiar with k folds crossvalidation, please refer the tutorial here: [A Gentle Introduction to k-fold Cross-Validation](https://machinelearningmastery.com/k-fold-crossvalidation/). How grading works: 1. The same as 2b however, we use your `generate_k_folds()` instead of ours. #### Functions to complete in the `submission` module: 1. `generate_k_folds()` — ### Part 3: Random Forests _[25 pts]_ * File to use: **_mod_complex_binary.csv, mod_complex_multi.csv_** * Allowed use of numpy, collections.Counter, and math.log * Allowed to write additional functions to improve your score * Allowed to switch to Entropy and splitting entropy * Grading: * 15 pts: average test accuracy over 10 rounds should be >= 50% * 20 pts: average test accuracy over 10 rounds should be >= 70% * 25 pts: average test accuracy over 10 rounds should be >= 80% Decision boundaries drawn by decision trees are very sharp, and fitting a decision tree of unbounded depth to a set of training examples almost inevitably leads to overfitting. In an attempt to decrease the variance of your classifier you are going to use a technique called ‘Bootstrap Aggregating’ (often abbreviated as ‘bagging’). Decision stumps are very short decision trees used in Ensemble classification such as Random Forests * They are usually short (depth limited) * They use smaller (but more of them) random datasets for training * They use a subset of attributes drawn randomly from the training set * They fit the tree to the sampled dataset and are considered specialized to the set * Advanced learners may use weighting of their classifier trees to improve performance * They use majority voting (every tree in the forest votes) to classify a sample A Random Forest is a collection of decision trees, built as follows: 1. For every tree we’re going to build: 1. Subsample the examples provided us (with replacement) in accordance with a provided example subsampling rate. 2. From the samples, choose attributes (without replacement) at random to learn on (as specified in attribute subsampling rate) 3. Fit a decision tree to the subsample of data we’ve chosen (to a limited depth). When sampling attributes you choose from the entire set of attributes for every sample drawn (but specify the sampling method does not use replacement) Complete `RandomForest.fit()` to fit the decision tree as we describe above, and fill in `RandomForest.classify()` to classify a given list of examples. You can use your decision tree implementation or create another. Your features and classify should use numpy arrays datasets of (_m_ x _n_) features of (_m_ x _n_-1) and classify of (_n_ x _1_). To test, we will be using a forest with 80 trees, with a depth limit of 5, example subsample rate of 0.3 and attribute subsample rate of 0.3 How grading works: 1. Similar to 2b but with the call to Random Forest. #### Functions to complete in the `RandomForest` class: 1. `fit()` 2. `classify()` — #### Part 4 (Optional) Boosting Competition Challenge (Extra Credit) #### Let the games begin! — 让游æˆå¼€å§‹ — ας ξεκινήσει το παιχνίδι #### THIS WILL REQUIRE A SEPARATE SUBMISSION * Files to use: **_complex_binary.csv, complex_multi.csv_** * Allowed use of numpy, collections.Counter, and math.log * Allowed to write additional functions to improve your score * Allowed to switch to Entropy and splitting entropy * Ranked by Balanced Accuracy Weighted, Precision, and Recall * Ties broken by efficiency (speed) * Extra Credit Points towards your final grade: * 5 pts: 1st place algorithm test over 10 rounds * 4 pts: 2nd place algorithm test over 10 rounds * 3 pts: 3rd place algorithm test over 10 rounds * 2 pts: 4th place algorithm test over 10 rounds * 1 pt: 5th place algorithm test over 10 rounds Decision boundaries drawn by decision trees are very sharp, and fitting a decision tree of unbounded depth to a set of training examples almost inevitably leads to overfitting. In an attempt to decrease the variance of your classifier you are going to use a technique called ‘Boosting’ implementing one of the boosting algorithms such as, Ada-, Gradient- and XG-, boost or your personal favorite. Similar to RF, the Decision stumps are short decision trees used in these Ensemble classification methods * They are usually short (depth limited) * They use smaller (but more of them) random datasets for training with sampling bias * They use a subset of attributes sampled from the training set * They fit the tree to the sampled dataset and are considered specialized to the set * They use weighting of their sampling and classifiers to reflect the balance or unbalance of the data * They use majority voting (every tree in the forest votes) to classify a sample Ada-boost Algorithm example [Zhu, et al.]: N Samples, M classifiers, W weights, C classifications, K classes, I indicator 1. Initialize the observation weights wi = 1/n, i = 1, 2, . . . , n. 2. For m = 1 to M: 1. Fit a classifier T(m)(x) to the training data using weights wi. 2. Compute err(m) = Sum(i=1..n)wi I(ci != T(m)(xi)) / Sum(i=1..n) wi 3. Compute α(m) = log (1−err(m)/err(m)) + log(K − 1). 4. Set wi ↠wi · exp (α(m) I(ci != T(m)(xi)), i = 1, . . . , n. 5. Re-normalize wi. 3. Output C(x) = argmax(k) sum(m=1..M) α(m) · I(T(m)(x) = k). [Multi-class AdaBoost](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.158.4221&rep=rep1&type=pdf) Zhu, Ji & Rosset, Saharon & Zou, Hui & Hastie, Trevor. (2006). Multi-class AdaBoost. Statistics and its interface. 2. 10.4310/SII.2009.v2.n3.a8. When sampling attributes you choose from the entire set of attributes without replacement based on the weighted distribution. Notice that you favor or bias towards misclassified samples, which improves your overall accuracy. Visualize how the short trees balance classification bias. Complete `ChallengeClassifier.fit()` to fit the decision tree as we describe above, and fill in `ChallengeClassifier.classify()` to classify examples. Use your decision tree implementation as your classifier or create another. Your features and classify should use numpy arrays datasets of (_m_ x _n_) features of (_m_ x _n_-1) and classes of (_m_ x _1_). How grading works: To test, we will be running 10 rounds, using your boosting with 200 trees, with a depth limit of 3, example subsample rate of 0.1 and attribute subsample rate of 0.2. You will have a time limit. #### Functions to complete in the `ChallengeClassifier` class: 1. `init()` 2. `fit()` 3. `classify()` — ### Part 5: Return Your name! _[1 pts]_ Return your name from the function `return_your_name()` — ### Helper Notebook #### Note: You do not need to implement anything in this notebook. This part is not graded, so you can skip this part if you wish to. This notebook is just for your understanding purpose. It will help you visualize Decision trees on the dataset provided to you. The notebook Visualize_tree.iypnb can be use to visualize tree on the datasets. Things you can Observe: 1. How the values are split? 2. What is the gini value at leaf nodes? 3. What does internal nodes represents in this DT? 4. Why all leaf nodes are not at same depth? Feel free to change and experiment with this notebook. you can look and use Information gain as well instead of gini to see how the DT built based on that. ### Video and picture attribution [cc]: All GT OMSCS materials are copyrighted and retain rights prohibiting redistribution or alteration Creative Commons sources share and share alike were used for the videos: [[File:Lucanus Cervus fighting.webm|Lucanus_Cervus_fighting]] Nicolai Urbaniak, CC0, via Wikimedia Commons https://commons.wikimedia.org/wiki/File:2013-06-07_13-41-29-insecta-anim.ogv Thomas Bresson, CC BY 3.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Traumatic-insemination-and-female-counteradaptation-in-Strepsiptera-(Insecta)-srep25052-s2.ogv Peinert M, Wipfler B, Jetschke G, Kleinteich T, Gorb S, Beutel R, Pohl H, CC BY 4.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Broscus_cephalotes.webm О.Ð.П., CC BY-SA 4.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Termites_walking_on_the_floor_of_Eastern_Himalyan_rainforest.webm Jenis Patel, CC BY-SA 4.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:The_carrot_caterpillar_-.webm Contributor NamesPathé frères (France)Pathé Frères (U.S.)AFI/Nichol (Donald) Collection (Library of Congress)Created / PublishedUnited States : Pathé Frères, 1911., Public domain, via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Gaeana_calling.webm Shyamal, CC BY-SA 3.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Kluse_- _Tenebrio_molitor_larvae_eating_iceberg_lettuce_leaf_v_02_ies.webm Frank Vincentz, CC BY-SA 3.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Lispe_tentaculata_male_-_2012-05-31.ogv Pristurus, CC BY-SA 3.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Xylotrupes_socrates_(Siamese_rhinoceros_beetle)_behavior.webm Basile Morin, CC BY-SA 4.0 , via Wikimedia Commons laser – https://commons.wikimedia.org/wiki/File:Mosquito_dosing_by_laser_2.webm https://commons.wikimedia.org/wiki/File:Mosquito_dosing_by_laser_3.webm https://commons.wikimedia.org/wiki/File:Mosquito_dosing_by_laser_4.webm Matthew D. Keller et al., CC BY 4.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Laser-induced-mortality-of-Anophelesstephensi-mosquitoes-srep20936-s5.ogv Keller M, Leahy D, Norton B, Johanson T, Mullen E, Marvit M, Makagon A, CC BY 4.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Predicting-Ancestral-Segmentation-Phenotypes-from-Drosophila-to-Anopheles-Using-In-SilicoEvolution-pgen.1006052.s001.ogv Rothschild J, Tsimiklis P, Siggia E, François P, CC BY 4.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Focused_Laguerre-Gaussian_beam.webm Jack Kingsley-Smith, CC BY-SA 4.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:President_Reagan%27s_Remarks_at_Bowling_Green_State_University,_September_26,_1984.webm Reagan Library, CC BY 3.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:NID_Participants_Preparing_Their_Project_- _Workshop_On_Design_And_Development_Of_Digital_Experiencing_Exhibits_-_NCSM_-_Kolkata_2018-08-09_3141.ogv Biswarup Ganguly, CC BY-SA 4.0 , via Wikimedia Commons https://commons.wikimedia.org/wiki/File:Davos_2017__An_Insight,_An_Idea_with_Sergey_Brin.webm World Economic Forum, CC BY 3.0 , via Wikimedia Commons Creative Commons Attribution-Share Alike 4.0
â—â—â— Critical: Only 7 Submissions Allowed On Gradescope for this Assignment.âš ï¸âš ï¸âš ï¸ In this assignment, you will work with probabilistic models known as Bayesian networks to efficiently calculate the answer to probability questions concerning discrete random variables. Resources You will find the following resources helpful for this assignment. Canvas Videos: Textbook: 4th edition: Chapter 12: Quantifying Uncertainty Chapter 13: Probabilistic Reasoning 3rd edition: Chapter 13: Quantifying Uncertainty Chapter 14: Probabilistic Reasoning Setup â—â—â— Critical: Only 7 Submissions Allowed On Gradescope for this Assignment.âš ï¸âš ï¸âš ï¸ 1. Clone the project repository from Github git clone [your URL] Substitute your actual username where the angle brackets are. 1. Navigate to assignment_3/ directory 2. Activate the environment you created during Assignment 0 conda activate ai_env In case you used a different environment name, to list of all environments you have on your machine you can run conda env list. 3. Run the following command in the command line to install and update the required packages pip install torch torchvision -f https://download.pytorch.org/whl/torch_stable.html pip install –upgrade â—â—â— Critical: Only 7 Submissions Allowed On Gradescope for this Assignment.âš ï¸âš ï¸âš ï¸ Please include all of your own code for submission in submission.py. Important: There is a TOTAL submission limit of 7 on Gradescope for this assignment. This means you can submit a maximum of 7 times during the duration of the assignment. Please use your submissions carefully and do not submit until you have thoroughly tested your code locally. If you’re at 6 submissions, use your last submission wisely. The submission marked as ‘Active’ in Gradescope will be the submission counted towards your grade. Restrictions You are not allowed to use following set of modules from ‘pgmpy’ Library. pgmpy.sampling.* pgmpy.factor.* pgmpy.estimators.*Part 1 Bayesian network tutorial: [35 points total] To start, design a basic probabilistic model for the following system: James Bond, Q (Quartermaster), and M (Head of MI6) are in charge of the security system at MI6, the Military Intelligence Unit of the British Secret Service. MI6 runs a special program called “Double-0â€, where secret spy agents are trained and deployed to gather information concerning national security. A terrorist organization named “Spectre†is planning an espionage mission and its aim is to gain access to the secret “Double-0†files stored in the MI6 database. Q has designed a special security system to protect the secret “Double-0†files. In order to gain access to these files, Spectre needs to steal from MI6 a cipher and the key to crack this cipher. Q stores this cipher in his personal database, which is guarded by heavy security protocols. The key to cracking the cipher is known only to M, who is protected by Bond. 1a: Casting the net [10 points] Thus, Spectre can carry out their mission by performing the following steps: Hire professional hackers who can write programs to launch a cyberattack on Q’s personal database. Buy a state-of-the-art computer called “Contra†to actually launch this cyberattack. Hire ruthless mercenaries to kidnap M and get access to the key. Make sure Bond is not available with M at the time of the kidnapping. Use the cipher and key to access the target “Double-0†files. Sensing the imminent danger, MI6 has hired you to design a Bayes Network for modeling this espionage mission, so that it can be avoided. MI6 requires that you use the following name attributes for the nodes in your Bayes Network: “Hâ€: The event that Spectre hires professional hackers “Câ€: The event that Spectre buys Contra “Mâ€: The event that Spectre hires mercenaries “Bâ€: The event that Bond is guarding M at the time of the kidnapping “Qâ€: The event that Q’s database is hacked and the cipher is compromised “Kâ€: The event that M gets kidnapped and has to give away the key “Dâ€: The event that Spectre succeeds in obtaining the “Double-0†files Based on their previous encounters with Spectre, MI6 has provided the following classified information that can help you design your Bayes Network: Spectre will not be able to find and hire skilled professional hackers (call this false) with a probability of 0.5. Spectre will get their hands on Contra (call this true) with a probability of 0.3. Spectre will be unable to hire the mercenaries (call this false) with a probability of 0.2. The professional hackers will be able to crack Q’s personal database (call this true) without using Contra with a probability of 0.55. However, if they get their hands on Contra, they can crack Q’s personal database with a probability of 0.9. In case Spectre can not hire these professional hackers, their less experienced employees will launch a cyberattack on Q’s personal database. In this case, Q’s database will remain secure with a probability of 0.75 if Spectre has Contra and with a probability of 0.95 if Spectre does not have Contra. When Bond is protecting M, the probability that M stays safe (call this false) is 0.85 if mercenaries conduct the attack. Else, when mercenaries are not present, it the probability that M stays safe is as high as 0.99! However, if M is not accompanied by Bond, M gets kidnapped with a probability of 0.95 and 0.75 respectively, with and without the presence of mercenaries. With both the cipher and the key, Spectre can access the “Double-0†files (call this true) with a probability of 0.99! If Spectre has none of these, then this probability drops down to 0.02! In case Spectre has just the cipher, the probability that the “Double-0†files remain uncompromised is 0.4. On the other hand, if Spectre has just the key, then this probability changes to 0.65. Use the description of the model above to design a Bayesian network for this model. The pgmpy package is used to represent nodes and conditional probability arcs connecting nodes. Don’t worry about the probabilities for now. Use the functions below to create the net. You will write your code in submission.py. Fill in the function make_security_system_net() The following commands will create a BayesNet instance add node with name “node_name”: BayesNet = BayesianNetwork() BayesNet.add_node(“node_name”) You will use BayesNet.add_edge() to connect nodes. For example, to connect the parent and child nodes that you’ve already made (i.e. assuming that parent affects the child probability): Use function BayesNet.add_edge(,). For example: BayesNet.add_edge(“parent”,”child”) After you have implemented make_security_system_net(), you can run the following test in the command line to make sure your network is set up correctly. python probability_tests.py ProbabilityTests.test_network_setup 1b: Setting the probabilities [15 points] Now set the conditional probabilities for the necessary variables on the network you just built. Fill in the function set_probability() Using pgmpy’s factors.discrete.TabularCPD class: if you wanted to set the distribution for node ‘A’ with two possible values, where P(A) to 70% true, 30% false, you would invoke the following commands: cpd_a = TabularCPD(‘A’, 2, values=[[0.3], [0.7]]) If you wanted to set the distribution for P(G|A) to be | A |P(G=true given A)| | —— | —– | | T | 0.75| | F | 0.85| you would invoke: cpd_ga = TabularCPD(‘G’, 2, values=[[0.15, 0.25], [ 0.85, 0.75]], evidence=[‘A’], evidence_card=[2]) Reference for the function: https://pgmpy.org/_modules/pgmpy/factors/discrete/CPD.html Modeling a three-variable relationship is a bit trickier. If you wanted to set the following distribution for P(T|A,G) to be | A | G |P(T=true given A and G)| | — | — |:—-:| |T|T|0.15| |T|F|0.6| |F|T|0.2| |F|F|0.1| you would invoke cpd_tag = TabularCPD(‘T’, 2, values=[[0.9, 0.8, 0.4, 0.85], [0.1, 0.2, 0.6, 0.15]], evidence=[‘A’, ‘G’], evidence_card=[2, 2]) The key is to remember that first entry represents the probability for P(T==False), and second entry represents P(T==true). Add Tabular conditional probability distributions to the bayesian model instance by using following command. bayes_net.add_cpds(cpd_a, cpd_ga, cpd_tag) You can check your probability setups in the command line with python probability_tests.py ProbabilityTests.test_probability_setup and probability values: ``` python probability_tests.py ProbabilityTests.test_security_system_probabilities ``` 1c: Probability calculations : Perform inference [10 points] To finish up, you’re going to perform inference on the network to calculate the following probabilities: What is the marginal probability that the “Double-0†files get compromised? You just received an update that the British Elite Forces have successfully secured and shut down Contra, making it unavailable for Spectre. Now, what is the conditional probability that the “Double-0†files get compromised? Despite shutting down Contra, MI6 still believes that an attack is imminent. Thus, Bond is reassigned full-time to protect M. Given this new update and Contra still shut down, what is the conditional probability that the “Double-0†files get compromised? You’ll fill out the “get_prob” functions to calculate the probabilities: – get_marginal_double0() – get_conditional_double0_given_no_contra() – get_conditional_double0_given_no_contra_and_bond_guarding() Here’s an example of how to do inference for the marginal probability of the “A” node being True (assuming bayes_net is your network): solver = VariableElimination(bayes_net) marginal_prob = solver.query(variables=[‘A’], joint=False) prob = marginal_prob[‘A’].values To compute the conditional probability, set the evidence variables before computing the marginal as seen below (here we’re computing P(‘A’ = false | ‘B’ = true, ‘C’ = False)): solver = VariableElimination(bayes_net) conditional_prob = solver.query(variables=[‘A’],evidence={‘B’:1,’C’:0}, joint=False) prob = conditional_prob[‘A’].values NOTE: marginal_prob and conditional_prob return two probabilities corresponding to [False, True] case. You must index into the correct position in prob to obtain the particular probability value you are looking for. Part 2: Sampling [65 points total] For the main exercise, consider the following scenario. There are three frisbee teams who play each other: the Airheads, the Buffoons, and the Clods (A, B and C for short). Each match is between two teams, and each team can either win, lose, or draw in a match. Each team has a fixed but unknown skill level, represented as an integer from 0 to 3. The outcome of each match is probabilistically proportional to the difference in skill level between the teams. Sampling is a method for ESTIMATING a probability distribution when it is prohibitively expensive (even for inference!) to completely compute the distribution. Here, we want to estimate the outcome of the matches, given prior knowledge of previous matches. Rather than using inference, we will do so by sampling the network using two Markov Chain Monte Carlo models: (2c) Gibbs sampling and (2d) Metropolis-Hastings . 2a: Build the network. [10 points] For the first sub-part, consider a network with 3 teams : the Airheads, the Buffoons, and the Clods (A, B and C for short). 3 total matches are played. Build a Bayes Net to represent the three teams and their influences on the match outcomes. Fill in the function get_game_network() Assume the following variable conventions: | variable name | description| |———|:——:| |A| A’s skill level| |B | B’s skill level| |C | C’s skill level| |AvB | the outcome of A vs. B (0 = A wins, 1 = B wins, 2 = tie)| |BvC | the outcome of B vs. C (0 = B wins, 1 = C wins, 2 = tie)| |CvA | the outcome of C vs. A (0 = C wins, 1 = A wins, 2 = tie)| Use the following name attributes: “A” “B” “C” “AvB” “BvC” “CvA” Assume that each team has the following prior distribution of skill levels: |skill level|P(skill level)| |—-|:—-:| |0|0.15| |1|0.45| |2|0.30| |3|0.10| In addition, assume that the differences in skill levels correspond to the following probabilities of winning: | skill difference (T2 – T1) | T1 wins | T2 wins| Tie | |————|———-|—|:——–:| |0|0.10|0.10|0.80| |1|0.20|0.60|0.20| |2|0.15|0.75|0.10| |3|0.05|0.90|0.05| You can check your network implementation in the command line with python probability_tests.py ProbabilityTests.test_games_network 2b: Calculate posterior distribution for the 3rd match. [5 points] Suppose that you watched two of the three games and observed the following outcome: A beats B A draws with C Calculate the posterior distribution for the outcome of the BvC match in calculate_posterior(). Let’s first use the inference engine, VariableElimination, provided by the pgmpy library to perform inference. This result will be the ground truth for you to test your estimation in 2c) Gibbs and 2d) MH, where you are NOT allowed to use the inference engine there. You can check your posteriors in the command line with python probability_tests.py ProbabilityTests.test_posterior NOTE: In the following sections, we’ll be arriving at the same values by using sampling-based methods. Hints Regarding sampling for Part 2c, 2d, and 2e Hint 1: In both Metropolis-Hastings and Gibbs sampling, you’ll need access to each node’s probability distribution and nodes. You can access these by calling: A_cpd = bayes_net.get_cpds(‘A’) team_table = A_cpd.values AvB_cpd = bayes_net.get_cpds(“AvB”) match_table = AvB_cpd.values Hint 2: While performing sampling, you will have to generate your initial sample by sampling uniformly at random an outcome for each nonevidence variable and by keeping the outcome of your evidence variables (AvB and CvA) fixed. Hint 3: You’ll also want to use the random package, e.g. random.randint() or random.choice(), for the probabilistic choices that sampling makes. 2c: Gibbs sampling [15 points] Implement the Gibbs sampling algorithm, which is a special case of Metropolis-Hastings. You’ll do this in Gibbs_sampler(), which takes a Bayesian network and initial state value as a parameter and returns a sample state drawn from the network’s distribution. The function should just consist of a “single iteration” of the algorithm. “Single iteration” means this function only generate just one new sample based on the previous sample you have. The new sample is chosen with some distribution you have to compute by written down the equation. If an initial value is not given (initial state is None or and empty list), default to a state chosen uniformly at random from the possible states. Your sampling process could look like something below: state_chosen := randomly chosen index from init_state tuple if state_chosen = A: (derive your formula yourself) (Don’t use VariableElimination or other inference engine, or you will have 600 sec timeout issue on Grade Scope) prob = [your formula] sample new state with the prob else if state_chosen = B: … else if … Note: DO NOT USE the given inference engines or pgmpy samplers to run the sampling method, since the whole point of sampling is to calculate marginals without running inference. “YOU WILL SCORE 0 POINTS ON THIS ASSIGNMENT IF YOU USE THE GIVEN INFERENCE ENGINES FOR THIS PART” 2d: Metropolis-Hastings sampling This method should just perform a “single iteration” of the algorithm. If an initial value is not given, default to a state chosen uniformly at random from the possible states. Note: DO NOT USE the given inference engines to run the sampling method, since the whole point of sampling is to calculate marginals without running inference. “YOU WILL SCORE 0 POINTS IF YOU USE THE PROVIDED INFERENCE ENGINES, OR ANY OTHER SAMPLING METHOD” 2e: Comparing sampling methods [19 points] Now we are ready for the moment of truth. Given the same outcomes as in 2b, A beats B and A draws with C, you should now estimate the likelihood of different outcomes for the third match by running Gibbs sampling until it converges to a stationary distribution. We’ll say that the sampler has converged when, for “N” successive iterations, the difference in expected outcome for the 3rd match differs from the previous estimated outcome by less than “delta”. N is a positive integer, delta goes from (0,1). For the most stationary convergence, delta should be very small. N could take values like 10,20,…,100 or even more. Play it out yourself! Use the functions from 2c and 2d to measure how many iterations it takes for Gibbs and MH to converge to a stationary distribution over the posterior. See for yourself how close (or not) this stable distribution is to what the Inference Engine returned in 2b. And if not, try tuning those parameters(N and delta). (You might find the concept of “burn-in” period useful). You can choose any N and delta (with the bounds above), as long as the convergence criterion is eventually met. Repeat this experiment for Metropolis-Hastings sampling. Fill in the function compare_sampling() to perform your experiments Which algorithm converges more quickly? By approximately what factor? For instance, if Metropolis-Hastings takes twice as many iterations to converge as Gibbs sampling, you’d say that Gibbs converged faster by a factor of 2. Fill in sampling_question() to answer both parts. You only need to comment out or delete “raise NotImplementedError” and modify choice and factor. 2f: Return your name â—â—â— Critical: Only 7 Submissions Allowed On Gradescope for this Assignment.âš ï¸âš ï¸âš ï¸ [1 point] A simple task to wind down the assignment. Return your name from the function aptly called return_your_name(). ~~~~~~~~
This assignment will cover some of the concepts discussed in the Adversarial Search lectures. You will be implementing game playing agents for a variant of the game Isolation. Table of Contents Setup Jupyter Jupyter Tips FAQ IDE Setup For this assignment, we highly recommend you to create a new environment just for this one assignment. conda create -n ai_env_a2 python=3.9 Activate the environment: conda activate ai_env_a2 In case you used a different environment name, to get a list of all environments you have on your machine, you can run conda env list. Install correct package versions that will be used for visualising the game board. cd assignment_2 pip install -r requirements.txt Jupyter python -m ipykernel install –user –name ai_env_a2 –display-name “Python 3.9 (AI-A2)” Further instructions are provided in the notebook.ipynb. Run: jupyter notebook Once started you can access http://localhost:8888 in your browser. Jupyter Tips 1. My Jupyter notebook does not seem to be starting up or my kernel is not starting correctly. Ans: This probably has to do with activating virtual environments. If you followed the setup instructions exactly, then you should activate your conda environment using conda activate from the Anaconda Prompt and start Jupyter Notebook from there. 2. I was running cell xxx when I opened up my notebook again and something or the other seems to have broken. Ans: This is one thing that is very different between IDEs like PyCharm and Jupyter Notebook. In Jupyter, every time you open a notebook, you should run all the cells that a cell depends on before running that cell. This goes for cells that are out of order too (if cell 5 depends on values set in cell 4 and 6, you need to run 4 and 6 before 5). Using the “Run All” command and its variants (found in the “Cell” dropdown menu above) should help you when you’re in a situation like this. 3. The value of a variable in one of my cells is not what I expected it to be? What could have happened? FAQ 1. What depth does the server call my search algorithms with? Ans: The server will not pass a depth value to your CustomPlayer; whatever you set as the default parameter value will be used on Gradescope. Modifying this default value is extremely important in changing the performance of your agent. 2. How does Gradescope set up and run each game? Ans: Gradescope will run 20 games in order to determine the win ratio. Your player (CustomPlayer) will be K1 for 10 of those games and K2 for 10 of those games. Each player has 1 second to make each move and the first two moves (i.e. each player’s starting location) will be randomized. 3. Can we use multithreading of multiprocessing? Ans: Sorry, we will not allow multithreading or multiprocessing on this Assignment. It isn’t necessary to successfully complete the Assignment. 4. I have a question about the isolation API or the workings of the framework. Where should I learn more? 5. Can I add more functions to replace some of the existing functions? Can I import other packages as well? Ans: No. Please do not add any more functions or imports. You should be able to finish the assignment by replacing the NotImplementedError. A more in-depth FAQ will be posted on Ed IDE In case you are willing to use IDE (e.g. Pycharm) to implement your assignment in .py file. Please run: bash python helpers/notebook2script.py submission You will get autogenerated submission/submission.py file where you can write your code. However, make sure you have gone through the instructions in the notebook.ipynb at least once.
Search is an integral part of AI. It helps in problem solving across a wide variety of domains where a solution isn’t immediately clear. Your task is to implement several search algorithms that will calculate a route between two points in Romania while seeking to minimize time and space cost. We will be using an undirected network representing a map of Romania (and an optional Atlanta graph used for the Race!). Table of Contents Setup Dependencies Jupyter Jupyter Tips Submission Custom Tests Setup Create a conda environment if you have not already. For example: conda create –name a1_env python=3.9 -y Activate the environment: conda activate a1_env In case you used a different environment name to create the conda environment, you can list all environments you have on your machine by running conda env list. You can always refer back to the instructions provided in Assignment 0 for managing conda environments. Dependencies Install the necessary libraries for this assignment after activating your conda environment and navigating to the correct directory. pip install -r requirements.txt Jupyter To open the Jupyter Notebook, run: jupyter notebook This should automatically open the notebook.ipynb as a Jupyter Notebook. If it doesn’t automatically open, you can access the Jupyter Notebook at http://localhost:8888 in your browser. Jupyter Tips 1. My Jupyter notebook does not seem to be starting up or my kernel is not starting correctly. Ans: This probably has to do with activating virtual environments. If you followed the setup instructions exactly, then you should activate your conda environment using conda activate from the Anaconda Prompt and start Jupyter Notebook from there. 2. I was running cell xxx when I opened up my notebook again and something or the other seems to have broken. Ans: This is one thing that is very different between IDEs like PyCharm and Jupyter Notebook. In Jupyter, every time you open a notebook, you should run all the cells that a cell depends on before running that cell. This goes for cells that are out of order too (if cell 5 depends on values set in cell 4 and 6, you need to run 4 and 6 before 5). Using the “Run All” command and its variants (found in the “Cell” dropdown menu above) should help you when you’re in a situation like this. 3. The value of a variable in one of my cells is not what I expected it to be? What could have happened? Submission You will submit multiple files from the directory submission to Gradescope after following the instructions in notebook.ipynb. Custom Tests There are a series of custom tests provided if you would like to run them through the terminal instead of Jupyter Notebook. They are: 1. search_basic_tests.py: Sample basic tests, visualizes the Romania graph. 2. search_submission_tests_grid.py: Visualizes the search as a grid. 3. search_romania_tests.py: More comprehensive tests on the Romania graph than search_basic_tests. 4. search_atlanta_tests.py: Tests for the Atlanta graph. 5. search_case_visualizer.py: For visualizing specific failed cases of interest on the Romania graph. To run a full test, you can do something like: python search_romania_tests.py To run a specific test, you can do something like: python search_romania_tests.py SearchRomaniaTests.test_bfs_romania See the code for each test file for more detailed instructions and descriptions.
This assignment is designed to help you get comfortable with your local python environment, Git, introduce you to jupyter notebooks, provide a refresher on the Python language, and introduce you to Gradescope. After following the setup process in this README, you will follow the instructions in notebook.ipynb to make your first graded submission! Let’s get started! If you have not setup your Python environment yet, STOP! Complete the environment setup by following the instructions found at https://github.gatech.edu/omscs6601/env_setup. Then return here. A video demonstration of the instructions below can be found here. Table of Contents Get repository Packages Jupyter Summary Setup a local repository Georgia Tech has paid for Enterprise Github and you have the ability to build and store your code in private repositories. Your repositories can be found at https://github.gatech.edu/[YOUR_STUDENT_GT_ID], where [YOUR_STUDENT_GT_ID] should be replaced with your Georgia Tech username (i.e. gburdell3). Please make sure that any repository you create is private to avoid OSI violations. First things first, let’s pull this repository to your local machine: git clone https://github.gatech.edu/omscs6601/assignment_0.git Instructions to create a private forked repository for assignments If you find that you need to work off of a copy of a public repository (like this one), you can follow the instructions below to create a personal copy of the repository. Remember that the repository you create needs to be private so that you do not accidentally violate OSI policies. The instructions below are modified to reflect URLs for this Assignment 0 repository. 2. Clone the class repository for Assignment 0 by using the command in a local file directory of your choice. git clone –bare https://github.gatech.edu/omscs6601/assignment_0.git 1. Change your directory into the newly cloned repository and then mirror this to the private repo you created on Github. cd assignment_0.git git push –mirror https://github.gatech.edu/gburdell3/cs6601_a0 cd .. 1. You can now delete the assignment_0.git directory from your local files if you wish (you will no longer need it). 2. Now that your private repository on Github matches the Assignment 0 repository, you can clone the private repo onto your local system. git clone https://github.gatech.edu/gburdell3/cs6601_a0 1. Next you can change your local directory to point to this newly cloned repo and add a remote branch upstream pointing to the original Assignment 0 repository it was cloned from. cd cs6601_a0 git remote add upstream https://github.gatech.edu/omscs6601/assignment_0.git You check if the remote branch has been added using git remote -v 1. Now you can use your repository like so: If you do not specify the remote, it will default to the origin (your repo) 1. If you are scared of pushing to upstream you can disable pushing to upstream using git remote set-url –push upstream PUSH_DISABLED PackagesWe will be using multiple python packages throughout this class. Here are some of them: jupyter – interactive notebook (you will learn more about them soon) numpy – a package for scientific computing (multi-dimensional array manipulation) matplotlib – a plotting library networkx – a package for manipulating networks/graphs pandas – a package for data analysis pgmpy – library for probabilistic graphical models Making sure that you are in an active Conda environment (i.e. (ai_env) as seen in the setup), you can install all the packages for an assignment by using the command pip install -r requirements.txt, if the assignment comes with a requirements.txt file. Please navigate to your cloned Assignment 0 directory (i.e. cs6601_a0), activate your environment (conda activate ai_env), and run pip install -r requirements.txt. Once installed, you can run pip freeze to see the list of all of the packages installed in your ai_env environment. Jupyter Sometimes the assignment repositories will come with a Jupyter Notebook which will contain the instructions for completing the assignment and the code cells that you need to fill out. To open Jupyter Notebook, navigate to the file directory containing the notebook.ipynb file, make sure your conda environment is running and that the libraries have already been installed, and then run the below command: (ai_env) $ jupyter notebook This should automatically open the notebook.ipynb as a Jupyter Notebook. If it doesn’t automatically open, you can access the Jupyter Notebook at http://localhost:8888 in your browser. Assignment 0 Your first assignment in this course is to setup your Python environment following the above instructions and then to follow the tutorial in the provided Jupyter Notebook. Upon completion of the tutorial, you will upload two Python files (first_submission.py and priority_queue.py) to Gradescope. This submission is worth 2 points of your final grade. More details and instructions can be found in the provided Jupyter notebook. Good luck!
