Computer Science/61b/Projects/Network
Files
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 teams of 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 home directory. 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 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. 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.
- 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 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 results in both players completing 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 only be important for the Network tournament late in the semester.) The second MachinePlayer constructor MUST always create a MachinePlayer that 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.
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.
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, but it could cause 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 November. 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.
This is a difficult project. Do not wait to start working on it. If you don't have the code that identifies legal moves implemented by October 27, you would be well advised 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)
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
- 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, 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.)
- Who 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 (October 17/18). 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 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'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.
Grading
Your project will be graded in part on correctness and the quality of moves chosen 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 of encapsulation.
- 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 implemented minimax game tree search, and whether you use alpha-beta pruning.
Pre-coding organization
Members: Paul, -bb; Andrew, -fe; Jordan, -er
Gameboard & chips ADT
/* Paul */ // Gameboard abstract data type – Gameboard class // fields: public static final int SDEPTH = 10, given to no-depth constructor // methods: // inserts a chip of the given color in the specified place as determined by an x, y coord pair // returns true if the insertion succeeds; false otherwise boolean insertChip(int color, int x, int y) // move a given chip to a specified place as determined by an x, y coord pair // returns true if the move succeeds; false otherwise boolean moveChip(Chip c, int x, int y) // performs a move and returns true/false depending on whether it succeeded boolean performMove(int color, Move m) // returns the Chip at a given location as determined by an x, y coord pair Chip retrieveChip(int x, int y) // returns true if the given move is valid; false otherwise /* Verified conditions: # 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. # A player may not have more than two chips in a connected group, whether connected orthogonally or diagonally. */ boolean validMove(int color, Move m) // Chip abstract data type – Chip class // color field stores the chip's color as a static final int; x and y fields store the chip's x and y coords, respectively // fields: public static final int WHITE/BLACK = 1/0 (this is how we refer to colors, though I don't think anyone would need to) // public final static int DIMENSION = 8 for the dimensions of the board // methods: // returns the chip's color int getColor() // returns the x coord of the chip int getX() // returns the y coord of the chip int getY() // returns the checked state of the chip (used for network detection) boolean Checked() // sets the checked state of the chip to newval void setChecked(boolean newval)
Additional methods in Gameboard class
This is the real meat of the project.
/* Andrew */ // generates a 2-d array of moves and resulting gameboards for a given color // @return[0] is an array of Gameboards (Gameboard[x]) // @return[1] is an array of Moves corresponding to each board in return[0] (Move[x]) // thus the board after performing g.performMove(color, return[1][i]) is return[0][i] Object[][] generateMoves(Gameboard g, int color)
/* Paul */ // evaluates all possible moves to be generated from the this board using the minimax algorithm and alpha-beta pruning. // continues searching until it reaches depth or a win, whichever comes first Move evalTree(int color, int depth)
/* Jordan */ // evaluates the given network for a winning color // returns a probability of winning if there is no win // returns 999 if WHITE wins, -999 if BLACK wins int winner(Gameboard g)
Changes to MachinePlayer class
New fields
int color int opponent int depth Gameboard board
Methods
As I mentioned to Jordan over e-mail, all of the methods and constructors in MachinePlayer class become pretty trivial after we write all of the methods in the Gameboard class. I (Paul) have already done all of them, so assuming everything else works as planned, we should be ok.
