CS 61B Project 2 Network (The Game) Due 5:30 pm Friday, April 5, 2013 Interface design due in lab March 12-13 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 teams of 4 or more are allowed. Your project partners do NOT have to be in your lab. Copy the Project 2 directory by doing the following, starting from your home directory. cp -r ~cs61b/hw/pj2 . cd pj2 Suggested Timeline (if you want to finish on time) ================== Design the classes, modules, and interfaces (see "Teamwork"). March 11 Have working code for the easier modules. March 17 Have working code for identifying a network; progress on search. March 24 Finish project. April 5 Network ======= In this project you will implement a program that plays the game Network against a human player or another computer program. Network is played on an 8-by-8 board. There are two players, "Black" and "White." Each player has ten chips 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, 60 and 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; only White 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 not on 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's goal areas and terminates in the other. Each consecutive pair of chips in the sequence 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 be White chips on the board as well, but for clarity these are not shown.) Here are 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 the connection. In the second network listed above, a white chip in square 56 would break the connection to Black's lower goal. Although more than one chip may be placed in a goal area, a network can have only 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 chips in 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 counted once. 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 (i.e. changing direction). Because of the chip 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 a random number generator). The players alternate taking turns, with White moving first. The first three rules of legal play are fairly simple. 1) No chip may be placed in any of the four corners. 2) No chip may be placed in a goal of the opposite color. 3) 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 same color in a cluster. A group of three chips form a cluster if one of them is adjacent to the other two. In the following diagram, Black is not permitted to place a chip in any of the squares marked with an X, because doing so would form a group of 3 or more chips. (Of course, the far left and right columns are 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, a player places a chip on the board (following the rules above). Each player has ten 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 of the game comprises step moves. In a step move, a player moves a chip to a different square, subject to the same restrictions. A player is not permitted to 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 connection between two enemy chips. If the step move breaks the network at some other point, the enemy does not win, but if the network is still intact when the chip has been placed back on the board, the player taking the step move loses. If a player makes a move that causes both players to complete a network, the other player wins. To make sure you understand the rules, try playing a few games against your project partners. See the instructions in "Running Network" below. Or, use ten 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. One subtask is to write a method that identifies legal moves; another subtask is to write a method that finds a move that is likely to win the game. The MachinePlayer class is in the player package and extends the abstract Player 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 your interface to other players. You may add helper methods. Your MachinePlayer must record enough internal state, including the current board configuration, so that chooseMove() can choose a good (or at the very least, legal) move. In a typical game, two players and a referee each have their own internal representation of the board. If all the implementations are free 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 keeps its own copy to prevent malicious or buggy players from cheating or corrupting the board. If your MachinePlayer is buggy and attempts to make an illegal move, the referee will grant the win to your opponent. Most of your work will be implementing chooseMove(). You will be implementing the 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 possible responses by your opponent, and all possible responses by you, and so on to a specified "search depth." You will NOT need to implement a tree data structure; 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 for testing and grading. We can set up particular board configurations by constructing a MachinePlayer and making an alternating series of forceMove() and opponentMove() calls to put the board in the desired configuration. Then we will call chooseMove() to ensure that your MachinePlayer makes a good choice. The second MachinePlayer constructor, whose second parameter searchDepth is the chosen search depth, is also used for debugging and testing your code. A search depth of one implies that your MachinePlayer considers all the moves and chooses the one that yields the "best" board. A search depth of two implies that you consider your opponent's response as well, and choose the move that will yield the "best" board after your opponent makes the best move available to it. A search depth of three implies that you consider two MachinePlayer moves and one opponent move between them. The first MachinePlayer constructor should create a MachinePlayer whose search depth you have chosen so that it always returns a move within five seconds. (This precise time limit will be important only for the Network tournament late in the semester.) The second MachinePlayer constructor MUST create a MachinePlayer that always searches to exactly the specified search depth. You may want to design the MachinePlayer constructed by your first constructor so that it searches to a variable depth. In particular, you will almost certainly want to reduce your search depth for step moves, because there are many more possible step moves than add moves, and a search depth that is fast for add moves will be very slow for step moves. The Move class in Move.java is a container for storing the fields needed to define one move in Network. It is not an ADT and it has no interesting invariants, so all its fields are public. It is part of the interface of your MachinePlayer, and it is how your MachinePlayer communicates with other programs, so you cannot change Move.java in any way. If you would like to have additional methods or fields, feel free to extend the Move class; your MachinePlayer 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 MachinePlayer class that simply chooses some correct move, no matter how bad. These actions will give you partial credit on the project. Based on that foundation, you can implement something more sophisticated that incorporates strategy. Game trees rely on an "evaluation function" that assigns a score to each board that estimates how well your MachinePlayer is doing. An evaluation function is necessary because it is rarely possible to search all the way to the end of the game. 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 by your MachinePlayer, and a minimum negative score to a win by the opponent. Assign an intermediate score to a board where neither player has completed a network. One of the most important but difficult parts of implementing game search is inventing a board evaluation function that reliably evaluates these intermediate boards. For example, a rough evaluation function might count how many 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 one chip in each goal early in the game. I leave you to your own wits to improve upon these ideas. You should assign a slightly higher score to a win in one move than to a win in three moves, which should get a higher score that a win in five moves, and so on. Otherwise, your MachinePlayer might always choose the win in three over the 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 a winning network. A good place to look for clues is Section 13.3 of Goodrich and Tamassia, which describes depth-first search in graphs. It's not quite what you need for the job, but close enough that you'll be able to modify it. This is the hardest part of the whole project, so assign it to your smartest teammate and START EARLY!!! To earn full credit, you must implement alpha-beta search, which is discussed in Lecture 17. Alpha-beta search is a technique for "pruning" a game tree, so you don't need to search the entire tree. Alpha-beta search can be significantly faster than naive tree search. You can earn partial credit by implementing 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. This is the second-hardest part of the project, but the closer you stick to the Lecture 17 pseudocode, the more likely you are to succeed. You will almost certainly want to create a separate class to represent game boards internally. One decision you will have to make is whether to create a new game board or change an existing one each time you consider a move. The latter choice is faster (i.e. more likely to win the tournament), but it's also more bug-prone; it could cause very hard-to-solve bugs if you're not extremely careful about how and when you manipulate game boards. Late in the semester, we will hold a tournament pitting student MachinePlayers against each other. Participation in the tournament is optional and does not affect your grade. You will submit your contestant several weeks after the Project 2 due date, so you will have time to improve your MachinePlayer's evaluation function and strategy in April. During the tournament, we will strictly enforce a time limit of five seconds (which will be checked by our refereeing software) on the time to perform one chooseMove(). The winning team will receive gift certificates to Amoeba Music or Amazon. This is a difficult project. Do not wait to start working on it. If you don't have the code that identifies networks implemented by March 24, I advise you to wallow in neurotic spasms of fear and worry. We will have autograder software set up to test your submitted code for legal moves. Teamwork (10% of project grade) (show to your TA in Lab 7, March 12-13) ======== Before you start programming, read the Lecture 18 notes carefully, then break the project up into multiple modules (tasks). Decide what high-level methods and classes must be implemented, define the interfaces by which these methods and classes will communicate, and divide up the work among your team. Some possible modules (these seem reasonably modular) are 1) determining whether a move is valid, 2) generating a list of all valid moves, 3) finding the chips (of the same color) that form connections with a chip, 4) determining whether a game board contains any networks for a given player (very difficult; put your smartest teammate on this), 5) computing an evaluation function for a board (possibly difficult), and 6) performing minimax tree search (difficult). The file GRADER provided in the pj2 directory includes a questionnaire, which you are required to submit. Once you've worked out your classes, modules, and interfaces, write them down at the bottom of GRADER. Your description should include: - 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.) - Which partner is assigned the task of implementing each module? If you have defined your classes, modules, and module interfaces well, you should be able to implement any one of the modules without having decided how to implement any of the others. This will allow you to divide up the chores and 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 (March 12-13). Your Lab 7 score depends on having a finished draft of your modules and interfaces. Your TA will comment on your design decisions. You may change some of your design decisions based on your TA's feedback, and you will probably make other changes as you program. Be sure to update your GRADER to reflect these changes. The GRADER file you submit with this project should 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 GRADER with your project, you must also hand in a printed version of GRADER on which you have written "This is a truthful statement of how we divided the labor for this project." ALL of your team members must put their signatures under this statement. This statement is due the Monday after the project deadline. You will not receive a grade if you don't turn it in. Your design of classes and interfaces with be worth about 10% of your project grade. 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 colors, 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. Every combination of "machine", "human", and "random" works. It's particularly amusing to pit two random players against each other. If you put a "-q" switch right after the word "Network", Network will quit immediately when the game ends. This can be useful for batch testing of evaluation functions. Grading ======= Your project will be graded in part on correctness and the quality of moves chosen by chooseMove(). This grading will be done with automatic test cases. Be sure the following statements apply to your chooseMove(). 1) forceMove and opponentMove return true if the given move is legal. 2) forceMove and opponentMove return false if the given move is illegal. 3) chooseMove returns only legal moves. 4) If a winning move exists, chooseMove selects one. (This will happen automatically if you are searching one level of the game tree.) 5) 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.) 6) Your player can beat the random player almost every time. Any reasonable search strategy and evaluation function should accomplish this. You will also be graded on style, documentation, efficiency, and the use of encapsulation. 1) Every 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. Some 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. 2) 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. 3) 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 much 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. 4) You should have divided up the tasks into well-defined modules in your GRADER file and in your software. 5) 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. (Single-letter loop variables whose meanings are obvious are okay.) - 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 8 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 implemented minimax game tree search, and whether you use alpha-beta pruning. Submitting your Solution ======================== Be sure that you have updated all your answers in GRADER before submitting to reflect your final code. Don't forget that it's worth 10% of your grade. Designate one member of your team to submit the project. If you resubmit, the project should always be submitted by the same student. If for some reason a different partner must submit (because the designated member is out of town, for instance), you must send cs61b@cory.eecs a listing of your team members, explaining which of them have submitted the project and why. Let us know which submission you want graded. If you've submitted your project once, or even written a substantial amount of code together, you may not change partners without the permission of the instructor. The designated teammate only: change (cd) to your pj2 directory, which should contain the player directory (i.e. the player package), which should contain your MachinePlayer.java and other Java files. You may also submit other packages in your pj2 directory (e.g. a list package). Type "submit pj2". The submit program will not submit Move.java and Player.java, because you're not allowed to change them.