Session O1: Object-Oriented Design

In this laboratory session you will investigate the process of object-oriented design by considering the design of a computerized Othello game. The goals of this laboratory are to

• reinforce your skills in building and designing objects;
• introduce techniques for doing object-oriented design; and
• have some fun.

Your instructor will tell you which of the proposed experiments you are to perform.

Prerequisite skills:

• Objects and classes in Java
• Graphics in Java (optional)
• Inheritance (optional)

Required files:

• Player.java

Discussion

You have learned that Java is an object-oriented language. You have also seen a number of reasons to use object-oriented languages. For example, objects provide a natural mechanism for modeling many problems and solutions. In addition, well-designed objects provide a natural mechanism for supporting reuse. But how does one do good object design? There is no real substitute for practice and experience: you learn object design by designing the objects for programs and then reflecting (and re-reflecting) on your designs. However, there are a number of processes by which beginning designers can develop the basic skills. We will investigate a few of those in this laboratory session.

The processes we will investigate include narratives, question and answer sessions, drawing diagrams, and generalization through related examples. You will find that it is often best to do design in dialog with others, as one person may find both flaws and additional possibilities in the design of another person.

Since design skills come from experience, it is important that you record your design decisions when you make them. Then, as you work on your project, you should reflect on those decisions and continue to record observations. If you have made a bad decision, it helps to have the implications documented so that you can avoid making similarly inappropriate decisions in the future. If you have made a good decision, it helps to have it documented so that you can reuse the ideas that led to that decision.

These strategies are certainly not the only ones you can use to improve your design skills. For example, you may find it helpful to study the design of larger systems. You might read about the design of such a system or even attempt to replicate that design.

Narratives

As an example, we will consider the game of Othello. In particular, we will think about how we might design a program that allows people to play Othello. If you do not know Othello, do not worry; here is a description:

Othello is a two-person game played on an eight-by-eight board. It is often convenient to number the rows of the board 1-8 and the columns A-H. The game begins with two black pieces and two white pieces on the center four squares of the board (D4, D5, E4, and E5). There is a black piece in the top-left and bottom-right of those four squares (D4 and E5). There is a white piece in the top-right and bottom-left of those four squares (D5 and E4). Players alternate turns, with each player making a legal move when it is his or her turn. A legal move consists of placing a piece so that two of pieces surround a row, column, or diagonal of the opponent's pieces. All of the opponent's pieces are then flipped (from black to white or from white to black). If a player cannot make a legal move, that player loses his or her turn. Play continues until there are no longer blank squares on the board or neither player can make a legal move. The player with the most pieces is the winner.

Note that this is, in effect, a short narrative describing the game. Such narrative descriptions are good first steps in object design. As with all pieces of prose, this narrative included both nouns and verbs. It is often the case that nouns correspond closely to the objects and classes in a program and that verbs correspond closely to the methods these objects and classes provide. If you circle the nouns, you are on your way to determining which objects and classes belong in your program. If you box the verbs, you are also on your way to determining the methods.

For example, you might note that the description uses the nouns player, piece, and move. This makes it likely that a program that simulates an Othello game will include the classes Player, Piece, and Move. What methods will these classes provide? Now we can turn our attention to the verbs. We see that players make moves and that pieces flip. This suggests that the Player class will most likely include a makeMove or chooseMove methods and that the Piece class will include a flip method.

Other nouns might suggest particular objects. For example, ``black'' is presumably an instance of Color, or at least the state of a Piece (or both). Still other nouns may be extraneous. For example, while the description of Othello uses the term ``opponent'', it is unlikely that we will need an Opponent class or even an opponent object in class Player. However, it is possible that some methods might benefit from an opponent variable.

In Experiment O1.1 you will begin to consider the design of an Othello class.

Question and answer sessions

The objects, classes, and methods one develops through narratives are often somewhat sketchy and are usually insufficient to form a whole program. We have not yet determined what attributes or fields each class needs, nor have we determined what parameters the methods will need. In addition, there are often a number of implicit objects in every description. How do we garner this additional information? We can garner information through a more careful reading of the narrative, asking questions as we go. What types of questions should we ask?

