Changes

==ModulesFiles==*[[/player]] package ==Description== CS 61B Project 2 Network (The Game) Due 4pm Friday, November 3, 2006 Interface design due in lab October 17 Warning: This project is substantially more time-consuming than Project 1. Start early. This is a team project. Form a team of 2 or 3 people. No teams of 1 or teamsof 4 or more are allowed. You project partners do NOT have to be in your lab. Copy the Project 2 directory by doing the following, starting from your homedirectory. Don't forget the "-r" switch in the cp command.  mkdir pj2 cd pj2 cp -r $master/hw/pj2/* . ===Suggested Timeline (if you want to finish on time)===*Design the classes, modules, and interfaces (see "Teamwork"). October 13*Have working code for the easier modules. October 20*Have working code for identifying a network; progress on search. October 27*Finish project. November 2 ===Network===In this project you will implement a program that plays the game Networkagainst a human player or another computer program. Network is played on an8-by-8 board. There are two players, "Black" and "White." Each player has tenchips of its own color to place on the board. White moves first.  ----------------------------------------- | | 10 | 20 | 30 | 40 | 50 | 60 | | ----------------------------------------- | 01 | 11 | 21 | 31 | 41 | 51 | 61 | 71 | ----------------------------------------- | 02 | 12 | 22 | 32 | 42 | 52 | 62 | 72 | ----------------------------------------- | 03 | 13 | 23 | 33 | 43 | 53 | 63 | 73 | ----------------------------------------- | 04 | 14 | 24 | 34 | 44 | 54 | 64 | 74 | ----------------------------------------- | 05 | 15 | 25 | 35 | 45 | 55 | 65 | 75 | ----------------------------------------- | 06 | 16 | 26 | 36 | 46 | 56 | 66 | 76 | ----------------------------------------- | | 17 | 27 | 37 | 47 | 57 | 67 | | ----------------------------------------- The board has four goal areas: the top row, the bottom row, the left column,and the right column. Black's goal areas are squares 10, 20, 30, 40, 50, 60and 17, 27, 37, 47, 57, 67. Only Black may place chips in these areas.White's goal areas are 01, 02, 03, 04, 05, 06 and 71, 72, 73, 74, 75, 76; onlyWhite may play there. The corner squares--00, 70, 07, and 77--are dead;neither player may use them. Either player may place a chip in any square noton the board's border. ===Object of Play===Each player tries to complete a "network" joining its two goal areas.A network is a sequence of six or more chips that starts in one of the player'sgoal areas and terminates in the other. Each consecutive pair of chips in thesequence are connected to each other along straight lines, either orthogonally(left, right, up, down) or diagonally. The diagram below shows a winning configuration for Black. (There should beWhite chips on the board as well, but for clarity these are not shown.) Hereare two winning black networks. Observe that the second one crosses itself.  60 - 65 - 55 - 33 - 35 - 57 20 - 25 - 35 - 13 - 33 - 55 - 57  ----------------------------------------- | | | BB | | | | BB | | _0 ----------------------------------------- | | | | | | | | | _1 ----------------------------------------- | | | | | BB | | | | _2 ----------------------------------------- | | BB | | BB | | | | | _3 ----------------------------------------- | | | | | | | | | _4 ----------------------------------------- | | | BB | BB | | BB | BB | | _5 ----------------------------------------- | | | | | | | | | _6 ----------------------------------------- | | | BB | | | BB | | | _7 ----------------------------------------- 0_ 1_ 2_ 3_ 4_ 5_ 6_ 7_ An enemy chip placed in the straight line between two chips breaks theconnection. In the second network listed above, a white chip in square 56would break the connection to Black's lower goal. Although more than one chip may be placed in a goal area, a network can haveonly two chips in the goal areas: the first and last chips in the network.Neither of the following are networks, because they both make use of two chipsin the upper goal.  60 - 20 - 42 - 33 - 35 - 57 20 - 42 - 60 - 65 - 55 - 57 A network cannot pass through the same chip twice, even if it is only countedonce. For that reason the following is not a network.  20 - 25 - 35 - 33 - 55 - 35 - 57 A network cannot pass through a chip without turning a corner. Because of thechip in square 42, the following is not a network.  60 - 42 - 33 - 35 - 25 - 27 ===Legal Moves===To begin the game, choose who is Black and who is White in any manner (we use arandom number generator). The players alternate taking turns, with Whitemoving first. The first three rules of legal play are fairly simple.# No chip may be placed in any of the four corners. # No chip may be placed in a goal of the opposite color.# No chip may be placed in a square that is already occupied. The fourth rule is a bit trickier.:4. A player may not have more than two chips in a connected group, whether connected orthogonally or diagonally. This fourth rule means that you cannot have three or more chips of the samecolor in a cluster. A group of three chips form a cluster if one of them isadjacent to the other two. In the following diagram, Black is not permitted toplace a chip in any of the squares marked with an X, because doing so wouldform a group of 3 or more chips. (Of course, the far left and right columnsare also off-limits to Black.)  ----------------------------------------- | | X | X | BB | X | | | | ----------------------------------------- | | X | BB | X | X | X | X | | ----------------------------------------- | | X | X | X | X | BB | X | | ----------------------------------------- | | | | | X | BB | X | | ----------------------------------------- | | | BB | | X | X | X | | ----------------------------------------- | | X | X | | | | BB | | ----------------------------------------- | | BB | | | | X | | | ----------------------------------------- | | | | | BB | | | | ----------------------------------------- There are two kinds of moves: add moves and step moves. In an add move, aplayer places a chip on the board (following the rules above). Each player hasten chips, and only add moves are permitted until those chips are exhausted.If neither player has won when all twenty chips are on the board, the rest ofthe game comprises step moves. In a step move, a player moves a chip to adifferent square, subject to the same restrictions. A player is not permittedto decline to move a piece (nor to "move from square ij to square ij"). A step move may create a network for the opponent by unblocking a connectionbetween two enemy chips. If the step move breaks the network at some otherpoint, the enemy does not win, but if the network is still intact when the chiphas been placed back on the board, the player taking the step move loses. If aplayer makes a move that results in both players completing a network, theother player wins. To make sure you understand the rules, try playing a few games against yourproject partners. See the instructions in "Running Network" below. Or, useten pennies, ten silver coins, and a checkerboard. Bibliographic note: Network is taken from Sid Sackson, "A Gamut of Games,"Dover Publications (New York), 1992. ===Your Task===Your job is to implement a MachinePlayer class that plays Network well. Onesubtask is to write a method that identifies legal moves; another subtask is towrite a method that finds a move that is likely to win the game. The MachinePlayer class is in the player package and extends the abstractPlayer class, which defines the following methods.  // Returns a new move by "this" player. Internally records the move (updates // the internal game board) as a move by "this" player. public Move chooseMove();  // If the Move m is legal, records the move as a move by the opponent // (updates the internal game board) and returns true. If the move is // illegal, returns false without modifying the internal state of "this" // player. This method allows your opponents to inform you of their moves. public boolean opponentMove(Move m);  // If the Move m is legal, records the move as a move by "this" player // (updates the internal game board) and returns true. If the move is // illegal, returns false without modifying the internal state of "this" // player. This method is used to help set up "Network problems" for your // player to solve. public boolean forceMove(Move m); In addition to the methods above, implement two constructors for MachinePlayer.  // Creates a machine player with the given color. Color is either 0 (black) // or 1 (white). (White has the first move.) public MachinePlayer(int color)  // Creates a machine player with the given color and search depth. Color is // either 0 (black) or 1 (white). (White has the first move.) public MachinePlayer(int color, int searchDepth) As usual, do not change the signatures of any of these methods; they are yourinterface to other players. You may add helper methods. Your MachinePlayer must record enough internal state, including the currentboard configuration, so that chooseMove() can choose a good (or at the veryleast, legal) move. In a typical game, two players and a referee each havetheir own internal representation of the board. If all the implementations arefree of bugs, they all have the same idea of what the board looks like,although each of the three uses different data structures. The referee keepsits own copy to prevent malicious or buggy players from cheating or corruptingthe board. If your MachinePlayer is buggy and attempts to make an illegalmove, the referee will grant the win to your opponent. Most of your work will be implementing chooseMove(). You will be implementingthe minimax algorithm for searching game trees, described in Lecture 17.A game tree is a mapping of all possible moves you can make, and all possibleresponses by your opponent, and all possible responses by you, and so on to aspecified "search depth." You will NOT need to implement a tree datastructure; a "game tree" is the structure of a set of recursive method calls. The forceMove() method forces your player to make a specified move. It is fortesting and grading. We can set up particular board configurations byconstructing a MachinePlayer and making an alternating series of forceMove()and opponentMove() calls to put the board in the desired configuration. Thenwe will call chooseMove() to ensure that your MachinePlayer makes a goodchoice. The second MachinePlayer constructor, whose second parameter searchDepth is thechosen search depth, is also used for debugging and testing your code.A search depth of one implies that your MachinePlayer considers all the movesand chooses the one that yields the "best" board. A search depth of twoimplies that you consider your opponent's response as well, and choose the movethat will yield the "best" board after your opponent makes the best moveavailable to it. A search depth of three implies that you consider twoMachinePlayer moves and one opponent move between them. The first MachinePlayer constructor should create a MachinePlayer whose searchdepth you have chosen so that it always returns a move within five seconds.(This precise time limit will only be important for the Network tournament latein the semester.) The second MachinePlayer constructor MUST always create aMachinePlayer that searches to exactly the specified search depth. You may want to design the MachinePlayer constructed by your first constructorso that it searches to a variable depth. In particular, you will almostcertainly want to reduce your search depth for step moves, because there aremany more possible step moves than add moves, and a search depth that is fastfor add moves will be very slow for step moves. The Move class in Move.java is a container for storing the fields needed todefine one move in Network. It is not an ADT and it has no interestinginvariants, so all its fields are public. It is part of the interface of yourMachinePlayer, and it is how your MachinePlayer communicates with otherprograms, so you cannot change Move.java in any way. If you would like to haveadditional methods or fields, feel free to extend the Move class; yourMachinePlayer may return subclasses of Move without any fear. ===Strategy===Where should you start? First, design the structure of your program (see"Teamwork" below). Then begin by writing a relatively simple MachinePlayerclass that simply chooses some correct move, no matter how bad. These actionswill give you partial credit on the project. Based on that foundation, you canimplement something more sophisticated that incorporates strategy. Game trees rely on an "evaluation function" that assigns a score to each boardthat estimates how well your MachinePlayer is doing. An evaluation function isnecessary because it is rarely possible to search all the way to the end of thegame. You need to estimate your odds of winning if you make a particular move.Your evaluation function should assign a maximum positive score to a win byyour MachinePlayer, and a minimum negative score to a win by the opponent. Assign an intermediate score to a board where neither player has completed anetwork. One of the most important but difficult parts of implementing gamesearch is inventing a board evaluation function that reliably evaluates theseintermediate boards. For example, a rough evaluation function might count howmany pairs of your chips can see each other, and subtract the opponent's pairs.A slightly better evaluation function would also try to establish at least onechip in each goal early in the game. I leave you to your own wits to improveupon these ideas. You should assign a slightly higher score to a win in one move than to a win inthree moves, which should get a higher score that a win in five moves, and soon. Otherwise, your MachinePlayer might always choose the win in three overthe win in one, move after move, and never get around to actually winning. You will need to invent an algorithm that determines whether a player has awinning network. A good place to look for clues is Section 13.3 of Goodrichand Tamassia, which describes depth-first search in graphs. It's not quitewhat you need for the job, but close enough that you'll be able to modify it. To earn full credit, you must implement alpha-beta search, which is discussedin Lecture 17. Alpha-beta search is a technique for "pruning" a game tree, soyou don't need to search the entire tree. Alpha-beta search can besignificantly faster than naive tree search. You can earn partial credit byimplementing game tree search without pruning. If you can't get that working,you can earn a little bit of partial credit by looking ahead one move. You will almost certainly want to create a separate class to represent gameboards internally. One decision you will have to make is whether to createa new game board or change an existing one each time you consider a move. Thelatter choice is faster, but it could cause hard-to-solve bugs if you're notextremely careful about how and when you manipulate game boards. Late in the semester, we will hold a tournament pitting student MachinePlayersagainst each other. Participation in the tournament is optional and does notaffect your grade. You will submit your contestant several weeks after theProject 2 due date, so you will have time to improve your MachinePlayer'sevaluation function and strategy in November. During the tournament, we willstrictly enforce a time limit of five seconds (which will be checked by ourrefereeing software) on the time to perform one chooseMove(). The winning teamwill receive gift certificates to Amoeba Music. This is a difficult project. Do not wait to start working on it. If you don'thave the code that identifies legal moves implemented by October 27, you wouldbe well advised to wallow in neurotic spasms of fear and worry. We will haveautograder software set up to test your submitted code for legal moves. ===Teamwork (10% of project grade)===Before you start programming, read the Lecture 18 notes carefully, then breakthe project up into multiple modules (tasks). Decide what high-level methodsand classes must be implemented, define the interfaces by which these methodsand classes will communicate, and divide up the work among your team. Somepossible modules (these seem reasonably modular) are# determining whether a move is valid,# generating a list of all valid moves,# finding the chips (of the same color) that form connections with a chip,# determining whether a game board contains any networks for a given player,# computing an evaluation function for a board, and# performing minimax tree search The file GRADER provided in the pj2 directory includes a questionnaire, whichyou are required to submit. Once you've worked out your classes, modules, andinterfaces, write them down at the bottom of GRADER. Your description shouldinclude:* A list of the classes your program will need.* A list of each of the "modules" used in or by MachinePlayer, which might be similar to, but more detailed, than the list above.* For each module, list the class(es) the module will be implemented in. It may (or may not) make it easier for you to work as a team if each module is in a separate class.* For each module, describe its interface--specifically, the prototype and behavior of each method that is available for external callers (outside the module) to call. Don't include methods that are only meant to be called from within the module. For each method, provide (1) a method prototype and (2) a complete, unambiguous description of the behavior of the method/module. (This description will also appear before the method* in your code's comments.)* Who is assigned the task of implementing each module? If you have defined your classes, modules, and module interfaces well, youshould be able to implement any one of the modules without having decided howto implement any of the others. This will allow you to divide up the choresand work quickly as a team. See the Lecture 18 notes for details. You should have a draft of your GRADER file ready to show your TA in Lab 7(October 17/18). Your Lab 7 score depends on having a finished draft of yourmodules and interfaces. Your TA will comment on your design decisions. You may change some of your design decisions based on your TA's feedback, andyou will probably make other changes as you program. Be sure to update yourGRADER to reflect these changes. The GRADER file you submit with this projectshould reflect the FINAL decisions you make about modules and interfaces. Before you submit, make sure your GRADER file tells us who ''actually''implemented each portion of your project. Although you must hand in GRADERwith your project, you must also hand in a printed version of GRADER on whichyou have written "This is a truthful statement of how we divided the labor forthis project." ALL of your team members must put their signatures under thisstatement. This statement is due the Monday after the project deadline. Youwill not receive a grade if you don't turn it in. Your design of classes and interfaces with be worth about 10% of your projectgrade. ===Running Network===You can run Network from your pj2 directory in several ways.  java Network human random This pits you against a very naive machine player that makes random legal moves. Use this to learn to play the game. The human plays white and the random player play black. To reverse this, swap "human" and "random".  java Network human human Compete against your project partner.  java Network human machine Compete against your MachinePlayer.  java Network machine random Your MachinePlayer competes against the random player.  java Network machine machine Your MachinePlayer competes against itself. All the combinations of "machine", "human", and "random" work. It'sparticularly amusing to pit two random players against each other. If you put a "-q" switch right after the word "Network", Network will quitimmediately when the game ends. This can be useful for batch testing. ===Grading===Your project will be graded in part on correctness and the quality of moveschosen by chooseMove(). This grading will be done using automatic test cases.Be sure the following statements apply to your chooseMove(). # forceMove and opponentMove return true if the given move is legal.# forceMove and opponentMove return false if the given move is illegal.# chooseMove returns only legal moves.# If a winning move exists, chooseMove selects one. (This will happen automatically if you are searching one level of the game tree.)# If you cannot win in this step, but can prevent your opponent from winning during its next move, chooseMove selects a move that does this. (This will happen automatically if you are searching two levels of the# game tree.)# Your player can beat the random player almost every time. Any reasonable search strategy should accomplish this. You will also be graded on style, documentation, efficiency, and the use ofencapsulation. # Each method must be preceded by a comment describing its behavior unambiguously. These comments must include descriptions of what each parameter is for, and what the method returns (if anything). They must also include a description of what the method does (though not necessarily how it does it) detailed enough that somebody else could implement a method that does the same thing from scratch, using only the comments and this readme file.# methods serve as entry points to the modules you designed when you began the project. The prototypes and behavioral descriptions of these methods are interfaces, and should be included in GRADER.# All classes, fields, and methods must have the proper public/private/ protected/package qualifier. We will deduct points if you make things public that could conceivably allow a user to corrupt the data structure.# There are no asymptotic limits on running time. However, part of your job is to avoid using inefficient algorithms and data structures. If your MachinePlayer takes substantially longer than 5 seconds to search to a depth of two on a Soda lab machine, we will scrutinize your submission for inefficient algorithms and data structures.# You should have divided up the tasks into well-defined modules in your GRADER file and in your software.# We will deduct points for code that does not match the following style guidelines.:*Classes that contain extraneous debugging code, print statements, or meaningless comments that make the code hard to read will be penalized. (It's okay to have methods whose sole purpose is to contain lots of debugging code, so long as your comments inform the reader who grades your project that he can skip those methods. These methods should not contain anything necessary to the functioning of your project.):*Your file should be indented in the manner enforced by Emacs (e.g., a two-space or four-space indentation inside braces), and used in the lecture notes throughout the semester. The indentation should clearly show the structure of nested statements like loops and if statements. Sloppy indentation will be penalized.:*All if, else, while, do, and for statements should use braces. (Ask me if you want to know why.):*All classes start with a capital letter, all methods and (non-final) data fields start with a lower case letter, and in both cases, each new word within the name starts with a capital letter. Constants (final fields) are all capital letters only.:*Numerical constants with special meaning should always be represented by all-caps "final static" constants.:*All class, method, field, and variable names should be meaningful to a human reader.:*Methods should not exceed about 100 lines. Any method that long can probably be broken up into logical pieces. The same is probably true for any method that needs more than 7 levels of indentation.:*Avoid unnecessary duplicated code; if you use the same (or very similar) fifteen lines of code in two different places, those lines should probably be a separate method call.:*Programs should be easy to read. Finally, we will be looking at your code to see whether you have implementedminimax game tree search, and whether you use alpha-beta pruning. ==Pre-coding organization==