COSC 2123/1285 Algorithms and AnalysisSemester 1, 2018Assignment 2Guess WhoDue date: 11:59pm Sunday, 27th May 2018 Weight: 15%Pairs Assignment1 ObjectivesThere are three key objectives for this project:Implement a Guess Who game.Design and implement Guess Who guessing algorithms.Have fun!This assignment is designed to be completed in groups of 2, or pairs. We suggest that you workin pairs, but you may work individually.2 BackgroundGuess Who is a classic two player game. The game consists of a set of characters/persons1 withvarious attributes, e.g., hair or eye colour. Each player initially choose a person from this set. Theaim of the game is each player takes turns to guess their opponent’s chosen person. Each turn,a player can ask a question, such as, \does your person have green eyes?&", which the opponentanswers yes/no. From the answer, a player can eliminate the possible persons that their opponenthave. The game ends when a player make a correct guess of the opponent’s chosen person. Seehttps://en.wikipedia.org/wiki/Guess_Who%3F for more details.Traditionally, Guess Who is played between human players. In this assignment, your group willdevelop algorithms to automatically play Guess Who.3 TasksThe project is broken up into a number of tasks to help you progress. Task A is to design and developthe data structures to store game information and the players. Task B and C develops algorithms toplay Guess Who, using your own data structures from task A. For details on how each task will beassessed, please see \Assessment&" section.Task A: Design and Implement the Data Structures of a Guess Who Game (3marks)In this task, your group will design and implement the way a Guess Who game is stored and itsinformation accessed. This includes loading of the game from game con guration les (see section\Details of Files&" for details) and the storing of the chosen person in a player class.1We will use person from hereonin to avoid confusion with character/letter.Your design of these data structures may want to consider the way the Guess Who game is setup.Each player store their own copies of the game con guration information, which avoids forcing allplayers to store their game information the same way. This allows each group to go about their designin the way they consider appropriate, and even players from di erent groups to play against eachother.Task B: Implement Random Guessing Player (5 marks)In this task, your group will implement a random guessing player for Guess Who. Each round, thistype of player considers the remaining candidates that could be their opponent’s chosen person. Eachcandidate has a set of attribute-value pairs associated with them. Let the union of the attribute-valuepairs sets of all candidates be denoted by S. Then this type of player will random select a pair (a,v)from S, and then ask whether the chosen person has the value of v for attribute a. If the answer isyes, then eliminate all candidates who don’t have value v for attribute a. If the answer is no, theneliminate all candidates that have the value v for attribute a. Eventually, this type of player shouldhave one remaining candidate, then the player should guess this candidate as the opponent’s chosenperson.This algorithm works, because the set of persons are all unique, as in there is one more moreattribute-value that sets them apart from the other persons in the game. This means each questionwill at least eliminate one person per round, and should not remove opponent’s chosen person, soeventually this should be the remaining person.Task C: Implement Binary Search based Guessing Player (5 marks)In this task, your group will implement a smarter type of player. This one is based on the decrease-and-conquer principle, similar to binary search. Similar to the random guessing player, each round thistype of player also considers the attribute-value pairs of the remaining candidates. However, insteadof randomly asking about an attribute-value pair, this type of player will try to ask about a pair thateliminates as close to half the candidates (might not be possible to get exactly half, but as close aspossible). Again, when there is only one candidate left, this player should guess this candidate as theopponent’s chosen person.This algorithm works, as it also decrease the number of candidates each round, but should noteliminate the actual opponent’s chosen person. However, it should be on average faster than randomguessing player, as each time, the number of candidates is roughly halved. Recall for binary search, ithas good worst case complexity because it halves the problem each iteration. For both Tasks B andC, we are in fact implementing a binary decision tree (the following is not essential to complete theassignment, but provides the rationale why this works - your lecturer will discuss this in class more),where a non-leaf node represent an attribute and value the player guesses, and each children representfurther guessing possibilities based on no (one child) or yes (other child) answers. As each node in thetree represents a question, a path from root to leaf in the decision tree constitutes a guessing trace. Ifthe decision tree has minimal height (which it will more likely have if we more or less half candidateseach time), recall that such a tree has the best worst case possible, meaning on average, the length ofthe guessing trace should be shorter than the guessing trace of the random strategy, which can havelong paths for some candidates.4 Details for all tasksTo help you get started and to provide a framework for testing, you are provided with skeletoncode that implements some of the mechanics of the game. The main class (GuessWho) implementsfunctionality of a two player Guess Who game, a method to log the game to check correctness and toparse parameters. The list of les provided are listed in Table 1.le descriptionGuessWho.java Class implementing basic framework of the Guess Who game. Donot modify this le unless you have to.Player.java Interface class for a player. Do not modify this le.RandomGuessPlayer.java Class implementing the random guessing player.BinarySearchGuessPlayer.java Class implementing the binary search based guessing player.Guess.java Class implementing a ’guess’. Do not modify this le.Table 1: Table of supplied Java les.The framework provided implements a two player game. As explained earlier, the framework isdesigned such that each player is allowed to have their own way of representing the game. Thisallows your players to play against some of ours, or even other groups (given certain conditions aresatis ed, please ask your lecturer rst). Also, it de nes how the players should interact. ExamineGuessWho.java, particularly the code that iterates through the rounds. Note each player takes turnat making a guess via a Guess object, then the opponent answers, then this answer is passed back tothe player. Examine the Guess class and see \Guess Structure&" below to understand how a guess isimplemented in this framework.The framework also automatically logs the question-answer traces of the game. This allows us toevaluate if your players avoid asking redundant questions and the answers are correct (see \Assessment&"section for more details).Note, you may modify the GuessWho class, but we strongly suggest you not to, as this contains thecode for the game mechanics and the logging code and you do not want to break this. We also ask youto avoid modifying the \Do not modify&" ones, as they form. the interface between players. You mayadd methods and java les, but it should be within the structure of the skeleton code, i.e., keep thesame directory structure. Similar to assignment 1, this is to minimise compiling and running issues.However, you can change all the *Player.java les, including implementing/extending from a commonplayer parent class. No that ultimately your *Player classes must implement the Player interface.Also note that the onus is on you to ensure correct compilation on the core teaching servers.As a friendly reminder, remember how packages work and IDE like Eclipse will automatically addthe package quali ers to les created in their environments.Guess structureThere are two types of guesses, one for asking if opponent’s chosen player has a certain attribute-valuepair, the other for asking if the chosen player is a certain person.In the Guess class, there are three attributes, mType, mAttribute and mValue.When asking about attribute-value pair, set mType to Attribute and mAttribute and mValue tothe asked attribute and value respectively.When asking about if the chosen player is someone, set mType to Person, mAttribute to \&"(empty string) and mValue to the person’s name. See the Guess class for more details.For a player, when the answer(Guess guess) method is called, they should return true if thequestion/guess is true, and false otherwise. For the receiveAnswer(Guess guess, boolean answer)method, the player that was asking the question is updated with the answer, and should also returntrue if the game has nished (i.e., they guessed a person and the answer was true). For all other typesof guesses and questions, that player should return false. See Player interface and Guess Who classfor more details.Compiling and ExecutingTo compile the les, run the following command from the root directory (the directory that Guess-Who.java is in):javac -cp .:jopt-simple-5.0.2.jar *.java代做Java实验、代写留学生Java Pairs Assignment、帮做Algorithms and AnalysiNote that for Windows machine, remember to replace ’:’ with ’;’ in the classpath.To run the Guess Who framework:java -cp .:jopt-simple-5.0.2.jar GuessWho [-l ] wheregame log le: name of the le to write the log of the game.game con guration le: name of the le that contains the attributes, values and persons in theGuess Who game.chosen person le: name of the le that speci es which person that each player have chosen.player 1 type: speci es which type of player to use for rst player, one of [random | binary],with random is the random guessing player and binary is the binary-search based guessing player.player 2 type: speci es which type of player to use for second player, one of [random | binary].The jar le contains a library for reading command line options.We next describe the contents of the game con guration and chosen person les.4.1 Details of FilesGame con guration leThe game con guration les speci es all the set of attributes, values and persons in a Guess Whogame. The le has the following format:[ a t t r i b u t e 1 ] [ l i s t of values i t can take ][ a t t r i b u t e 2 ] [ l i s t of values i t can take ]. . .[ a t t r i b u t e n ] [ l i s t of values i t can take ]l i s t of persons in the gameBoth attribute and it list of values are strings, separated by a space.Each person in the person list has the following format:[ person name ][ a t t r i b u t e 1 ] [ value of a t t r i b u t e 1 ][ a t t r i b u t e 2 ] [ value of a t t r i b u t e 2 ]. . .[ l a s t a t t r i b u t e ] [ value of l a s t a t t r i b u t e ]An example game con guration le is as follows:hairLength short medium longg l a s s e s round square noneeyeColor black brown blue greenP1hairLength longg l a s s e s roundeyeColor brownP2hairLength shortg l a s s e s roundeyeColor blackP3hairLength mediumg l a s s e s noneeyeColor blueThis speci es the following game:Three attributes, hairLength, glasses and eyeColour.attribute hairLength can take values fshort, medium, longg.attribute glasses can take values fround, square, noneg.attribute eyeColor can take values fblack, brown, blue, greeng.Three persons in this game:{ Person \P1&" has hairLength = long, glasses = round and eyeColour = brown.{ Person \P2&" has hairLength = short, glasses = round and eyeColour = black.{ Person \P3&" has hairLength = medium, glasses = none and eyeColour = blue.Chosen person leThe chosen person le speci es the person chosen by each player. It is formated as follows:[ name of chosen person f o r player 1 ] [ name of chosen person f o r player 2 ]The names are separated by a space.An example chosen person le is as follows:P1 P3This speci es that player 1 has chosen person P1, and player 2 has chosen person P3.4.2 Clari cation to Speci cationsPlease periodically check the assignment FAQ for further clari cations about speci cations. In ad-dition, the lecturer will go through di erent aspects of the assignment each week, so even if youcannot make it to the lectures, be sure to check the course material page on Canvas to see if there areadditional notes posted.5 AssessmentThe project will be marked out of 15.The assessment in this project will be broken down into a number of components. The followingcriteria will be considered when allocating marks. All evaluation will be done on the core teachingservers.Note that for this and all implemented player algorithms, they should only ask non-redundantquestions. A non-redundant question should eliminates one or more of the candidate persons afterbeing asked. A redundant question is one that doesn’t eliminate any candidates, e.g., ask about anattribute-value pair that none of the remaining candidate have. This is one way we can evaluate thecorrectness of your implementations. The other approach is to evaluate whether the answers yourimplement player replies is correct, e.g., if their chosen person has blue eyes, and the question/guessasked by opponent is whether the person has blue eyes, then the correct answer is true/yes, andincorrect answer is false/no.Task A (3/15):We will assess your classes for modelling a Guess Who game as follows:1. Does the design hold all the necessary game information, i.e., at least the attributes and valuesin the game, the persons in the game, the chosen person in one or more player classes?2. Is it a modular and understandable design?3. Is it able to load the game con guration settings correctly?Task B (5/15):For this task, we will evaluate your player algorithm on whether:1. It implements a random guessing strategy, as outlined in the speci cations.2. Produces a non-redundant guessing and correct answer trace.Task C (5/15):Similar to task B, for this task, we will evaluate your player algorithm on whether:1. It implements a binar-search based guessing strategy, as outlined in the speci cations.2. Produces a non-redundant guessing and correct answer trace.3. Additionally, over a number of games, does it on average, beat the random guessing player oftask B, i.e., does it win more than it loses against the random guessing player?Coding style. and Commenting (2/15):You will be evaluated on your level of commenting, readability and modularity. This should be atleast at the level expected of a second year undergraduate student who has done some programmingcourses.5.1 Late SubmissionsLate submissions will incur a deduction of 1.5 marks per day or part of day late. Please ensure yoursubmission is correct (all les are there, compiles etc), resubmissions after the due date and time willbe considered as late submissions. The core teaching servers and Canvas can be slow, so please ensureyou have your assignments are done and submitted a little before the submission deadline to avoidsubmitting late.6 Team StructureThis project is designed to be done in pairs (group of two). If you have di culty in nding a partner,post on the discussion forum or contact your lecturer. If there are issues with work division andworkload in your group, please contact your lecture as soon as possible.In addition, please submit what percentage each partner made to the assignment (a contributionsheet will be made available for you to ll in), and submit this sheet in your submission. The con-tributions of your group should add up to 100%. If the contribution percentages are not 50-50, thepartner with less than 50% will have their marks reduced. Let student A has contribution X%, andstudent B has contribution Y%, and X > Y . The group is given a group mark of M. Student A willget M for assignment 1, but student B will get MXY.7 SubmissionThe nal submission will consist of:Contribution sheet: Before you submit, please ll in the Contribution sheet and put the le intoJava source code folder (see below for format of this folder). Note, we have introduced this toresolve the few occasions where there has been genuine disputes about contributions. Hopefully,most of you (in partnerships) will ll in 50-50 split, as the partner with less than 50Your Java source code of your implementations. All the les mentioned in the list of les aboveshould be placed directly into in a single folder named, e.g. Assign2-s12345-s67890, with s12345and s67890 are your student numbers.Please make sure you:Include all the les, not just your implementation les. Speci cally you must at least includeGuess.java, GuessWho.java, Game.java, BinaryGuessPlayer.java, RandomGuessPlayer.java andjopt-simple-5.0.2.jar, as well as the Contribution sheet mentioned above.Do not place the les under any sub folders like src, javaSrc, etc. unless they are part of yourcustom Java packages. Just place all of them under the same folderDo not capitalise the ’s’ character of the name of the folder like Assign2-S12345-S67890.Compress the folder in zip format with the same name of the folder, e.g. Assign2-s12345-s67890.zip, so that when we unzip it, there should be just one folder Assign2-s12345-s67890 withall the les (and Java packages, if you have any) right inside it, and not under another folderstructure.The submission will be done via Canvas.8 Plagiarism PolicyUniversity Policy on Academic Honesty and Plagiarism: You are reminded that all submitted projectwork in this subject is to be the work of you and your partner. It should not be shared with othergroups, nor should you elicit external tutoring services to do the assignment for you. Multiple auto-mated similarity checking software will be used to compare submissions. It is University policy thatcheating by students in any form. is not permitted, and that work submitted for assessment purposesmust be the independent work of the student(s) concerned. Plagiarism of any form. will result in zeromarks being given for this assessment, and can result in disciplinary action.For more details, please see the policy at http://www1.rmit.edu.au/students/academic-integrity.9 Getting HelpThere are multiple venues to get help. There are weekly consultation hours (see Canvas for time andlocation details). In addition, you are encouraged to discuss any issues you have with your Tutor orLab Demonstrator. We will also be posting common questions on Canvas and we encourage you tocheck and participate in the discussion forum on Canvas. Although we encourage participation in theforums, please refrain from posting solutions.& 转自：http://ass.3daixie.com/2018052758777245.html