• For various actions, you might ask ``What object does this action?''
• You might also ask ``What information do we need in order to do this?''
• For objects and classes, you might ask ``How would I normally describe such objects and what would they normally do?''

For example, closer reading of the description of Othello suggests that someone needs to determine whose turn it is. It may be helpful to use a Referee class that selects the current player. It may also be that the class that runs the game makes this determination.

Similarly, you note that there are many references to legal moves. What determines whether a move is legal? A set of Rules. The Rules also determine when the game is over and, in effect, who moves next.

Now let us consider the makeMove method. What information does a player need to make a move? The player certainly needs to know his or her color, the state of the board, and the applicable rules. Since a player always has the same color, we might make that a field in the Player class. On the other hand, the state of the board changes, so we might make that a parameter of the makeMove method. The rules are consistent, so we might also make those a field in the Player class.

Are these the only decisions we could have made? Certainly not. We might have instead chosen to make all color, board, and rules all parameters to the makeMove method or all fields in the Player class, or some other combination. How do you decide what is best to do? Again, experience will tell you. For now, a good strategy is to make things that can be changed by other objects (e.g., the board) parameters, while things that will remain consistent throughout the game (e.g., the rules) can be fields.

You might note that we have not begun to specify how makeMove operates, we have only specified what it does. At this point, it is appropriate to stay at this level of abstraction. In part, the how will be determined by our further steps. In part, the how may differ depending on other issues. For example, in a text-based Othello game, makeMove might draw the board and prompt for the player to type in a move; in a graphical Othello game, makeMove might wait for the player to click on a legal square; in a game against the computer, the computer player will make a move by running an algorithm that chooses an appropriate space.

Finally, we might ask ourselves what constitutes a move. Basically, it is the placement of a piece on the board at a particular position. This suggests that the Move class will have at least two attributes: a Piece and a Position. We also note that moves update the board. This suggests that the Board class will need an update method that takes a Move as a parameter.

In Experiment O1.2 you will refine your descriptions.

Beginning coding

At this stage in your design, you should have a rough outline of the classes you will need in the program, some of the methods those classes will need to provide, and some of the fields each class will use. You can use this information to start writing the code for your programs. For example, I've determined that each Player will need a Color for its pieces and a makeMove method. I might also note that I'll need the Color in order to create a particular player, giving me an idea of what the constructor will look like. This analysis leads to the following class description.

import Color;

/**
 * A person playing an Othello game (or, perhaps, any game).
 *
 * @author Samuel A. Rebelsky
 * @version 1.1 of September 1998
 */
public class Player {
  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+

  /** The color of the pieces the player places on the board. */
  protected Color mycolor;


  // +--------------+--------------------------------------------
  // | Constructors |
  // +--------------+

  /**
   * Create a new player that uses a particular color of
   * piece.
   */
  public Player(Color piececolor) {
    this.mycolor = piececolor;
  } // Player(Color)


  // +---------+-------------------------------------------------
  // | Methods |
  // +---------+

  /**
   * Choose a move to make (but don't make the move).
   */
  public Move makeMove(Board b) {
    // Code not yet available.
  } // makeMove(Board)

} // class Player

In Experiment O1.3 you will begin to develop classes for the project.

Narrating interactions

Our descriptions up to this point have ignored an important component: interaction with the user or users. While not all programs, classes, objects, or methods will interact with the user, many will. How do we determine what role such interactions play in the design of our program? We write more detailed narratives that describe how we envision users interacting with the program.

For example, we might describe two players using our Othello game as follows.

Two players, William and Jonathan, start the game. The game prompts for the player name. William enters his name for white; Jonathan enters his name for black. The game displays the game board (with white pieces at D5 and E4 and black pieces at D4 and E5). It then prompts William for his move. William places a white piece at C4, surrounding the black piece at D4. The game automatically flips the piece at D4 and then prompts Jonathan for his move. Jonathan chooses to place a black piece at A1. The game determines that this is not a legal move, informs Jonathan, and then asks for another move.

You'll note that we used ``the game'' a great deal in this narrative. You will often find that you use a similar noun (perhaps ``the program'') in describing interaction. Often, this will be your controlling object, or even the the main routine in that object.

How do we use such narratives? Sometimes it is to identify additional objects and classes (as in the Game class suggested in the previous paragraph). More frequently, it is to identify additional classes and methods that are necessary. For example, we might note that we need to draw boards, perhaps with a draw method provided by the Board class.

Again, it helps to ask questions. For example ``How does it display the game board?'' or ``How does it prompt for moves?'' You might also ask ``What object does the prompting?'' In this case, it is likely that the Player object prompts for moves as part of its work for the makeMove method. In order to do this, it may need additional parameters or fields, such as a SimpleOutput object to write to and a SimpleInput object to read from.

As we progress towards a full implementation, we can turn our narrative and questions into pseudocode, as in

To play Othello:
  create the board, rules, and players
  while the rules do not indicate that the game is over
    if the current player has an available move then
      repeatedly
        ask the current player to select a move
      until the player selects a legal move
      make that move, updating the board
      switch players
    else // the current player has no legal moves
      switch players
    end if
  end while
  count the pieces and report the winner

Thinking of alternative situations is also helpful. For example, one might describe an interaction between one player and the computer as follows.

Michelle starts the Othello game. It asks her whether she wants to play against the computer or another player. She selects the computer as an opponent. The game then asks for her name. She enters her name, Michelle. The game tells her that it will play white and she will play black. It then displays the board. The computer moves first and places a white piece at C4.

Again, we may want to ask some questions. For example, ``How does the computer make a move?'' One method would be to check every square on the board, identify all the legal moves, and pick one using some heuristic (a simple one is ``the first legal move I find''; a more interesting one might be ``the one that flips the most pieces''; better ones may pay attention to placement of pieces and number of pieces on the board).

Comparing alternate narratives can also help identify some objects. For example, if we read the second narrative again, we may ask ourselves ``Which object computes the computer's move?'' Since objects in class Player develop moves in the first scenario, it may make sense to use related objects in the second scenario. In particular, we might consider building a subclass of the Player object, such as ComputerPlayer.

In Experiment O1.4 you will develop narratives for some of the interactions in the game. In Experiment O1.5 you will continue coding the Othello game.

Diagrams of relationships

As you may have guessed, most object-oriented programs are not just collections of random objects, interacting chaotically. Rather, the interactions between objects are carefully scripted. How does one script these interactions? We can develop scripts by thinking carefully about the relationships between objects, again based on our earlier narratives.

The interaction narratives give a good beginning. For example, we can tell that:

• Some method of the Game object calls the display method of the a Board object.
• Some method of the Game object calls the makeMove method of a Player object, which returns a Move object.
• The makeMove method of some Player objects request a Move from some type of interaction object or objects.

Many programmers find it helpful to diagram these relationships, representing them visually in addition to or instead of textually. Often, it is best for each programmer to decide on the visualization that is most appropriate for him or her. Typically a diagram will include a box for each object in the program, with sub-boxes for each of the methods. A call to a method is represented by a line from calling object or method to callee. The response may be represented by a dotted line.

In Experiment O1.6 you will practice drawing diagrams.

Generalization and encapsulation

As we saw earlier, one of the primary reasons to do object-oriented programming is that it can easily support reuse. That is, well designed objects that work in one program should also be usable in another program. Similarly, by changing just one or two objects in a program, one might make it do something somewhat different.

In our Othello game, we might decide to support other size boards (e.g., 10x10 or 6x6), more than two players, or alternate starting positions. Each change may affect multiple classes. It is our goal to minimize the number of classes affected.

For example, if we had finished coding the Othello game and later decided to support different size boards (and we were not careful about the original design of the game), it is likely that we will need to change

• the makeMove method of the Player class, since there are a wider variety of spaces to select;
• the Rules class to support the different size boards; and
• the Board class to include a constructor which takes the board size as a parameter.

If we design the various classes in such a way that they make fewer assumptions, these updates might be easier. For example, if we had written the makeMove method so that it queried the board for its size or for a list of legal spaces, then it might not be necessary to update makeMove at all when we changed the size of the board. The secret is to think about these alternatives before coding, rather than afterwards.

As another example, consider the pseudocode for a game of Othello that we developed earlier. Could we reuse this code for other games simply by changing the board, players, and rules? No. The pseudocode includes a number of assumptions about the rules of Othello. For example, it assumes that players alternate turns (except when one player cannot make a move). If we were going to support other games, such as chess, we would need to write a new description. Hence, it might be better to rewrite the algorithm as follows:

To play a game
  create the game board, rules, and players
  while the rules do not indicate that the game is over
    determine the current player
    let that player make a move
  end while
  determine the winner

In fact, we could even make this a parameterized method

To play a game given a board, rules, and players
  while the rules do not indicate that the game is over
    determine the current player
    let that player make a move
  end while
  determine the winner

In Experiment O1.7 you will consider other generalizations for the design of the Othello game.

Experiments

Name: ________________
ID:_______________

Experiment O1.1: Determine potential objects and classes for an Othello simulation

Here is the description of Othello that appeared above.

Othello is a two-person game played on an eight-by-eight board. It is often convenient to number the rows of the board 1-8 and the columns A-H. The game begins with two black pieces and two white pieces on the center four squares of the board (D4, D5, E4, and E5). There is a black piece in the top-left and bottom-right of those four squares (D4 and E5). There is a white piece in the top-right and bottom-left of those four squares (D5 and E4). Players alternate turns, with each player making a legal move when it is his or her turn. A legal move consists of placing a piece so that two of pieces surround a row, column, or diagonal of the opponent's pieces. All of the opponent's pieces are then flipped (from black to white or from white to black). If a player cannot make a legal move, that player loses his or her turn. Play continues until there are no longer blank squares on the board or neither player can make a legal move. The player with the most pieces is the winner.

Step 1. Circle all of the nouns.

Step 2. For each noun, decide whether that noun represents something you need to represent in the program or something not necessary to the program. If the noun represents something necessary to the program, decide whether it is an object or a class. If the noun represents something unnecessary, suggest why.

Step 3. Box all of the verbs.

Step 4. For each verb, decide whether the verb represents a method a class might implement. Then attach each verb to the appropriate class or classes.

Experiment O1.2: Refining your descriptions

Step 1. Reread the description of Othello and make a list of at least two new questions of the form ``who does this?'' What additional objects or classes, if any, do the answers to these questions suggest?

Step 2. Look at your list of methods and, for each method, ask ``What information do I need in order for this method to succeed?'' Make a list of methods and their required pieces of information.

Step 3. Look at the required pieces of information you developed in step 2 and for each piece decide whether it is more appropriately a parameter to the method or a field in the object.

Step 4. Consider each of the classes you developed in this experiment and in Experiment O1.1. For each class, consider what fields you will need. This may require you to reflect on how you would normally describe the object or on how the object operates.

Experiment O1.3: Beginning coding

Step 1. Based on your analysis of Othello, create a Move class. Your class need only include fields, constructors, and empty methods. You need not enter the bodies of any methods you include. Summarize the design of your class.

Step 2. Based on your analysis of Othello, create a Board class. Again, include only fields, constructors, and empty methods. Summarize the design of your class.

Step 3. Based on your analysis of Othello, create a Rules class. Once again, include only fields, constructors, and empty methods. Summarize the design of your class.

Experiment O1.4: Narrating interactions

Step 1. Write a narrative describing the interaction with the Game object at the end of a game. You may need to play a game of Othello by hand to reach an end state, or you may find it appropriate to make one up. Try to consider other aspects of the rules as you write this narrative. Your narrative should be between one hundred and two hundred words.

Step 2. The original interaction narrative (the one describing the beginning of the game) is woefully lacking in details, as is illustrated by the questions we asked earlier. For example, it does not describe how the board is displayed or how input is read from the players. Rewrite the narrative so as to clarify these issues. Your new narrative should be approximately two hundred words.

Step 3. Expand your narrative from Step 1 to include more details, as suggested in step 2.

Step 4. Pick at least two new classes, methods, method parameters, or fields suggested by these narratives, and update your code from the previous experiment to include the updates. Enter your changes here.

Experiment O1.5: Selective coding

Step 1. Earlier, we developed pseudocode for a game of Othello. Translate this into Java code. In particular, create an Othello class with a main routine that corresponds to this pseudocode. Your main routine should contain real Java code, although it need not work yet (since the other classes are unlikely to be complete).

Step 2. Consider whether any of the pieces of the main routine would be better represented as separate objects or methods. Enter your suggestions here.

Step 3. Write a makeMove method for the Player class. Your method will need to prompt for the move to make and return a corresponding Move. Describe your algorithm here.

Experiment O1.6: Diagramming

Step 1. Make a list of eight method calls that might appear in an implementation of an Othello game. For each call, note which method of which object would make the call and which object would provide the called method. For example, it is likely that the main method of OthelloGame will call the display method of Board.

Step 2. Draw a picture showing the interactions between the objects described in step 1. Feel free to use whatever form you deem most appropriate.

Experiment O1.7: Generalization

Step 1. Describe an interesting alternate board on which we might play Othello.

Step 2. Suggest an alternate game (other than chess) in which we might use the Othello board.

Step 3. What other classes will need to be changed if we play Othello on different boards? Why?

Step 4. What does this suggest about the design of the Board class in your Othello game? In particular, what fields are truly needed, and what belong in subclasses? More importantly, what methods should Boards include?

Post-Laboratory Problems

Problem O1-A: Describe a game

Pick a game and write a short two paragraph description of the game comparable to the description of Othello from this laboratory. Using this description, identify the objects and classes that might be used in a simulation of that game.

Problem O1-B: A simple Othello interface

We are on our way to a working Othello game. The first step is to get a working interface. You will need

• Frameworks for all the appropriate classes: Othello, Rules, Player, Board, and Piece. A framework contains only class definition, constructors (possibly empty) and methods (again, possibly empty). You may have written some of these frameworks for Experiment O1.3. When a method needs to return a value, return a ``reasonable'' default value. For example, the isLegal method of the Rules class might always return true.
• An Othello class with a main routine. You may have written this for Experiment O1.5.
• A makeMove method for the Player class that prompts for a move and returns a corresponding Move object. You may have written this for Experiment O1.5.
• A display method for the Board class. You will need to write that now.
• An initialize method for the Rules class that places pieces on the board. You will need to write that now.

By filling in the details, you should be able to get a simple working interface for the Othello game in which players can enter moves and see a board. At this point, the pieces should not flip and may not even display.

Note that as you fill in the details, you may realize that you need additional methods. For example, although we have not discussed it, the Board class will clearly need a placePiece method.

Problem O1-C: Update Board

Update the Board class so that it will remember where pieces are placed on the board and display them appropriately.

Problem O1-D: Update Rules

Finish the Rules class. You will need to ensure that it is able to

• check whether or not a move is legal;
• determine if a player has a legal move;
• determine whether the game is over;
• identify the winner when the game is over;
• place pieces in the initial configuration; and
• update the board after a move is made.

This problem is perhaps the most difficult in this assignment.

Problem O1-E: Changing Othello's board

Using your code from the previous problems, update Othello so that it is played on a rectangular 6x8 board. What classes did you need to change?

Problem O1-F: Changing Othello's rules

Using your code from the previous problems, update Othello so that the initial state of the board contains two black pieces and two white pieces on the center four squares, with the black pieces forming a row and the white pieces forming a row. What classes did you need to change?

Problem O1-G: Changing Othello's pieces

Using your code from the previous problems, update Othello so that pieces have three colors: white, black, and red. Assume that they flip in sequence: white to black, black to red, red to white. What classes did you need to change? What other questions did you need to ask in order for these updates to be successful and useful?